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

作　　者：Gang WU Meng-dong YANG 

机构地区：[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 andEngmeermg,Southeast University,Nanjing 210096,China

出　　处：《Journal of Zhejiang University-Science C(Computers and Electronics)》2012年第4期281-294,共14页浙江大学学报C辑（计算机与电子（英文版）

基　　金：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);the Key Laboratory of Advanced Information Science and Network Technology of Beijing (No.XDXX1011)

摘　　要：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.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 pos- sible reuse. Evaluation results on three mainstream RDF benchmarks illustrate the effectiveness and efficiency of our approaches. Comparisons with previous research are also provided.

关 键 词：SPARQL Resource Description Framework （RDF） Semantic caching Algebraic expression tree （AET） ENTITY 

分 类 号：TP392[自动化与计算机技术—计算机应用技术]