大规模RDF图数据上高效率分布式查询处理
作者:
作者单位:

作者简介:

王鑫(1981-),男,天津人,博士,副教授,CCF高级会员,主要研究领域为知识图谱数据管理,图数据库,大规模知识处理;徐强(1993-),女,硕士生,主要研究领域为知识图谱数据管理,图数据库;柴乐乐(1995-),女,硕士生,主要研究领域为知识图谱表示学习;杨雅君(1983-),男,博士,讲师,CCF专业会员,主要研究领域为图数据管理,图挖掘;柴云鹏(1983-),男,博士,副教授,博士生导师,CCF专业会员,主要研究领域为分布式系统,云计算,存储系统.

通讯作者:

杨雅君,E-mail:yjyang@tju.edu.cn

中图分类号:

基金项目:

国家自然科学基金(61572353,61402323,61472427);天津市自然科学基金(17JCYBJC15400);数字出版技术国家重点实验室开放课题;北京自然科学基金(4172031)


Efficient Distributed Query Processing on Large Scale RDF Graph Data
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61572353, 61402323, 61472427); Natural Science Foundation of Tianjin (17JCYBJC15400); Opening Project of State Key Laboratory of Digital Publishing Technology; Natural Science Foundation of Beijing (4172031)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    知识图谱是智能数据的主要表现形式,随着知识图谱领域的不断发展,大量的智能图数据以资源描述框架(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.

    参考文献
    相似文献
    引证文献
引用本文

王鑫,徐强,柴乐乐,杨雅君,柴云鹏.大规模RDF图数据上高效率分布式查询处理.软件学报,2019,30(3):498-514

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2018-07-20
  • 最后修改日期:2018-09-20
  • 录用日期:
  • 在线发布日期: 2019-03-06
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号