On relational support for XML publishing: beyond sorting and tagging

ABSTRACT

In this paper, we study whether the need for efficient XML publishing brings any new requirements for relational query engines, or if sorting query results in the relational engine and tagging them in middleware is sufficient. We observe that the mismatch between the XML data model and the relational model requires relational engines to be enhanced for efficiency. Specifically, they need to support relation valued variables. We discuss how such support can be provided through the addition of an operator, GApply, with minimal extensions to existing relational engines. We discuss how the operator may be exposed in SQL syntax and provide a comprehensive study of optimization rules that govern this operator. We report the results of a preliminary performance evaluation showing the speedup obtained through our approach and the effectiveness of our optimization rules.

REFERENCES

• 1: P. Bohannon, S. Ganguly, H. Korth, P. Narayan, and P. Shenoy. Optimizing view queries in ROLEX to support navigable result trees. In Proceedings of VLDB, 2002.
• 2: M. Carey, D. Florescu, Z. Ives, Y. Lu, J. Shanmugasundaram, E. Shekita, and S. Subramanian. XPERANTO: Publishing object-relational data as XML. In WebDB, 2000.
• 3: Pedro Celis , Hansjörg Zeller, Subquery Elimination: A Complete Unnesting Algorithm for an Extended Relational Algebra, Proceedings of the Thirteenth International Conference on Data Engineering, p.321, April 07-11, 1997
• 4: D. Chamberlin, D. Florescu, J. Robie, J. Siméon, and M. Stefanescu. XQuery: A query language for XML. World Wide Web Consortium, http://www.w3.org/TR/xquery, Feb 2000.
• 5: Damianos Chatziantoniou , Kenneth A. Ross, Querying Multiple Features of Groups in Relational Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.295-306, September 03-06, 1996
• 6: Damianos Chatziantoniou , Kenneth A. Ross, Groupwise Processing of Relational Queries, Proceedings of the 23rd International Conference on Very Large Data Bases, p.476-485, August 25-29, 1997
• 7: Surajit Chaudhuri , Kyuseok Shim, Including Group-By in Query Optimization, Proceedings of the 20th International Conference on Very Large Data Bases, p.354-366, September 12-15, 1994
• 8: J. Clark and S. DeRose. XML path language (XPath) 1.0. W3C recommendation. World Wide Web Consortium, http://www.w3.org/TR/xpath, Nov. 1999.
• 9: T. P. P. Council. TPC-H: Decision support for adhoc queries. http://www.tpc.org.
• 10: M. Fernández, A. Morishima, D. Suciu, and W. Tan. Publishing relational data in XML: The SilkRoute approach. In IEEE Data Engineering Bulletin, 2001.
• 11: M. Fernández, D. Suciu, and W. Tan. SilkRoute: Trading between relations and XML. In WWW9, 2000.
• 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: Goetz Graefe , William J. McKenna, The Volcano Optimizer Generator: Extensibility and Efficient Search, Proceedings of the Ninth International Conference on Data Engineering, p.209-218, April 19-23, 1993
• 14: Ashish Gupta , Venky Harinarayan , Dallan Quass, Aggregate-Query Processing in Data Warehousing Environments, Proceedings of the 21th International Conference on Very Large Data Bases, p.358-369, September 11-15, 1995
• 15: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 16: Jayavel Shanmugasundaram , Jerry Kiernan , Eugene J. Shekita , Catalina Fan , John Funderburk, Querying XML Views of Relational Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.261-270, September 11-14, 2001
• 17: 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
• 18: Q. Wang, D. Maier, and L. Shapiro. Algebraic unnesting of nested object queries. In Technical Report, Oregon Graduate Institute, 1999.
• 19: Weipeng P. Yan , Per-Åke Larson, Performing Group-By before Join, Proceedings of the Tenth International Conference on Data Engineering, p.89-100, February 14-18, 1994
• 20: Weipeng P. Yan , Per-Åke Larson, Eager Aggregation and Lazy Aggregation, Proceedings of the 21th International Conference on Very Large Data Bases, p.345-357, September 11-15, 1995

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Relational databases

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

          Nouns: XML

General Terms:
Algorithms, Design, Experimentation, Performance