云环境下海量语义数据的查询策略
2017-06-15胡志刚景冬梅陈柏林郑美光杨柳
胡志刚，景冬梅，陈柏林，郑美光，杨柳
云环境下海量语义数据的查询策略
胡志刚，景冬梅，陈柏林，郑美光，杨柳
(中南大学软件学院，湖南长沙，410073)
为了实现对海量RDF数据的高效查询，研究RDF数据在分布式数据库HBase中的存储方法。基于MapReduce设计海量RDF数据的两阶段查询策略，将查询分为SPARQL预处理阶段与分布式查询执行阶段。SPARQL预处理阶段设计实现基于SPARQL变量关联度的查询划分算法JOVR，通过计算SPARQL查询语句中变量的关联度确定连接变量的连接顺序，根据连接变量将SPARQL子句连接操作划分到最小数量的MapReduce任务中；分布式查询执行阶段执行SPARQL预处理阶段划分的MapReduce任务，实现对海量RDF数据的并行查询。采用LUBM标准测试数据集对查询策略予以验证。研究结果表明：JOVR算法能够高效地实现对海量RDF数据的查询，并具有较强的稳定性与可扩展性。
并行处理；语义信息查询策略；MapReduce；SPARQL；海量RDF
随着语义Web的发展，各领域RDF(resource description framework)[1]语义数据急剧增加，如Wikipedia[2]、生物信息学[3]、媒体数据[4]、社交网络[5]等。以链接开放数据(Linked open data, LOD)工程为例[6]，截止到2014−04，LOD工程中共包含1 014个RDF开放数据集，与2011年的295个RDF开放数据集、310亿个RDF三元组相比，规模扩大了3倍多。传统的语义Web查询工具能够提供支持RDF数据标准查询语言SPARQL(simple protocol and RDF query language)的查询环境，但都是运行于单机环境中，处理海量RDF数据时的计算性能有待提高。目前，RDF数据呈现出大规模性、高速增长性与多样性等大数据(big data)[7−8]特性，因此，人们对利用并行计算技术处理海量RDF数据已达成共识。Hadoop是一款开源云计算平台，其核心是 HDFS(hadoop distributed file system)和MapReduce框架。HDFS分布式文件系统具有高容错性，能够提供高吞吐量的数据访问，很适合海量数据集上的应用。运行于HDFS之上的HBase分布式数据库性能高，并且可靠性高。MapReduce分布式程序开发框架能够简化分布式程序的设计与实现，高效处理海量数据，因此，研究人员开始将具备大数据处理能力的云计算 Hadoop技术引入语义Web研究领域[9]。近年来，研究人员基于云环境提出了一些语义数据存储与查询策略，但在存储空间和查询效率方面仍需要进一步研究与优化。本文的主要研究工作如下：1) 采用文献[9]提出的存储方法，基于“二元组合”行键的SPO存储策略，设计3张HBase表(，和)存储海量RDF数据；2) 设计实现SPARQL查询划分算法JOVR，通过计算SPARQL语句中变量关联度确定连接变量的连接顺序，并根据连接变量将SPARQL子句连接操作划分到最小数量的MapReduce任务中，以缩短查询大规模RDF数据的时间；3) 基于MapReduce分布式程序开发框架，高效地实现RDF数据并行查询。
1 相关概念与研究
1.1 相关概念
1) RDF。RDF用主语(Subject)、谓语(Project)、宾语(Object)的三元组<,,>形式描述Web上的资源。其中主语一般用统一资源标识符URI(uniform resource identifier)表示Web上的信息实体(或者概念)，谓语描述实体所具有的相关属性，宾语是对应的属性值[10]。例如
2) SPARQL。SPARQL是W3C(world wide web consortium，万维网联盟)提出的针对RDF数据的标准查询语言，与SQL的语法相似，通过SELECT查询方式查找满足条件的数据。表1所示为1个简单的SPARQL查询例子，用于从图书的数据集中查找出书的题目。
表1 SPARQL查询实例
表1中，SELECT子句表示查询的内容，WHERE子句表示待查询项满足的三元组模式。语句中带“?”的部分是查询中的未知变量，如“?”表示图书题目的未知变量。
3) HBase。HBase是基于Google中Bigtable开发的1个高可靠性、面向列、可伸缩的分布式存储系 统[12]。HBase存储的是松散型数据，介于映射(key/value)与关系型数据之间，存储的数据从逻辑上看就像1张很大的表，其数据列可以根据需要动态增加，对由行和列所确定的单元(Cell)中数据，可由时间戳区分为多个版本。
4) MapReduce。MapReduce是1个分布式程序开发框架，其任务处理分为Map阶段和Reduce阶段，分别通过Map函数和Reduce函数实现。在Map阶段，输入数据经过自定义的Map函数处理后产生
1.2 相关研究
RDF分布式存储主要分为HDFS与HBase 2种方案。研究人员基于这2种方案提出了多种RDF查询算法。
1) MYUNG等[13]从HDFS中的RDF数据文件中读取对应的RDF数据，创建多个MapReduce任务迭代处理SPARQL子句连接操作。但该方法将RDF数据直接存放到HDFS上，缺少了高效的索引结构，而且其算法可能在SPARQL子句连接过程中创建较多的MapReduce任务。HUSAIN等[14]证明了在并行环境下，随着生成MapReduce任务数量降低，RDF数据查询时间会减少，但是同样采用HDFS存储RDF数据，缺少高效的索引结构，很难实现对海量RDF数据的快速随机访问。
2) SUN等[15]基于HBase，采用六张索引表(，，，，和)存储RDF数据，提出了1个迭代生成MapReduce任务的算法实现RDF数据查询。FRANKE等[16]设计了2张HBase表即T和T存储RDF数据，在SPARQL查询过程中优先选取匹配数据量较少的查询子句进行连接。以上这些算法都只侧重于减少SPARQL查询的中间结果集数量，但算法有可能会导致在SPARQL 子句连接过程中创建更多的MapReduce任务，因此，在有些情况下并不能明显缩短查询时间。
2 基于HBase的RDF数据存储策略
基于HBase的RDF三元组存储策略目前主要有3类[15−21]：1) 基于“一二元”行键的SPO存储策略，即任意选取三元组<,,>其中的一元或二元作为HBase表中的行键；2) 基于“列固定”行键的SPO存储策略，即选取三元组<,,>中的谓语作为HBase表中的固定列，主语、谓语作为行键；3) 基于“二元组合”行键的SPO存储策略，即任意选取三元组<,,>中的任意二元作为HBase表中的行键。
2.1 RDF数据的3种存储策略
SUN等[15]基于“一二元”行键的SPO存储策略设计了6张HBase表(，，，，和)，在HBase中的行键分别为，，，，和，用于在查询中快速匹配各种SPARQL三元组模式。
FRANKE等[16]基于“列固定”行键的SPO存储策略设计了2张HBase数据表T和T，列名存储对应的值，行键分别为和，分别用于匹配主语或宾语已知的SPARQL三元组模式，表单元则分别存储和。
本文采用文献[9]中基于“二元组合”行键的SPO存储策略，设计3张HBase表(，和)存储数据。行键分别为，和能够满足所有可能组合形式的SPARQL三元组模式查询匹配条件。表结构如表2所示。表2中，和分别为HBase表中行数和列数，且≥0,≥0；行键是主语值和谓语值的有序对<S,P>(∈[0,])，其对应的个宾语O(∈[0,])作为列名包含于1个列族中，每个表单元设计为null值。表和与表结构相似，分别将谓语和宾语、宾语和主语的有序对作为行键，列族中存放对应的主语值和谓语值。
表2 表SP_O在HBase中的存储结构
表3所示为SPARQL子句中不同的三元组模式与上述HBase表之间的查询映射关系，其中“?”，“?”和“?”分别表示主语、谓语和宾语是未知量，不带有“?”的表示主语、谓语和宾语是已知量。
表3 SPARQL三元组与HBase表映射关系
如表3所示，当三元组模式为(,,)或(?, ?, ?)时，可以对，和中任意1张表检索。当三元组模式中只有1个变量如(,, ?)时，将其中2个已知值和设为检索条件，对表的行键进行匹配；当三元组模式中有2个变量如(, ?, ?)时，利用HBase的Scan区域检索机制，根据已知值在表的行键区间内扫描，得到查询结果。
2.2 RDF数据存储策略分析与对比
从HBase中设计的表数量、空间开销以及时间开销3个方面对基于“一二元”行键的SPO存储策略、基于“列固定”行键的SPO存储策略以及基于“二元组合”行键的SPO存储策略进行对比分析，如表4 所示。
表4 基于HBase的存储策略比较
基于“一二元”行键的SPO存储策略减少了查询时间，但需要将RDF数据复制6次，增大了存储空间的开销。
基于“列固定”行键的SPO存储策略中设计了2张HBase数据表T和T，将谓语对应值作为固定的列名，减少了存储空间。但当和同时为未知量时，则需要对其中任意1个表进行全表扫描，必然会增加查询过程的时间开销。
本文采用的基于“二元组合”行键的SPO存储策略只需要将数据复制3次，与基于“一二元”行键的SPO存储策略相比减少了空间开销，并且只有当，和三者同时为未知量时才会对全表扫描，而基于“列固定”行键的SPO存储策略在和同时为未知量时就对全表进行扫描。所以，与基于“列固定”行键的存储策略相比减少了时间开销。
综上所述，本文采取的存储策略在数据存储空间开销和查询效率的平衡方面更有优势。
3 RDF数据的两阶段查询策略
本文提出的RDF数据的两阶段查询策略基于SPARQL检索在Hadoop平台中实现海量RDF数据的并行查询。以图1中的SPARQL查询语句为例，介绍策略的设计与实现方案。
3.1 RDF数据的两阶段查询策略框架
为了方便描述，首先定义以下概念。
图1 SPARQL查询实例query
定义1()表示SPARQL查询语句中的三元组模式。其中为三元组中变量集合，即{,,,,,}。
()中的每个成员，和中至少有1个是变量，否则SPARQL查询语句将无意义。图1所示的查询实例中三元组模式依次表示为1()，2(，3()，4()，5()。
定义2 连接变量是在2个或更多个<,,>三元组模式中出现的变量，用于多个查询子句连接。
定义3 关联度指与1个连接变量直接相关的其他连接变量的个数，表示为()，{,,}。
图1查询实例中与直接相关的连接变量有和，分别与和直接相关的连接变量只有，那么()=2，()=1，()=1。
定义4()是查询过程中MapReduce任务产生的含有变量的中间结果集，{,,,,,}。
定义5 查询时间指执行查询过程中所有MapReduce任务花费的时间总和，用()表示。每个MapReduce任务花费的时间用()表示，则所花费的时间总和用公式表示为
其中：代表当前SPARQL查询；job表示当前第个MapReduce任务；为MapReduce任务的数量；为连接变量的个数。
RDF数据的两阶段查询策略包含SPARQL预处理和分布式查询执行2个阶段，查询策略框架图如图2所示。
1) SPARQL预处理阶段提出了基于SPARQL变量关联度的查询划分算法JOVR(join on variable relation)。JOVR首先根据变量关联度从SPARQL查询三元组中顺序地选取连接变量，然后将SPARQL子句连接操作划分到最小数量的MapReduce任务中。
图2 RDF数据的两阶段查询策略框架图
2) 分布式查询执行阶段中对查询子句进行连接时，需要将数据从对应的HBase表中读出，然后在Map阶段进行数据过滤与组装，在Reduce阶段完成连接任务。
3.2 SPARQL预处理JOVR算法
JOVR算法通过计算SPARQL变量关联度确定连接变量的连接顺序，根据连接变量贪心划分SPARQL查询语句达到分布式查询阶段(MapReduce任务)数量最少的目标。
算法1: JOVR算法输入: Q (SPARQL查询)输出: job (MapReduce任务)集合 1: n←1 2: U←sortOnRel({u1,u2,…um}); //按关联度非递减对连接变量排序3: while Q≠Empty do4: jobn←Empty; //当前的job5: tmp←Empty; //存放中间连接结果6: for i←1 to m do7: if canJoin(Q, ui)=true then //Q中子集能够按照ui进行连接8: tmp←tmpjoinResult(Q, ui); //保存连接结果9: Q←Q−TP(Q,ui); //从Q中去掉已连接的子集10: jobn←jobn(join(Q, ui); //将连接操作加入当前job11: end if12: end for13: if tmp=Empty //不存在可以参与连接操作的三元组14: break; //结束循环15: Q←Qtmp; //在Q中加入中间连接产生的新变量集16: n←n +1;17: end while18: return { job1, job2,…jobn};
算法第2行是对个连接变量按关联度进行非降序排序，第6~12行采用贪心划分方法确定每个包含的操作。依次遍历连接变量，若能够按照当前变量u进行查询子句连接，则将连接产生的中间结果语句保存在临时变量中，同时从查询语句中去掉已经进行连接的子句，最后还需要将连接操作加入当前的job中。第13~14行指若当前不存在可以参与连接操作的子句，则不再生成新的，算法结束。第15~16行指当前剩余的查询语句不能按照任何连接变量进行连接，则在当前中加入中的语句，开始计算新的，重复第4~16行的操作，直到不会生成新的为止。
在上述算法中，对个连接变量进行快速排序的时间复杂度为lg，外层循环(while循环)最多执行次，内层循环(for循环)最多执行次，所以，该算法的总时间复杂度为((lg))(其中，为查询语句中连接变量的数量，为的数量，1≤≤)。
在图1 所示的SPARQL查询实例中，根据3.1节的定义，可以计算出中连接变量，和的关联度分别为()=2，()=1，()=1。依据JOVR算法，按照关联度非递减次序选取连接变量分别为，和，查询对应2个。查询划分过程如图3所示。
图3 JOVR算法中查询划分过程
从JOVR算法的查询划分过程可以分析出查询用时总和为。
已有研究人员基于JOVF( join on variable frequency)的算法[15]进行SPARQL查询划分。按照连接变量出现的次数进行非升序排序，贪心选择出现次数最多的连接变量，然后依次根据选取的连接变量划分得到。基于JOVF算法，图1所示的查询实例中，，和出现的次数分别为3，2和2，依次选择连接变量，和共划分为3个，划分过程如图4所示。
图4 JOVF算法中查询划分过程
从JOVF算法的查询划分过程可以分析出查询用时总和为
对比分析图3和图4可知：对于图1中的SPARQL查询实例，JOVR算法比JOVF算法划分的数量更少，因此，查询所用的时间更少。
3.3 分布式查询执行
SPARQL预处理阶段划分得到后，分布式查询执行阶段基于MapReduce实现对RDF数据的并行查询。这里结合图1中的查询实例介绍每个中连接操作的具体步骤，如图5所示。
1) HBase数据读取。当查询子句中的三元组参与连接操作时，需要将数据从对应的HBase表中读取。
2) Map阶段。将查询子句中三元组对应的数据集以
3) Reduce阶段，完成同一连接变量对应的多个查询子句的连接。如图51中对key为的子句连接后，得到的数据key仍然是，value是将参与连接操作数据的value部分合并而来，得到University+#，最后按照自定义的Reduce函数输出最终结果。
在有多个时，前1个的输出是后1个的输入(如图5所示)，2的输入分别来自于读取的数据集和1的输出数据集，经过Map阶段和Reduce阶段后，输出，和最终对应的数据，即SPARQL的查询结果。
图5 分布式查询执行过程实例
4 实验分析
4.1 实验环境
采用Hadoop-2.5.2作为运行平台，选取HBase-1.0.0作为RDF三元组存储数据库，并选用4台PC机(具体配置为Pentium IV，CPU 3.00 GHz，2 GB内存和160 GB硬盘空间)搭建实验平台。
本实验利用利哈伊大学开发的Lehigh University Benchmark(LUBM)[17]标准测试数据集，分别对 10，50，100，200，300和500 所大学的RDF数据集进行测试。
4.2 实验结果与分析
在不同数据集下，分别针对算法JOVF和JOVR测试5条在语句复杂程度上具有代表性的LUBM 查询语句，各查询语句与的对应关系如表5所示。为了保证实验结果的准确性，本实验将每条查询语句在不同数据集下分别测试5次，最后取得平均值。各查询花费的平均时间如表6所示。
1) 由表6可知：对于Q1和Q4这2个查询语句，JOVF和JOVR算法的平均时间几乎相同，这是因为在这2种算法中，Q1和Q4都对应1个(如表5所示)；而对于Q2，Q8和Q9， JOVF算法花费的时间为JOVR的1.5倍左右。由表5可知：在JOVF中，Q2，Q8和Q9对应的数量分别为3，2和3，在JOVR中三者对应的数量分别为2，1和2，由于启动耗时，查询时间会随着数量增多而相应增大。所以，JOVR的查询效率比JOVF的高。
2) JOVF和JOVR算法平均查询时间随着数据集增大而增大，分别如图6和图7所示。随着测试数据集规模的不断扩大，这2个算法的平均查询时间都并没有呈现指数增长趋势，而是平缓上升。JOVR中平均查询时间的增长率更小，表明JOVR在查询的稳定性方面比JOVF强。
3) 由表6可知：当测试数据集扩大50倍时，JOVF和JOVR算法的平均查询时间分别只增大约1.8倍和1.7倍，表明JOVF和JOVR都具有良好的可扩展性。
表5 LUBM查询语句与job的对应关系
表6 LUBM平均查询时间
1—Q1；2—Q2；3—Q4；4—Q8；5—Q9。
1—Q1；2—Q2；3—Q4；4—Q8；5—Q9。
综合以上分析，JOVR算法在查询效率、稳定性及可扩展性方面都取得了较好的结果，能够更好地支持海量RDF数据的查询。
5 结论
1) 提出了一种海量RDF数据两阶段查询策略，设计了基于SPARQL变量关联度的查询划分算法JOVR，达到了分布式查询过程中查询任务数量最少的目的。
2) 与JOVF算法相比，JOVR算法查询效率更高，稳定性更强，能够更好地支持海量RDF数据的查询。
3) JOVR主要针对SPARQL的简单查询模式，对SPARQL复杂组图模式分布式查询方法有待进一步研究。
[1] BRICKLEY D, GUHA R V. RDF schema 1.1[EB/OL]. [2014−09−21]. http:// www.w3.org/TR/rdf-schema.
[2] HOFFART J, SUCHANEK F M, BERBERICH K, et al. YAGO2: A spatially and temporally enhanced knowledge base from Wikipedia[J]. Artificial Intelligence, 2013, 194(1): 28−61.
[3] BELLEAU F, NOLIN M A, TOURIGNY N, et al. Bio2RDF: towards a mashup to build bioinformatics knowledge systems[J]. Journal of Biomedical Informatics, 2008, 41(5): 706−716.
[4] KOBILAROV G, SCOTT T, OLIVER S, et al. Media meets semantic web-how the bbc uses dbpedia and linked data to make connections[C]// European Semantic Web Conference on Semantic Web in Use Track. Heraklion, Greece, 2009: 723−737.
[5] MIKA P. Social networks and the semantic web: a retrospective of the past 10 years[C]// Proceedings of the 24th International Conference on World Wide Web. Florence, Italy, 2015: 1461.
[6] The Linked Open Data. The linked open data project (LOD). [2015−06−08]. http://www.w3.org/wiki/SweoIG/TaskForces/ CommunityProjects/LinkingOpenData.
[7] 孟小峰, 慈祥. 大数据管理: 概念、技术与挑战[J]. 计算机研究与发展, 2013, 50(1): 146−169. MENG Xiaofeng, CI Xiang. Big data management: concepts, techniques and challenges[J]. Journal of Computer Research and Development, 2013, 50(1): 146−169.
[8] 王珊, 王会举, 覃雄派, 等. 架构大数据: 挑战、现状与展望[J]. 计算机学报, 2011, 34(10): 1741−1752. WANG Shan, WANG Huiju, TAN Xiongpai, et al. Architecting big data: challenges, studies and forecasts[J]. Chinese Journal of Computers, 2011, 34(10): 1741−1752.
[9] 李韧. 基于Hadoop的大规模语义Web本体数据查询与推理关键技术研究[D]. 重庆: 重庆大学计算机学院, 2013: 39−45. LI Ren. Research on key technologies of large-scaled semantic web ontologies querying and reasoning based on Hadoop[D]. Chongqing: Chongqing University. College of Computer, 2013: 39−45.
[10] 杜小勇, 王琰, 吕彬. 语义Web数据管理研究进展[J]. 软件学报, 2009, 20(11): 2950−2964. DU Xiaoyong, WANG Yan, LÜ Bin. Research and development on Semantic Web data management[J]. Journal of Software, 2009, 20(11): 2950−2964.
[11] BECHHOFER S, HARMELEN F V, HENDLER J, et al. OWL web ontology language reference[EB/OL]. [2009−11−29]. http://w3.org/TR/owl-ref.
[12] 施惠俊. 基于云计算的海量语义信息并行推理方法研究[D]. 上海: 上海交通大学软件学院, 2012: 31−35. SHI Hunjun. Research of massive semantic information parallel inference method based on cloud computing[D]. Shanghai: Shanghai Jiaotong University. College of Software, 2012: 31−35.
[13] MYUNG J, YEON J, LEE S G. SPARQL basic graph pattern processing with iterative mapreduce[C]// Proceedings Massive Data Analytics Cloud (MDAC’10). Raleigh, USA, 2010: 1−6.
[14] HUSAIN M, MCGLOTHLIN J, MASUD M M, et al. Heuristics-based query processing for large RDF graphs using cloud computing[J]. IEEE Transactions on Knowledge & Data Engineering, 2011, 23(9): 1312−1327.
[15] SUN J, JIN Q. Scalable RDF store based on HBase and MapReduce[C]// International Conference on Advanced Computer Theory & Engineering. Chengdu, China, 2010: 633−636.
[16] FRANKE C, MORIN S, CHEBOTKO A, et al. Distributed semantic web data management in HBase and MySQL cluster[C]// Proceedings of the 2011 IEEE 4th International Conference on Cloud Computing. Washington, USA, 2011: 105−112.
[17] GUO Y, PAN Z, HEFLIN J. LUBM: a benchmark for OWL knowledge base systems[J]. Semantic Web Journal, 2005, 3(2/3): 158−182.
[18] LIU B, HUANG K, LI J, et al. An incremental and distributed inference method for large-scale ontologies based on MapReduce paradigm[J]. IEEE Transactions on Cybernetics, 2015, 45(1): 53−64.
[19] CHENG J, WANG W, GAO R. Massive RDF data complicated query optimization based on MapReduce[J]. Physics Procedia, 2012, 25(22): 1414−1419.
[20] LIU L, YIN J, GAO L. Efficient social network data query processing on MapReduce[C]// Proceeding of the 5th ACM Workshop on HotPlanet. HongKong, China, 2013: 27−32.
[21] WEISS C, KARRAS P, BERNSTEIN A. Hexastore: sextuple indexing for semantic web data management[C]// 34th International Conference on Very Large Data Bases (VLDB). Auckland, New Zealand, 2008: 1008−1019.
(编辑 陈灿华)
Massive semantic data query method based on cloud computing
HU Zhigang, JING Dongmei, CHEN Bailin, ZHENG Meiguang, YANG Liu
(School of Software, Central South University, Changsha 410073, China)
In order to achieve the efficient query for large-scale RDF data, the storage method of RDF triples in HBase was analyzed and a two-phase query strategy for large-scale RDF data was designed based on MapReduce, which was divided into two stages, i.e. the SPARQL pretreatment stage and the distributed query execution stage. In the SPARQL pretreatment stage, a SPARQL query classification algorithm-JOVR was implemented, which determined the join order of connection variables by calculating the correlation between the variables in a SPARQL query statement, and then the join between SPARQL clauses was divided into the minimum number of MapReduce jobs according to the connection variables. The distributed query execution phase accomplished large-scale RDF data query concurrently based on MapRdecue jobs from SPARQL pretreatment stage. The strategy was verified by LUMB benchmark set. The results show that JOVR can query large-scale RDF data efficiently with strong stability and scalability.
parallel processing; semantic information query strategy; MapReduce; SPARQL; large-scale RDF
10.11817/j.issn.1672-7207.2017.05.014
TP391
A
1672−7207(2017)05−1218−09
2016−06−16；
2016−08−22
国家自然科学基金资助项目(61301136, 61572525, 61602525) (Projects(61301136, 61572525, 61602525) supported by the National Natural Science Foundation of China)
杨柳，副教授，硕士生导师，从事语义信息处理、软件度量研究；E-mail: yangliu@csu.edu.cn
