摘要:知识图谱是智能数据的主要表现形式，随着知识图谱领域的不断发展，大量的智能图数据以资源描述框架（resource description framework，简称RDF）形式发布出来.RDF图上的SPARQL查询语义对应于图同态，是一个NP-完全问题.因此，如何使用分布式方法在大规模RDF图上有效回答SPARQL查询是一个富有挑战性的问题.目前已有研究使用MapReduce计算模型处理大规模RDF数据，但其将SPARQL查询拆分成单个的查询子句，没有考虑RDF数据的丰富语义和自身的图特性，导致MapReduce迭代次数过多.首先，利用RDF数据内嵌的语义和结构信息作为启发式信息，将查询图分解为星形的集合，可以在更少次迭代内得到查询结果.同时，分解算法给出中间结果较少的星形匹配顺序，基于此顺序，每轮MapReduce操作通过连接操作匹配一个新的星形，直至产生最终的答案.最后，在标准合成数据集WatDiv和真实数据集DBpedia上进行大量的实验评估.实验结果表明：所提基于星形分解的分布式SPARQL BGP匹配算法能够高效回答查询，查询时间比SHARD和S2X算法的查询时间平均提高一个数量级，且优化算法的查询时间与基本算法相比缩短了49.63%~78.71%.



Abstract:Knowledge graphs are the main representation form of intelligent data. With the development of knowledge graphs, more and more intelligent data has been released in the form of the resource description framework (RDF). It is known that the semantics of SPARQL correspond to graph homomorphism which is an NP-complete problem. Therefore, how to efficiently answer SPARQL queries in parallel over big RDF graphs has been widely recognized as a challenging problem. There are some research works using the MapReduce computational model to process big RDF graph. However, SPARQL queries in these works are decomposed into the set of query clauses without considering any semantics and graph structure embedded in RDF graph, which leads to overmuch MapReduce iterations. This study first decomposes the SPARQL query graph into a set of stars by utilizing the semantic and structural information embedded RDF graphs as heuristics, which can be matched in fewer MapReduce iterations. Meanwhile, a matching order of these stars is given to reduce intermediate results in MapReduce iterations. During the matching phase, each round of MapReduce adds one star with the join operation. The extensive experiments on both synthetic dataset WatDiv, and real-world dataset DBpedia are carried out. The experiments results demonstrate that the proposed star decomposition-based method can answer SPARQL BGP queries efficiently, which outperforms SHARD and S2X by one order of magnitude. Finally, extensive experiments show that the performance of the optimization algorithms is improved by 49.63% and 78.71% than the basic algorithm over both synthetic and real datasets.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/5696