skip to main content
10.1145/1031171.1031271acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
Article

Virtual cursors for XML joins

Published: 13 November 2004 Publication History

Abstract

Structural joins are a fundamental operation in XML query processing and a large body of work has focused on index-based algorithms for executing them. In this paper, we describe how two well-known index features -- path indices and ancestor information -- can be combined in a novel way to replace one or more of the physical index cursors in a structural join with <i>virtual cursors</i>. The position of a virtual cursor is derived from the path and ancestor information of a physical cursor. Implementation results are provided to show that, by eliminating index I/O, virtual cursors can improve the performance of structural joins by an order of magnitude or more.

References

[1]
S. Al-Khalifa, H. Jagadish, N. Koudas, J. Patel, D. Srivastava, and Y. Wu. Structural joins: A primitive for efficient xml query pattern matching. In ICDE, 2002.]]
[2]
J. Bremer and M. Gertz. On distributing xml repositories. In WebDB, 2003.]]
[3]
N. Bruno, N. Koudas, and D. Srivastava. Holistic twig joins: Optimal xml pattern matching. In ACM SIGMOD, 2002.]]
[4]
S. Chien, Z. Vagena, D. Zhang, V. Tsotras, and C. Zaniolo. Efficient structural joins on indexed xml documents. In VLDB, 2002.]]
[5]
World Wide Web Consortium. Xquery 1.0: An xml query language, August 2001. http://www.w3.org/TR/xquery/.]]
[6]
Extended technical report. Available upon request.]]
[7]
Marcus Fontoura, Jason Zien, Eugene Shekita, Sridhar Rajagopalan, and Andreas Neumann. High performance index build algorithms for intranet search engines. In VLDB, 2004.]]
[8]
H. Garcia-Molina, J. Ullman, and J. Widom. Database System Implementation. Prentice Hall, 2000.]]
[9]
R. Goldman and J. Widom. Dataguides: enabling query formulation and optimization in semistructured databases. In VLDB, 1997.]]
[10]
G.Salton and M. J. McGill. Introduction to modern information retrieval. McGraw-Hill, 1983.]]
[11]
L. Guo, F. Shao, C. Botev, and J. Shanmugasundaram. Xrank: Ranked keyword search over xml documents. In SIGMOD, 2003.]]
[12]
H. Jiang, H. Lu, W. Wang, and B. C. Ooi. Xr-tree: Indexing xml data for efficient structural join. In ICDE, 2003.]]
[13]
H. Jiang, W. Wang, and H. Lu. Efficient processing of xml twig queries with or-predicates. In SIGMOD, 2004.]]
[14]
H. Jiang, W. Wang, H. Lu, and J. Yu. Holistic twig joins on indexed xml documents. In VLDB, 2003.]]
[15]
R. Kaushik, P. Bohannon, J. Naughton, and H.F. Korth. Covering indexes for branching path queries. In SIGMOD, 2002.]]
[16]
R. Kaushik, P. Bohannon, J. Naughton, and P. Shanoy. Updates for structure indexes. In VLDB, 2002.]]
[17]
R. Kaushik, R. Krishnamurthy, J. Naughton, and R. Ramakrishnan. On the integration of structure indexes and inverted lists. Submitted for publication.]]
[18]
T. Milo and D. Suciu. Index structures for path expressions. In ICDT, 1999.]]
[19]
M. Olson, K. Bostic, and M. Seltzer. Berkeley DB. In Summer Usenix Technical Conf., 1999.]]
[20]
I. Tatarinov, S. Viglas, K. Beyer, J. Shanmugasundaram, E. Shekita, and C. Zhang. Storing and querying ordered xml using a relational dbms. In SIGMOD, 2002.]]
[21]
H. Wang, S. Park, W. Fan, and P. Yu. Vist: A dynamic index method for querying xml data by tree structures. In SIGMOD, 2003.]]
[22]
Xmark: The xml benchmark project. http://monetdb.cwi.nl/xml/index.html.]]
[23]
C. Zhang, J. Naughton, D. DeWitt, Q. Luo, and G. Lohman. On supporting containment queries in relational database management systems. In SIGMOD, 2001.]]

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
CIKM '04: Proceedings of the thirteenth ACM international conference on Information and knowledge management
November 2004
678 pages
ISBN:1581138741
DOI:10.1145/1031171
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: 13 November 2004

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. XML
  2. evaluation
  3. indexing
  4. join operator

Qualifiers

  • Article

Conference

CIKM04
Sponsor:
CIKM04: Conference on Information and Knowledge Management
November 8 - 13, 2004
D.C., Washington, USA

Acceptance Rates

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

Upcoming Conference

CIKM '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Structural XML Query ProcessingACM Computing Surveys10.1145/309579850:5(1-41)Online publication date: 26-Sep-2017
  • (2013)Optimizing XML queriesInformation Systems10.1016/j.is.2013.02.00338:6(863-884)Online publication date: 1-Sep-2013
  • (2013)Optimal and efficient generalized twig pattern processingThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-012-0295-522:3(369-393)Online publication date: 1-Jun-2013
  • (2012)XML query processingProceedings of the 16th International Database Engineering & Applications Sysmposium10.1145/2351476.2351478(8-13)Online publication date: 8-Aug-2012
  • (2012)Processing and Evaluating Partial Tree Pattern Queries on XML DataIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2011.13724:12(2244-2259)Online publication date: 1-Dec-2012
  • (2011)Indexing and querying XML using extended Dewey labeling schemeData & Knowledge Engineering10.1016/j.datak.2010.08.00170:1(35-59)Online publication date: 1-Jan-2011
  • (2010)Linear computation of the maximum simultaneous forward and backward bisimulation for node-labeled treesProceedings of the 7th international XML database conference on Database and XML technologies10.5555/1888011.1888016(18-32)Online publication date: 17-Sep-2010
  • (2010)Towards unifying advances in twig join algorithmsProceedings of the Twenty-First Australasian Conference on Database Technologies - Volume 10410.5555/1862242.1862252(57-66)Online publication date: 1-Jan-2010
  • (2010)Fast optimal twig joinsProceedings of the VLDB Endowment10.14778/1920841.19209553:1-2(894-905)Online publication date: 1-Sep-2010
  • (2010)XPath query processing improvementsProceedings of the 2010 Conference of the Center for Advanced Studies on Collaborative Research10.1145/1923947.1923957(86-99)Online publication date: 1-Nov-2010
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media