Article

Efficient ordering for XML data

Authors:

Damien K. Fisher,

William M. Shui,

Raymond K. WongAuthors Info & Claims

CIKM '03: Proceedings of the twelfth international conference on Information and knowledge management

Pages 350 - 357

https://doi.org/10.1145/956863.956929

Published: 03 November 2003 Publication History

Abstract

With the increasing popularity of XML, there arises the need for managing and querying information in this form. Several query languages, such as XQuery, have been proposed which return their results in document order. However, most recent efforts focused on query optimization have disregarded order. This paper presents a simple yet elegant method to maintain document ordering for XML data. Analysis of our method shows that it is indeed efficient and scalable, even for changing data.

References

[1]

Serge Abiteboul. Querying semi-structured data. In Proceedings of ICDT, volume 1186 of Lecture Notes in Computer Science, pages 1--18, Delphi, Greece, 8--10 January 1997. Springer.

[2]

Toshiyuki Amagasa, Masatoshi Yoshikawa, and Shunsuke Uemura. Qrs: A robust numbering scheme for xml documents. In Proceedings of IEEE ICDE, March 2003.

[3]

Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito. Two simplified algorithms for maintaining order in a list. In Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), volume 2461 of Lecture Notes in Computer Science, pages 152--164, Rome, Italy, September 17--21 2002.

[4]

Tim Bray, Jean Paoli, C. M. Sperberg-McQueen, and Eve Maler. Extensible Markup Language (XML) 1.0 (second edition). http://www.w3.org/TR/2000/REC-xml-20001006, 2000.

[5]

Online Computer Library Center. Introduction to the Dewey Decimal Classification. http://www.oclc.org/oclc/fp/about/about_the_ddc.htm .

[6]

Edith Cohen, Haim Kaplan, and Tova Milo. Labeling Dynamic XML Trees. In Proceedings of PODS, pages 271--281, New York, June 3--5 2002. ACM Press.

[7]

Alin Deutsch, Mary Fernandez, Daniela Florescu, Alon Levy, and Dan Suciu. A query language for XML. Computer Networks (Amsterdam, Netherlands: 1999), 31(11--16):1155--1169, May 1999.

Digital Library

[8]

P. Dietz and D. Sleator. Two algorithms for maintaining order in a list. In Proceedings of the nineteenth annual ACM conference on Theory of computing, pages 365--372. ACM Press, 1987.

Digital Library

[9]

Paul F. Dietz. Maintaining order in a linked list. In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 122--127, 1982.

Digital Library

[10]

W3C Working Draft. XML Path Language (XPath) 2.0. http://www.w3.org/TR/2002/WD-xpath20-20021115, November 2002.

[11]

W3C Working Draft. XQuery 1.0: An XML query language. http://www.w3.org/TR/2002/WD-xquery-20021115, November 2002.

[12]

Mary Fernández, Yana Kadiyska, Dan Suciu, Atsuyuki Morishima, and Wang-Chiew Tan. SilkRoute: A framework for publishing relational data in XML . ACM Transactions on Database Systems, 27(4):438--493, December 2002.

Digital Library

[13]

R. Goldman, J. McHugh, and J. Widom. From Semistructured Data to XML: Migrating the Lore Data Model and Query Language. In Workshop on the Web and Databases (WebDB '99), pages 25--30, 1999.

[14]

Roy Goldman, Narayanan Shivakumar, Suresh Venkatasubramanian, and Hector Garcia-Molina. Proximity Search in Databases. In Proceedings of VLDB, pages 26--37. Morgan Kaufmann Publishers, 1998.

Digital Library

[15]

Roy Goldman and Jennifer Widom. DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. In Proceedings of VLDB, pages 436--445, East Sussex - San Francisco, August 1998. Morgan Kaufmann.

Digital Library

[16]

Roy Goldman and Jennifer Widom. Summarizing and Searching Sequential Semistructured Sources. Technical Report, Stanford University, 2000.

[17]

H. V. Jagadish et al. TIMBER: A native XML database. VLDB Journal: Very Large Data Bases, 11(4):274--291, 2002.

Digital Library

[18]

W. Eliot Kimber. HyTime and SGML : Understanding the HyTime HYQ Query Language . Technical Report Version 1.1, IBM Corporation, August 1993.

[19]

Yong Kyu Lee, Seong-Joon Yoo, Kyoungro Yoon, and P. Bruce Berra. Index structures for structured documents. In ACM International Conference on Digital Libraries, pages 91--99, 1996.

Digital Library

[20]

Alberto Lerner and Dennis Shasha. AQuery: Query Language for Ordered Data, Optimization Techniques, and Experiments. In Proceedings of VLDB, to appear, 2003.

Digital Library

[21]

Quanzhong Li and Bongki Moon. Indexing and querying XML data for regular path expressions. In Proceedings of VLDB, pages 361--370, 2001.

Digital Library

[22]

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

[23]

J. McHugh, S. Abiteboul, R. Goldman, D. Quass, and J. Widom. Lore: A database management system for semistructured data. SIGMOD Record, 26(3):54--66, September 1997.

Digital Library

[24]

Jason McHugh and Jennifer Widom. Query optimization for XML. In Proceedings of VLDB, pages 315--326, 1999.

Digital Library

[25]

Igor Tatarinov, Stratis D. Viglas, Kevin Beyer, Jayavel Shanmugasundaram, Eugene Shekita, and Chun Zhang. Storing and querying ordered XML using a relational database system. In Proceedings of the 2002 ACM SIGMOD international conference on Management of data, pages 204--215. ACM Press, 2002.

Digital Library

[26]

Chun Zhang et al. On supporting containment queries in relational database management systems. In SIGMOD Conference, 2001.

Digital Library

Cited By

Zhou JBao ZWang WZhao JMeng X(2014)Efficient query processing for XML keyword queries based on the IDList indexThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-013-0313-223:1(25-50)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1007/s00778-013-0313-2
Fisher DLam FShui WWong R(2006)Dynamic labeling schemes for ordered XML based on type informationProceedings of the 17th Australasian Database Conference - Volume 4910.5555/1151736.1151743(59-68)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.5555/1151736.1151743
Silberstein AHe HYi KYang J(2005)BOXesProceedings of the 21st International Conference on Data Engineering10.1109/ICDE.2005.29(285-296)Online publication date: 5-Apr-2005
https://dl.acm.org/doi/10.1109/ICDE.2005.29
Show More Cited By

Index Terms

Efficient ordering for XML data
1. Information systems
  1. Data management systems
    1. Database management system engines

Recommendations

Mapping of bibliographical standards into XML

The most popular bibliographical standards, which prescribe the exchange of bibliographical data in machine readable form, are MARC (Machine Readable Cataloguing) and UNIMARC (Universal Machine Readable Cataloguing). This paper presents two schemas, ...
An Efficient Schema-Based Technique for Querying XML Data

As data integration over the Web has become an increasing demand, there is a growing desire to use XML as a standard format for data exchange. For sharing their grammars efficiently, most of the XML documents in use are associated with a document ...
Reformulating XPath queries and XSLT queries on XSLT views

Applications using XML for data representation very often use different XML formats and thus require the transformation of XML data. The common approach transforms entire XML documents from one format into another, e.g. by using an XSLT stylesheet. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '03: Proceedings of the twelfth international conference on Information and knowledge management

November 2003

592 pages

ISBN:1581137230

DOI:10.1145/956863

General Chair:
Donald Kraft
Louisiana State University
,
Program Chairs:
Ophir Frieder
Illinois Institute of Technology
,
Joachim Hammer
University of Florida
,
Sajda Qureshi
University of Nebraska, Omaha
,
Len Seligman
The MITRE Corporation

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: 03 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 3 - 8, 2003

LA, New Orleans, USA

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

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

5
Total Citations
View Citations
1,275
Total Downloads

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

Reflects downloads up to 27 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhou JBao ZWang WZhao JMeng X(2014)Efficient query processing for XML keyword queries based on the IDList indexThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-013-0313-223:1(25-50)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1007/s00778-013-0313-2
Fisher DLam FShui WWong R(2006)Dynamic labeling schemes for ordered XML based on type informationProceedings of the 17th Australasian Database Conference - Volume 4910.5555/1151736.1151743(59-68)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.5555/1151736.1151743
Silberstein AHe HYi KYang J(2005)BOXesProceedings of the 21st International Conference on Data Engineering10.1109/ICDE.2005.29(285-296)Online publication date: 5-Apr-2005
https://dl.acm.org/doi/10.1109/ICDE.2005.29
El-Sayed MDimitrova KRundensteiner E(2005)Efficiently supporting order in XML query processingData & Knowledge Engineering10.1016/j.datak.2004.11.00154:3(355-390)Online publication date: 1-Sep-2005
https://dl.acm.org/doi/10.1016/j.datak.2004.11.001
El-Sayed MDimitrova KRundensteiner EChiang RLaender ALim E(2003)Efficiently supporting order in XML query processingProceedings of the 5th ACM international workshop on Web information and data management10.1145/956699.956731(147-154)Online publication date: 7-Nov-2003
https://dl.acm.org/doi/10.1145/956699.956731

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