一种基于双层索引结构的起源图查询方法

摘要

本发明公开一种基于双层索引结构的起源图查询方法，包含以下步骤：首先，面向起源图查询，提出一种双层索引结构；其次，设计基于词典表全局索引，表中记录起源数据与数据之间匹配关系以及起源图ID；然后，提出基于位图局部索引，依据起源图RDF查询方式，提出了满足Triple？Pattern查询的索引和三种join查询方式，并且基于索引设计了相应的查询算法。最后，通过测试，验证了基于双层索引结构的起源图查询方法的可行性和有效性。

说明书

技术领域

本发明涉及大数据管理领域的起源数据的管理，着重针对数据起源图的查询 方案的设计与实现。本发明根据数据起源图特点给出一种基于双层索引结构的起 源图查询方法。该方法分别从全局和局部两个层次进行设计：一方面通过词典表 可以匹配数据与其起源数据之间的关系提出基于词典表全局索引算法；另一方面 根据起源图ID快速定位起源所存储在云计算服务器节点，提出基于位图局部索 引结构，包括6种不同的选择索引和3种join链接索引，并设计了相应的查询算 法。

背景技术

数据起源是对数据处理的整个历史的信息，包括数据的来源和处理这些数据 的所有后继过程。随着大数据的不断发展，云计算环境下如何高效的查询起源信 息变得尤为重要，如何高效的查询起源信息成为了一个亟待解决的问题。

本发明针对云计算环境下数据起源查询问题，引入一种双层索引结构，分别 从全局索引和局部索引两方面进行分析，设计了一种起源图查询方法，并对方法 可行的、有效的进行验证。

发明内容

发明目的：针对现有技术中存在的问题，本发明提供一种基于双层索引结构 的起源图查询方法。

技术方案：一种基于双层索引结构的起源图查询方法，首先，面向起源图查 询，提出一种双层索引结构。其次，设计基于词典表全局索引，表中记录起源数 据与数据之间匹配关系以及起源图ID，即能够关联起源与数据之间的关系，又 能够迅速定位到起源所存储云服务器节点以减少用户查询响应时间；然后，提出 基于位图局部索引，依据起源图RDF查询方式，提出了满足八种TriplePattern 查询的索引和三种join查询方式，并且基于索引设计了相应的查询算法。

面向起源图查询的双层索引结构

以往的分布式环境下存储起源数据，查询起源仅仅依赖master节点来分配 任务进行查找，通常需要遍历整个集群，消耗大量的时间和资源。而现有分布式 环境下起源存储系统基本都是基于主键来快速查询，缺少高效的索引结构，不能 提供多维查询和join等查询。高效的索引结构能有效的提高查询效率，缩短用户 查询时的响应时间。

为提高查询效率，结合起源图特点，提出了一种双层索引结构。索引结构包 括基于词典表全局索引和基于位图局部索引。全局索引查询起源图所存储的服务 器节点，局部索引对全局索引查询到的服务器节点细化查询，进而查询到所需的 起源数据。全局索引分布在云环境下每一个节点上，当用户请求到达时，只需参 照本地服务器的全局索引结构即能得出所要查询起源图所在节点位置。局部索引 是只建立在本地服务器所存储的起源数据的索引，每一个节点之间的局部索引并 没有依赖关系。

基于词典表的全局索引及全局查询算法

首先给出词典表结构设计，在此基础上，完成基于全局索引的查询流程。

1、词典表结构设计

根据数据起源特点，从两方面设计词典表HCPTable。首先，存储起源图名 称和对应数据项。数据项就是起源所描述的数据，将一次工作流中的所有数据都 对应一个起源图，粗粒度的描述起源与数据之间的关系。其次，存储起源图名称 与对应ID。每一次工作流的执行则会产生一个数据起源图，起源ID则在存储过 程中依据Hash(key)映射产生。全局索引中起源图ID为一致性哈希索引算法的输 入项，根据起源ID可以快速计算出起源图所存储服务器节点。

2、基于全局索引的查询流程

根据HCPTable中查询起源图ID从起源图的根节点开始遍历到叶子节点， 根据叶子节点得出起源图存储服务器。全局索引查询流程如下：

(1)查找词典表得到起源图ID编号

(2)根据查询需求来查找满足要求的子节点

(3)计算输出子节点编号

基于位图的局部索引及局部查询算法

为了提高查询起源图数据效率，考虑用户查询时的语句多样性，弥补选择索 引Is、Ip、Io在对单个TriplePattern的查询时的不足，对主语谓语已知的三元 组设计索引Isp和Ips，对谓语宾语已知的三元组设计索引Ipo和Iop，对主语宾 语已知的三元组设计索引Iso和Ios，形成完整的局部位图索引结构，包括选择 索引Is、Ip、Io、Isp、Ipo、Iso和join索引Is'、Io'、Iso'。

局部索引支持对单个云存储服务器节点上的起源图数据的细化查询。起源图 查询包含两部分：单个TriplePattern查询和join查询。

(1)单个TriplePattern查询

选择索引Is、Ip、Io、Isp、Ipo、Iso对主语、谓语、宾语、主语谓语、 谓语宾语、主语宾语进行单个TriplePattern的查询。

(2)join查询

选择索引Is'、Io'、Iso'用于处理主语共享变量、宾语共享变量和主语宾语 共享变量进行join查询。

附图说明

图1为双层索引结构；

图2为基于全局索引的起源查询流程图；

图3为一致性二叉树分布模型；

图4为RDF三元组join种类；

图5为索引空间占用分析曲线图；

图6为查询性能分析曲线图。

具体实施方式

下面结合具体实施例，进一步阐明本发明，应理解这些实施例仅用于说明本 发明而不用于限制本发明的范围，在阅读了本发明之后，本领域技术人员对本发 明的各种等价形式的修改均落于本申请所附权利要求所限定的范围。

基于双层索引结构的起源图查询方法，首先，面向起源图查询，提出一种双 层索引结构。其次，设计基于词典表全局索引，表中记录起源数据与数据之间匹 配关系以及起源图ID，即能够关联起源与数据之间的关系，又能够迅速定位到 起源所存储云服务器节点以减少用户查询响应时间；然后，提出基于位图局部索 引，依据起源图RDF查询方式，提出了满足八种TriplePattern查询的索引和三 种join查询方式，并且基于索引设计了相应的查询算法。

面向起源图查询的双层索引结构

以往的分布式环境下存储起源数据，查询起源仅仅依赖master节点来分配 任务进行查找，通常需要遍历整个集群，消耗大量的时间和资源。而现有分布式 环境下起源存储系统基本都是基于主键来快速查询，缺少高效的索引结构，不能 提供多维查询和join等查询。高效的索引结构能有效的提高查询效率，缩短用户 查询时的响应时间。

索引结构包括基于词典表全局索引和基于位图局部索引。全局索引查询起源 图所存储的服务器节点，局部索引对全局索引查询到的服务器节点细化查询，进 而查询到所需的起源数据。全局索引分布在云环境下每一个节点上，当用户请求 到达时，只需参照本地服务器的全局索引结构即能得出所要查询起源图所在节点 位置。局部索引是只建立在本地服务器所存储的起源数据的索引，每一个节点之 间的局部索引并没有依赖关系。设计的双层索引结构具体如图1所示。

基于词典表的全局索引及全局查询算法

首先给出词典表结构设计，在此基础上，完成基于全局索引的查询流程。

1、词典表结构设计

根据数据起源特点，从两方面设计词典表HCPTable。首先，存储起源图名 称和对应数据项。数据项就是起源所描述的数据，将一次工作流中的所有数据都 对应一个起源图，粗粒度的描述起源与数据之间的关系。其次，存储起源图名称 与对应ID。每一次工作流的执行则会产生一个数据起源图，起源ID则在存储过 程中依据Hash(key)映射产生。全局索引中起源图ID为一致性哈希索引算法的输 入项，根据起源ID可以快速计算出起源图所存储服务器节点。设计的词典表 HCPTable的存储结构实例如表1所示。

表1词典表HCPTable的存储结构

2、基于全局索引的起源图存储节点查询流程

基于全局索引的起源图存储节点查询流程如图2所示。

(1)查找词典表得到起源图ID

(2)查找从树的root节点开始，根据起源图ID查询起源所存储在树中的 服务器节点，运用公式1计算选择子节点。公式1中ID是起源图ID号， root.Number是根节点的编号。

nodenum＝ID％root.Number(1)

根据计算结果选择子节点，验证子节点node.Isleaf属性判断是否叶子节点， 如果是叶子节点则执行步骤(4)，否则执行步骤(3)。

(3)以该节点作为新的root节点，继续从步骤(2)开始执行。

(4)计算输出此节点编号。

首先，流程每一次的执行都会选择树的一个叶子节点，执行从root节点开 始到叶子节点。查询方法类似折半查找，所以时间复杂度为O(log(n))。其次， 本发明采用一致性二叉树分布存储，这样的二叉树结构存储方式也会比其他多叉 树的效率高很多。

3、一致性二叉树分布存储

一致性二叉树分布存储的思想在于对服务器进行分层分组，并结合一致性哈 希算法将数据均匀的分布到各个云服务器中。一致性二叉树叶子节点表示云端的 各个服务器节点，用来存放起源图数据。

一致性二叉树分布模型基于二叉树结构，在每一层次节点都被分为多个互不 相交的有限集中，其中每一个集合本身又是一棵树，从而将所有存储节点分到不 同层次的不同组里。叶子节点中存放相应的服务器编号。

定义1一致性二叉分布树：一致性二叉树是由n个节点的有限集T组成的 二叉树，T＝{V，E}，V是结点的集合，E是边的集合。

有限集T中每一个叶子表示云计算服务器位置。对于每个节点，可以用唯 一的一个数字序列定义，从左至右依次代表该节点所经历过路径的编号，其中子 树从左边到右边依次编号0，1，00，.......。如图3中查询D节点编号为11，这 棵一致性分布树中也就唯一确定了D节点在树中的具体位置，即查询D节点经 过1和1两条路径。当树中所有的叶子节点的编号都完成的时候，这棵树的逻辑 结构也就确定。二者之间是单映射的关系。运用一致性二叉树的时候，可以把其 抽象为一个二维数组，就可以用二维数组来维护树形结构。

算法实现：

全局查询的目的在于定位起源图所在服务器节点，本发明设计一致性分布式 存储将不同起源图均匀存储到树中不同的叶子节点中。在查询起源图时，根据起 源图ID查询起源所存储在树中的服务器节点。

起源节点查询算法Match_Node具体如下：

基于位图的局部索引及局部查询算法

本发明中起源图数据以三元组为单元进行顺序存储，三元组的编号从1到n， 用pos(t_i)来表示每一个三元组t_i在图中的存储位置i，用pos^-1(t_i)返回三元组t_i在 图中的位置i，其中t_i∈G，G是一个RDF图的三元组集合，D是RDF图的集合， G＝{t₁,t₂,...t_n},G_i∈D,D＝{G₁,G₂,...G_n}。

使用S、P和O来分别表示RDF数据集中主语、谓语和宾语集合。如公式2 所示

S＝S₁∪S₂∪....∪S_n,S_i＝{s|(s,p,o)∈G_i},G_i∈D,D＝{G₁,G₂,...G_n}

P＝P₁∪P₂∪....∪P_n,P_i＝{p|(s,p,o)∈G_i},G_i∈D,D＝{G₁,G₂,...G_n}(2)

O＝O₁∪O₂∪....∪O_n,O_i＝{o|(s,p,o)∈G_i},G_i∈D,D＝{G₁,G₂,...G_n}

1、对单个TriplePattern的查询

由于单个TriplePattern中主语、谓语和宾语可能是变量，那么针对单个三元 组的查询需要设计多维索引。多维索引的主要思想是通过三元组中的非变量查询 变量。SPARQL查询子句中对单个三元组TriplePattern子句查询的表达式以及所 表示的语义如表2所示。

表2TriplePattern表达式及其含义

子句表达式 含义 1 (s,p,o) 若三元组存在，则返回三元组，否则返回空值 2 (？s,p,o) 给定谓语、宾语，返回满足三元组的主语结果集 3 (s,？p,o) 给定谓语、宾语，返回满足三元组的主语结果集 4 (s,p,？o) 给定谓语、宾语，返回满足三元组的主语结果集 5 (？s,？p,o) 给定谓语、宾语，返回满足三元组的主语结果集 6 (s,？p,？o) 给定谓语、宾语，返回满足三元组的主语结果集 7 (？s,p,？o) 给定谓语，返回满足三元组的主语和宾语结果集 8 (？s,？p,？o) 返回所有三元组

定义2位图索引Is：索引Is是RDF图G中所有三元组主语的集合 {(s₁,v₁),(s₂,v₂),....,(s_n,v_n)}。其中，s∈S。v_i为图G中的一个位向量，并且向量 中的k位置为1当且仅当图G中存在三元组t_k＝pos(k),t_k∈G,t_k.s＝s_i。

Is索引设计的目的在于对查询主语的查询语句能够在RDF图中快速的查到 相应的三元组。其中Is的大小是固定的，与所在起源图中包含RDF三元组的个 数相同。

同理，同样的方式建立索引Ip和Io，可以快速的查询到以谓语或宾语作为 关键字的三元组。如果查询语句中主语、谓语和宾语都是已知，那么可以结合索 引Is、Io和Ip三个索引查询：Is∧Ip∧Is。

定义3位图索引Isp：索引Isp是RDF图G中所有三元组主语谓语集合 {(s₁p₁,v₁),(s₂p₂,v₂),....,(s_np_n,v_n)}。其中，s∈S，p∈P。v_i为图G中的一个位向 量，并且为向量中的k位置为1当且仅当图G中存在三元组 t_k＝pos^-1(k),t_k∈G,t_k.sp＝s_ip_i。

同理，同样的方式建立索引Ips、Ipo、Iop、Iso、Ios，可以快速的查询到 以主语谓语、谓语宾语、宾语谓语、主语宾语和宾语主语作为关键字的三元组。

2、含有join的查询

三元组之间的关联性是通过三元组之间是不是存在同名的未绑定变量判断 的。根据同名变量出现的位置可以将关联关系化为三种：Subject-Subject链接、 Object-Object链接和Object-Subject链接，RDF三元组join种类如图4所示。

定义位图索引Is'：索引Is'是RDF图G中所有包含相同主语的三元组集合 {(1,v₁),(2,v₂),....,(n,v_n)}。其中n＝|G|，1,2...n则是图中连续位置标识。v_i为图G 中的一个位向量，并且为向量中的k位置为1当且仅当图G中存在三元组 t_k＝pos(k),t_k∈G,t_i＝pos(i),t_k.s＝t_i.s。

同理索引Io'建立类似Is'。本文没有针对谓语建立Ipp，因为在图中谓语的 量相对主语和宾语来说较少并且查询相同谓语的三元组并无意义。

定义4位图索引Iso'：索引Iso是RDF图G中所有包含相同主语和宾语的 三元组集合{(1,v₁),(2,v₂),....,(n,v_n)}。其中n＝|G|，1,2...n则是图中连续位置标识。 vⁱ为图G中的一个位向量，并且为向量中的k位置为1当且仅当图G中存在三 元组t_k＝pos(k),t_k∈G,t_i＝pos(i),t_i∈G,t_k.o＝t_i.s。索引Ios'则为索引Iso'的转置： Ios'＝Iso'^T。

索引Isp、Ips、Ipo、Iop、Iso、Ios为选择索引，用于处理已知主语谓语、 谓语宾语或者主语宾语的查询请求，其中Isp和Ips、Ipo和Iop、Iso和Ios索引 所描述的三元组在实际图中存储位置相同，故只需Isp、Ipo和Iso。

综上，本发明采用索引Is、Ip、Io、Isp、Ipo和Iso对主语、谓语、宾语、 主语谓语、谓语宾语或者主语宾语已知的三元组进行查询。索引Is'、Io'、Iso'、 Ios'用于处理主语共享变量、宾语共享变量和主语宾语共享变量的join查询请 求。位图索引存储框架T_D如表3所示。

表3位图索引存储框架T_D

3、算法实现

对单个TriplePattern的查询算法ASI_TP根据三元组中已知项查询未知项， 如下所示；

对join查询的算法AJI_TP能够在两个三元组各自的主语、宾语、主语和谓 语、谓语和宾语、主语和谓语分别相同时能够快速匹配，如下所示；

以及对BGP查询的算法Match_BGP，如下所示：

其中ASI_TP和AJI_TP为对BGP查询时所调用的过程算法。Match_BGP 算法将BGP中所有的trplepattern进行预处理，即重新排序，具体步骤如下：

1、确立选择度高的trplepattern排序靠前，trplepattern选择度由高到低的顺 序如下：

(1)Subject非变量

(2)Subject、Predicate和Object都非变量且谓语非rdf：type

(3)Subject为变量，Predicate和Object都非变量且谓语为rdf：type

(4)Subject和Predicate为变量，Object非变量

(5)Subject和Object为变量，Predicate非变量且谓语非rdf：type

(6)Subject和Object为变量，Predicate为rdf：type

(7)Subject、Object和Predicate都为变量。

2、对排序后的RDF三元组集bgp中第一个trplepattern调用函数ASI_TP 算法查询，所返回变量存储在v_seva。并且根据v_seva得出结果集S。如果结果集S 为空，则直接返回空集。

3、取下一个trplepattern，查询之前先判断该trplepattern与之前的trplepattern 是否有共享变量，如果有共享变量，则调用算法AJI_TP，记录当前trplepattern 处理的结果集S_tpi，合并当前结果集与v_seva得出的结果集。

4、重复第三步骤，直到所有结果集都查询结束。

5、替换结果集S中的位向量，根据位向量得出具体的RDF三元组。返回查 询的结果集。

实验验证

1、空间占用分析

本文局部索引技术增加了三个新索引来加速查询效率，所以存储所占用空间 多三个索引所占存储空间。

一次工作流中产生400个RDF三元组中相同的主语、谓语或者宾语的三元 组会多次出现，索引Is、Ip和Io并不用对每一个三元组都建立索引项。含有相 同元素的三元组，采用位图向量的bit位来标记即可。比如相同主语只需要在位 图索引中对该主语首次建立的位图向量中对应位置1即可。该位置表示其在数据 库中存储的逻辑位置。

对于工作流记录的起源数据中相同主语谓语、谓语宾语和主语宾语的三元组 重复项同样很多，那么对于重复项只需在首次建立的向量中不同位置设置“1”即 可，存储时只需存储一个位图索引。因此，本文在原有的6个索引的基础上添加 三个索引项，索引的数量增加了50％，而索引存储空间仅仅增加了25％左右， 如图5所示。

2、查询性能分析

本发明针对德克萨斯大学起源数据标准数据集分别测试了11条UTPB查询 语句来测试本发明所设计索引结构的查询性能。

实验在Hadoop集群环境下，对D1、D2、D3、D4、D5五个数据集想分别 进行了11条语句的查询测试。每一个查询在五个数据集上各运行5次取相应时 间的平均值，查询性能分析如图6所示。

通过实例执行结果分析，证明了本发明的可行性也验证了所提出的双层索引 结构在应对海量数据起源存储时，随着数据量的增加，其存储和查询性相对优越， 客户查询请求响应及时。面对复杂的查询请求与海量的数据性能依然很好。