Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Query processing over XML data sources has emerged as a popular topic. XML is an ordered data model and XQuery expressions return results that have a well-defined order. However little work on how order is supported in XML query processing has been done to date. In this paper we study the challenges related to handling order in the XML context, namely challenges imposed by the XML data model, by the variety of distinct XML operators and by incremental view maintenance. We have proposed an efficient solution that addresses these issues. We use a key encoding for XML nodes that supports both node identity and node order. We have designed order encoding rules based on the XML algebraic query execution data model and on node encodings that does not require any actual sorting for intermediate results during execution. Our approach supports more efficient incremental view maintenance as it makes most XML operators distributive with respect to bag union. Our approach is implemented in the context of Rainbow [25], an XML data management system developed at WPI. We prove the correctness of our order encoding approach, namely that it ensures order handling for query processing and for view maintenance. We also show, through experiments, that the overhead of maintaining order in our approach is indeed neglectible.

REFERENCES

• 1: Kurt Deschler , Elke Rundensteiner, MASS: a multi-axis storage structure for large XML documents, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956963]
• 2: K. Dimitrova, M. El-Sayed, and E. A. Rundensteiner. Order-sensitive view maintenance of materialized xquery views. In ER, 2003.
• 3: M. El-Sayed and et al. Addressing Order Challenges in XML Query Processing. Technical Report WPI-CS-TR-03-25, Worcester Polytechnic Institute, 2003.
• 4: Leonidas Fegaras , Ramez Elmasri, Query Engines for Web-Accessible XML Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.251-260, September 11-14, 2001
• 5: D. K. Fisher and et al. Efficient Ordering for XML Data. Technical Report UNSW-CSE-TR-0316, University of New South Wales, Australia, June 2003.
• 6: D. Florescu and D. Kossman. Storing and Querying XML data using an RDBMS. IEEE Data Engineering Bulletin, 11(3): 27--34, 1999.
• 7: R. Goldman, J. McHugh, and J. Widom. From Semistructured Data to XML: Migrating the Lore Data Model and Query Language. In WebDB (Informal Proceedings), pages 25--30, 1999.
• 8: 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]
• 9: Efficient Storage of XML Data, Proceedings of the 16th International Conference on Data Engineering, p.198, February 28-March 03, 2000
• 10: H. Liefke. Horizontal query optimization on ordered semistructured data. In WebDB (Informal Proceedings), pages 61--66, 1999.
• 11: Hartmut Liefke , Susan B. Davidson, View Maintenance for Hierarchical Semistructured Data, Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, p.114-125, September 04-06, 2000
• 12: 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
• 13: U. Nambiar, Z. Lacroix, S. Bressan, M. L. Lee, and Y. G. Li. Xml benchmarks put to the test. In IIWAS, September 2001.
• 14: Stelios Paparizos , Shurug Al-Khalifa , H. V. Jagadish , Laks V. S. Lakshmanan , Andrew Nierman , Divesh Srivastava , Yuqing Wu, Grouping in XML, Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers, p.128-147, March 24-28, 2002
• 15: A. Schmidt, F. Waas, M. Kersten, M. Carey, I. Manolescu, D. Florescu, and R. Busse. XMARK: A benchmark for XML Data Management. In VLDB, pages 974--985, August 2002.
• 16: Jayavel Shanmugasundaram , Eugene Shekita , Rimon Barr , Michael Carey , Bruce Lindsay , Hamid Pirahesh , Berthold Reinwald, Efficiently publishing relational data as XML documents, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.133-154, September 2001
• 17: 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
• 18: 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]
• 19: Feng Tian , David J. DeWitt , Jianjun Chen , Chun Zhang, The design and performance evaluation of alternative XML storage strategies, ACM SIGMOD Record, v.31 n.1, March 2002 [doi>10.1145/507338.507341]
• 20: W3C. XML™.http://www.w3.org/XML, 1998.
• 21: W3C. XQuery 1. 0 Formal Semantics. http://www.w3.org/TR/query-semantics/, June 2001.
• 22: W3C. XML Path Language (XPath) Version 1.0. http://www.w3.org/TR/xpath, November 2003.
• 23: W3C. XML Query Data Model. W3C Working Draft. http://www.w3.org/TR/xpath-datamodel/, May 2003.
• 24: W3C. XQuery 1. 0: An XML Query Language. http://www.w3.org/TR/xquery/, May 2003.
• 25: Xin Zhang , Katica Dimitrova , Ling Wang , Maged El Sayed , Brian Murphy , Bradford Pielech , Mukesh Mulchandani , Luping Ding , Elke A. Rundensteiner, Rainbow: multi-XQuery optimization using materialized XML views, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872861]
• 26: Xin Zhang , Bradford Pielech , Elke A. Rundesnteiner, Honey, I shrunk the XQuery!: an XML algebra optimization approach, Proceedings of the 4th international workshop on Web information and data management, November 08-08, 2002, McLean, Virginia, USA [doi>10.1145/584931.584936]
• 27: X. Zhang and E. A. Rundensteiner. XAT: XML Algebra for the Rainbow System. Technical Report WPI--CS--TR--02--24, Worcester Polytechnic Institute, July 2002.

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, Management, Performance

Keywords:
XML data management systems, XML query, XQuery, algebra, order in XML, query