Improving SPARQL query performance with algebraic expression tree based caching and entity caching

Gang WU; Meng-dong YANG

doi:10.1631/jzus.C1101009

Your Location：

Home >

Browse articles >

Improving SPARQL query performance with algebraic expression tree based caching and entity caching

用于更智能网络的语义技术专辑 | Updated：2022-12-09

- Improving SPARQL query performance with algebraic expression tree based caching and entity caching
- Improving SPARQL query performance with algebraic expression tree based caching and entity caching
- 信息与电子工程前沿（英文） 2012年13卷第4期页码：281-294
- Affiliations：
  
  1.College of Information Science and Engineering, Northeastern University, Shenyang 110004, China
  2.MOE Key Laboratory of Medical Image Computing, Northeastern University, Shenyang 110004, China
  3.School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
- Author bio：
  
  [ "Gang WU, E-mail: wugang@ise.neu.edu.cn" ]
  [ "Meng-dong YANG, E-mail: mdyang@seu.edu.cn" ]
- Funds：
  
  Project supported by the National Natural Science Foundation of China (Nos. 60903010, 61025007, and 60933001), the National Basic Research Program (973) of China (No. 2011CB302206), the Natural Science Foundation of Jiangsu Province, China (No. BK2009268), the Fundamental Research Funds for the Central Universities (No. N110404013), and the Key Laboratory of Advanced Information Science and Network Technology of Beijing (No. XDXX1011)
- DOI：10.1631/jzus.C1101009
  中图分类号： TP392
- 收稿：2011-08-08，
  
  修回：2012-;2-17，
  
  纸质出版：2012-04
- Accepted：
Scan QR Code
Improving SPARQL query performance with algebraic expression tree based caching and entity caching[J]. 信息与电子工程前沿（英文）, 2012,13(4):281-294.

Gang WU, Meng-dong YANG. Improving SPARQL query performance with algebraic expression tree based caching and entity caching[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(4): 281-294.
Improving SPARQL query performance with algebraic expression tree based caching and entity caching[J]. 信息与电子工程前沿（英文）, 2012,13(4):281-294. DOI： 10.1631/jzus.C1101009.

Gang WU, Meng-dong YANG. Improving SPARQL query performance with algebraic expression tree based caching and entity caching[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(4): 281-294. DOI： 10.1631/jzus.C1101009.

摘要

Abstract

To obtain comparable high query performance with relational databases

diverse database technologies have to be adapted to confront the complexity posed by both Resource Description Framework (RDF) data and SPARQL query. Database caching is one of such technologies that improves the performance of database with reasonable space expense based on the spatial/ temporal/semantic locality principle. However

existing caching schemes exploited in RDF stores are found to be dysfunctional for complex query semantics. Although semantic caching approaches work effectively in this case

little work has been done in this area. In this paper

we try to improve SPARQL query performance with semantic caching approaches

i.e.

SPARQL algebraic expression tree (AET) based caching and entity caching. Successive queries with multiple identical sub-queries and star-shaped joins can be efficiently evaluated with these two approaches. The approaches are implemented on a two-level-storage structure. The main memory stores the most frequently accessed cache items

and items swapped out are stored on the disk for future possible reuse. Evaluation results on three mainstream RDF benchmarks illustrate the effectiveness and efficiency of our approaches. Comparisons with previous research are also provided.

关键词

Keywords

references

D.J. Abadi , , , A. Marcus , , , S. Madden , , , K.J. Hollenbach . . Scalable Semantic Web Data Management Using Vertical Partitioning . . 33rd Int. Conf. on Very Large Data Bases , , 2007 . . p.411 - - 422 . . . .

C. Bizer , , , A. Schultz . . The Berlin SPARQL Benchmark . . Int. J. Semant. Web Inform. Syst. , , 2009 . . 5 ( ( 2 ): ): 1 - - 24 . . DOI: 10.4018/jswis.2009040101 http://doi.org/10.4018/jswis.2009040101 . .

J. Broekstra , , , A. Kampman , , , F. van Harmelen . . Sesame: a generic architecture for storing and querying RDF and RDF schema . . LNCS , , 2002 . . 2342 54 - - 68 . . DOI: 10.1007/3-540-48005-6_7 http://doi.org/10.1007/3-540-48005-6_7 . .

R. Castillo , , , U. Leser , , , C. Rothe . . RDFMatView: Indexing RDF Data for SPARQL Queries . . Technical Report, Humboldt University, Berlin, Germany. , , 2010 . . .

L. Chen , , , E.A. Rundensteiner , , , S. Wang . . XCache: a Semantic Caching System for XML Queries . . ACM SIGMOD Int. Conf. on Management of Data , , 2002 . . p.618 DOI: 10.1145/564691.564771 http://doi.org/10.1145/564691.564771 . .

E.I. Chong , , , S. Das , , , G. Eadon , , , J. Srinivasan . . An Efficient SQL-Based RDF Querying Scheme . . 31st Int. Conf. on Very Large Data Bases , , 2005 . . p.1216 - - 1227 . . . .

S. Dar , , , M.J. Franklin , , , B.T. Jónsson , , , D. Srivastava , , , M. Tan . . Semantic Data Caching and Replacement . . 22nd Int. Conf. on Very Large Data Bases , , 1996 . . p.330 - - 341 . . . .

O. Erling , , , I. Mikhailov . . RDF Support in the Virtuoso DBMS . . First Conf. on Social Semantic Web , , 2007 . . p.59 - - 68 . . . .

Y. Guo , , , Z. Pan , , , J. Heflin . . LUBM: a benchmark for OWL knowledge base systems . . Web Semant. , , 2005 . . 3 ( ( 2-3 ): ): 158 - - 182 . . DOI: 10.1016/j.websem.2005.06.005 http://doi.org/10.1016/j.websem.2005.06.005 . .

A. Harth , , , J. Umbrich , , , A. Hogan , , , S. Decker . . YARS2: a federated repository for querying graph structured data from the Web . . LNCS , , 2007 . . 4825 211 - - 224 . . DOI: 10.1007/978-3-540-76298-0_16 http://doi.org/10.1007/978-3-540-76298-0_16 . .

G. Klyne , , , J.J. Carroll . . Resource Description Framework (RDF): Concepts and Abstract Syntax . . W3C Recommendation. Available from , , http://www.w3.org/TR/2004/REC-rdf-concepts-20040212/ http://www.w3.org/TR/2004/REC-rdf-concepts-20040212/ , , 2004 . . [Accessed on Jan. 16, 2012] . .

L. Li , , , B. Knig-Ries , , , N. Pissinou , , , K. Makki . . Strategies for Semantic Caching . . 12th Int. Conf. on Database and Expert Systems Applications , , 2001 . . p.284 - - 298 . . DOI: 10.1007/3-540-44759-8_29 http://doi.org/10.1007/3-540-44759-8_29 . .

M. Martin , , , J. Unbehauen , , , S. Auer . . Improving the performance of semantic Web applications with SPARQL query caching . . LNCS , , 2010 . . 6089 304 - - 318 . . DOI: 10.1007/978-3-642-13489-0_21 http://doi.org/10.1007/978-3-642-13489-0_21 . .

T. Neumann , , , G. Weikum . . RDF-3X: a risc-style engine for RDF . . Proc. VLDB Endow. , , 2008 . . 1 ( ( 1 ): ): 647 - - 659 . . . .

A. Owens , , , A. Seaborne , , , N. Gibbins , , , M. Schraefel . . Clustered TDB: a Clustered Triple Store for Jena . . Available from , , http://eprints.ecs.soton.ac.uk/16974/1/www2009fixedref.pdf http://eprints.ecs.soton.ac.uk/16974/1/www2009fixedref.pdf , , 2008 . . [Accessed on Jan. 16, 2012] . .

E. Prud′hommeaux , , , A. Seaborne . . SPARQL Query Language for RDF . . W3C Recommendation. Available from , , http://www.w3.org/TR/2008/REC-rdf-sparql-query-20080115/ http://www.w3.org/TR/2008/REC-rdf-sparql-query-20080115/ , , 2008 . . [Accessed on Jan. 16, 2012] . .

Q. Ren , , , M.H. Dunham , , , V. Kumar . . Semantic caching and query processing . . IEEE Trans. Knowl. Data Eng. , , 2003 . . 15 ( ( 1 ): ): 192 - - 210 . . DOI: 10.1109/TKDE.2003.1161590 http://doi.org/10.1109/TKDE.2003.1161590 . .

K.A. Ross . . Cache-Conscious Query Processing . . Encyclopedia of Database Systems , , 2009 . . p.301 - - 304 . . DOI: 10.1007/978-0-387-39940-9_2151 http://doi.org/10.1007/978-0-387-39940-9_2151 . .

S. Sakr , , , G. Al-Naymat . . Relational processing of RDF queries: a survey . . ACM SIGMOD Rec. , , 2010 . . 38 ( ( 4 ): ): 23 - - 28 . . DOI: 10.1145/1815948.1815953 http://doi.org/10.1145/1815948.1815953 . .

M. Schmidt , , , T. Hornung , , , G. Lausen , , , C. Pinkel . . SP 2 Bench: a SPARQL Performance Benchmark . . IEEE 25th Int. Conf. on Data Engineering , , 2008 . . p.222 - - 233 . . DOI: 10.1109/ICDE.2009.28 http://doi.org/10.1109/ICDE.2009.28 . .

Wikipedia . . Resource Description Framework . . Available from , , http://en.wikipedia.org/wiki/Resource_Description_Framework http://en.wikipedia.org/wiki/Resource_Description_Framework , , 2012 . . [Accessed on Jan. 16, 2012] . .

K. Wilkinson , , , C. Sayers , , , H.A. Kuno , , , D. Reynolds . . Efficient RDF Storage and Retrieval in Jena2 . . First Int. Workshop on Semantic Web and Databases , , 2003 . . p.131 - - 150 . . . .

R. Castillo , , , U. Leser , , , C. Rothe . . RDFMatView: Indexing RDF Data for SPARQL Queries . . Technical Report, Humboldt University. , , 2010 . . .

T. Neumann , , , G. Weikum . . RDF-3X: a RISC-style engine for RDF . . Proc. VLDB Endow. , , 2008 . . 1 ( ( 1 ): ): 647 - - 659 . . . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据