MTree: an XML XPath graph index

ABSTRACT

This paper introduces the MTree index algorithm, a special purpose XML XPath index designed to meet the needs of the hierarchical XPath query language. With the increasing importance of XML, XPath, and XQuery, several methods have been proposed for creating XML structure indexes and many variants using relational technology have been proposed. This work proposes a new XML structure index, called MTree, which is designed to be optimal for traversing all XPath axes. The primary feature of MTree lies in its ability to provide the next subtree root node in document order, for all axes, to each context node in O(1). MTree is a special purpose XPath index structure that matches the special purpose query requirements for XPath. This approach is in contrast to other approaches that map the problem domain into general purpose index structures such as B-Tree that must reconstruct the XML tree from those structures for every query. MTree supports modification operations such as insert and delete. MTree has been implemented both in memory and on disk, and performance results using XMark benchmark data are presented showing up to two orders of magnitude improvement over other well-known implementations.

REFERENCES

• 1: Anders Berglund, Scott Boag, Don Chamberlin, Mary F. Fernández, Michael Kay, Jonathan Robie, Jérôme Siméon. XML Path Language (XPath) 2.0 W3C Working Draft 29 October 2004, http://www.w3.org/TR/xpath20/
• 2: Torsten Grust, Accelerating XPath location steps, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564705]
• 3: R. J. Bayardo , D. Gruhl , V. Josifovski , J. Myllymaki, An evaluation of binary xml encoding optimizations for fast stream based xml processing, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988719]
• 4: Peter Buneman, Martin Grohe, Ghristoph Kock. Path Queries on Compressed XML. Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003.
• 5: 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]
• 6: Rajasekar Krishnamurthy, Raghav Kaushik, and Jeffery F. Naughton. XML-to-SQL Query Translation Literature: The State of the Art and Open Problems, XML Symposium (XSym) 2003, pages 1--18 http://www.cs.wisc.edu/~sekar/publications.html
• 7: Mary Fernandez and Jerome Simeon. Growing XQuery. ECOOP 2003 - Object-Oriented Programming, 17th European Conference, Darmstadt, Germany, July 21--25, 2003, Proceedings, pages 405--430
• 8: Xeres2 Java Parser http://xml.apache.org/xerces2-j/
• 9: Sax Document Tracer Example http://xml.apache.org/xerces2-j/samples-sax.html
• 10: Michael Stoner. Portable Performance Measurement Macros for Intel Architecture. http://www.intel.com/cd/ids/developer/asmona/eng/microprocessors/ia32/pentium4/optimization/19949.htm?page=1
• 11: XMark---An XML Benchmark Project. http://monetdb.cwi.nl/xml/index.ht
• 12: Georg Gottlob, Christoph Koch, Reinhard Pickler. Efficient Algorithms for Processing XPath Queries. Proceedings of the 28th VLDB Conference, Hong Kong, China, 2002
• 13: Xalan-Java version 2.6.0. http://xml.apache.org/xalan-j
• 14: 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
• 15: Saxon-B 8.1.1. http://saxon.sourceforge.net/
• 16: S. Al-Khalifa, H. V. Jagadish, J. M. Patel, Y. Wu, N. Koudas, and D. Srivastava. Structural joins: a primitive for efficient XML query pattern matching, pages 141--152, ICDE, 2002
• 17: Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543620]
• 18: Eclipse IDE. http://www.eclipse.org/
• 19: 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]
• 20: Jason McHugh , Jennifer Widom, Query Optimization for XML, Proceedings of the 25th International Conference on Very Large Data Bases, p.315-326, September 07-10, 1999
• 21: 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]
• 22: Raghav Kaushik , Rajasekar Krishnamurthy , Jeffrey F. Naughton , Raghu Ramakrishnan, On the integration of structure indexes and inverted lists, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007656]
• 23: Amelie Marian and Jerome Simeon. Projecting XML Documents. Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003
• 24: Zhiyuan Chen , Chen Li , Jian Pei , Yufei Tao , Haixun Wang , Wei Wang , Jiong Yang , Jun Yang , Donghui Zhang, Recent progress on selected topics in database research: a report by nine young Chinese researchers working in the United States, Journal of Computer Science and Technology, v.18 n.5, p.538-552, September 2003
• 25: Thomas Schwentick, XPath query containment, ACM SIGMOD Record, v.33 n.1, March 2004 [doi>10.1145/974121.974140]
• 26: Hanyu Li , Mong Li Lee , Wynne Hsu , Chao Chen, An evaluation of XML indexes for structural join, ACM SIGMOD Record, v.33 n.3, September 2004 [doi>10.1145/1031570.1031576]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
  E.5 FILES
      Subjects: Organization/structure

General Terms:
Algorithms

Keywords:
XML, XPath, graph, index, threaded paths