SPARQL Query Optimization Based on Longest Property Path Filtering

doi:10.19678/j.issn.1000-3428.0048650

Computer Engineering ›› 2018, Vol. 44 ›› Issue (11): 7-13. doi: 10.19678/j.issn.1000-3428.0048650

Previous Articles Next Articles

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

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

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

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

作者简介:林晓庆(1979—),女,讲师、博士研究生,主研方向为RDF数据关键字查询;张富,副教授、博士;程经纬,讲师、博士。
基金资助:
国家自然科学基金(61672139);辽宁省自然科学基金(2015020048)

Abstract

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

摘要：

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

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

CLC Number:

TP311.13

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

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

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0048650

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

References

［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]	WU Weixin, HAN Jingyu, ZHU Man. RDF Grouping Compression Based on Delta Encoding [J]. Computer Engineering, 2020, 46(11): 117-123.
[2]	RAO Zhihong,LIU Jie,CHEN Jianfeng. Research on Massive Knowledge Storage for Network Monitoring and Early Warning [J]. Computer Engineering, 2018, 44(3): 138-143.
[3]	LI Guo-ding,FENG Zhi-yong,RAO Guo-zheng,WANG Xin. SPARQL Basic Graph Pattern Search Algorithm Based on Bulk Synchronous Parallel [J]. Computer Engineering, 2014, 40(9): 37-41.
[4]	HE Tian-zhong,ZHOU Zhong-mei,HUANG Zai-xiang. Classification Rules Learning Algorithm Based on Selectivity [J]. Computer Engineering, 2014, 40(8): 179-182,189.
[5]	LIU Jian-Meng, SHI Yi-Min, ZHANG Dun, CHEN Cun-Heng. A Method of Semantic Similarity Measure for RDF Graph [J]. Computer Engineering, 2013, 39(3): 223-228,235.
[6]	LV Yan-Hui. Conversion of RDF(S) Model to Relational Database Schema [J]. Computer Engineering, 2011, 37(9): 65-67.
[7]	ZHU Liang; FENG Yan-chao; LIU Chun-nian; YANG Wen-zhu. Histogram Based on Distribution Density and Selectivity Estimation [J]. Computer Engineering, 2010, 36(5): 64-66.
[8]	LI Xiao-ya; HUANG Dao-ping; WU Hong-yan. Selectivity of Single-hop or Multi-hop Routing for Wireless Sensor Network [J]. Computer Engineering, 2009, 35(3): 13-14,5.
[9]	WANG Jin-peng; ZHANG Ya-fei; MIAO Zhuang. RDF(S) Triple-level Inference Control Algorithm [J]. Computer Engineering, 2009, 35(19): 17-19.
[10]	GAO Yu; LIU Guo-hua. Selectivity Estimation of Characteristic Data Spatial Join [J]. Computer Engineering, 2008, 34(3): 105-107.
[11]	YUAN Jin-ping; BAO Ai-hua; YAO Li. Semantic Web Techniques and Its Logic Foundations [J]. Computer Engineering, 2008, 34(24): 194-196.
[12]	ZHEN Lu; JIANG Zuhua; LIU Chao; LIANG Jun. Research of Engineering Design Knowledge Representation on Semantic Web [J]. Computer Engineering, 2007, 33(12): 199-201.
[13]	LI Wei; CHEN Haopeng. Acquirement Software Requirements Based on OWL [J]. Computer Engineering, 2006, 32(21): 73-75.

Please choose a citation manager

Content to export

SPARQL Query Optimization Based on Longest Property Path Filtering

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

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 13

Recommended Articles

Metrics

Comments

模态框（Modal）标题

Please choose a citation manager

Content to export

SPARQL Query Optimization Based on Longest Property Path Filtering

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

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 13

Recommended Articles

Metrics

Comments