A comprehensive XQuery to SQL translation using dynamic interval encoding

ABSTRACT

The W3C XQuery language recommendation, based on a hierarchical and ordered document model, supports a wide variety of constructs and use cases. There is a diversity of approaches and strategies for evaluating XQuery expressions, in many cases only dealing with limited subsets of the language. In this paper we describe an implementation approach that handles XQuery with arbitrarily-nested FLWR expressions, element constructors and built-in functions (including structural comparisons). Our proposal maps an XQuery expression to a single equivalent SQL query using a novel dynamic interval encoding of a collection of XML documents as relations, augmented with information tied to the query evaluation environment. The dynamic interval technique enables (suitably enhanced) relational engines to produce predictably good query plans that do not preclude the use of sort-merge join query operators. The benefits are realized despite the challenges presented by intermediate results that create arbitrary documents and the need to preserve document order as prescribed by semantics of XQuery. Finally, our experimental results demonstrate that (native or relational) XML systems can benefit from the above technique to avoid a quadratic scale up penalty that effectively prevents the evaluation of nested FLWR expressions for large documents.

REFERENCES

• 1: Galax. Available from http://db.bell-labs.com/galax/.
• 2: IPSI-XQ - the XQuery demonstrator. Available from http://ipsi.fhg.de/oasys/projects/ipsi-xq/.
• 3: Kweelt. Available from http://kweelt.sourceforge.net.
• 4: QuiP. Available from http://developer.softwareag.com/ tamino/quip/.
• 5: X-Hive/DB. Available from http://www.x-hive.com.
• 6: XMark -- an XML benchmark project. Available from http://www.xml-benchmark.org.
• 7: V. Aguilera, S. Cluet, P. Veltri, D. Vodislav, and F. Wattez. Querying XML documents in Xyleme. In Proc. ACM SIGIR Workshop on XML and Information Retrieval, 2000.
• 8: 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
• 9: D. Barbosa, A. Barta, A. O. Mendelzon, G. A. Mihaila, F. Rizzolo, and P. Rodriguez-Guianolli. ToX - The Toronto XML Engine. In Proc. Workshop on Information Integration on the Web, pages 66--73, 2001.
• 10: S. Boag, D. Chamberlin, D. Florescu, J. Robie, J. Simeon, and M. Stefanescu. XQuery 1.0: An XML Query Language. Technical report, W3C, 2001.
• 11: From XML Schema to Relations: A Cost-Based Approach to XML Storage, Proceedings of the 18th International Conference on Data Engineering, p.64, February 26-March 01, 2002
• 12: L. J. Brown , M. P. Consens , I. J. Davis , C. R. Palmer , F. W. Tompa, A structured text ADT for object-relational databases, Theory and Practice of Object Systems, v.4 n.4, p.227-244, Oct. 12, 1998 [doi>10.1002/(SICI)1096-9942(1998)4:4<227::AID-TAPO3>3.3.CO;2-L]
• 13: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 14: 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
• 15: J. Celko. Trees, Databases and SQL. DBMS, 7(10):48--57, 1994.
• 16: D. Chamberlin, XQuery: An XML query language, IBM Systems Journal, v.41 n.4, p.597-615, October 2002
• 17: D. Chamberlin, P. Fankhauser, M. Marchiori, and J. Robie. XML Query Use Cases. Technical report, W3C, 2001.
• 18: Y. Chen, G. Mihaila, S. Padmanabhan, and R. Bordawekar. Labeling Your XML. (preliminary version presented at CASCON'02 Conf.), October 2002.
• 19: Edith Cohen , Haim Kaplan , Tova Milo, Labeling dynamic XML trees, 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.543648]
• 20: Mariano P. Consens , Tova Milo, Optimizing queries on files, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.301-312, May 24-27, 1994, Minneapolis, Minnesota, United States
• 21: Mariano P. Consens , Tova Milo, Algebras for querying text regions (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-22, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212437]
• 22: P. Fankhauser, M. Fernandez, A. Malhotra, M. Rys, J. Simeon, and P. Wadler. XQuery 1.0 Formal Semantics. Technical report, W3C, 2001.
• 23: Mary Fernández , Yana Kadiyska , Dan Suciu , Atsuyuki Morishima , Wang-Chiew Tan, SilkRoute: A framework for publishing relational data in XML, ACM Transactions on Database Systems (TODS), v.27 n.4, p.438-493, December 2002 [doi>10.1145/582410.582413]
• 24: Thorsten Fiebig , Guido Moerkotte, Evaluating Queries on Structure with eXtended Access Support Relations, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.125-136, May 18-19, 2000
• 25: D. Florescu and D. Kossmann. Storing and Querying XML Data using an RDMBS. IEEE Data Engineering Bulletin, 22(3):27--34, 1999.
• 26: 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
• 27: Jason McHugh , Serge Abiteboul , Roy Goldman , Dallas Quass , Jennifer Widom, Lore: a database management system for semistructured data, ACM SIGMOD Record, v.26 n.3, p.54-66, Sept. 1997 [doi>10.1145/262762.262770]
• 28: Jayavel Shanmugasundaram , Eugene J. Shekita , Rimon Barr , Michael J. Carey , Bruce G. Lindsay , Hamid Pirahesh , Berthold Reinwald, Efficiently Publishing Relational Data as XML Documents, Proceedings of the 26th International Conference on Very Large Data Bases, p.65-76, September 10-14, 2000
• 29: Jayavel Shanmugasundaram , Kristin Tufte , Chun Zhang , Gang He , David J. DeWitt , Jeffrey F. Naughton, Relational Databases for Querying XML Documents: Limitations and Opportunities, Proceedings of the 25th International Conference on Very Large Data Bases, p.302-314, September 07-10, 1999
• 30: Richard Thomas Snodgrass , Ilsoo Ahn , Gadi Ariav , Don Batory , James Clifford , Curtis E. Dyreson , Ramez Elmasri , Fabio Grandi , Christian S. Jensen , Wolfgang Käfer , Nick Kline , Krishna Kulkarni , T. Y. Cliff Leung , Nikos Lorentzos , John F. Roddick , Arie Segev , Michael D. Soo , Suryanarayana M. Sripada, TSQL2 language specification, ACM SIGMOD Record, v.23 n.1, p.65-86, March 1994 [doi>10.1145/181550.181562]
• 31: Igor Tatarinov , Stratis D. Viglas , Kevin Beyer , Jayavel Shanmugasundaram , Eugene Shekita , Chun Zhang, Storing and querying ordered XML using a relational database system, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564715]
• 32: F. Tian, D. DeWitt, J. Chen, and C. Zhang. The design and performance evaluation of alternative XML storage strategies. Technical report, University of Wisconsin, 2002.
• 33: David Toman, Point-Based Temporal Extension of Temporal SQL, Proceedings of the 5th International Conference on Deductive and Object-Oriented Databases, p.103-121, December 08-12, 1997
• 34: D. Toman and G. E. Weddell. Querying XML: On the Utility of Interval Encoding. Technical report, University of Waterloo, 2002.
• 35: XRel: a path-based approach to storage and retrieval of XML documents using relational databases, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.110-141, Aug. 2001 [doi>10.1145/383034.383038]
• 36: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States

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.3 Languages

          Nouns: SQL
      H.2.4 Systems
          Subjects: Query processing

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Algorithms, Design, Languages