一种基于数据划分实现分布式SPARQL查询的方法

杜　方

(宁夏大学数学计算机学院　宁夏 银川 750021)



一种基于数据划分实现分布式SPARQL查询的方法

杜方

(宁夏大学数学计算机学院宁夏 银川 750021)

当海量RDF数据存储在分布式平台上时，数据划分的策略将直接影响海量数据的查询效率。为了提高分布式平台上的海量数据查询效率，提出一种基于分布式平台的有效数据划分方法。该方法根据RDF数据图的特征将数据分布在集群的各个节点上，并在此基础上对SPARQL查询语句进行分解，实现高效的分布式查询。算法在云平台上实现，并在真实的RDF数据集上对算法进行了测试。实验结果证明，与基准方法相比，该算法在查询效率上有很大的提高。

RDF数据SPARQL查询分布式查询数据划分数据分布云平台

0　引　言

随着语义网的不断发展，网络上涌现出大量的RDF数据集，如Freebase[1]、DBPedia[2]、Linked Open Data[3]等。这些数据的RDF三元组的数量通常都在10亿甚至百亿以上，海量的数据为RDF数据查询带来了新的挑战。SPARQL[4]查询是W3C推荐的一种RDF数据查询语言，它的语法与SQL语句的语法相似，但不包括from子句。目前效率最高的SPARQL查询方法是由Neumann等人所提出的RDF-3X查询引擎[5]。但RDF-3X是针对单个节点上的静态RDF数据集所设计，该方法在RDF三元组的主语、谓词和宾语上建立spo、sop、pso等六种顺序的完备索引，在单个节点上将数据冗余存储在六个B+树结构中。完备的索引以及数据冗余在很大程度上提高了查询效率，但是当面对海量、动态的RDF数据时，冗余的集中式存储将成为瓶颈，RDF-3X的效率优势将不复存在。

RDF-3X在集中式环境下实现RDF数据的查询处理。早期的研究均采用集中式处理，例如3-store[6]、Sesame[7]、jena2[8]等，这些研究都采用传统的关系数据库存储和管理RDF数据，借助关系数据库的成熟技术实现对RDF数据的查询。但传统数据库技术在处理海量数据查询时效率低下，特别是RDF数据查询中包含大量的自连接，这使得传统方法无法有效处理查询。

也有一些研究者提出了在分布式平台上实现对海量RDF数据的处理，例如较早的方法YARS[9]将其方法扩展到分布式平台上，提出了YARS2[10]方法；Stuckenschmidt等人也在文献[11]中提出了分布式RDF查询处理的方法。这两种方法在分布式平台的每个节点上仍采用关系数据库存储和管理RDF数据，因此仍然无法真正避免大量自连接带来的问题。分布式平台上的RDF查询处理包括两部分：数据分布和查询分解。在文献[12]中，Huang等人根据RDF图将距离近的边和点分布在一个机器节点上，查询时根据谓词将查询语句分解成可并行的的子查询，然后将子查询提交至相关节点。文献[13]首先按照谓词对RDF数据进行垂直划分，对于大的数据分布再按照宾语进行二次划分。Myung等人[14]根据RDF图结构直接将数据分布在云平台上，文献[15]按照键值对来分布数据。查询时通常将SPARQL查询语句分解为多个星型子查询，然后将这些子查询提交至相关节点进行处理。还有一些研究者考虑从查询语句本身的特点对其进行分解。文献[16]将链式SPARQL查询语句分解为多个星型查询，在分布式处理时每次迭代过程仅处理其中的一个星型子查询，最后再将这些子查询结果进行进一步处理。文献[17]事先对常用的一些分析性查询进行预定义，将出现频率高的对应实体名称预存至一张表，并在表上创建索引，这样一些常用的查询可以得到预先处理。但这些划分方法均不考虑数据间的逻辑关系，数据较为平均地分布在各节点上。当进行复杂查询时，仍然会产生大量的中间结果需要在多个节点中传递，从而影响查询效率。

本文提出一种有效的RDF数据划分策略。该方法根据RDF数据集所形成的图的特征对数据进行划分，数据分布在云平台的各节点上，在考虑数据语义关系的同时兼顾节点间的负载平衡。处理查询请求时，将查询分解至语义相关的对应节点，而语义不相关的节点将不参与查询处理。这样利用数据分布裁剪查询的搜索空间，在很大程度上减少了节点间的通信。对于一些简单的SPARQL星型查询，通常很少的节点甚至单个节点就可以实现查询处理。对于分布式平台上的数据处理，通信代价是影响处理效率的一个很大因素。本文提出的方法有效地减少了通信代价，提高了查询效率。本文的主要贡献在于：

1) 提出了一种有效的数据划分方案。该方案根据RDF数据图的特征实现数据划分，然后依据数据分片的大小将其分布至云平台的各个节点，分布时同时考虑各节点间的负载平衡。

2) 提出了一种查询处理及优化的方法。该方法在数据划分的基础上，将查询分解至相关节点，实现查询的并行处理。

3) 在构造数据集和实际数据集上进行了实验。实验结果表明，本文所提出的方法能够很好地提高查询效率，证明了方法的有效性。

1　基于RDF数据图的划分策略

数据的划分策略包括两部分：一是如何将海量数据进行划分，二是如何将这些划分后的数据合理地分布至平台中的各个计算机节点。本节将从这两个方面来讨论本文所提出的方法。

1) RDF数据图

每条RDF数据都是一个形如的三元组，其中s为主语，p为谓词，o为宾语。一个RDF三元组构成一个简单的图(如图1(a)所示)，其中主语和宾语为图中顶点，谓词为边。相同主语的三元组称为一个实体，如图1(b)所示为一个实体。一个海量RDF数据集中有上百亿条三元组，这些三元组构成大量实体，而实体间亦有边(谓词)相连。因此一个RDF数据集是一个大的数据图，每个顶点和每条边都带有文字标记，这些文字信息是RDF数据所包含的语义信息，实体是构成完整的语义信息的单位。

图1　RDF数据图

定义1实体的模式

例如：图1(b)中实体的模式为{borninplace,Awarded,YearofBirth,Researcharea}。RDF实体的模式在本文中也泛称为RDF数据的模式。 一个实体的模式即为该实体对应图中边上的标记的集合，该集合反映了实体语义的核心内容。

2) 保持语义的数据划分

分布式平台上数据的划分需要考虑两个主要因素：机器的负载平衡和网络通信总量[18]。为使机器负载平衡，需将数据尽可能地平均划分，将其分布至分布式集群中的各个节点，但这样划分会使得查询涉及很多节点，因此并不能保证节点间的通信总量尽可能少。若仅考虑网络通信总量，则可将密集子图放在同一机器节点，但这样可能导致机器负载的极端不平衡。如果将一个机器节点上的数据称为一个数据分片，并设查询涉及的数据分片数量为N，则查询的代价可用式(1)来衡量:

(1)

由于分布式计算的启动代价和查询计划的生成代价相对固定， 因此α可看作常量。而执行查询的代价主要与查询的搜索空间大小、中间结果的大小以及机器节点间进行连接操作时的读写代价有关。中间结果的大小主要影响节点内的数据读写时间，在分布式环境下这部分代价可忽略不计；搜索空间的大小与数据分片的大小有直接关系；节点间连接操作的读写代价主要与查询涉及的分片的数量有关，因此影响查询代价的主要因素为查询所涉及的数据分片的数量以及数据分片的大小。

RDF数据上的查询为语义查询。如果能够结合数据语义对RDF数据集进行划分，将语义相关的数据尽可能地划分为同一个数据分片，那么将在很大程度上减少查询相关分片的数量。因此需要找到一种保持语义的数据划分方法实现RDF的数据分布。

RDF数据语义主要体现为实体的模式，例如从图1(b)可以看出，实体AlbertEinstein的模式{borninplace,Awarded,YearofBirth,Researcharea}体现了该实体在数据集中的核心内容。为了保持语义，按照实体的模式对RDF数据集进行划分，即相同模式的实体划分在一起，模式对应图中的边，在划分时以边带入邻接点，则保证了语义的完整。但是RDF数据集中的数据来自于大量不同的网页，因此实体的模式也多种多样，即使是相同类型的数据也通常会有不完全相同的谓词。如果直接按照模式对数据进行划分，则会产生数量巨大的数据分片，无法将这些分片直接分布至有限的机器节点。通过数据分析发现，同类型或相似类型的RDF数据通常会有相似的模式[19]。根据文献[19]中的方法，首先对RDF实体进行聚类，将模式相似的实体聚类到一起，聚类时的相似度取值是影响聚类结果的重要因素。RDF数据集中的实体数量大，若相似度太高，则得到的聚类数目太多，无法高效处理查询；但若相似度太低，聚类中的不相关实体太多，同样无法提高查询效率，因此需要合理地设计相似度来控制聚类的数目。同时，若每个聚类中RDF三元组数量过多，则查询时搜索空间可能过大，影响查询效率。在文献[19]中通过实验给出了相似度阈值及聚类中三元组数目参数值，在本文的方法中我们仍然采用同样的数值作为聚类参数，在保证每个聚类中实体足够相似的基础上控制聚类的大小。

算法1保持语义的RDF数据初次划分方法SHRDFPA

输入：待划分的RDF数据集，DS

输入：聚类的模式相似度阈值，ɛ

输入：每个聚类中包含的实体数量阈值，δ

输出：初次划分后的数据聚类集合R1,R2,…,Rn

1.将DS中每个RDF三元组的主语s作为key，谓词p：宾语o作为value，即进行分发，将DS中的RDF三元组聚集为实体集合E

2.将聚集后的实体集合中每个实体的谓词集合P作为key，主语s作为value，即进行分发，将模式相同的实体聚集为集合P

3.对P中的实体按照所包含三元组的数量降序排列

4.将P1划分至R1，R1写入R集合，并令R(D1) =P1

5.forP集合中除P1外的每个Pido

6.forR集合中的每个Rjdo

7.if(Pi与P(Rj)的相似度≥ɛ 并且Rj中的实体数量≤δ)

8.将Pi划分至Rj

9.P(Rj) =P(Rj) ∪Pi

10.else新建一个Rk

11.将Pi划分至Rk，

12.Rk写入D集合

13.P(Rk) =Pi

14.endfor

15.endfor

16.输出集合R

对于每个聚类结果Ri，将Ri中实体模式的并集作为Ri的模式，写作P(R)。数据的初次划分以Ri为单位，即每个Ri作为一个基本数据分片。算法1为云平台上保持语义的RDF数据初次划分方法。

算法第1行至第3行首先对待划分的RDF数据集进行预处理，包括将数据集中的RDF三元组聚集为实体，并将模式相同的实体聚集为模式集合，然后将模式集合中的实体按照三元组数量进行降序排列。算法第4行首先将P1划分至第一个聚类分片，在接下来的双重循环中考查模式集合中的每个Pi。若该Pi与已有的聚类Rj的模式相似度大于阈值，并且该聚类中的实体数量小于阈值，则将Pi放入该聚类，否则Pi将放入新的聚类中(算法第5行至第15行)。

3) 数据分布策略

对于RDF数据集来说，划分后的网络通信总量主要与查询时节点间的通信次数有关，若查询时涉及的数据分片过多，则查询时中间结果的读写会造成巨大的网络通信代价。文献[19]的实验表明，对RDF数据集聚类后查询涉及的聚类数目通常在较小范围，因此可以考虑将一个聚类划分为一个数据分片的方法，以此来减少网络通信总量。但这样的划分方法会导致以下问题：(1)RDF数据集中存在较严重的数据倾斜问题，以BTC数据集为例，实体数量在前三位的聚类就占数据集实体总数的50%；如果直接将初次划分的结果Ri作为数据分片分布至每个机器节点，会产生极大和极小的数据分片，造成机器负载的极端不平衡；(2) 在大的Ri上进行查询处理时，由于搜索空间太大，不能有效地提高查询效率；(3) 在大的Ri上建立和维护索引都较困难，数据的更新更会带来不可忽视的代价，使得方法不具有良好的可扩展性。因此在数据分布时需要对数据量较大的Ri进行再划分，而将较小的聚类进行组合，在减少通信代价的同时尽可能均衡机器负载。

设某个聚类Ri中的实体数量为NR，则当NR>φ时对Ri进行再划分，φ为阈值，其值可由式(2)计算得到：

(2)

其中NE为RDF数据集中的实体总数，Np为云平台中的机器节点数量，λ为(0,1]之间的可调规范化因子。λ的取值需要参照网络带宽w，当w较大时，并行时的通信代价小，则可将λ调小，反之则可将λ调大。再次划分采用哈希划分法：设有需要进行再划分的聚类Ri，对Ri中RDF实体的主语进行哈希运算，实现再次分片得到划分集合ρ。无需再次划分的聚类与这些再次划分后的每个ρj构成的集合将被分布在分布式平台的各个机器节点上，属于同一个R的ρj会被分配到不同机器节点上，同一个机器节点上的数据为一个数据分片D。划分后的数据分片Di中所包含R的模式的并集为Di的模式，写作P(D)。这样的数据划分及分布以实体为单位，同一个实体在同一个机器节点上，既保持了实体的语义，又保证了SPARQL查询中的星型查询能够在单个节点上执行，同时使得涉及不同实体的查询能够尽可能并行执行，从而在很大程度上提高查询效率。图2为一个数据划分与分布示意图。

图2　数据划分与分布示意图

2　查询处理与优化

SPARQL查询分为星型查询和链式查询，图3(a)和(b)分别为星型查询和链式查询的例子。一个链式查询可以分解为多个独立的星型查询，因此星型查询是SPARQL查询的基本查询处理单位。来自用户的链式查询经过语法与语义处理后被重写为多个星型查询，这些星型查询之间以s-o连接(o-o连接可以再分解为两个星型查询)。例如图3(b)中的链式查询可以分解为以?x、?y和?p为中心的三个星型查询，这三个查询间均以s-o连接。分解后的查询由查询优化器给出连接的先后顺序。在执行查询时，根据预先建立的谓词倒排索引，按照查询语句的谓词集合将语句提交至查询相关分片所在机器节点，并行处理后得到中间结果。

图3　SPARQL查询

定义2查询相关分片

设有数据分片集合D及查询q，q涉及到的谓词集合为P(q)，则查询相关分片定义为{Di|Di∈D∩(P(Di)⊇P(q))}。

分布式平台的每个机器节点上均配置RDF-3X查询引擎，保证分解后的查询语句能够在每个节点上高效地执行。并行执行后的中间结果直接存储在分布式平台上，这样既保证有节点故障时仍然能够正确执行查询，同时防止中间结果过大无法放入内存。

查询优化器根据连接变量之间的冲突来决定连接的顺序，无冲突的连接查询可以并行执行，而有冲突的连接需要按照连接变量之间的依赖关系先后执行。例如图3(b)中以?y为中心的星型查询与以?p为中心的星型查询之间无冲突，可并行执行；而以?y为中心的星型查询与以?x中心的星型查询之间有冲突，?y的执行依赖于?x的结果。此时一个可行的执行方案是首先得到?x的结果，然后并行执行以?p为中心和以?y为中心的星型查询。

3　实验分析

3.1实验环境

实验在8个机器节点组成的云平台上进行，机器CPU均为Intel双核1.86GHz，内存为3GB至8GB不等，分布式环境为Hadoop1.0.4，每个节点上装载RDF-3X0.3.7。

实验选取的真实RDF数据集为BTC(BillionTripleChallenge)[20]，BTC数据集包含了来自DBPedia、Yago、Freebase等12个RDF数据集中的数据，共有超过32亿的RDF三元组。该数据集中有95 898个不同的谓词，经过去重、去噪音的初步处理后，保留其中10亿多条三元组作为实验数据。

用来进行对比实验的RDF数据集为目前最为常用的测试数据集LUBM(LehighUniversityBenchmark)[21]。LUBM是以大学为本体的构造数据集，数据集的大小可根据用户需求设置相关参数得到。本实验中的LUBM数据集包含197 986个大学的相关信息，共11亿条RDF三元组，其中包括18个谓词、2.17亿个实体。

3.2数据分布测试实验

在这部分实验中，我们采用三种方法对BTC数据集进行划分，分别为直接哈希划分、直接聚类划分以及在聚类结果的基础上进行再划分。其中直接哈希划分是指根据实体的主语进行哈希分布；直接聚类划分是按照数据集的聚类结果进行数据分布；在聚类结果的基础上进行再划分是本文所提出的方法，三种方法的对比试验结果如图4所示。从实验结果可以看出，直接哈希分布和直接聚类分布均会出现严重的数据倾斜问题，这是由于BTC数据集中的实体分布存在明显的长尾现象。在前面的工作[19]中，对BTC中实体所包含三元组数量进行了统计，其中包含三元组最多的两个实体占整个数据集三元组总数的30%，而用本文方法再划分后，各节点上数据基本处于均衡状态。

图4　三种数据划分方法比较

3.3查询效率测试实验

这部分实验中，我们与目前在云平台实现RDF数据查询的方法MR-RDF[15]进行了比较，查询实验分别在BTC和LUBM两个数据集上进行。

3.3.1LUBM上的查询效率测试实验

在LUBM上的查询实验共选取了8个查询语句：Q1-Q8。这些查询语句分为3组，其中查询1、4为简单的星型查询，查询2、6、7为包含一个s-o连接的链式查询，查询3、5、8为包含多个s-o连接的复杂链式查询。实验结果如表1所示，从实验结果中可以看出本文方法总体查询效率明显优于MR-RDF。其中Q2、Q4、Q6-Q8查询的效率比MR_RDF方法快10～30倍，其原因主要在于：1) 通过监控发现这几个查询均被分解至大于等于4个节点，这样的分布保证了各节点间的负载均衡，并行度高；2) 由于分布均衡所以中间结果小，降低了通信代价；3) 从查询语句本身来看，这几个查询均包含常见谓词和宾语，利用聚类可以预先对搜索空间进行较大幅度裁剪，进一步提高查询效率。本文方法在查询Q3和Q5上的执行效率也要明显优于MR-RDF。Q3和Q5中包含复杂的连接查询，MR-RDF方法需要多次MapReduce迭代任务才能处理这样的查询。而我们的方法直接在云平台上通过节点调度实现分布式处理，减少了MapReduce的任务启动时间，因此提高了查询效率。Q1为简单的星型查询，且其结果集较大，本文方法和MR-RDF都需要大量的时间向HDFS写结果数据，因此本文方法和MR-RDF方法相比，效率只是稍有提高。

表1　LUMB上的查询效率测试结果(单位：秒)

3.3.2BTC上的查询效率测试实验

BTC上的查询语句也分为三组(具体语句见附录中查询Q9-Q15)，其中Q9和Q11为仅包含一个s-o连接的链式查询，Q10和Q13为包含未知谓词的查询，Q12、Q14和Q15为包含多个连接的复杂链式查询。实验结果如表2所示，同样从实验结果可以看出，在真实数据集BTC上，本文方法要明显优于MR-RDF。

表2　BTC上的查询效率测试结果(单位：秒)

由于BTC数据集中的谓词数量比LUBM多，因此查询时的中间结果远小于LUBM上的查询。从总体查询结果中可以看出，BTC上的查询时间明显小于LUBM上的查询时间。特别是Q10和Q13由于中间结果很小，因此本文方法远远优于MR-RDF。

3.4可扩展性测试实验

为了测试方法的可扩展性,我们在实验中分别改变LUBM数据集的大小和云平台中节点的数目，图5为预处理(包括数据划分和分布)的时间对比。

图5　预处理的时间对比结果

图5(a)所示为改变云平台中的节点数量，测试在不同节点数量下预处理时间的变化。图5(b)是在节点数目为20，数据量为50GB时，与文献[12]中的方法进行预处理时间的对比。从(a)实验结果可以看出，当云平台中节点数量增加时，预处理时间大量减少。(b) 的实验结果表明，当数据大小和节点数目固定时，本文的方法预处理时间远远小于文献[12]中的方法。这是因为文献[12]对数据进行预处理的时间主要用在三元组的分布，图划分方法的复杂导致数据分布耗费大量时间，而本文的方法相对简单，因此在时间上有很大提高。

图6给出了处理复杂查询Q5的效率，并与文献[14]中的方法进行了对比。

图6　可扩展性实验——与文献[14]对比

Q5为包含多个连接的复杂查询，从实验结果可以看出，当云平台中节点数量从2增加至32个时，本文的方法在查询处理效率上有显著的提高。同时对比文献[14]中的MRLUBM方法，本文的方法整体优于MRLUBM。这是因为首先随着节点数量的增加，数据可以分布在更多的节点上，更好实现并行，同时有效减少中间结果的大小，因此查询时间呈明显的下降趋势。而MRLUBM在进行查询处理时需要不可忽视的MapReduce启动时间，因此在整体上所需的查询处理时间较多。图5和图6的实验均证明了本文方法具有良好的可扩展性。

4　结　语

本文提出了一种有效的基于云平台的RDF数据划分方法，该方法在对数据划分时既保持了RDF数据的语义特征，又保证数据分布的均衡性。实验证明，本文方法能够有效提高查询效率，并具有良好的可扩展性。总体上来说，本文方法主要受中间结果影响，中间结果较小时，本文方法在查询效率上具有明显优势；而当中间结果大时，由于需要大量的I/O时间和节点间的通信代价，本文方法虽仍然优于对比方法，但效果不够明显。因此未来的工作将进一步针对中间结果较大的查询进行研究和方法改进。

[1]Freebase[OL] .2015-1-6.http://www.freebase.com/.

[2]DBPedia[OL].2015-1-6.http://dbpedia.org/.

[3]LinkedOpenData[OL].2015-1-8.http://linkeddata.org/.

[4]SPARQL[OL].2015-1-30.http://www.w3.org/TR/rdf-sparql-query/.[5]NeumannT,WeikumG.RDF-3X:arisc-styleengineforRDF[C]//Proceedingsofthe34thInternationalConferenceonVeryLargeDataBases,Auckland,NewZealand,2008.USA:ACM,2008,1(1):647-659.

[6]HarrisS,GibbinsN.3store:Efficientbulkrdfstorage[C]//Proceedingsofthe1stInternationalWorkshoponPracticalandScalableSemanticSystems,SanibelIsland,2003.USA:CEUR-WSpress,2003,89:1-15.

[7]BroekstraJ,KampmanA,HarmelenFV.Sesame:agenericarchitectureforstoringandqueryingrdfandrdfschema[C]//InternationalSemanticWebConference,Sardinia,Italy2002.London:Springer,2002:54-68.

[8]WilkinsonK,SayersC,KunoHA,etal.EfficientRDFstorageandretrievalinjena2[C]//ThefirstinternationalworkshoponSemanticWebandDatabases,Berlin,Germany,2003:131-150.

[9]HarthA,DeckerS.Optimizedindexstructuresforqueryingrdffromtheweb[C]//Proceedingsofthe3rdLatinAmericanWebCongress,BuenosAires,Argentina,2005.USA:IEEEComputerSociety,2005:71-80.

[10]HarthA,UmbrichJ,HoganA,etal.Yars2:afederatedrepositoryforqueryinggraphstructureddatafromtheweb[C]//Proceedingsofthe6thInternationalSemanticWebConference(ISWC)andthe2ndAsianSemanticWebConference(ASWC),Busan,Korea, 2007.Berlin:Springer,2007:211-224.

[11]StuckenschmidtH,VdovjakR,HoubenGJ,etal.IndexstructuresandalgorithmsforqueryingdistributedRDFrepositories[C]//Proceeingsofthe13thInternationalConferenceonWorldWideWeb,NewYork,USA, 2004.USA:ACMPress,2004:631-639.

[12]HuangJW,AbadiDJ,RenK.Scalablesparqlqueryingoflargerdfgraphs[C]//ProceedingsoftheVLDBEndowment,Seattle,USA,2011,4(11):1123-1134.

[13]TranT,WangHF,HaaseP.Hermes:datawebsearchonapay-as-you-gointegrationinfrastructure[J].WebSemantics:Science,ServicesandAgentsontheWorldWideWeb,2009,7(3):189-203.

[14]MyungJ,YeonJ,LeeSG.Sparqlbasicgraphpatternprocessingwithiterativemapreduce[C]//Proceedingsofthe2010WorkshoponMassiveDataAnalyticsontheCloud,Raleigh,USA, 2010.USA:ACMpress,2010:1-6.

[15]HusainMF,McGlothlinJP,MasudMM,etal.Heuristics-basedqueryprocessingforlargeRDFgraphsusingcloudcomputing[J].IEEETransactionsonKnowledgeandDataEngineering,2011,23(9):1312-1327.

[16]KimH,RavindraP,AnyanwuK.FromSPARQLtomapreduce:thejourneyusinganestedtriplegroupalgebra[C]//ProceedingsoftheVLDBEndowment,Seattle,USA,2011,4(12):1426-1429.

[17]KotoulasS,UrbaniJ.SPARQLqueryansweringonasharednothingarchitecture[C]//ProceedingsoftheWorkshoponSemanticDataManagement,the36thInternationalConferenceonVeryLargeDataBases(SemData@VLDB2010),Singapore, 2010.USA:CEUR-WSpress,2010:1-6.

[18] 张俊林.大数据日知录:架构与算法 [M].北京:电子工业出版社,2014.

[19]DuF,ChenYG,DuXY.Partitionedindexesforentitysearchoverrdfknowledgebases[C]//Proceedingsofthe17thInternationalConferenceonDatabaseSystemsforAdvancedApplications,Busan,SouthKorea,2012.Berlin:Springer,2012:141-155.

[20]BillionTripleChallenge[OL].2015-2-1.http://challenge.semanticweb.org/.

[21]GuoYB,PanZX,HeflinJ.Lubm:abenchmarkforOWLknowledgebasesystems[J].WebSemantics:Science,ServicesandAgentsontheWorldWideWeb,2005,3(2-3):158-182.

AN APPROACH FOR IMPLEMENTING DISTRIBUTED SPARQL QUERY BASED ON DATA PARTITION

Du Fang

(School of Mathematics and Computer Science,Ningxia University,Yinchuan 750021,Ningxia,China)

When billions of RDF data are stored on distributed platform, the strategy of data partitioning is to directly affect the efficiency of massive data query. In order to improve the query efficiency on distributed platform, we proposed a distributed platform-based efficient data partitioning method. The method places data onto each node in computer cluster according to the feature of RDF data chart, and parses SPARQL query sentence on this basis to achieve efficient distributed query. The algorithm was implemented on cloud computing platform, and has been tested on real RDF dataset. Experimental results demonstrated that the method introduced in the paper achieved great improvement in query efficiency compared with benchmark method.

RDF dataSPARQL queryDistributed queryData partitioningData placementCloud computing platform

2015-04-22。国家自然科学基金项目(61363018)。杜方，副教授，主研领域：智能信息管理，数据库技术。

TP311

A

10.3969/j.issn.1000-386x.2016.10.006