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

Special Issue on Semantic Technologies for a Smarter Web | 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
- Frontiers of Information Technology & Electronic Engineering Vol. 13, Issue 4, Pages: 281-294(2012)
- 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：
- DOI：10.1631/jzus.C1101009
  CLC： TP392
- Received：08 August 2011，
  
  Revised：2012-;2-17，
  
  Published：2012-04
- Accepted：
Scan QR Code
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：

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 . . . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰