Some rewrite optimizations of DB2 XQuery navigation

ABSTRACT

IBM® DB2® 9 is a truly hybrid commercial database system that combines XML and relational data. It provides native support for XML storage and indexing, and query evaluation support for XQuery. By building a hybrid system, the designers of DB2 9 were able to use the existing SQL query evaluation and optimization techniques to develop similar methods for XQuery. However, SQL and XQuery are sufficiently different that new optimization techniques can and are being developed in the new XQuery domain. This paper describes a few such techniques, all based on static rewrites of XQuery expressions.

REFERENCES

• 1: 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
• 2: Attila Barta , Mariano P. Consens , Alberto O. Mendelzon, Benefits of path summaries in an XML query optimizer supporting multiple access methods, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: Kevin Beyer , Don Chambérlin , Latha S. Colby , Fatma Özcan , Hamid Pirahesh , Yu Xu, Extending XQuery for analytics, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066215]
• 4: Kevin Beyer , Roberta J. Cochrane , Vanja Josifovski , Jim Kleewein , George Lapis , Guy Lohman , Bob Lyle , Fatma Özcan , Hamid Pirahesh , Normen Seemann , Tuong Truong , Bert Van der Linden , Brian Vickery , Chun Zhang, System RX: one part relational, one part XML, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066197]
• 5: Kevin Beyer , Fatma Özcan , Sundar Saiprasad , Bert Van der Linden, DB2/XML: designing for evolution, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066299]
• 6: Donald D. Chamberlin , Jonathan Robie , Daniela Florescu, Quilt: An XML Query Language for Heterogeneous Data Sources, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.1-25, May 18-19, 2000
• 7: Li Chen , Elke A. Rundensteiner, XQuery containment in presence of variable binding dependencies, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060789]
• 8: Zhimin Chen , H. V. Jagadish , Laks V. S. Lakshmanan , Stelios Paparizos, From tree patterns to generalized tree patterns: on efficient evaluation of XQuery, Proceedings of the 29th international conference on Very large data bases, p.237-248, September 09-12, 2003, Berlin, Germany
• 9: B. Choi, M. Fernandez, J. Simeon. The XQuery Formal Semantics: A Foundation for Implementation and Optimization. Technical Report MS-CIS-02-25, University of Pennsylvania, 2002.
• 10: David DeHaan , David Toman , Mariano P. Consens , M. Tamer Özsu, A comprehensive XQuery to SQL translation using dynamic interval encoding, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872832]
• 11: T. Fiebig , S. Helmer , C.-C. Kanne , G. Moerkotte , J. Neumann , R. Schiele , T. Westmann, Anatomy of a native XML base management system, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.292-314, December 2002 [doi>10.1007/s00778-002-0080-y]
• 12: P. Gassner, G. M. Lohman, B. Schiefer, Y. Wang. Query Optimization in the IBM DB2 Family. IEEE Data Eng. Bulletin Journal 1993, Volume 16, number 4: 4--18.
• 13: L. M. Haas , J. C. Freytag , G. M. Lohman , H. Pirahesh, Extensible query processing in starburst, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.377-388, June 1989, Portland, Oregon, United States
• 14: H. V. Jagadish , S. Al-Khalifa , A. Chapman , L. V. S. Lakshmanan , A. Nierman , S. Paparizos , J. M. Patel , D. Srivastava , N. Wiwatwattana , Y. Wu , C. Yu, TIMBER: A native XML database, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.274-291, December 2002 [doi>10.1007/s00778-002-0081-x]
• 15: H. V. Jagadish , Laks V. S. Lakshmanan , Divesh Srivastava , Keith Thompson, TAX: A Tree Algebra for XML, Revised Papers from the 8th International Workshop on Database Programming Languages, p.149-164, September 08-10, 2001
• 16: Vanja Josifovski , Marcus Fontoura , Attila Barta, Querying XML streams, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.197-210, April 2005 [doi>10.1007/s00778-004-0123-7]
• 17: Raghav Kaushik , Rajasekar Krishnamurthy , Jeffrey F. Naughton , Raghu Ramakrishnan, On the integration of structure indexes and inverted lists, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007656]
• 18: A. Kwong, M. Gertz. Schema-based Optimization of XPath Expressions. Technical report, University of California at Davis, Dept. of Computer Science, 2001
• 19: Zhen Hua Liu , Muralidhar Krishnaprasad , Vikas Arora, Native Xquery processing in oracle XMLDB, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066259]
• 20: P. Michiels. XQuery Optimization. Proceedings of the VLDB 2003 PhD Workshop.
• 21: Matthias Nicola , Bert van der Linden, Native XML support in DB2 universal database, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 22: Patrick O'Neil , Elizabeth O'Neil , Shankar Pal , Istvan Cseri , Gideon Schaller , Nigel Westbury, ORDPATHs: insert-friendly XML node labels, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007686]
• 23: Shankar Pal , Istvan Cseri , Oliver Seeliger , Michael Rys , Gideon Schaller , Wei Yu , Dragan Tomic , Adrian Baras , Brandon Berg , Denis Churin , Eugene Kogan, XQuery implementation in a relational database system, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 24: Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan, Extensible/rule based query rewrite optimization in Starburst, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.39-48, June 02-05, 1992, San Diego, California, United States
• 25: Michael Rys , Don Chamberlin , Daniela Florescu, XML and relational database management systems: the inside story, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066298]
• 26: 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
• 27: Thomas Schwentick, XPath query containment, ACM SIGMOD Record, v.33 n.1, March 2004 [doi>10.1145/974121.974140]
• 28: Hong Su , Elke A. Rundensteiner , Murali Mani, Semantic query optimization for XQuery over XML streams, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 29: 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]
• 30: Y. Wu, J. Patel, H. V. Jagadish. Structured Join Order Selection for XML Query Optimization. ICDE 2003: 443--454.
• 31: World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Data Model (XDM). W3C Recommendation 23 January 2007. http://www.w3.org/TR/xpath-datamodel/
• 32: World Wide Web Consortium (W3C). XQuery 1.0: An XML Query Language. W3C Recommendation 23 January 2007. http://www.w3.org/TR/xquery/
• 33: World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Formal Semantics. World Wide Web Consortium (W3C). http://www.w3.org/TR/xquery-semantics/
• 34: Benjamin B. Yao , M. Tamer Özsu , John Keenleyside, XBench - A Family of Benchmarks for XML DBMSs, Proceedings of the VLDB 2002 Workshop EEXTT and CAiSE 2002 Workshop DTWeb on Efficiency and Effectiveness of XML Tools and Techniques and Data Integration over the Web-Revised Papers, p.162-164, January 2003

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Experimentation, Performance

Keywords:
db2, optimization, xml, xquery