Recursion in XQuery: put your distributivity safety belt on

ABSTRACT

We introduce a controlled form of recursion in XQuery, an inflationary fixed point operator, familiar from the context of relational databases. This operator imposes restrictions on the expressible types of recursion, but it is sufficiently versatile to capture a wide range of interesting use cases, including Regular XPath and its core transitive closure operator.

While the optimization of general user-defined recursive functions in XQuery appears elusive, we describe how inflationary fixed points can be efficiently evaluated, provided that the recursive XQuery expressions are distributive. We test distributivity syntactically and algebraically, and provide experimental evidence that XQuery processors can benefit substantially from this mode of evaluation.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Loredana Afanasiev. Distributivity for XQuery Expressions. Technical report, University of Amsterdam, 2007.
• 3: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of the 18th International Conference on Data Engineering, p.141, February 26-March 01, 2002
• 4: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• 5: Denilson Barbosa , Alberto Mendelzon , John Keenleyside , Kelly Lyons, ToXgene: a template-based data generator for XML, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564769]
• 6: Scott Boag, Don Chamberlin, Mary F. Fernández, Daniela Florescu, Jonathan Robie, and Jérôme Siméon. XQuery 1.0: An XML query language. W3C Recommendation, 2007.
• 7: Peter Boncz , Torsten Grust , Maurice van Keulen , Stefan Manegold , Jan Rittinger , Jens Teubner, MonetDB/XQuery: a fast XQuery processor powered by a relational engine, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142527]
• 8: Denise Draper, Peter Fankhauser, Mary F. Fernández, Ashok Malhotra, Kristoffer Rose, Michael Rys, Jérôme Siméon, and Philip Wadler. XQuery 1.0 and XPath 2.0 Formal Semantics. W3C Recommendation, 2007.
• 9: EXSLT: A Community Initiative to Provide Extensions to XSLT.
• 10: Wenfei Fan , Floris Geerts , Xibei Jia , Anastasios Kementsietsidis, SMOQE: a system for providing secure access to XML, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 11: Wenfei Fan, Floris Geerts, Xibei Jia, and Anastasios Kementsietsidis. Rewriting Regular XPath Queries on XML Views. In Proc. ICDE, 2007.
• 12: César Galindo-Legaria , Milind Joshi, Orthogonal optimization of subqueries and aggregation, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.571-581, May 21-24, 2001, Santa Barbara, California, United States
• 13: Georg Gottlob , Christoph Koch, Monadic Queries over Tree-Structured Data, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.189-202, July 22-25, 2002
• 14: Maxim Grinev and Dmitry Lizorkin. XQuery Function Inlining for Optimizing XQuery Queries. In Proc. ADBIS, 2004.
• 15: Torsten Grust, Jan Rittinger, and Jens Teubner. eXrQuy: Order Indifference in XQuery. In Proc. ICDE, 2007.
• 16: Torsten Grust , Sherif Sakr , Jens Teubner, XQuery on SQL hosts, Proceedings of the Thirtieth international conference on Very large data bases, p.252-263, August 31-September 03, 2004, Toronto, Canada
• 17: Torsten Grust and Jens Teubner. Relational Algebra: Mother Tongue---XQuery: Fluent. In Twente Data Management Workshop (TDM), 2004.
• 18: Torsten Grust , Maurice van Keulen , Jens Teubner, Staircase join: teach a relational DBMS to watch its (axis) steps, Proceedings of the 29th international conference on Very large data bases, p.524-535, September 09-12, 2003, Berlin, Germany
• 19: Ulrich Güntzer , Werner Kießling , Rudolf Bayer, On the Evaluation of Recursion in (Deductive) Database Systems by Efficient Differential Fixpoint Iteration, Proceedings of the Third International Conference on Data Engineering, p.120-129, February 03-05, 1987
• 20: Jiawei Han , Ghassan Z. Qadah , Chinying Chaou, The Processing and Evaluation of Transitive Closure Queries, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.49-75, March 14-18, 1988
• 21: Jan Hidders, Philippe Michiels, Jan Paredaens, and Roel Vercammen. LiXQuery: A Foundation for XQuery Research. SIGMOD Record, 3(4), 2005.
• 22: Michael Kay. The Saxon XSLT and XQuery Processor.
• 23: Maarten Marx, Conditional XPath, ACM Transactions on Database Systems (TODS), v.30 n.4, p.929-959, December 2005 [doi>10.1145/1114244.1114247]
• 24: Jim Melton and Alan R. Simon. SQL: 1999 - Understanding Relational Language Components. Morgan Kaufmann, 2002.
• 25: Christian Nentwich , Licia Capra , Wolfgang Emmerich , Anthony Finkelstein, xlinkit: a consistency checking and smart link generation service, ACM Transactions on Internet Technology (TOIT), v.2 n.2, p.151-185, May 2002 [doi>10.1145/514183.514186]
• 26: Chang-Won Park , Jun-Ki Min , Chin-Wan Chung, Structural function inlining technique for structurally recursive XML queries, Proceedings of the 28th international conference on Very Large Data Bases, p.83-94, August 20-23, 2002, Hong Kong, China
• 27: 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
• 28: John Snelson. Higher Order Functions for XQuery, 2008. Technical Note submitted to W3C, http://snelson.org.uk/~jpcs/higher_order_functions/index.cgi.
• 29: Balder ten Cate, The expressivity of XPath with transitive closure, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142398]