More Web Proxy on the site http://driver.im/

Article

Accelerating XPath location steps

Author:

Torsten GrustAuthors Info & Claims

SIGMOD '02: Proceedings of the 2002 ACM SIGMOD international conference on Management of data

Pages 109 - 120

https://doi.org/10.1145/564691.564705

Published: 03 June 2002 Publication History

Abstract

This work is a proposal for a database index structure that has been specifically designed to support the evaluation of XPath queries. As such, the index is capable to support all XPath axes (including ancestor, following, preceding-sibling, descendant-or-self, etc.). This feature lets the index stand out among related work on XML indexing structures which had a focus on regular path expressions (which correspond to the XPath axes children and descendant-or-self plus name tests). Its ability to start traversals from arbitrary context nodes in an XML document additionally enables the index to support the evaluation of path traversals embedded in XQuery expressions. Despite its flexibility, the new index can be implemented and queried using purely relational techniques, but it performs especially well if the underlying database host provides support for R-trees. A performance assessment which shows quite promising results completes this proposal.

References

[1]

Anders Berglund, Scott Boag, Don Chamberlin, Mary F. Fernandez, Michael Kay, Jonathan Robie, and Jérôme Siméon. XML Path Language (XPath) 2.0. Technical Report W3C Working Draft, Version 2.0, World Wide Web Consortium, December 2001. http://www.w3.org/TR/xpath20/.]]

[2]

Christian Böhm, Stefan Berchtold, Hans-Peter Kriegel, and Urs Michel. Multidimensional Index Structures in Relational Databases. Journal of Intelligent Information Systems (JIIS), 15(1):51-70, 2000.]]

Digital Library

[3]

John Bosak. XML markup of Shakespeare's plays, January 1998. http://www.ibiblio.org/pub/sun-info/standards/xml/eg/.]]

[4]

Don Chamberlin, James Clark, Daniela Florescu, Jonathan Robie, Jérôme Siméon, and Mugur Stefanescu. XQuery 1.0: An XML Query Language. Technical Report W3C Working Draft, World Wide Web Consortium, December 2001. http://www.w3.org/TR/xquery.]]

[5]

Zhiyuan Chen, H. V. Jagadish, Flip Korn, Nick Koudas, S. Muthukrishnan, Raymond Ng, and Divesh Srivastava. Counting Twig Matches in a Tree. In Proc. of the 17th Int'l Conference on Data Engineering (ICDE), pages 595-604, Heidelberg, Geramny, April 2001. IEEE Computer Society.]]

Digital Library

[6]

Brain F. Cooper, Neal Sample, Michael J. Franklin, Gisli R. Hjaltason, and Moshe Shadmon. A Fast Index for Semistructured Data. In Proc. of the 27th Int'l Conference on Very Large Data Bases (VLDB), pages 341-360, Rome, Italy, September 2001.]]

Digital Library

[7]

Paul F. Dietz and Daniel D. Sleator. Two Algorithms for Maintaining Order in a List. In Conference Record of the 19th Annual ACM Symposium on Theory of Computing (STOC), pages 365-372, New York City, May 1987. ACM Press.]]

Digital Library

[8]

Daniela Florescu and Donald Kossmann. A Performance Evaluation of Alternative Mapping Schemes for Storing XML Data in a Relational Database. Technical Report 3680, INRIA, Rocquencourt, France, May 1999.]]

[9]

Roy Goldman and Jennifer Widom. DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. In Proc. of the 23rd Int'l Conference on Very Large Databases (VLDB), pages 436-445, Athens, Greece, August 1997.]]

Digital Library

[10]

Antonin Guttman. R-Trees: A Dynamic Index Structure for Spatial Searching. In SIGMOD 1984, Proc. of Annual Meeting, pages 47-57, Boston, Massachusetts, June 1984. ACM Press.]]

Digital Library

[11]

Joseph M. Hellerstein, Jeffrey F. Naughton, and Avi Pfeffer. Generalized Search Trees for Database Systems. In Proc. of the 21st Int'l Conference on Very Large Databases (VLDB), pages 562-573, Zurich, Switzerland, September 1995.]]

Digital Library

[12]

Ibrahim Kamel and Christos Faloutsos. On Packing R-Trees. In Proc. of the 2nd Int'l Conference on Information and Knowledge Management (CIKM), pages 490-499, Washington DC, USA, November 1993.]]

Digital Library

[13]

Hans-Peter Kriegel, Marco Pötke, and Thomas Seidl. Managing Intervals Efficiently in Object-Relational Databases. In Proc. of the 26th Int'l Conference on Very Large Databases (VLDB), pages 407-418, Cairo, Egypt, September 2000.]]

Digital Library

[14]

Quanzhong Li and Bongki Moon. Indexing and Querying XML Data for Regular Path Expressions. In Proc. of the 27th Int'l Conference on Very Large Data Bases (VLDB), pages 361-370, Rome, Italy, September 2001.]]

Digital Library

[15]

SAX (Simple API for XML). http://sax.sourceforge.net/.]]

[16]

Albrecht R. Schmidt, Florian Waas, Martin L. Kersten, Daniela Florescu, Ioana Manolescu, Michael J. Carey, and Ralph Busse. The XML Benchmark Project. Technical Report INS-R0103, CWI, Amsterdam, The Netherlands, April 2001.]]

Digital Library

[17]

Dan Suciu and Tova Milo. Index Structures for Path Expressions. In Proc. of the 7th Int'l Conference on Database Theory (ICDT), number 1540 in Lecture Notes in Computer Science (LNCS), pages 277-295, Jerusalem, Israel, January 1999. Springer Verlag.]]

Digital Library

[18]

Chun Zhang, Jeffrey Naughton, David DeWitt, Qiong Luo, and Guy Lohman. On Supporting Containment Queries in Relational Database Management Systems. In Proc. of the ACM SIGMOD Int'l Conference on Management of Data, pages 425-436, Santa Barbara, California, May 2001. ACM Press.]]

Digital Library

Cited By

Fent PMoerkotte GNeumann T(2023)Asymptotically Better Query Optimization Using Indexed AlgebraProceedings of the VLDB Endowment10.14778/3611479.361150516:11(3018-3030)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611505
Hao WMatsuzaki KSato S(2021)A Dual-Index Based Representation for Processing XPath Queries on Very Large XML DocumentsCloud Computing10.1007/978-3-030-69992-5_2(18-30)Online publication date: 13-Feb-2021
https://doi.org/10.1007/978-3-030-69992-5_2
Olteanu D(2020)The relational data borg is learningProceedings of the VLDB Endowment10.14778/3415478.341557213:12(3502-3515)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3415478.3415572
Show More Cited By

Index Terms

Accelerating XPath location steps

Recommendations

Accelerating XPath evaluation in any RDBMS

This article is a proposal for a database index structure, the XPath accelerator, that has been specifically designed to support the evaluation of XPath path expressions. As such, the index is capable to support all XPath axes (including ancestor, ...
A new structure for accelerating XPath location steps
WAIM '06: Proceedings of the 7th international conference on Advances in Web-Age Information Management

Multidimensional indices have been successfully introduced to the field of querying on XML data. Using R*-tree, T. Grust proposed an interesting method to support all XPath axes. In that method, each node of an XML document is labeled with a five-...
Meta-data indexing for XPath location steps
SIGMOD '06: Proceedings of the 2006 ACM SIGMOD international conference on Management of data

XML is the de facto standard for data representation and exchange over the Web. Given the diversity of the information available in XML, it is very useful to annotate XML data with a wide variety of meta-data, such as quality and sensitivity. When ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '02: Proceedings of the 2002 ACM SIGMOD international conference on Management of data

June 2002

654 pages

ISBN:1581134975

DOI:10.1145/564691

Conference Chair:
Bongki Moon
University of Wisconsin - Madison
,
General Chair:
David DeWitt
University of Wisconsin - Madison
,
Program Chair:
Michael Franklin
University of California, Berkeley

Copyright © 2002 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 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS02

Sponsor:

SIGMOD/PODS02: International Conference on Management of Data and Symposium on Principles Database and Systems

June 3 - 6, 2002

Wisconsin, Madison

Acceptance Rates

SIGMOD '02 Paper Acceptance Rate 42 of 240 submissions, 18%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

283
Total Citations
View Citations
1,681
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fent PMoerkotte GNeumann T(2023)Asymptotically Better Query Optimization Using Indexed AlgebraProceedings of the VLDB Endowment10.14778/3611479.361150516:11(3018-3030)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611505
Hao WMatsuzaki KSato S(2021)A Dual-Index Based Representation for Processing XPath Queries on Very Large XML DocumentsCloud Computing10.1007/978-3-030-69992-5_2(18-30)Online publication date: 13-Feb-2021
https://doi.org/10.1007/978-3-030-69992-5_2
Olteanu D(2020)The relational data borg is learningProceedings of the VLDB Endowment10.14778/3415478.341557213:12(3502-3515)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3415478.3415572
Perlasca PFrasca MBa CGliozzo JNotaro MPennacchioni MValentini GMesiti M(2020)Multi-resolution visualization and analysis of biomolecular networks through hierarchical community detection and web-based graphical toolsPLOS ONE10.1371/journal.pone.024424115:12(e0244241)Online publication date: 22-Dec-2020
https://doi.org/10.1371/journal.pone.0244241
Khamis MCurtin RMoseley BNgo HNguyen XOlteanu DSchleich M(2020)Functional Aggregate Queries with Additive InequalitiesACM Transactions on Database Systems10.1145/342686545:4(1-41)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.1145/3426865
Kocher DAugsten NBoncz PManegold SAilamaki ADeshpande AKraska T(2019)A Scalable Index for Top-k Subtree Similarity QueriesProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3319892(1624-1641)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3319892
Bahta RAtay MLo DKim DGamess E(2019)Translating JSON Data into Relational Data Using Schema-oblivious ApproachesProceedings of the 2019 ACM Southeast Conference10.1145/3299815.3314467(233-236)Online publication date: 18-Apr-2019
https://dl.acm.org/doi/10.1145/3299815.3314467
Abo Khamis MCurtin RMoseley BNgo HNguyen XOlteanu DSchleich MSuciu DSkritek SKoch C(2019)On Functional Aggregate Queries with Additive InequalitiesProceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3294052.3319694(414-431)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3294052.3319694
Kohn ALeis VNeumann T(2018)Adaptive Execution of Compiled Queries2018 IEEE 34th International Conference on Data Engineering (ICDE)10.1109/ICDE.2018.00027(197-208)Online publication date: Apr-2018
https://doi.org/10.1109/ICDE.2018.00027
Grust TJagadish HÖzcan FYu C(2018)XQuery ProcessorsEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_800(4846-4852)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_800
Show More Cited By

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.

Media

Figures

Other

Tables

View Table of Contents