XQuery containment in presence of variable binding dependencies

ABSTRACT

Semantic caching is an important technology for improving the response time of future user queries specified over remote servers. This paper deals with the fundamental query containment problem in an XQuery-based semantic caching system. To our best knowledge, the impact of subtle differences in XQuery semantics caused by different ways of specifying variables on query containment has not yet been studied. We introduce the concept of variable binding dependencies for representing the hierarchical element dependencies preserved by an XQuery. We analyze the problem of XQuery containment in the presence of such dependencies. We propose a containment mapping technique for nested XQuery in presence of variable binding dependencies. The implication of the nested block structure on XQuery containment is also considered. We mention the performance gains achieved by a semantic caching system we build based on the proposed technique.

REFERENCES

• 1: A. Deutsch and V. Tannen. Containment of Regular Path Expressions under Integrity Constraints. In KRDB, Rome, Italy, pages 1--11, June 2001.
• 2: Marcelo Arenas , Leonid Libkin, An information-theoretic approach to normal forms for relational and XML data, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.15-26, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773155]
• 3: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, Rewriting of regular expressions and regular path queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.194-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303996]
• 4: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 5: L. Chen. A Semantic Caching System for XML Queries. Dissertation, WPI, 2003.
• 6: L. Chen and E. A. Rundensteiner. ACE-XQ: A CachE-aware XQuery Answering System. In WebDB, pages 31--36, June 2002.
• 7: Li Chen , Elke A. Rundensteiner , Song Wang, XCache: a semantic caching system for XML queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564771]
• 8: Li Chen , Song Wang , Elke A. Rundensteiner, Replacement strategies for XQuery caching systems, Data & Knowledge Engineering, v.49 n.2, p.145-175, May 2004 [doi>10.1016/j.datak.2003.10.002]
• 9: A. Deutsch, Y. Papakonstantinou, and Y. Xu. The NEXT Logical Framework for XQuery. In VLDB, Toronto, Canada, pages 168--179, 2004.
• 10: X. Dong, A. Halevy, and I. Tatarinov. Containment of nested xml queries. In VLDB, Toronto, Canada, pages 132--143, 2004.
• 11: Wenfei Fan , Jérôme Siméon, Integrity constraints for XML, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.23-34, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335172]
• 12: Frank Neven , Thomas Schwentick, XPath Containment in the Presence of Disjunction, DTDs, and Variables, Proceedings of the 9th International Conference on Database Theory, p.315-329, January 08-10, 2003
• 13: Gerome Miklau , Dan Suciu, Containment and equivalence for an XPath fragment, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543623]
• 14: IPSI-XQ. http://ipsi.fhg.de/oasys/projects/ipsi-xq/index_e.html.
• 15: D. Lee and W. W. Chu. Constraints-Preserving Transformation from XML Document Type Definition to Relational Schema. In ER, Salt Lake City, Utah, pages 323--338, 2000.
• 16: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 17: Ioana Manolescu , Daniela Florescu , Donald Kossmann, Answering XML Queries on Heterogeneous Data Sources, Proceedings of the 27th International Conference on Very Large Data Bases, p.241-250, September 11-14, 2001
• 18: Igor Tatarinov , Alon Halevy, Efficient query reformulation in peer data management systems, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007629]
• 19: M. Vincent and J. Liu. Multivalued Dependencies in XML. In BNCOD, Coventry, UK, pages 4--18, 2003.
• 20: W3C. XML Query Use Cases, W3C Working Draft 02, May, 2003. http://www.w3.org/TR/xquery-use-cases.
• 21: W3C. XQuery 1.0 and XPath 2.0 Formal Semantics. http://www.w3.org/TR/query-semantics/, May 2003.
• 22: Peter T. Wood, Containment for XPath Fragments under DTD Constraints, Proceedings of the 9th International Conference on Database Theory, p.300-314, January 08-10, 2003
• 23: Sihem Amer-Yahia , SungRan Cho , Laks V. S. Lakshmanan , Divesh Srivastava, Minimization of tree pattern queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.497-508, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation

General Terms:
Algorithms, Theory

Keywords:
XQuery containment, variable binding dependency