›› 2010, Vol. 25 ›› Issue (2): 347-361.

• Distributed Computing and Systems • Previous Articles     Next Articles

An Effective Semantic Cache for Exploiting XPath Query/View Answerability

Guo-Liang Li (李国良), Member, CCF, ACM, and Jian-Hua Feng (冯建华), Senior Member, CCF, Member, ACM, IEEE   

  1. Department of Computer Science and Technology, Tsinghua National Laboratory for Information Science and Technology, Tsinghua University, Beijing 100084, China
  • Received:2008-04-02 Revised:2009-10-09 Online:2010-03-05 Published:2010-03-05
  • About author:
    Guo-Liang Li received his B.S. degree from the Department of Computer Science and Technology, Harbin Institute of Technology (HIT), and M.S. and Ph.D. degrees from Department of Computer science and technology, Tsinghua University, where he is currently working as a fa-culty member. He is a member of China Computer Federation (CCF). His research interests are in the fields of database indexing, data integration, and data cleaning. He has published papers in the top international conferences, such as ACM SIGMOD, ACM SIGIR, VLDB, IEEE ICDE, WWW, ACM CIKM, IEEE ICDM, and top international journals, such as DMKD, Information System.

    Jian-Hua Feng received his B.S., M.S. and Ph.D. degrees in computer science and technology from Tsinghua University. He is currently working as a faculty of Department Computer Science and Technology in Tsinghua University. He is a senior member of CCF. His main research interests are in native XML database, keyword search and data mining. He has published papers in the international top journals and conferences, such as DMKD, Information Systems|ACM SIGMOD, ACM SIGKDD, VLDB, IEEE ICDE, ACM SIGIR, WWW, ACM CIKM, IEEE ICDM, SDM, ER.
  • Supported by:

    This work is partly supported by the National Natural Science Foundation of China under Grant No. 60873065, the National High Technology Research and Development 863 Program of China under Grant Nos. 2007AA01Z152 and 2009AA011906, and the National Basic Research 973 Program of China under Grant No. 2006CB303103.

Maintaining a semantic cache of materialized XPath views inside or outside the database is a novel, feasible and efficient approach to facilitating XML query processing. However, most of the existing approaches incur the following disadvantages: 1) they cannot discover enough potential cached views sufficiently to effectively answer subsequent queries; or 2) they are inefficient for view selection due to the complexity of XPath expressions. In this paper, we propose SCEND, an effective Semantic Cache based on dEcompositioN and Divisibility, to exploit the XPath query/view answerability. The contributions of this paper include: 1) a novel technique of decomposing complex XPath queries into some much simpler ones, which can facilitate discovering more potential views to answer a new query than the existing methods and thus can adequately exploit the query/view answerability; 2) an efficient view-section method by checking the divisibility between two positive numbers assigned to queries and views; 3) a cache-replacement approach to further enhancing the query/view answerability; 4) an extensive experimental study which demonstrates that our approach achieves higher performance and outperforms the existing state-of-the-art alternative methods significantly.

[1] Dar S, Franklin M J, J′onsson B T, Srivastava D, Tan M. Semantic data caching and replacement. In Proc. VLDB1996, Mumbai (Bombay), India, September 3-6, 1996, pp.330-341.

[2] Mandhani B, Suciu D. Query caching and view selection for XML databases. In Proc. VLDB 2005, Trondheim, Norway, August 30-September 2, 2005, pp.469-480.

[3] Feng J H, Li G L, Ta N. A semantic cache framework for secure XML queries. J. Comput. Sci. & Technol., 2008, 23(6): 988-997.

[4] Luo Q, Krishnamurthy S, Mohan C, Pirahesh H, Woo H, Lindsay B G, Naughton J F. Middle-tier database caching for e-business. In Proc. ACM SIGMOD Int. Conf. Management of Data, Madison, USA, June 3-6, 2002, pp.600-611.

[5] Re C, Brinkley J, Hinshaw K, Suciu D. Distributed XQuery. In Proc. Information Integration on the Web (IIWeb), VLDB Workshop, Toronto, Canada, Aug. 30, 2004, pp.116-121,

[6] Chandra A K, Merlin P M. Optimal implementation of conjunctive queries in relational data bases. In Proc. STOC, May 2-4, 1977, Boulder, Colorado, USA, pp.77-90.

[7] Miklau G, Suciu D. Containment and equivalence for a fragment of XPath. J. ACM, 2004, 51(1): 2-45.

[8] Milo T, Suciu D. Index structures for path expressions. In Proc. ICDT, Jerusalem, Israel, January 10-12, 1999, pp.277295.

[9] Wu X, Lee M L, Hsu W. A prime number labeling scheme for dynamic ordered XML trees. In Proc. ICDE, Boston, USA, March 30-April 2, 2004, pp.66-78.

[10] Miklau G, Suciu D. Containment and equivalence for an XPath fragment. In Proc. PODS, Madison, USA, June 35, 2002, pp.65-76.

[11] Li G, Feng J, Zhang Y, Zhou L. Efficient holistic twig joins in leaf-to-root combining with root-to-leaf way. In Proc. DASFAA, Bangkok, Thailand, April 9-12, 2007, pp.834-849.

[12] Bruno N, Koudas N, Srivastava D. Holistic twig joins: Optimal XML pattern matching. In Proc. ACM SIGMOD Int. Conf. Management of Data, Madison, Wisconsin, June 3-6, 2002, pp.310-321.

[13] Li G, Feng J, Wang J, Zhang Y, Zhou L. Incremental mining of frequent query patterns from XML queries for caching. In Proc. ICDM, December 18-22, 2006, Hong Kong, China, pp.350-361.

[14] http://dblp.uni-trier.de/xml/.

[15] http://www.cs.washington.edu/research/.

[16] http://www.xml-benchmark.org/.

[17] Al-Khalifa S, Jagadish H V, Patel J M, Wu Y, Koudas N, Srivastava D. Structural joins: A primitive for efficient XML query pattern matching. In Proc. ICDE 2002, February 26March 1, 2002, San Jose, USA, pp.141-152.

[18] Chen T, Lu J, Ling T W. On boosting holism in XML twig pattern matching using structural indexing techniques. In Proc. ACM SIGMOD Int. Conf. Management of Data, Baltimore, USA, June 14-16, 2005, pp.455-466.

[19] Lu J, Ling T W, Chan C Y, Chen T. From region encoding to extended dewey: On efficient processing of XML twig pattern matching. In Proc. VLDB, Trondheim, Norway, August 30-September 2, 2005, pp.193-204.

[20] Yang L H, Lee M L, Hsu W. Efficient mining of XML query patterns for caching. In Proc. VLDB, Berlin, Germany, September 9-12, 2003, pp.69-80.

[21] Balmin A, ¨Ozcan F, Beyer K S, Cochrane R, Pirahesh H. A framework for using materialized XPath views in XML query processing. In Proc. VLDB 2004, Toronto, Canada, August 31-September 3, 2004, pp.60-71.

[22] Li G, Feng J, Ta N, Zhang Y, Zhou L. SCEND: An efficient semantic cache to adequately explore answerability of views. In Proc. WISE 2006, Wuhan, China, October 23-26, 2006, pp.460-473.

[23] Feng J, Ta N, Zhang Y, Li G. Exploit sequencing views in semantic cache to accelerate XPath query evaluation. In Proc. WWW 2007, Banff, Canada, May 8-12, 2007, pp.1337-1338.

[24] Chen L, Rundensteiner E A, Wang S. XCache: A semantic caching system for XML queries. In Proc. ACM SIGMOD Int. Conf. Management of Data, Madison, USA, June 3-6, 2002, p.618.

[25] Hristidis V, Petropoulos M. Semantic caching of XML databases. In Proc. ACM SIGMOD Int. Conf. Management of Data, Madison, USA, June 3-6, 2002, pp.25-30.

[26] Xu W. The framework of an XML semantic aching system. In Proc. ACM SIGMOD Int. Conf. Management of Data, Baltimore, USA, June 13-16, 2005, pp.127-132.

[27] Yagoub K, Florescu D, Issarny V, Valduriez P. Caching strategies for data-intensive Web sites. In Proc. VLDB 2000, September 10-14, 2000, Cairo, Egypt, pp.188-199.

[28] Chen L, Rundensteiner E A. XCache: XQuery-based Caching System. In Proc. Int. Workshop on the Web and Databases, Madison, Wisconsin, June 3-6, 2002, pp.31-36.

[29] Yang L H, Li M L, Hsu W, Acharya S. Mining frequent quer patterns from XML queries. In Proc. DASFAA 2003, March 26-28, Kyoto, Japan, 2003, pp.355-362.

[30] Chen Y, Yang L H, Wang Y G. Incremental mining of frequent XML query pattern. In Proc. ICDM 2004, November 1-4, 2004, Brighton, UK, pp.343-346.

No related articles found!
Full text



No Suggested Reading articles found!

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved