XML query optimization in the presence of side effects

ABSTRACT

The emergence of database languages with side effects, notably for XML, raises significant challenges for database compilers and optimizers. In this paper, we extend an algebra for the W3C XML query language with operations that allow data to be immediately updated. We study the impact of that extension on logical optimization, join detection, and pipelining. The main result of this work is to show that, with proper care, a number of important optimizations based on nested relational algebras remain applicable in the presence of side effects. Our approach relies on an analysis of the conditions that must be checked in order for algebraic rewritings to hold. An implementation and experimental results demonstrate the effectiveness of the approach.

REFERENCES

• 1: BEA AquaLogic DSP documentation: Sample retail application. http://edocs.bea.com/aldsp/docs25/install/sampleapp.html.
• 2: Scott Boag, Don Chamberlain, Mary F. Fernández, Daniela Florescu, Jonathan Robie, and Jérôme Siméon. XQuery 1.0: An XML Query Language, W3C Recommendation, 2007.
• 3: Peter Buneman , Leonid Libkin , Dan Suciu , Val Tannen , Limsoon Wong, Comprehension syntax, ACM SIGMOD Record, v.23 n.1, p.87-96, March 1994 [doi>10.1145/181550.181564]
• 4: Michael Carey, Data delivery in a service-oriented world: the BEA aquaLogic data services platform, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142551]
• 5: Don Chamberlain, Michael Carey, Daniela Florescu, Donald Kossmann, and Jonathan Robie. XQueryP: Programming with XQuery. In XIME-P, 2006.
• 6: Don Chamberlain, Daniela Florescu, and Jonathan Robie. XQuery Update Facility, W3C Working Draft 11 July 2006, 2007.
• 7: James Clark. XSL Transformations (XSLT), W3C Recommendation, 1999.
• 8: Sophie Cluet, Designing OQL: allowing objects to be queried, Information Systems, v.23 n.5, p.279-305, July 1998 [doi>10.1016/S0306-4379(98)00013-1]
• 9: Leonidas Fegaras, Query unnesting in object-oriented databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.49-60, June 01-04, 1998, Seattle, Washington, United States
• 10: Leonidas Fegaras, Optimizing Queries with Object Updates, Journal of Intelligent Information Systems, v.12 n.2-3, p.219-242, March 1999 [doi>10.1023/A:1008757010516]
• 11: Steven Feuerstein , Bill Pribyl, Oracle PL/SQL Programming, 4th Edition, O'Reilly Media, Inc., 2005
• 12: Daniela Florescu , Andreas Grünhagen , Donald Kossmann, XL: an XML programming language for web service specification and composition, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511456]
• 13: Galax: An Implementation of XQuery. "http://www.galaxquery.org/".
• 14: Giorgio Ghelli, Nicola Onose, Kristoffer Høgsbro Rose, and Jérôme Siméon. A Better Semantics for XQuery with Side-Effects. In DBPL, pages 81--96, 2007.
• 15: Giorgio Ghelli, Christopher Re, and Jérôme Siméon. XQuery!: An XML Query Language with Side Effects. In EDBT Workshops, pages 178--191, 2006.
• 16: Giorgio Ghelli, Kristoffer Høgsbro Rose, and Jérôme Siméon. Commutativity Analysis in XML Update Languages. In ICDT, pages 374--388, 2007.
• 17: Jan Hidders, Jan Paredaens, and Roel Vercammen. On the Expressive Power of XQuery-Based Update Languages. In XSym, pages 92--106, 2006.
• 18: Simon Peyton Jones. Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell. In "Engineering theories of software construction", ed Tony Hoare, Manfred Broy, Ralf Steinbruggen, IOS Press, 2001.
• 19: The LINQ Project. http://msdn.microsoft.com/XML/linqproject.
• 20: Norman May , Sven Helmer , Guido Moerkotte, Strategies for query unnesting in XML databases, ACM Transactions on Database Systems (TODS), v.31 n.3, p.968-1013, September 2006 [doi>10.1145/1166074.1166081]
• 21: Guido Moerkotte. Building Query Compilers, Draft Manuscript, December 2005. http://db.informatik.uni-mannheim.de/~moer.
• 22: Simon L. Peyton Jones , Philip Wadler, Imperative functional programming, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-84, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158524]
• 23: Christopher Re , Jerome Simeon , Mary Fernandez, A Complete and Efficient Algebraic Compiler for XQuery, Proceedings of the 22nd International Conference on Data Engineering, p.14, April 03-07, 2006 [doi>10.1109/ICDE.2006.6]
• 24: Albrecht Schmidt , Florian Waas , Martin Kersten , Michael J. Carey , Ioana Manolescu , Ralph Busse, XMark: a benchmark for XML data management, Proceedings of the 28th international conference on Very Large Data Bases, p.974-985, August 20-23, 2002, Hong Kong, China
• 25: Philip Wadler. Web Development without Tiers. In 5th International Symposium on Formal Methods for Components and Objects, 2006.
• 26: Limsoon Wong, Kleisli, a functional query system, Journal of Functional Programming, v.10 n.1, p.19-56, January 2000 [doi>10.1017/S0956796899003585]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems
          Subjects: Evaluation strategies

General Terms:
Languages, Performance

Keywords:
algebra, optimization, side-effects, updates, xml, xquery