Storing and querying ordered XML using a relational database system

ABSTRACT

XML is quickly becoming the de facto standard for data exchange over the Internet. This is creating a new set of data management requirements involving XML, such as the need to store and query XML documents. Researchers have proposed using relational database systems to satisfy these requirements by devising ways to "shred" XML documents into relations, and translate XML queries into SQL queries over these relations. However, a key issue with such an approach, which has largely been ignored in the research literature, is how (and whether) the ordered XML data model can be efficiently supported by the unordered relational data model. This paper shows that XML's ordered data model can indeed be efficiently supported by a relational database system. This is accomplished by encoding order as a data value. We propose three order encoding methods that can be used to represent XML order in the relational data model, and also propose algorithms for translating ordered XPath expressions into SQL using these encoding methods. Finally, we report the results of an experimental study that investigates the performance of the proposed order encoding methods on a workload of ordered XML queries and updates.

REFERENCES

• 1: P. Bohannon, J. Freire,P. Roy, J. Simeon. From XML Schema to Relations: A Cost-based Approach to XML Storage. ICDE 2002.
• 2: M. Carey et al., XPERANTO: Publishing Object-Relational Data as XML. In Workshop on Web and Databases (WebDB), 2000.
• 3: Brian Cooper , Neal Sample , Michael J. Franklin , Gisli R. Hjaltason , Moshe Shadmon, A Fast Index for Semistructured Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.341-350, September 11-14, 2001
• 4: Alin Deutsch , Mary Fernandez , Dan Suciu, Storing semistructured data with STORED, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.431-442, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 5: Mary Fernandez , Atsuyuki Morishima , Dan Suciu, Efficient evaluation of XML middle-ware queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.103-114, May 21-24, 2001, Santa Barbara, California, United States
• 6: M. F. Fernandez, et al. Publishing Relational Data as XML: The SilkRoute Approach. IEEE Data Engineering Bulletin 24(2), 2001.
• 7: D. Florescu, D. Kossmann, Storing and Querying XML Data using an RDBMS. IEEE Data Engineering Bulletin 22(3), 1999.
• 8: Dao Dinh Kha , Masatoshi Yoshikawa , Shunsuke Uemura, An XML Indexing Structure with Relative Region Coordinate, Proceedings of the 17th International Conference on Data Engineering, p.313-320, April 02-06, 2001
• 9: Online Computer Library Center. Introduction to the Dewey Decimal Classification. http://www.oclc.org/oclc/fp/about/about_the_ddc.htm.
• 10: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, Sequence query processing, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.430-441, May 24-27, 1994, Minneapolis, Minnesota, United States
• 11: 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
• 12: 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
• 13: Jayavel Shanmugasundaram , Eugene Shekita , Jerry Kiernan , Rajasekar Krishnamurthy , Efstratios Viglas , Jeffrey Naughton , Igor Tatarinov, A general technique for querying XML documents using a relational database system, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603871]
• 14: Takeyuki Shimura , Masatoshi Yoshikawa , Shunsuke Uemura, Storage and Retrieval of XML Documents Using Object-Relational Databases, Proceedings of the 10th International Conference on Database and Expert Systems Applications, p.206-217, August 30-September 03, 1999
• 15: Richard Snodgrass , Ilsoo Ahn, A taxonomy of time databases, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.236-246, May 1985, Austin, Texas, United States
• 16: Igor Tatarinov , Zachary G. Ives , Alon Y. Halevy , Daniel S. Weld, Updating XML, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.413-424, May 21-24, 2001, Santa Barbara, California, United States
• 17: I. Tatarinov, et al. Storing and Querying Ordered XML using a Relational DBMS. Tech Report, Univ. of Washington, 2002.
• 18: The Plays of Shakespeare in XML. http://www.oasis-open.org/cover/bosakShakespeare200.html.
• 19: World Wide Web Consortium. Document Object Model (DOM) Level 3 Core Specification. W3C Recommendation Sept. 2001.
• 20: World Wide Web Consortium, Extensible Markup Language (XML). W3C Recommendation, February 1998.
• 21: World Wide Web Consortium. XML Path Language (XPath), Version 1.0, W3C Recommendation, November 1999.
• 22: World Wide Web Consortium. XQuery: A Query Language for XML. W3C Working Draft, June 2001.
• 23: F. Yergeau, UTF-8, A Transformation Format of ISO 10646. Request for Comments 2279, January 1998.
• 24: 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
• 25: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

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

          Nouns: SQL
      H.2.4 Systems
          Subjects: Transaction processing

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

          Nouns: XML

General Terms:
Documentation, Management, Standardization, Theory