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

许国艳，罗章璇，宋 健，吕 鑫

(河海大学 计算机与信息学院，南京 211100)

(*通信作者电子邮箱gy_xu@126.com)

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

许国艳*，罗章璇，宋 健，吕 鑫

(河海大学 计算机与信息学院，南京 211100)

(*通信作者电子邮箱gy_xu@126.com)

为解决现有的起源图查询效率低和资源占用率高的问题,考虑起源信息和数据本身之间的关联关系以及起源信息内部结构特点，提出了一种基于双层索引结构的起源图查询方法。首先，面向起源图查询，提出了一种包括基于词典表全局索引和基于位图局部索引的双层索引结构，全局索引用于查询起源图所存储的服务器节点，局部索引用于对全局索引查询到的服务器节点细化查询；然后，基于双层索引结构，设计了一种起源图查询方法，针对6种选择索引和3种join链接索引实现了查询算法。实验结果表明，所提方法既提高了查询效率，又降低了内存资源的浪费。

起源图；双层索引结构；词典表；位图

0 引言

在云平台环境下，随着大数据应用的不断发展，各种数据越来越多，数据的起源信息规模也就越来越大。甚至在很多应用领域起源信息已经超过其所描述数据的信息量，起源信息的管理难度越来越大。云平台环境下如何高效地查询起源信息变得尤为重要，如何高效地查询起源信息成为了一个亟待解决的问题。

数据起源[1]是对数据处理的整个历史的信息，包括数据的来源和处理这些数据的所有后继过程。目前，Chebotko等[2]在HBase数据库基础上，对基于资源描述框架(Resource Description Framework， RDF)图的起源数据集的存储和索引和查询进行了研究：一方面，将数据起源图进行分布式存储，并针对RDF三元组的查询设计位图索引；另一方面，建立Is、Ip、Iss、Ioo、Iso索引提高查询效率，并在此索引机制上提出了相应的查询算法。朱敏[3]则充分运用HBase提供的Row-key索引，对RDF数据的存储与查询进行了研究，设计了满足子类、子属性和逆属性的查询算法。

由于上述方法都是采用一次遍历整个表或者是将RDF三元组分多表存储来设计多维索引，以此来提高查询效率，不能满足灵活高效的多维查询和join等查询，随着数据集越来越多，查询的效率也会明显下降。

因此针对现有研究的不足，本文根据具体查询需要细化索引，提出了一种双层索引结构，并进一步设立了基于双层索引结构的起源图查询方法。

1 相关工作

1.1 基于RDF的起源图描述

RDF[4]提供了一种用于表达语义信息并使其能在应用程序间交换而不丧失语义的通用框架，描述了资源本身的属性及资源与资源之间存在的关系。RDF是以三元组形式对资源的陈述，RDF三元组包括一个主语(subject)、一个谓语(predicate)和一个宾语(object)。RDF图可以通过带有标签的节点和带有标签的边表示，RDF图中的节点就是它包含的所有三元组的主语和宾语，边是所包含的所有谓语。每一个三元组对应为图上的一个“节点-边-节点”的子图。PROV[5]是数据起源模型，可以采用RDF图描述起源信息。本文起源信息采用PROV建模，并用RDF图进行描述。

定义1 数据起源集。一个数据起源集D包含一个或者多个RDF图{G1,G2,…,Gn},n≥0。其中每一个数据起源图拥有唯一的ID标识Gi∈D。

定义2 起源图。一个起源图G为一次工作流所产生的起源信息，由多个RDF三元组{t1,t2,…,tn}构成，n=|G|，ti∈G。其中每一个RDF三元组ti∈G都由(S，P，O)组成，S表示主语，P表示谓语，用于描述主语和谓语之间的关系，O表示宾语。

1.2 起源图存储与索引

1.2.1 起源图存储

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

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

有限集T中每一个叶子表示云服务器位置。对于每个节点，可以用唯一的一个数字序列定义，从左至右依次代表该节点所经历过路径的编号，其中子树从左边到右边依次编号0，1，00，…。如图1中查询D节点编号为11，这棵一致性分布树中也就唯一确定了D节点在树中的具体位置，即查询D节点经过1和1两条路径。

1.2.2 一致性哈希索引

一致性哈希算法[6]是在哈希算法基础上提出的，其主要思想是：首先得出每个服务节点的Hash值，并将其配置到一个0～232的圆环区间上；其次使用同样的方法求出数据key的Hash值，也将其映射到这个圆环上；然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务节点上。如果超过232仍然找不到服务节点，就会保存到第一个节点上。一致性哈希算法最大限度地抑制了Hash键的重新分配，在一定程度上很好地解决了数据的均衡和扩展性问题[7]。一致性哈希算法索引示意如图2所示。

1.2.3 位图索引

位图索引[8]其核心思想是利用一个位向量(BitVector)来表示被索引对象的某一个取值是否在被索引数据中存在，在处理大量数据包含相同属性时有很好的效果，目前被用于云数据管理[9-10]。

定义4 位图索引。位图索引即通过一个位向量来表示被索引的值或者属性是否在文件中。其中如果被索引的值出现在文件中，该位向量中对应的位置将被置1，否则置0。

对RDF三元组进行索引时，对于主语、谓语或者宾语其中一项是相同的三元组仅仅只需要一个向量，使用向量中的bit来表示主语相同的不同三元组存放位置。

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

2.1 双层索引结构

现在分布式环境下起源信息基本都是基于主键来查询，但是缺少提供多维和join等查询的高效的索引结构。本文针对现有的起源图查询效率低和资源占用率高的问题,面向起源图查询，提出了一种包括基于词典表全局索引和基于位图局部索引的双层索引结构，具体如图3所示。全局索引用于查询起源图所存储的服务器节点，局部索引用于对全局索引查询到的服务器节点细化查询，最终查询到所需的起源信息。全局索引分布在云环境下每一个节点上，当用户请求到达时，只需参照本地服务器的全局索引结构即能得出所要查询起源图所在节点位置。局部索引是只建立在本地服务器所存储的起源信息的索引，每一个节点之间的局部索引并没有依赖关系。

图3 双层索引结构

2.2 基于词典表全局索引

全局索引设计的目的是查询到数据所存放的服务器节点，起源信息的全局索引设计不仅要能够根据起源信息查询到服务器节点，而且要能够关联起源信息与数据本身。虽然词典表索引在查询效率上不如哈希索引，但是词典表能够同时满足对服务器节点查询需求和对数据起源与数据本身之间的关联关系查询的需求。所以，本文提出了基于词典表的云计算环境下起源信息的全局索引方案，具体设计了词典表结构。

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

图4 词典表HCPTable的存储结构

2.3 基于位图局部索引

局部索引设计的目的是对单个云存储服务器节点上的起源图细化查询。起源图查询包含两部分：单个TriplePattern查询和join查询。在原有的位图索引中，针对单个TriplePattern的查询设计的索引存在一些不足：比如对给定的主语谓语，在查询时不能直接从索引表中得到所需信息，必须首先查询该主语的位图向量，然后查询该谓语的位图向量，最后进行逻辑计算方可获得。为了提高查询起源图效率，考虑用户查询时语句多样性，针对两种查询方式，本文提出了一种改进的基于位图的多维局部索引。多维索引的主要思想是通过三元组中的非变量查询变量，比如三元组中的主语为变量，那么可以通过宾语和谓语来查询确定该三元组的主语，即为了弥补选择索引Is、Ip、Io在对单个TriplePattern的查询时的不足，对主语谓语已知的三元组设计索引Isp和Ips，对谓语宾语已知的三元组设计索引Ipo和Iop，对主语宾语已知的三元组设计索引Iso和Ios，形成完整的局部位图索引结构，包括选择索引Is、Ip、Io、Isp、Ipo、Iso和join索引Is′、Io′、Iso′。

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

3 基于双层索引结构的起源图查询算法

3.1 基于词典表全局索引的节点查询算法

全局查询的目的在于定位起源图所在服务器节点，本文根据一致性分布式存储将不同起源图均匀存储到树中不同的叶子节点中。在查询起源图时，从树的root节点开始，根据起源图ID查询起源所存储在树中的服务器节点。起源节点查询算法Match_Node具体如下所示。

算法1 起源节点查询算法Match_Node。

输入：起源图G.id、一致性树tree。 输出：节点node。 算法： //在一致性树tree中查询id编号的起源图 node Map(id,tree){ node=tree.root; int temp=1; in_id=id; //如果node是叶子节点则返回存储起源图ID的服务器节点 //如果不是叶子节点，则接着执行循环进行计算查找 While(node is not leaf){ temp=node.Number; node=node.Children[in_id%node.Number]; in_id=id/temp;} return node;}

表1 位图索引存储TD

3.2 基于位图局部索引的细化查询算法

根据起源图Triple Pattern查询和join查询两个部分以及本文所设计的局部索引，节点内查询起源图的算法包括对单个Triple Pattern的查询算法ASI_TP和对join查询的算法ASI_JP，单个Triple Pattern查询和join查询是基础。BGP(Basic Graph Pattern)是常见的起源图模式，BGP图的查询主要包括单个Triple Pattern查询和join查询，BGP查询的算法Match_BGP主要通过调用ASI_TP和AJI_TP实现。

3.2.1 ASI_TP算法

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

算法2 对单个Triple Pattern的查询算法ASI_TP。

输入：起源图G.id,Triple Pattern tp=(sp,pp,op),tableTD。 输出：位图向量v，v[k]=1。tripletk=pos(k)。其中树中位置K的三元组tk与tp匹配。 算法：

//TD中row-key为G.id所在行中Is、Ip、Io分别作为索引

//主语是非变量

if tp.sp非变量，tp.op和tp.pp是变量

thenv=v∧Is(tp.sp)；

//宾语是非变量

elseiftp.op非变量,tp.spandtp.pp是变量

thenv=v∧Io(tp.op)；

//谓语是非变量

elseiftp.pp非变量,tp.sp和tp.op为变量

thenv=v∧Ip(tp.pp)；

//主语、谓语是非变量

elseiftp.sp和tp.pp非变量,tp.op为变量

thenv=v∧Isp(tp.sp)；

//谓语、宾语是非变量

elseiftp.pp和tp.op非变量,tp.sp为变量

thenv=v∧Ipo(tp.po)；

//主语、宾语是非变量

elseiftp.sp和tp.op非变量,tp.pp为变量

thenv=v∧Isp(tp.so)；

//主语、宾语是非变量

elseiftp.sp、tp.op和tp.pp均为变量

thenv=v∧Is(tp.sp)‖Io(tp.op)‖Ip(tp.pp)‖Isp(tp.sp)‖Ipo(tp.po)‖Iso(tp.so)；returnv;

3.2.2AJI_TP算法

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

算法3 对join查询的算法AJI_TP。

输入：起源图G.id、已知位置TriplePatterntp=(sp,pp,op),tp在图中位置p,tripletp=pos-1(p)、tableTD以及所需join操作TriplePatterntp′。 输出：位图向量v，v[k]=1。tripletk=pos(k)。tk∈G,其中树中位置K的三元组tk与tp的主语、主语、宾语、主语和谓语、谓语和宾语或者主语和谓语相匹配。 算法：

v[p]=0;

//TD中row-key为G行中Is′、Io′、Iso′分别作为索引

//主语相同变量匹配

iftp.sp与tp′.sp非变量并且tp.sp=tp′.sp

Thenv=v∧Is′(p)；

//宾语主语相同变量配

elseiftp.op与tp′.op非变量并且tp.op=tp′.op

Thenv=v∧Io′(p)；

//主语与谓语相同变量匹配

elseiftp.sp与tp′.op非变量并且tp.sp=tp′.op

Thenv=v∧Iso(p)；

//谓语与主语相同变量匹配

elseiftp.op与tp′.sp非变量并且tp.op=tp′.sp

Thenv=v∧Ios(p)；

Returnv;

3.2.3Match_BGP算法

Match_BGP算法首先将BGP中所有的TriplePattern进行预处理，即重新排序，确立选择度高的TriplePattern排序靠前；然后调用ASI_TP算法和AJI_TP算法实现最终结果集，如下所示。

算法4BGP查询的算法Match_BGP。

vseva=ASI_TP(G.id,tpi,TD);

//第一个TriplePattern处理结果集合

ifS=∅，returnS；

endif

endif

endfor

//当前TriplePattern所在图中位置

Sjoin=Sjoin∪({s}×Stpi);

endfor

S=Sjoin

ifS=∅,thenreturnS

endif;

endfor

//替换S中triple位置为TriplePattern

returnS

4 实验结果

4.1 实验环境及数据集

本文所提出的基于双层索引结构的起源图查询方法用到的实验环境及平台如下：分布式Hadoop集群系统的硬件环境为包含4个节点，其中1台作为HBasemaster节点，其他3台机器作为slave节点。集群系统使用操作系统为Ubuntu12.04、Hadoop版本为1.0.0、开发环境为JavaSE1.6、HBase版本为0.94.3。本文所采用的数据集是德克萨斯大学起源数据标准(UniversityofTexasProvenanceBenchmark,UTPB)[11]产生的起源图。

4.2 空间占用分析

本文局部索引技术在文献[2]基础上改进，是在文献[2]的基础上增加了3个新索引来提高查询效率，所以存储空间要多出3个索引所占存储空间。

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

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

图5 索引空间占用百分比

4.3 查询性能分析

基于词典表全局索引查询算法具有更高的效率，首先，流程每一次的执行都会选择树的一个叶子节点，执行从root节点开始到叶子节点，查询方法类似折半查找，所以算法时间复杂度为O(logn)。其次，本文采用一致性二叉树分布存储，这样的二叉树结构存储方式也会比其他多叉树的效率高很多。

基于位图方式对起源存储建立索引，起源图所包含三元组的个数直接决定了位图向量的位数，由于计算机对于二进制数计算擅长，对位图向量处理时速度较快，因此，本文在应付海量查询语句时，能够快速匹配到三元组，减少用户查询的响应时间。

本文针对德克萨斯大学起源数据标准数据集分别测试了11条UTPB查询语句来测试本发明所设计索引结构的查询性能。11条UTPB查询语句用Q1,Q2,…,Q11表示，其中Q1是查询所有起源图的标识，Q2是查询一个指定标识的起源图，Q3是查询一个指定起源图的所有数据的起源关系，Q4是查询一个指定起源图的所有过程的触发关系，Q5是查询一个指定起源图的所有数据的使用关系，Q6是查询一个指定起源图的所有数据的生成关系，Q7是查询一个指定起源图的所有控制关系，Q8是查询一个指定起源图的所有数据，Q9是查询一个指定起源图中的一个执行工作流涉及的所有输入和输出数据，Q10是查询一个指定起源图的所有过程，Q11是查询一个指定起源图的所有因为错误停止的过程。采用UTPB的“DatabaseExperiment”工作流来产生起源图，每次工作流所产生的RDF三元组描述一次完整工作流过程，共生成D1、D2、D3、D4、D5五个数据集，具体如表2所示。实验对D1、D2、D3、D4、D5五个数据集分别进行了UTPB的11条查询语句的测试。由于面向起源图查询的双层索引结构的设计，可以通过本地服务器的全局索引直接找到起源图所存储的服务器节点，通过上一步找到的服务器节点中的局部索引可以直接查询到所需的起源信息，具体通过完整的包括选择索引Is、Ip、Io、Isp、Ipo、Iso和join索引Is′、Io′、Iso′的局部位图索引结构实现每一种不同种类起源信息的直接查询，所以，设计可以有效提升查询效率。通过实验，证明了本文所提出的双层索引结构在应对海量起源图存储时，随着数据量的增加，其存储和查询性相对优越，客户查询请求响应及时，面对复杂的查询请求时性能依然较好。具体查询性能情况如图6所示。

表2 起源图数据集

图6 查询性能比较

5 结语

本文在现有起源图索引结构研究基础上，结合数据起源图自身特点以及在云计算环境下查询所面临的新难点，提出了基于双层索引结构的起源图查询方法。在基于一致性二叉树的分布存储策略基础上，给出了基于词典表全局索引和基于位图局部索引，设计云环境下起源图查询算法，并验证了算法的可行性。总之，提出的基于双层索引结构的起源图查询方法具有高效性，有应用价值和前景。

)

[1]DAVIDSONSB,LUDASCHERB,MCPHILIPST,etal.Provenanceinscientificworkflowsystems[J].IEEEDataEngineeringBulletin, 2007, 30(4): 44-50.

[2]CHEBOTKOA,ABRAHAMJ,BRAZIERP,etal.Storing,indexingandqueryinglargeprovenancedatasetsasRDFgraphsinApacheHBase[C]//Proceedingsofthe2013IEEENinthWorldCongressonServices.Piscataway,NJ:IEEE, 2013: 1-8.

[3] 朱敏.基于HBase的RDF数据存储与查询研究[D].南京：南京大学,2013:24-48.(ZHUM.ResearchonstorageandqueryofRDFdatabasedonHBase[D].Nanjing:NanjingUniversity, 2013: 24-48.)

[4]W3C.RDF1.1conceptsandabstractsyntax[EB/OL].[2016-06-15].https://www.w3.org/TR/2014/REC-rdf11-concepts-20140225.

[5]W3C.PROV—overview[EB/OL].[2016-06-15].https://www.w3.org/TR/2013/NOTE-prov-overview-20130430/.

[6]ATREM,CHAOJIV,ZAKIMJ,etal.Matrixbitloaded:ascalablelightweightjoinqueryprocessorforRDFdata[C]//Proceedingsofthe19thInternationalConferenceonWorldWideWeb.NewYork:ACM, 2010: 41-50.

[7] 杨彧剑,林波.分布式存储系统中一致性哈希算法的研究[J].电脑知识与技术,2011,7(22):5295-5296.(YANGYJ,LINB.Researchonconsistenthashingmethodindistributedstoragesystem[J].ComputerKnowledgeandTechnology, 2011, 7(22): 5295-5296.)

[8] 赵彦荣,王伟平,孟丹,等.基于Hadoop的高效连接查询处理算法CHMJ[J].软件学报,2012,23(8):2032-2041.(ZHAOYR,WANGWP,MENGD,etal.EfficientjoinqueryprocessingalgorithmCHMJbasedonHadoop[J].JournalofSoftware, 2012, 23(8): 2032-2041.)

[9] 郭峻峰.数据仓库查询优化方法及索引技术研究[D].合肥：合肥工业大学,2010:14-43.(GUOJF.Researchofqueryoptimizationandindexofdatawarehouse[D].Hefei:HefeiUniversityofTechnology, 2010: 14-43.)

[10] 孟必平,王腾蛟,李红燕,等.分片位图索引:一种适用于云数据管理的辅助索引机制[J].计算机学报,2012,35(11):2306-2316.(MENGBP,WANGTJ,LIHY,etal.Slicebitmapindex:anauxiliaryindexingmechanismforclouddatamanagement[J].ChineseJournalofComputers, 2012, 35(11): 2306-2316.)

[11] 郭栋,王伟,曾国荪.基于一致性树分布的数据分布式存储方法[J].计算机应用,2013,33(12):3432-3436.(GUOD,WANGW,ZENGGS.Distributeddatastoragemethodbasedonconsistenttreedistribution[J].JournalofComputerApplications, 2013, 33(12): 3432-3436.)

[12]UniversityofTexasProvenanceBenchmark(UTPB) [EB/OL].[2016-06-12].http://faculty.utpa.edu/chebotkoa/utp.

ThisworkispartiallysupportedbytheNationalHighTechnologyResearchandDevelopmentProgram(863Program)ofChina(2013BAB06B04),theTechnologyProjectofChinaHuanengGroupHeadquarters(HNKJ13-H17-04),theNaturalScienceFoundationofJiangsuProvince(BK20130852),theSpecialFundforPublicWelfareIndustryoftheMinistryofWaterResourcesofChina(201501007).

XU Guoyan, born in 1971, Ph.D., associate professor.Her research interests include big data, data provenance.

LUO Zhangxuan, born in 1989, M.S.candidate.His research interest is data provenance management.

SONG Jian, born in 1991, M.S.candidate.His research interest is big data management.

LYU Xin, born in 1983, Ph.D., lecturer.His research interests include cryptography, network information security.

Provenance graph query method based on double layer index structure

XU Guoyan*, LUO Zhangxuan, SONG Jian, LYU Xin

(CollegeofComputerandInformation,HohaiUniversity,NanjingJiangsu211100,China)

To solve the problem of low query efficiency and high resource occupancy of the existing provenance graph query system, and consider the internal structure characteristics of provenance information, the relationship between the provenance of information and the data itself, a provenance graph query method based on double layer index structure was proposed.Firstly, for provenance graph query, a double layer index structure including global index based on dictionary table and local index based on bitmap was established.Global index was used to query the server nodes stored in provenance graph, and local index was for refining the query inside one server node.Secondly, based on the dual index structure, a provenance graph query method was designed, in view of the six kinds of selection index and three kinds of join link index.The experimental results show that the proposed method not only improves the query efficiency, but also reduces the waste of memory resources.

provenance graph; double layer index structure; dictionary table; bitmap

2016-07-20;

2016-08-06。 基金项目:国家863计划项目(2013BAB06B04)；中国华能集团公司总部科技项目(HNKJ13-H17-04)；江苏省自然科学基金资助项目(BK20130852)；水利部公益性行业科研专项经费项目(201501007)。

许国艳(1971—)，女，内蒙古赤峰人，副教授，博士，主要研究方向：大数据、数据起源； 罗章璇(1989—)，男，安徽滁州人，硕士研究生，主要研究方向：数据起源管理； 宋健(1991—)，男，江苏盐城人，硕士研究生，主要研究方向：大数据管理； 吕鑫(1983—)，男，江苏南京人，讲师，博士，主要研究方向：密码学、网络信息安全。

1001-9081(2017)01-0048-06

10.11772/j.issn.1001-9081.2017.01.0048

TP311

A