PDF《大规模 RDF 图数据上高效率分布式查询处理》

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.

ac.cn Journal of Software,2019,30(3):498?514 [doi: 10.13328/j.cnki.jos.005696] http://www.jos.org.cn ?中国科学院软件研究所版权所有. Tel: +86-10-62562563 大规模 RDF 图数据上高效率分布式查询处理 ? 王鑫1,2 , 徐强1,2 , 柴乐乐 1,2 , 杨雅君 1,2,4 , 柴云鹏

3 1 (天津大学 智能与计算学部,天津 300354)

2 (天津市认知计算与应用重点实验室,天津 300354)

3 (中国人民大学 信息学院,北京 100872)

4 (数字出版技术国家重点实验室,北京 100871) 通讯作者: 杨雅君, E-mail: [email protected] 摘要: 知识图谱是智能数据的主要表现形式,随着知识图谱领域的不断发展,大量的智能图数据以资源描述框 架(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%. 关键词: 星形分解;

分布式;

基本图模式匹配;

大规模 RDF 图;

MapReduce 中图法分类号: TP311 中文引用格式: 王鑫,徐强,柴乐乐,杨雅君,柴云鹏.大规模 RDF 图数据上高效率分布式查询处理.软件学报,2019,30(3): 498?514. http://www.jos.org.cn/1000-9825/5696.htm 英文引用格式: Wang X, Xu Q, Chai LL, Yang YJ, Chai YP. Efficient distributed query processing on large scale RDF graph data. Ruan Jian Xue Bao/Journal of Software, 2019,30(3):498?514 (in Chinese). http://www.jos.org.cn/1000-9825/5696.htm Efficient Distributed Query Processing on Large Scale RDF Graph Data WANG Xin1,2 , XU Qiang1,2 , CHAI Le-Le1,2 , YANG Ya-Jun1,2,4 , CHAI Yun-Peng3

1 (College of Intelligence and Computing, Tianjin University, Tianjin 300354, China)

2 (Tianjin Key Laboratory of Cognitive Computing and Application, Tianjin 300354, China)

3 (School of Information, Renmin University of China, Beijing 100872, China)

4 (State Key Laboratory of Digital Publishing Technology, Beijing 100871, China) ? 基金项目: 国家自然科学基金(61572353, 61402323, 61472427);

天津市自然科学基金(17JCYBJC15400);

数字出版技术国家 重点实验室开放课题;

北京自然科学基金(4172031) Foundation item: 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) 本文由智能数据管理与分析技术专刊特约编辑樊文飞教授、王国仁教授、王朝坤副教授推荐. 收稿时间: 2018-07-20;