Skip to main content
SpringerLink
Log in

Semantic cache replacement strategy for XML algebra-based query optimization

  • Computer Science
  • Published:
Wuhan University Journal of Natural Sciences

Abstract

Aiming at the fact that traditional cache replacement strategy lacks pertinence to the semantic cache in the process of extensible markup language (XML) algebra query, a replacement strategy based on the semantic cache contribution value is proposed. First, pattern matching rules for XML algebra query and semantic caches are given. Second, the method of calculating the semantic cache contribution value is proposed. In XML documents with four different sizes, the experimental results of time efficiency show that this strategy supports environment of the XML algebra query and it has better time efficiency than both least frequency used (LFU) and least recently used (LRU).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Deutsch A, Popa L, Tannen V. Physical data independence, constraints, and optimization with universal plans[C]// Proc 25th International Conference on Very Large Data Bases (VLDB). San Francisco: Morgan Kaufmann Press, 1999: 459–470.

    Google Scholar 

  2. Zhang Q Y, Wang M. An optimization method based on XML query algebra[C]// Proceedings of 2010 International Conference on Broadcast Technology and Multimedia Communication. Berlin, Heidelberg: Springer-Verlag, 2012: 199–206.

    Google Scholar 

  3. Liu X P, Chen L, Wan C, et al. Exploiting structures in keyword queries for effective XML search [J]. Information Sciences, 2013, 240(48): 56–71.

    Article  Google Scholar 

  4. Zhou H J, Yang J M. A query cache replacement scheme based on semantic comparability metric in ORM [J]. Journal of Hunan University (Natural Sciences), 2009, 36(11): 371–382(Ch).

    Google Scholar 

  5. Wu X, Theodoratos D, Wang W H, et al. Optimizing XML queries: Bitmapped materialized views vs. indexes [J]. Information System, 2013, 38(6): 863–884.

    Article  Google Scholar 

  6. Jagadish H V, Lakshmanan L V S, Srivastava D, et al. TAX: A tree algebra for XML[C]// Proc 8th International Workshop on Database Programming Language, LNCS 2397. Berlin: Springer-Verlag, 2001: 149–164.

    Google Scholar 

  7. Chien S Y, Vagena Z, Zhang D, et al. Evolution of cache replacement policies to track heavy-hitter flows[C]// Proceedings of 12th International Conference on Passive and Active Measurement Conference (PAM). Berlin: Springer-Verlag, 2011: 21–31.

    Google Scholar 

  8. Wu T, Zhang W, Zhou X, et al. LWI replacement policy for client semantic cache [J]. Journal of Computer Research and Development, 2003, 40(8): 1223–1229(Ch).

    Google Scholar 

  9. Basu J. Associative Caching in Client-Server Databases[D]. Stanford: Stanford University, 1998.

    Google Scholar 

  10. Chen L, Wang S, Rundensteiner E A. Replacement strategies for XQuery caching systems [J]. Data and Knowledge Engineering, 2004, 49(2): 145–175.

    Article  Google Scholar 

  11. O’Neil E J, O’Neil P E, Weikum G. The LRU-K Page replacement algorithm for database disk buffering[C]//Proc ACM SIGMOD International Conference on Management of Data. Washington D C: ACM Press, 1993: 297–306.

    Google Scholar 

  12. Bilardi G, Ekanadham K, Pattnaik P. Efficient stack distance computation for a class of priority replacement policies [J]. International Journal of Parallel Programming, 2013, 41(3):430–468.

    Article  Google Scholar 

  13. Dar S, Franklin M J, Jónsson B, et al. Semantic data caching and replacement[C]//Proc 22th International Conference on Very Large Data Bases (VLDB). San Francisco: Morgan Kaufmann Press, 1996: 330–341.

    Google Scholar 

  14. Jagadish H V, Al-Khalifa S, Chapman A, et al. Timber: A native XML database [J]. The VLDB Journal, 2002, 11: 274–291.

    Article  Google Scholar 

  15. Hamid A, Khan S. Optimization of semantic caching for XML database[C]// Proc 1st International Conference on Information and Communication Technologies. Piscataway N J: IEEE Press, 2005: 201–205.

    Google Scholar 

  16. Ren Q, Dunham M H. Semantic caching and query processing [J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(1): 192–210.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan, 430065, Hubei, China

    Fangfang Xu, Yaoyao Li & Jinguang Gu

  2. Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System, Wuhan, 430065, Hubei, China

    Fangfang Xu, Yaoyao Li & Jinguang Gu

Authors
  1. Fangfang Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yaoyao Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jinguang Gu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jinguang Gu.

Additional information

Foundation item: Supported by the National Natural Science Foundation of China(60803160 and 61272110), the Key Projects of National Social Science Foundation of China(11&ZD189), the Natural Science Foundation of Hubei Province(2013CFB334), the Natural Science Foundation of Educational Agency of Hubei Province(Q20101110), the State Key Lab of Software Engineering Open Foundation of Wuhan University(SKLSE2012-09-07) and the Wuhan Key Technology Support Program(2013010602010216)

Biography: XU Fangfang, female, Master candidate, research direction: semantic Web.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xu, F., Li, Y. & Gu, J. Semantic cache replacement strategy for XML algebra-based query optimization. Wuhan Univ. J. Nat. Sci. 20, 165–172 (2015). https://doi.org/10.1007/s11859-015-1076-y

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11859-015-1076-y

Keywords

CLC number

Search

Navigation