Commutativity analysis for XML updates

ABSTRACT

An effective approach to support XML updates is to use XQuery extended with update operations. This approach results in very expressive languages which are convenient for users but are difficult to optimize or reason about. A crucial question underlying many static analysis problems for such languages, from optimization to view maintenance, is whether two expressions commute. Unfortunately, commutativity is undecidable for most existing XML update languages. In this article, we propose a conservative analysis for an expressive XML update language that can be used to determine commutativity. The approach relies on a form of path analysis that computes upper bounds for the nodes that are accessed or modified in a given expression. Our main result is a theorem that can be used to identify commuting expressions. We illustrate how the technique applies to concrete examples of query optimization in the presence of updates.

REFERENCES

• 1: Benedikt, M., Bonifati, A., Flesca, S., and Vyas, A. 2005a. Adding updates to XQuery: Semantics, optimization, and static analysis. In Proceedings of the International Workshop on XQuery Implementation, Experience and Perspectives (XIME-P '05).
• 2: Benedikt, M., Bonifati, A., Flesca, S., and Vyas, A. 2005b. Verification of tree updates for optimization. In Proceedings of Computer-Aided Verification (CAV'05). Lecture Notes in Computer Science, Vol. 4590, Springer, 379--393.
• 3: Michael Benedikt , Wenfei Fan , Gabriel Kuper, Structural properties of XPath fragments, Theoretical Computer Science, v.336 n.1, p.3-31, 25 May 2005 [doi>10.1016/j.tcs.2004.10.030]
• 4: Biron, P. V. and Malhotra, A. 2001. XML schema part 2: Datatypes. W3C recommendation. http://www.w3.org/TR/2001/REC-xmlschema-2-20010502.
• 5: Boag, S., Chamberlin, D., Fernández, M. F., Florescu, D., Robie, J., and Siméon, J. 2007. XQuery 1.0: An XML query language. W3C recommendation. http://www.w3.org/TR/2007/REC-xquery-20070123/.
• 6: Bray, T., Hollander, D., and Layman, A. 1999. Namespaces in XML. W3C recommendation, World Wide Web Consortium. http://www.w3.org/TR/REC-xml-names.
• 7: Chamberlin, D., Carey, M., Florescu, D., Kossman, D., and Robie, J. 2006. XQuery P: Programming with XQuery. In Proceedings of the 3rd International Workshop on XQuery Implementation, Experience, and Perspectives (XIME-P' 06).
• 8: Chamberlin, D., Florescu, D., Melton, J., Robie, J., and Siméon, J. 2007. XQuery update facility. W3C working draft. http://www.w3.org/TR/2007/WD-xquery-update-10-20070828/.
• 9: Cooper, E., Lindley, S., Wadler, P., and Yallop, J. 2006. Links: Web programming without tears. In Proceedings of the 5th International Symposium on Formal Methods for Components and Objects (FMCO).
• 10: Dekeyser, S., Hidders, J., and Paredaens, J. 2003. Instance independent concurrency control for semistructured databases. In Proceedings of the 11th Italian Symposium on Advanced Database Systems (SEBD'03). 323--334.
• 11: Stijn Dekeyser , Jan Hidders , Jan Paredaens, A Transaction Model for XML Databases, World Wide Web, v.7 n.1, p.29-57, March 2004 [doi>10.1023/B:WWWJ.0000015864.75561.98]
• 12: Draper, D., Fankhauser, P., Fernández, M., Malhotra, A., Rose, K., Rys, M., Siméon, J., and Wadler, P. 2006. XQuery 1.0 and XPath 2.0 formal semantics, W3C recommendation. http://www.w3.org/TR/REC-xquery-semantics-20070123/.
• 13: Charles Elkan, Independence of logic database queries and update, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.154-160, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298557]
• 14: Fernández, M., Malhotra, A., Marsh, J., Nagy, M., and Walsh, N. 2007. XQuery 1.0 and XPath 2.0 data model. W3C recommendation. http://www.w3.org/TR/2007/REC-xpath-datamodel-20070123/.
• 15: Ghelli, G., Ré, C., and Siméon, J. 2006. XQuery! An XML query language with side effects. In Proceedings of the DataX Workshop.
• 16: Ghelli, G., Rose, K., and Siméon, J. 2007. Commutativity analysis in XML update languages. In Proceedings of the International Conference on Database Theory (ICDT).
• 17: Beda Christoph Hammerschmidt , Martin Kempa , Volker Linnemann, On the Intersection of XPath Expressions, Proceedings of the 9th International Database Engineering & Application Symposium, p.49-57, July 25-27, 2005 [doi>10.1109/IDEAS.2005.39]
• 18: Hidders, J., Paredaens, J., and Vercammen, R. 2006. On the expressive power of Xquery-based update languages. In Databases and XML Technologies, Proceedings of the 4th International XML Database Symposium. Springer, Berlin.
• 19: Vladimir Lanin , Dennis Shasha, A symmetric concurrent B-tree algorithm, Proceedings of 1986 ACM Fall joint computer conference, p.380-389, November 1986, Dallas, Texas, United States
• 20: Lehti, P. 2001. Design and implementation of a data manipulation processor for an XML query processor. Diplomarbeit, Technical University of Darmstadt, Darmstadt, Germany.
• 21: Alon Y. Levy , Yehoshua Sagiv, Queries Independent of Updates, Proceedings of the 19th International Conference on Very Large Data Bases, p.171-181, August 24-27, 1993
• 22: Amélie Marian , Jérôme Siméon, Projecting XML documents, Proceedings of the 29th international conference on Very large data bases, p.213-224, September 09-12, 2003, Berlin, Germany
• 23: 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]
• 24: Igor Tatarinov , Zachary G. Ives , Alon Y. Halevy , Daniel S. Weld, Updating XML, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.413-424, May 21-24, 2001, Santa Barbara, California, United States
• 25: Mads Tofte , Jean-Pierre Talpin, Region-based memory management, Information and Computation, v.132 n.2, p.109-176, Feb. 1, 1997 [doi>10.1006/inco.1996.2613]
• 26: Wadler, P. 1999. Two semantics of XPath. Discussion note for W3C XSLT Working Group. http://homepages.inf.ed.ac.uk/wadler/papers/xpath-semantics/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance

Keywords:
XML, XQuery, commutativity, optimization, updates