基于最长属性路径过滤的SPARQL查询优化

doi:10.19678/j.issn.1000-3428.0048650

计算机工程 ›› 2018, Vol. 44 ›› Issue (11): 7-13. doi: 10.19678/j.issn.1000-3428.0048650

基于最长属性路径过滤的SPARQL查询优化

林晓庆^1,2,张富¹,程经纬¹

1.东北大学计算机科学与工程学院,沈阳 110819; 2.辽东学院信息工程学院,辽宁丹东 118003

收稿日期:2017-09-14 出版日期:2018-11-15 发布日期:2018-11-15
作者简介:林晓庆(1979—),女,讲师、博士研究生,主研方向为RDF数据关键字查询;张富,副教授、博士;程经纬,讲师、博士。
基金资助:
国家自然科学基金(61672139);辽宁省自然科学基金(2015020048)

SPARQL Query Optimization Based on Longest Property Path Filtering

LIN Xiaoqing^1,2,ZHANG Fu¹,CHENG Jingwei¹

1.School of Computer Science and Engineering,Northeastern University,Shenyang 110819,China; 2.School of Information Engineering,Eastern Liaoning University,Dandong,Liaoning 118003,China

Received:2017-09-14 Online:2018-11-15 Published:2018-11-15

摘要/Abstract

摘要：

SPARQL查询过程中产生的大量中间结果严重影响查询效率。针对该问题,提出一种两阶段的查询优化方法。在第一阶段,将查询内含有相同变量的联结划分为一块,通过计算每块内的选择度重新排列联结。在第二阶段,利用属性路径索引对剩余的联结进行中间结果过滤。实验结果表明,该方法能够有效减少查询的中间结果,提高查询的执行效率。

关键词: 资源描述框架, SPARQL查询, 选择度, 属性路径, 三元组过滤, 中间结果

Abstract:

A large number of intermediate results during executing SPARQL query greatly affect the query efficiency.For this,a query optimization method with two phases is proposed.In the first phase,it divides a query that contains the same variable into a block by calculating the selectivity within each block to rearrange the join.In the second phase,it emploies the longest property path index to filter intermediate results.Experimental results show that the proposed method can effectively reduce the number of intermediate results and improve the query performance.

Key words: Resource Description Framework(RDF), SPARQL query, selectivity, property path, triple filtering, intermediate result

中图分类号:

TP311.13

林晓庆,张富,程经纬. 基于最长属性路径过滤的SPARQL查询优化[J]. 计算机工程, 2018, 44(11): 7-13.

LIN Xiaoqing,ZHANG Fu,CHENG Jingwei. SPARQL Query Optimization Based on Longest Property Path Filtering[J]. Computer Engineering, 2018, 44(11): 7-13.

http://www.ecice06.com/CN/Y2018/V44/I11/7

参考文献

［1］WILKINSON K,SAYERS C,KUNO H A,et al.Efficient RDF storage and retrieval in Jena2［C］//Proceedings of SWDB’03.Berlin,Germany:［s.n.］,2003:131-150.
［2］BROEKSTRA J,KAMPMAN A,HARMELEN F.Sesame:a generic architecture for storing and querying RDF and RDF schema ［C］//Proceedings of ISWC’02.Washington D.C.,USA:IEEE Press,2002:54-68.
［3］ABADI D J,MARCUS A,MADDEN S R,et al.SW-store:a vertically partitioned DBMS for semantic Web data management［J］.VLDB Journal,2009,18(2):385-406.
［4］NEUMANN T,WEIKUM G.The RDF-3X engine for scalable management of RDF data［J］.VLDB Journal,2010,19(1):91-113.
［5］WEISS C,KARRAS P,BERNSTEIN A.Hexastore:sextuple indexing for semantic Web data management［J］.Proceedings of the VLDB Endowment,2008,1(1):1008-1019.
［6］ZOU L,MO J,CHEN L,et al.gStore:answering SPARQL queries via subgraph matching［J］.Proceedings of the VLDB Endowment,2011,4(8):482-493.
［7］KIM K,MOON B,KIM H J.R3F:RDF triple filtering method for efficient SPARQL query processing［J］.World Wide Web,2015,18(2):317-357.
［8］YUAN P,XIE C,JIN H,et al.Dynamic and fast processing of queries on large-scale RDF data［J］.Knowledge and Information Systems,2014,41(2):311-334.
［9］AHN J,EOM J H,NAM S,et al.xStore:Federated temporal query processing for large scale RDF triples on a cloud environment［J］.Neurocomputing,2017,256:5-12.
［10］PENG P,ZOU L,ZSU M T,et al.Processing SPARQL queries over distributed RDF graphs［J］.VLDB Journal,2014,25(2):243-268.
［11］AHN J,IM D H,KIM H G.SigMR:MapReduce-based SPARQL query processing by signature encoding and multi-way join［J］.Journal of Supercomputing,2015,71(10):3695-3725.
［12］YUAN P,LIU P,WU B,et al.TripleBit:a fast and compact system for large scale RDF data［J］.Proceedings of the VLDB Endowment,2013,6(7):517-528.
［13］KIM K,MOON B,KIM H J.RG-index:an RDF graph index for efficient SPARQL query processing［J］.Expert Systems with Applications,2014,41(10):4596-4607.
［14］董书暕,汪璟玢.HMSST:一种高效的SPARQL查询优化算法［J］.计算机科学,2014,41(s2):323-326.
［15］SPARQL 1.1 query language［EB/OL］.［2017-09-21］. http://www.w3.org/TR/sparql11-query/.
［16］THANH T,WANG H,RUDOLPH S,et al.Top-k exploration of query candidates for efficient keyword search on graphshaped(RDF) data［C］//Proceedings of IEEE International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2009:405-416.
［17］SCHMIDT M,HORNUNG T,LAUSEN G,et al.SP2Bench:a SPARQL performance benchmark［C］//Proceedings of the 25th International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2009:371-393.
［18］MORSEY M,LEHMANN J,AUER S,et al.DBpedia SPARQL benchmark performance assessment with real queries on real data［C］//Proceedings of the 10th International Semantic Web Conference.Koblenz,Germany:［s.n.］,2011:454-469.

[1]	伍伟鑫, 韩京宇, 朱曼. 基于差分编码的RDF分组压缩[J]. 计算机工程, 2020, 46(11): 117-123.
[2]	饶志宏,刘杰,陈剑锋. 面向网络监测预警的海量知识存储研究[J]. 计算机工程, 2018, 44(3): 138-143.
[3]	李国鼎,冯志勇,饶国政,王鑫. 基于BSP 的SPARQL 基本图模式查询算法[J]. 计算机工程, 2014, 40(9): 37-41.
[4]	何田中,周忠眉,黄再祥. 基于选择度的分类规则学习算法[J]. 计算机工程, 2014, 40(8): 179-182,189.
[5]	刘建明, 史一民, 张俊, 陈存衡. 一种RDF图的语义相似性度量方法[J]. 计算机工程, 2013, 39(3): 223-228,235.
[6]	吕艳辉. RDF(S)模型到关系数据库模式的转换[J]. 计算机工程, 2011, 37(9): 65-67.
[7]	王进鹏;张亚非;苗壮. RDF(S)三元组的推理控制算法[J]. 计算机工程, 2009, 35(19): 17-19.
[8]	袁金平;鲍爱华;姚莉. 语义Web技术及其逻辑基础[J]. 计算机工程, 2008, 34(24): 194-196.
[9]	查琦;郑诚;陈涛;. 基于RDFS的数据结构描述[J]. 计算机工程, 2008, 34(24): 77-78.
[10]	镇璐;蒋祖华;刘超;梁军. 语义Web中工程设计类知识表示研究[J]. 计算机工程, 2007, 33(12): 199-201.
[11]	李伟;陈昊鹏. 基于OWL的软件需求获取[J]. 计算机工程, 2006, 32(21): 73-75.

选择文件类型/文献管理软件名称

选择包含的内容

基于最长属性路径过滤的SPARQL查询优化

SPARQL Query Optimization Based on Longest Property Path Filtering

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于最长属性路径过滤的SPARQL查询优化

SPARQL Query Optimization Based on Longest Property Path Filtering

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

本文评价