一种基于多维渐增数据模型的数据查询方法

摘要

本发明一种基于多维渐增数据模型的数据查询方法，属于数据查询技术领域，本发明将某些频繁出现的键建立成为集合空间中的维，并根据值(value)在维上进行分段，而对于那些出现次数较少的键定义为平凡键，通过这样的方式，所有的数据都会被组织成一个高维的模型，简称为key-cube(键立方)；在查询过程中，符合查询条件的数据会被锁定在相关的cell(单元格)之中，因此查询的范围大大的减小了；其次这个数据模型具有一定的适应性会根据数据中键值对出现的次数从而做出相应的反应；这个key-cube是渐增式的，随着键值中数据的增多，此模型会根据键的频繁程度拓展出新的维，从而形成新的key-cube。

说明书

技术领域

本发明属于数据查询技术领域，具体涉及一种基于多维渐增数据模型的数据查询方法。

背景技术

近些年，随着互联网技术的迅猛发展与数据采集技术的不断提高，人们可获得的数据量 越来越大，然而随着如此海量数据的出现，传统的关系型数据库已经不能满足人们对拓展性 以及可伸缩性的需求，尤其是在应付web2.0网站，特别是超大规模和高并发的SNS类型的 web2.0纯动态网站方面，传统的关系型数据库已经显得力不从心，暴露了很多难以克服的问 题。因此研究者们强调找到一个有效的，成本低廉的，有着良好并行性和伸缩性的方式来存 储这些海量的数据；经研究调查，目前来说，在工业和学术界广泛接受的是一种新型的非关 系型数据库；与传统的基于行存储的数据库相比，它采取基于列的存储方式，不需要事先定 义数据模式，预定义表结构，此外制表，列族或者列簇为它的基本数据模型。在这个模型中， 一条记录或者数据被一系列键值对的集合来表示；然而，在这种情况下，当数据量达到TB 甚至PB级的时候，数据的查询效率，以及数据查询的实时性仍然是我们所面临的一个巨大 的挑战。

最近几年，为解决对海量数据中查询效率以及性能的问题，不同的大型数据库提出了层 次结构；例如基于DHT的P2P系统。它使用的是两层架构，一层是为了资源共享，另一层 是为了资源发现，以便加速多维数据查询的过程；但是这个方法依赖于一个具有顺序的hash 函数，和一个较小数量的P2P节点来存储数据；由于被分配到节点数据都会降低它的维度到 一维空间，因此P2P的节点上散布着一维数据的取值范围；随后作者也提出了一个多维查询 算法，在一个稳定的网络环境下，该模型能够表现出良好的性能，但是在实际情况下，真实 的网络环境并不如实验设想的那样稳定，查询效果并不像那样理想。

发明内容

针对现有技术的不足，本发明提出一种基于多维渐增数据模型的数据查询方法，以达到 提高查询效率并优化查询时间目的。

一种基于多维渐增数据模型的数据查询方法，具体包括以下步骤：

步骤1、确定出数据库中高频率的属性类型，并根据所确定的属性类型建立多维渐增数 据模型；

步骤2、对多维渐增数据模型中的每一维属性的值进行分段，包括空段、溢出段和合理 段；

步骤3、将数据库中每一条记录中的数据按照每一维属性的分段进行划分，若某一段中 数据量大于设定值，则对该段再进行下一层的分段，若每一段中的数据量均小于设定值，则 停止分段；

步骤4、根据每个维所划分的段，在多维渐增数据模型中构成单元格，并将单元格各段 的索引按照建维顺序进行线性化，将线性化后的数据作为单元格的标识号；

步骤5、当有新的数据导入数据库时，更新多维渐增数据模型；

步骤6、根据实际所需查询的属性类型，在当前多维渐增数据模型中查询所需属性的标 识号，即获得对应单元格的所有数据；

步骤7、根据查询所获的数据采用回溯操作的方式查询历史数据，具体包括：

步骤7-1、对多维渐增数据模型的维进行回溯，获得每次更新时和初始时多维渐增数据模 型的对应单元格；

步骤7-2、在所获的单元格中对各段进行回溯，即由子段寻找父段；

步骤7-3、对回溯后获得的父段的索引按照建维顺序进行线性化，从而查询获得对应单元 格内的所有数据。

步骤1所述的高频率的属性类型为出现频率大于70％属性类型。

步骤3所述的设定值为：所有段数据量之和的30％。

步骤3所述的数据库中每一条记录中的数据，包括数值型和文本型；

当为数据型时：采用平均分的方式进行分段，即对数据的取值范围进行等宽划分；

当为文本型时：第一层时，按照属性的首字母将26个字母进行分段；

第n层时，按照属性从前向后的第n个字母将26个字母进行分段。

步骤7-3所述的单元格，若其位于边缘部分，则需将其内部不符合查询条件的数据进行 滤除。

本发明优点：

本发明提出一种基于多维渐增数据模型的数据查询方法，通常真实环境中的一条数据都 是由许多的键值(key-value)对所组成，对于这些键值对来说，它们可能具有相同的键(key)， 或者属于同一条记录；本发明将某些频繁出现的键建立成为集合空间中的维，并根据值 (value)在维上进行分段，而对于那些出现次数较少的键定义为平凡键，通过这样的方式， 所有的数据都会被组织成一个高维的模型，简称为key-cube(键立方)；在查询过程中，符合 查询条件的数据会被锁定在相关的cell(单元格)之中，因此查询的范围大大的减小了；其次 这个数据模型具有一定的适应性会根据数据中键值对出现的次数从而做出相应的反应；这个 key-cube是渐增式的，随着键值中数据的增多，此模型会根据键的频繁程度拓展出新的维， 从而形成新的key-cube。

附图说明

图1为本发明一种具体实施方式中基于多维渐增数据模型的数据查询方法流程图；

图2为本发明一种具体实施方式中的所用数据的示意图；

图3为本发明一种具体实施方式中的对数值型数据分段划分的示意图；

图4为本发明一种具体实施方式中的对文本型数据分段划分的示意图；

图5为本发明一种具体实施方式中的对数值型数据的段进行再分的示意图；

图6为本发明一种具体实施方式中的对文本型数据的段进行再分的示意图；

图7为本发明一种具体实施方式中的对维进行回溯的示意图；

图8为本发明一种具体实施方式中的对段进行回溯的示意图。

具体实施方式

下面结合附图对本发明一种实施例做进一步说明。

本发明实施例中，以RITA中航班延迟的数据为例，记录了1987-2008年航班延迟的详细信 息，每一条记录都包括了29个属性如Year(年)，Month(月)，DayofMonth(天数)，DayOfWeek (周数)，DepTime(实际离场时间)，CRSDepTime(预计离场时间)，ArrTime(实际到达时间)， CRSArrTime(预计到达时间)，UniqueCarrier(航空公司代码)，FlightNum(航班号)等，但是在这 29个属性中有些属性的值是可空的，如CancellationCode(取消的原因)，而对于Cancelled(是 否被取消)，Diverted(改飞)，CarrierDelay(货物晚点)，WeatherDelay(天气晚点)，NASDelay (NAS晚点)，SecurityDelay(安全晚点)，LateAircraftDelay(飞机晚点)这些属性中有部分 数据非零数，大部分数据是0；当基于这些记录进行数据分析或执行特定查询时，整个操作的 时间开销极大，并且浪费了大量的存储，通过本发明提出的基于多维渐增数据模型的查询方 法对数据的查询进行优化；并且在此实验中，将每一条记录都看成是这29个键值对的集合， 并且当某个键中的数据是0或空时，就在这条记录中去掉这个键，如图2所示，R_n表示记录； K表示键，即属性；V₁表示值。

本发明实施例中，基于多维渐增数据模型的数据查询方法，方法流程图如图1所示，具体 包括以下步骤：

步骤1、确定出数据库中出现频率大于70％属性类型，并根据所确定的属性类型建立多 维渐增数据模型；

本发明实施例中，数据源都是由一系列的键值对所组成，根据某一个键在源数据或者新 增数据中出现的次数从而可以判断出这个键在数据中出现的频繁程度，将出现不频繁的键称 为不频繁键，将出现频繁的键称为维键；随着数据量的增多，某个不频繁的键在新增的数据 中出现次数变得频繁，可将新增的频繁键建立成为维；将维键建立成一个维，每一个维都有 一个唯一维名称(name)，并且记录下每个维建立的顺序(index)以及维建立的版本号 (version)，因此一个维可用元祖<index，name，version，I>来表示，其中，I表示活跃段id (标识号)的集合；

本发明实施例中，运用Mapreduce计算工具对源数据或者新增数据中的键值对进行扫描， 并对数据中的每个键出现的频数进行统计，将出现次数多于总数的70％的键称为维键，其余 的键称为不频繁键，在本实施中，维键有21个，分别是Year(年)，Month(月)，DayofMonth (天数)，DayOfWeek(周数)，DepTime(实际离场时间)，CRSDepTime(预计离场时间)， ArrTime(实际到达时间)，CRSArrTime(预计到达时间)，UniqueCarrier(航空公司代码)， FlightNum(航班号)，TailNum(机翼的数量)，Dest(目的地)，ActualElapsedTime(实际起飞时间)， CRSElapsedTime(预计起飞时间)，AirTime(飞行时间)，ArrDelay(到达延迟)，DepDelay(出 发晚点)，Origin(出发地)，Distance(距离)，TaxiIn(到达滑行)，TaxiOut(起飞滑行)， 不频繁键是Cancelled(是否被取消)，CancellationCode(取消原因)，Diverted(改飞)， CarrierDelay(货物晚点)，WeatherDelay(天气晚点)，NASDelay(NAS晚点)，SecurityDelay (安全晚点)，LateAircraftDelay(飞机晚点)；

本发明实施例中，将每个维键根据其出现的频繁程度排序，如果此模型中已经有维了， 就依次在排序后的结果加上现有模型中最大维的顺序号，如果模型中还没有维，排序的结果 就是建维的顺序，如果有频繁程度一样的维键，就根据字母序；本发明实施例中，维键 ActualElapsedTime可以表示成<1，ActualElapsedTime，1，I>，维键AirTime可以表示成<2， AirTime，1，I>，维键Origin(出发地)可以表示成<16，Origin，1，I>，维键Month可以表示成 <15，Month，1，I>；index从1开始计数，它不会随着模型的更新而重置，在第一次建立模型的 时候version从1开始计数，以后每更新模型一次，都将version加1，以此来区别模型的不同 版本；随着数据量的增多，CarrierDelay变得相当频繁，因此可将CarrierDelay建立成为新的 维<22，CarrierDelay，2，I>；

步骤2、对多维渐增数据模型中的每一维属性的值进行分段，包括空段、溢出段和合理 段；

本发明实施例中，将包含某个维键的特定范围的值的集合称作一个段，因此一个维可以 由n个不相交的段组成；维上所有段的取值范围是维的一个覆盖；每个段可表示为一个二元 组<i，sv>，其中i表示段的id号，sv表示每个段建立的时期，从1开始计数，并且以1递增， 同一时期可以创建不同的段。

本发明实施例中，在维的初始阶段，为了表示对数值型数据与文本型数据分段方式的不 同，分别以Origin和Month维举例；对数值型数据和文本型数据分别采用图3和图4的方式 进行分段，其中s1表示值为空的情况(空段)，s2，s4分别表示值超出正常范围的情况(溢出 段)，s3表示所属键正常范围的取值情况(合理段)，基于常识可知，月份的正常的取值范围 是1到12，并且在数据中发现对于Origin中，其字母的开头一般为c到q。对数值型数据与 文本型数据分段的最大的不同是：由于文本型数据都是由各个字母所组成，因此在每一层的 分段都是对文本型数据中的第i个字母进行分段，分段过程中不区分大小写。在维中，这些 段也有唯一的id，这个id采用按序编码的方式进行编码，此编码方式应该能为段的回溯服务， 此时Origin维中的段分别有：<s1，1>，<s2，1>，<s3，1>，<s4，1>，Month中的段有： <s1，1>，<s2，1>，<s3，1>，<s4，1>，与此同时一个新的多维的cube被建立起来；

步骤3、将数据库中每一条记录中的数据按照每一维属性的分段进行划分，若某一段中 数据量大于所有段数据量之和的30％，则对该段再进行下一层的分段，若每一段中的数据量 均小于所有段数据量之和的30％，则停止分段；

本发明实施例中，除了s1之外的所有段都可以进行再次被分成固定数量的子段，因此将 没有子段的段成为活跃段，有子段的段成为休眠段；随着数据的增多，会造成段中所对应数 据的不均衡，在这种情况下可对段进行再分操作；

本发明实施例中，当段中所对应的数据超过了200M，可以采取分段的方式，如图5和图 6所示，对段中的数据进行再次划分，本发明实施例中，规定除了s1之外的其他段可固定的 再分为3个子段，并且对于数值型数据，进行等宽划分，对于文本型数据，进行字符个数上 的等宽划分，此时Origin维中的段分别有：<s1，1>，<s2，1>，<s8，2>，<s9，2>，<s10，2>，<s4，1>，Month 中的段有：<s1，1>，<s2，1>，<s8，2>，<s9，2>，<s10，2>，<s4，1>；

步骤4、根据每个维所划分的段，在多维渐增数据模型中构成单元格，并将单元格各段 的索引按照建维顺序进行线性化，将线性化后的数据作为单元格的标识号；

本发明实施例中，一条数据可以根据cube每个维上段的取值范围定位到空间中的一个单 元格，在这个单元格中对应了包含具有相同键并且取值在同一个段中的多条数据，将构成单 元格的段的Index按建维的顺序进行线性化，然后将线性化之后的结果作为每个cell的id；

本发明实施例中，采用z-ordering的方式对构成单元格的段的Index按建维的顺序进行线 性化，然后将线性化之后的结果作为每个cell的id；

步骤5、当有新的数据导入数据库时，更新多维渐增数据模型；

步骤6、根据实际所需查询的属性类型，在当前多维渐增数据模型中查询所需属性的标 识号，即获得对应单元格的所有数据；

本发明实施例中，对查询语句进行分析，形如select..from..where...，根据where后的查 询条件定位到所要约束的维键，可以通过计算得出在当前的cube中维上符合查询条件的一系 列段；将符合查询条件的段按照段所对应维的顺序进行线性化，线性化后的结果就是目前cube 中符合查询结果的所有数据；

本发明实施例中，采用的查询语句是select*fromthiswhereMonth＞3andOrigin＝ ‘BOS’.；从查询语句可知，查询条件中包含的维键是Month＜15，Month，1，I_month>和Origin＜16， Origin，1，I_Origin>，I_month＝{1，2，8，9，10，4}，I_Origin＝{1，2，8，9，10，4}，因此在活跃段中只有Month中的 s8，s9，s10，s4和Origin中的s2满足条件，然而对于Month中的s8和Origin中的s2会存 在一些不符合查询条件的数据，由这些段所组成的单元格称为处于边缘部分的单元格，会对 他们进行后续的过滤处理；将Month维和Origin维中符合查询条件的s8，s9，s10，s4和s2，与 其他各个维的段，按照建维的顺序，采用z-ordering的方式进行线性化；

步骤7、根据查询所获的数据采用回溯操作的方式查询历史数据；

本发明实施例中，由于此模型是渐增的，目前的cube可能是增维之后的版本，因此目前 所查询出的结果只是一部分查询结果，对于每一个线性化之后的结果，还需要进行回溯操作 来寻找历史数据中的查询结果；

具体包括：

步骤7-1、对多维渐增数据模型的维进行回溯，获得每次更新时和初始时多维渐增数据模 型的对应单元格；

本发明实施例中，对维的回溯找出由不同维版本够成的各个cube；维上的回溯过程如图7 所示，图中，由上至下由最大维版本为n至最大维版本为1；记录下当前的所有维，在其中 找出具有最高维版本的维，然后删除此版本的维，循环整个过程直到维中的版本只有1，最 后在每个过程中记录的维的集合就是所对应的不同时期的键立方，即不同时期的历史数据； 本发明实施例中，维版本最高为2，只增了CarrierDelay维，因此不同时期的cube只有两个， 第一个cube由之前的21个维键组成，第二个cube由之前的21个维键加上新增的CarrierDelay 维组成。

步骤7-2、在所获的单元格中对各段进行回溯，即由子段寻找父段；

本发明实施例中，对维上段的回溯，在各个cube中对段进行回溯；在各个时期的cube 中会有不同的段发生改变，因此还需要在各个段的顺序列表中进行段的回溯，段的回溯就是 由子段找父段的过程，如图8所示，即根据当前子段的id，得到父段id的过程，其过程主要 为：将线性化的结果y进行反线性化，得到构成该结果的各个维中段a₁，a₂，...a_n，在这些中段 中找出具有最大段版本号的段a_n，然后根据段的编码方式，可以由段的id进而得到其父段b_n的id；在本实施中，例如对Month和Origin维中的段s3都进行了再分，并且除了s1不可再 分，其他每个段可分子段的数量都固定为3，因此，当对s8，s9，s10进行回溯的时即可获得 其父段s3；

步骤7-3、对回溯后获得的父段的索引按照建维顺序进行线性化，从而查询获得对应单元 格内的所有数据；所述的单元格，若其位于边缘部分，则需将其内部不符合查询条件的数据 进行滤除。

本发明实施例中，最后对所有的回溯结果进行线性化，从而查询出所有符合条件的单元 格；查询结果中的一些处于边缘部分的单元格，它们所包含的数据中会有一些不符合查询条 件的数据，因此只需对这些边缘单元格用mapreduce做过滤处理，在本实施中，例如对Month 中的s8和Origin中的s2过滤处理中，1＜＝Month＜3的数据和Origin中以a(不区分大小写)开 头的数据会被过滤掉，当过滤过程完成之后，所有符合查询条件的数据会被查询出来。