Virtual cursors for XML joins

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: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 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: Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 9: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 10: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 11: Lin Guo , Feng Shao , Chavdar Botev , Jayavel Shanmugasundaram, XRANK: ranked keyword search over XML documents, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872762]
• 12: H. Jiang, H. Lu, W. Wang, and B. C. Ooi. Xr-tree: Indexing xml data for efficient structural join. In ICDE, 2003.
• 13: Haifeng Jiang , Hongjun Lu , Wei Wang, Efficient processing of XML twig queries with OR-predicates, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007578]
• 14: H. Jiang, W. Wang, H. Lu, and J. Yu. Holistic twig joins on indexed xml documents. In VLDB, 2003.
• 15: Raghav Kaushik , Philip Bohannon , Jeffrey F Naughton , Henry F Korth, Covering indexes for branching path queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564707]
• 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: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceeding of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 19: M. Olson, K. Bostic, and M. Seltzer. Berkeley DB. In Summer Usenix Technical Conf., 1999.
• 20: Igor Tatarinov , Stratis D. Viglas , Kevin Beyer , Jayavel Shanmugasundaram , Eugene Shekita , Chun Zhang, Storing and querying ordered XML using a relational database system, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564715]
• 21: Haixun Wang , Sanghyun Park , Wei Fan , Philip S. Yu, ViST: a dynamic index method for querying XML data by tree structures, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872774]
• 22: Xmark: The xml benchmark project. http://monetdb.cwi.nl/xml/index.html.
• 23: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Experimentation, Performance

Keywords:
XML, evaluation, indexing, join operator