Optimizing cursor movement in holistic twig joins

ABSTRACT

Holistic twig join algorithms represent the state of the art for evaluating path expressions in XML queries. Using inverted indexes on XML elements, holistic twig joins move a set of index cursors in a coordinated way to quickly find structural matches. Because each cursor move can trigger I/O, the performance of a holistic twig join is largely determined by how many cursor moves it makes, yet, surprisingly, existing join algorithms have not been optimized along these lines. In this paper, we describe TwigOptimal, a new holistic twig join algorithm with optimal cursor movement. We sketch the proof of TwigOptimal's optimality, and describe how TwigOptimal can use information in the return clause of XQuery to boost its performance. Finally, experimental results are presented, showing TwigOptimal's superiority over existing holistic twig join algorithms.

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: Ziv Bar-Yossef , Marcus Fontoura , Vanja Josifovski, Buffering in query evaluation over XML streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065195]
• 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: Ting Chen , Jiaheng Lu , Tok Wang Ling, On boosting holism in XML twig pattern matching using structural indexing techniques, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066209]
• 5: S. Chien, Z. Vagena, D. Zhang, V. Tsotras, and C. Zaniolo. Efficient structural joins on indexed xml documents. In VLDB, 2002.
• 6: World Wide~Web Consortium. Xquery 1.0: An xml query language, August 2001. http://www.w3.org/TR/xquery/.
• 7: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 8: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 9: 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]
• 10: H. Jiang, H. Lu, W. Wang, and B. C. Ooi. Xr-tree: Indexing xml data for efficient structural join. In ICDE, 2003.
• 11: 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]
• 12: H. Jiang, W. Wang, H. Lu, and J. Yu. Holistic twig joins on indexed xml documents. In VLDB, 2003.
• 13: Vanja Josifovski , Marcus Fontoura , Attila Barta, Querying XML streams, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.197-210, April 2005 [doi>10.1007/s00778-004-0123-7]
• 14: R. Kaushik, R. Krishnamurthy, J. Naughton, and R. Ramakrishnan. On the integration of structure indexes and inverted lists. Submitted for publication.
• 15: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 16: M. Olson, K. Bostic, and M. Seltzer. Berkeley DB. In Summer Usenix Technical Conf., 1999.
• 17: 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]
• 18: Xmark: The xml benchmark project. http://monetdb.cwi.nl/xml/index.html.
• 19: Beverly Yang , Marcus Fontoura , Eugene Shekita , Sridhar Rajagopalan , Kevin Beyer, Virtual cursors for XML joins, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031271]
• 20: 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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Experimentation, Performance

Keywords:
XML, evaluation, indexing, twig joins