Article

Efficiently supporting order in XML query processing

Authors:

Maged El-Sayed,

Katica Dimitrova,

Elke A. RundensteinerAuthors Info & Claims

WIDM '03: Proceedings of the 5th ACM international workshop on Web information and data management

Pages 147 - 154

https://doi.org/10.1145/956699.956731

Published: 07 November 2003 Publication History

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]

K. Deschler and E. Rundensteiner. Mass: A multi-axis storage structure for large xml documents. In CIKM, 2003.]]

Digital Library

[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]

L. Fegaras and R. Elmasri. Query Engine for Web-Accessible XML data. In The VLDB Journal, pages 251--260, 2001.]]

Digital Library

[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.]]

Digital Library

[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 and et al. Timber: A native xml database. In VLDB Journal, Volume 11, Issue 4, pages 274--291, 2002.]]

[9]

C.-C. Kanne and G. Moerkotte. Efficient storage of XML data. In ICDE, page 198, 2000.]]

Digital Library

[10]

H. Liefke. Horizontal query optimization on ordered semistructured data. In WebDB (Informal Proceedings), pages 61--66, 1999.]]

[11]

H. Liefke and S. B. Davidson. View maintenance for hierarchical semistructured data. In Data Warehousing and Knowledge Discovery, pages 114--125, 2000.]]

Digital Library

[12]

I. Manolescu, D. Florescu, and D. Kossmann. Answering XML Queries on Heterogeneous Data Sources. In VLDB, Roma, Italy, pages 241--250, Sept. 2001.]]

Digital Library

[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]

S. Paparizos, S. Al-Khalifa, H. Jagadish, L. Lakshmanan, A. Nierman, D. Srivastava, and Y. Wu. Grouping in xml. XMLDM'02, vol. 2490, 2002.]]

Digital Library

[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.]]

Digital Library

[16]

J. Shanmugasundaram, E. Shekita, R. Barr, M. Carey, B. Lindsay, H. Pirahesh, and B. Reinwald. Efficiently publishing relational data as XML documents. VLDB Journal: Very Large Data Bases, 10(2-3): 133--154, 2001.]]

Digital Library

[17]

J. Shanmugasundaram, K. Tufte, G. He, C. Zhang, apD. DeWitt, and J. Naughton. Relational databases for querying xml documents: Limitations and opportunities. In frameVLDB, pages 302--314, 1999. in VLDB, pages 302--314, 1999.]]

Digital Library

[18]

I. Tatarinov and et al. Storing and Querying Ordered XML interUsing a Relational Database System. In SIGMOD, pages 204--215, 2002.]]

Digital Library

[19]

F. Tian, D. J. DeWitt, J. Chen, and C. Zhang. The design and reperformance evaluation of alternative xml storage strategies. sortIn SIGMOD, March 2002.]]

Digital Library

[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]

X. Zhang and et al. Rainbow: Multi-XQuery Optimization Using Materialized XML Views. In SIGMOD Demo, page 671, 2003.]]

Digital Library

[26]

X. Zhang, B. Pielech, and E. A. Rundensteiner. Honey, I Shrunk the XQuery! - An XML Algebra Optimization Approach. In WIDM, pages 15--22, Nov. 2002.]]

Digital Library

[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.]]

Cited By

Wang SWang LRundensteiner E(2007)Isolating order semantics in order-sensitive xquery-to-SQL translationProceedings of the 24th British national conference on Databases10.5555/1770274.1770293(147-159)Online publication date: 3-Jul-2007
https://dl.acm.org/doi/10.5555/1770274.1770293
Wang SWang LRundensteiner E(2007)Isolating Order Semantics in Order-Sensitive XQuery-to-SQL TranslationData Management. Data, Data Everywhere10.1007/978-3-540-73390-4_14(147-159)Online publication date: 2007
https://doi.org/10.1007/978-3-540-73390-4_14
Shui WLam FFisher DWong R(2005)Querying and maintaining ordered XML data using relational databasesProceedings of the 16th Australasian database conference - Volume 3910.5555/1082222.1082232(85-94)Online publication date: 30-Jan-2005
https://dl.acm.org/doi/10.5555/1082222.1082232
Show More Cited By

Index Terms

Efficiently supporting order in XML query processing
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
    2. Query languages
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Efficiently supporting order in XML query processing
Special issue: WIDM 2003

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 issues related to handling order ...
XML Processing and Data Integration with XQuery

Most Web applications exchange data as XML, but they create and process this data with languages that don't have native support for XML. With appropriate middleware, XQuery can dramatically simplify this process, treating all data sources as though they ...
An XML Schema integration and query mechanism system

The availability of large amounts of heterogeneous distributed web data necessitates the integration of XML data from multiple XML sources for many reasons. For example, currently, there are many e-commerce companies, which offer similar products but ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WIDM '03: Proceedings of the 5th ACM international workshop on Web information and data management

November 2003

164 pages

ISBN:1581137257

DOI:10.1145/956699

Program Chairs:
Roger Chiang
University of Cincinnati, USA
,
Alberto H. F. Laender
Federal University of Minas Gerais, Brazil
,
Ee-Peng Lim
Nanyang Technological University, Singapore

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 November 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CIKM03

Sponsor:

CIKM03: 12th International Conference on Information and Knowledge Management

November 7 - 8, 2003

Louisiana, New Orleans, USA

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
966
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang SWang LRundensteiner E(2007)Isolating order semantics in order-sensitive xquery-to-SQL translationProceedings of the 24th British national conference on Databases10.5555/1770274.1770293(147-159)Online publication date: 3-Jul-2007
https://dl.acm.org/doi/10.5555/1770274.1770293
Wang SWang LRundensteiner E(2007)Isolating Order Semantics in Order-Sensitive XQuery-to-SQL TranslationData Management. Data, Data Everywhere10.1007/978-3-540-73390-4_14(147-159)Online publication date: 2007
https://doi.org/10.1007/978-3-540-73390-4_14
Shui WLam FFisher DWong R(2005)Querying and maintaining ordered XML data using relational databasesProceedings of the 16th Australasian database conference - Volume 3910.5555/1082222.1082232(85-94)Online publication date: 30-Jan-2005
https://dl.acm.org/doi/10.5555/1082222.1082232
Zhang HTompa FMunson EVion-Dury J(2004)Querying XML documents by dynamic shreddingProceedings of the 2004 ACM symposium on Document engineering10.1145/1030397.1030401(21-30)Online publication date: 28-Oct-2004
https://dl.acm.org/doi/10.1145/1030397.1030401

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten