On rewriting XPath queries using views

ABSTRACT

The problem of rewriting a query using a materialized view is studied for a well known fragment of XPath that includes the following three constructs: wildcards, descendant edges and branches. In earlier work, determining the existence of a rewriting was shown to be coNP-hard, but no tight complexity bound was given. While it was argued that Σ₃^p is an upper bound, the proof was based on results that have recently been refuted. Consequently, the exact complexity (and even decidability) of this basic problem has been unknown, and there have been no practical rewriting algorithms if the query and the view use all the three constructs mentioned above.

It is shown that under fairly general conditions, there are only two candidates for rewriting and hence, the problem can be practically solved by two containment tests. In particular, under these conditions, determining the existence of a rewriting is coNP-complete. The proofs utilize various novel techniques for reasoning about XPath patterns. For the general case, the exact complexity remains unknown, but it is shown that the problem is decidable.

REFERENCES

• 1: Foto Afrati , Chen Li , Prasenjit Mitra, Rewriting queries using views in the presence of arithmetic comparisons, Theoretical Computer Science, v.368 n.1-2, p.88-123, December, 2006 [doi>10.1016/j.tcs.2006.08.020]
• 2: Foto N. Afrati , Chen Li , Jeffrey D. Ullman, Using views to generate efficient evaluation plans for queries, Journal of Computer and System Sciences, v.73 n.5, p.703-724, August, 2007 [doi>10.1016/j.jcss.2006.10.019]
• 3: Andrey Balmin , Fatma Özcan , Kevin S. Beyer , Roberta J. Cochrane , Hamid Pirahesh, A framework for using materialized XPath views in XML query processing, Proceedings of the Thirtieth international conference on Very large data bases, p.60-71, August 31-September 03, 2004, Toronto, Canada
• 4: Answering Regular Path Queries Using Views, Proceedings of the 16th International Conference on Data Engineering, p.389, February 28-March 03, 2000
• 5: L. Chen and E. A. Rundensteiner. XCache: XQuery-based caching system. In WebDB, pages 31--36, 2002.
• 6: Sara Cohen , Werner Nutt , Alexander Serebrenik, Rewriting aggregate queries using views, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.155-166, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303992]
• 7: 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
• 8: S. Flesca , F. Furfaro , E. Masciari, On the minimization of Xpath queries, Proceedings of the 29th international conference on Very large data bases, p.153-164, September 09-12, 2003, Berlin, Germany
• 9: Gösta Grahne , Alex Thomo, Query containment and rewriting using views for regular path queries under constraints, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.111-122, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773165]
• 10: Benny Kimelfeld , Yehoshua Sagiv, Revisiting redundancy and minimization in an XPath fragment, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353355]
• 11: Laks V. S. Lakshmanan , Hui Wang , Zheng Zhao, Answering tree pattern queries using views, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 12: 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]
• 13: Bhushan Mandhani , Dan Suciu, Query caching and view selection for XML databases, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 14: Gerome Miklau , Dan Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM (JACM), v.51 n.1, p.2-45, January 2004 [doi>10.1145/962446.962448]
• 15: 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
• 16: Jeffrey D. Ullman, Information integration using logical views, Theoretical Computer Science, v.239 n.2, p.189-210, May 28, 2000 [doi>10.1016/S0304-3975(99)00219-4]
• 17: 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
• 18: Liang Huai Yang , Mong Li Lee , Wynne Hsu, Efficient mining of XML query patterns for caching, Proceedings of the 29th international conference on Very large data bases, p.69-80, September 09-12, 2003, Berlin, Germany