[1] Zhu Yanqin, Hua Ling,. Optimization of RDF link traversal based query execution [J]. Journal of Southeast University (English Edition), 2013, 29 (1): 27-32. [doi:10.3969/j.issn.1003-7985.2013.01.006]

Copy

Optimization of RDF link traversal based query execution()

基于RDF链接遍历查询方案的优化

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

29

Issue:

2013 1

Page:

27-32

Research Field:

Computer Science and Engineering

Publishing date:

2013-03-20

Info

Title:

Optimization of RDF link traversal based query execution

基于RDF链接遍历查询方案的优化

Author(s):

Zhu Yanqin;  Hua Ling

School of Computer Science and Technology, Soochow University, Suzhou 215006, China

朱艳琴;  花岭

苏州大学计算机科学与技术学院, 苏州 215006

Keywords:

web of linked data;  resource description framework link traversal based query execution(RDF-LTE);  SPARQL query;  query optimization

互联数据Web;  RDF-LTE;  SPARQL查询;  查询优化

PACS:

TP391

DOI:

10.3969/j.issn.1003-7985.2013.01.006

Abstract:

Aiming at the problem that only some types of SPARQL(simple protocal and resource description framework query language)queries can be answered by using the current resource description framework link traversal based query execution(RDF-LTE)approach, this paper discusses how the execution order of the triple pattern affects the query results and cost based on concrete SPARQL queries, and analyzes two properties of the web of linked data, missing backward links and missing contingency solution. Then three heuristic principles for logic query plan optimization, namely, the filtered basic graph pattern(FBGP)principle, the triple pattern chain principle and the seed URIs principle, are proposed. The three principles contribute to decrease the intermediate solutions and increase the types of queries that can be answered. The effectiveness and feasibility of the proposed approach is evaluated. The experimental results show that more query results can be returned with less cost, thus enabling users to develop the full potential of the web of linked data.

针对采用现有的RDF链接遍历查询执行方案只能回答部分类型SPARQL查询的问题, 结合具体的SPARQL查询, 讨论了元组模式执行顺序对查询结果及查询代价的影响, 分析了互联数据Web的2个问题:缺乏反向链接性与不支持偶然发现的解.然后, 提出了3个启发式的逻辑查询计划优化原则:FBGP原则、元组模式链原则和种子URIs原则.这3个原则有助于减少中间解和增加可回答的查询类型数目.并通过实验证明了其有效性和可行性.实验结果表明, 优化后的方案能够以较小的代价得到更多的查询结果, 从而有助于用户更好地发挥互联数据Web的潜能.

References:

[1] Berners-Lee T. Linked data[EB/OL].(2006-06-18)[2012-09-20]. http://www.w3.org/DesignIssues/LinkedData.html.
[2] Hartig O, Langegger A. A database perspective on consuming linked data on the web[J]. Datenbank-Spektrum, 2010, 10(2):57-66.
[3] Oren E, Delbru R, Catasta M, et al. Sindice.com: a document-oriented index for open linked data[J]. International Journal of Metadata Semantics and Ontologies, 2008, 3(1):27-52.
[4] Cheng G, Qu Y. Searching linked objects with falcons: approach, implementation and evaluation[J]. International Journal on Semantic Web and Information Systems, 2009, 5(3):49-70.
[5] Sheth A P, Larson J A. Federated database systems for managing distributed, heterogeneous, and autonomous databases[J]. ACM Computing Surveys, 1990, 22(3):183-236.
[6] Quilitz B, Leser U. Querying distributed RDF data sources with SPARQL[C]//Proceedings of the 5th European Semantic Web Conference on the Semantic Web. Canary Islands, Spain, 2008:524-538.
[7] Hartig O, Bizer C, Freytag J C. Executing SPARQL queries over the web of linked data[C]//Proceedings of the 8th International Semantic Web Conference. Washington DC, USA, 2009:293-309.
[8] Klyne G, Garroll J J. Resource description framework(RDF): concepts and abstract syntax[EB/OL].(2004-02-10)[2012-09-20]. http://www.w3.org/TR/rdf-concepts/.
[9] Stuckenschmidt H, Vdovjak R, Houben G-J. Index structures and algorithms for querying distributed RDF repositories[C]//Proceedings of the 13th International Conference on World Wide Web. New York, USA, 2004: 631-639.
[10] Lampo T, Vidal M E, Danilow J, et al. To cache or not to cache: the effects of warming cache in complex SPARQL queries[C]// Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2011:716-733.

Memo

Memo:

Biography: Zhu Yanqin(1964—), female, doctor, professor, yqzhu@suda.edu.cn.
Foundation items: The National Natural Science Foundation of China(No.61070170), the Natural Science Foundation of Higher Education Institutions of Jiangsu Province(No.11KJB520017), Suzhou Application Foundation Research Project(No.SYG201238).
Citation: Zhu Yanqin, Hua Ling. Optimization of RDF link traversal based query execution[J].Journal of Southeast University(English Edition), 2013, 29(1):27-32.[doi:10.3969/j.issn.1003-7985.2013.01.006]

Common functions