Rewriting nested XML queries using nested views

ABSTRACT

We present and analyze an algorithm for equivalent rewriting of XQuery queries using XQuery views, which is complete for a large class of XQueries featuring nested FLWR blocks, XML construction and join equalities by value and identity. These features pose significant challenges which lead to fundamental extension of prior work on the problems of rewriting conjunctive and tree pattern queries. Our solution exploits the Nested XML Tableaux (NEXT) notation which enables a logical foundation for specifying XQuery semantics. We present a tool which inputs XQuery queries and views and outputs an XQuery rewriting, thus being usable on top of any of the existing XQuery processing engines. Our experimental evaluation shows that the tool scales well for large numbers of views and complex queries.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: 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
• 3: A. Balmin, F. Ozcan, K. Beyer, R. Cochrane, and H. Pirahesh. A framework for using materialized xpath views in xml query processing. In VLDB, 2004.
• 4: Kevin Beyer , Don Chambérlin , Latha S. Colby , Fatma Özcan , Hamid Pirahesh , Yu Xu, Extending XQuery for analytics, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066215]
• 5: Michael J. Carey , Jerry Kiernan , Jayavel Shanmugasundaram , Eugene J. Shekita , Subbu N. Subramanian, XPERANTO: Middleware for Publishing Object-Relational Data as XML Documents, Proceedings of the 26th International Conference on Very Large Data Bases, p.646-648, September 10-14, 2000
• 6: 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]
• 7: Surajit Chaudhuri, Optimization of real conjunctive queries, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.59-70, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153856]
• 8: Chandra Chekuri , Anand Rajaraman, Conjunctive Query Containment Revisited, Proceedings of the 6th International Conference on Database Theory, p.56-70, January 08-10, 1997
• 9: A. Deutsch, Y. Papakonstantinou, and Y. Xu. The NEXT logical framework for XQuery. In VLDB, 2004.
• 10: A. Deutsch and V. Tannen. MARS: A system for publishing XML from mixed and redundant storage. In VLDB, 2003.
• 11: Alin Deutsch , Val Tannen, Reformulation of XML Queries and Constraints, Proceedings of the 9th International Conference on Database Theory, p.225-241, January 08-10, 2003
• 12: Y. Diao, D. Florescu, D. Kossmann, M. Carey, M. Franklin. Memoization in a streaming xquery processor. In XSym 2004.
• 13: X. Dong, A. Y. Halevy, and I. Tatarinov. Containment of nested XML queries. In VLDB, 2004.
• 14: S. Flesca, F. Furfaro, and E. Masciari. On the minimization of XPath queries. In VLDB, 2003.
• 15: Jörg Flum , Markus Frick , Martin Grohe, Query Evaluation via Tree-Decompositions, Proceedings of the 8th International Conference on Database Theory, p.22-38, January 04-06, 2001
• 16: Georg Gottlob , Christoph Koch , Reinhard Pichler, The complexity of XPath query evaluation, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.179-190, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773171]
• 17: 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]
• 18: Alfons Kemper , Guido Moerkotte, Advanced Query Processing in Object Bases Using Access Support Relations, Proceedings of the 16th International Conference on Very Large Data Bases, p.290-301, August 13-16, 1990
• 19: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 20: Alon Y. Levy , Dan Suciu, Deciding containment for queries with complex objects (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.20-31, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263665]
• 21: 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
• 22: 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]
• 23: 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
• 24: Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom, Object Exchange Across Heterogeneous Information Sources, Proceedings of the Eleventh International Conference on Data Engineering, p.251-260, March 06-10, 1995
• 25: Yannis Papakonstantinou , Vasilis Vassalos, Query rewriting for semistructured data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.455-466, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 26: Prakash Ramanan, Efficient algorithms for minimizing tree pattern queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564726]
• 27: Shariq Rizvi , Alberto Mendelzon , S. Sudarshan , Prasan Roy, Extending query rewriting techniques for fine-grained access control, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007631]
• 28: Patrick Valduriez, Join indices, ACM Transactions on Database Systems (TODS), v.12 n.2, p.218-246, June 1987 [doi>10.1145/22952.22955]
• 29: Stijn Vansummeren, Deciding well-definedness of XQuery fragments, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065173]
• 30: W3C. XML Query Use Cases . Available from http://www.w3.org/TR/xmlquery-use-cases/.
• 31: W3C. XQuery: A query Language for XML. Available from http://www.w3.org/TR/xquery.
• 32: 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
• 33: Wanhong Xu , Z. Meral Özsoyoglu, Rewriting XPath queries using materialized views, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 34: Cong Yu , Lucian Popa, Constraint-based XML query rewriting for data integration, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007611]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.0 GENERAL

General Terms:
Algorithms, Design, Experimentation, Languages, Theory

Keywords:
XML nested query, reformulation, rewriting, views