Accelerating XPath evaluation in any RDBMS

ABSTRACT

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, 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 the child and descendant axes only. The index has been designed with a close eye on the XPath semantics as well as the desire to engineer its internals so that it can be supported well by existing relational database query processing technology: the index (a) permits set-oriented (or, rather, sequence-oriented) path evaluation, and (b) can be implemented and queried using well-established relational index structures, notably B-trees and R-trees.We discuss the implementation of the XPath accelerator on top of different database backends and show that the index performs well on all levels of the memory hierarchy, including disk-based and main-memory based database systems.

REFERENCES

• 1: Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
• 2: Berglund, A., Boag, S., Chamberlin, D., Fernandez, M. F., Kay, M., Robie, J., and Siméon, J. 2002. XML Path Language (XPath) 2.0. Tech. Rep. W3C Working Draft, Version 2.0, World Wide Web Consortium. Aug. http://www.w3.org/TR/xpath20/.
• 3: Boag, S., Chamberlin, D., Fernandez, M., Florescu, D., Robie, J., and Siméon, J. 2002. XQuery 1.0: An XML Query Language. Tech. Rep. W3C Working Draft, World Wide Web Consortium. Aug. http://www.w3.org/TR/xquery.
• 4: Christian Böhm , Stefan Berchtold , Hans-Peter Kriegel , Urs Michel, Multidimensional Index Structures in Relational Databases, Journal of Intelligent Information Systems, v.15 n.1, p.51-70, July—Aug. 2000 [doi>10.1023/A:1008729828172]
• 5: Boncz, P. A. 2002. Monet: A next-generation DBMS kernel for query-intensive applications. Ph.D. dissertation. University of Amsterdam, The Netherlands.
• 6: Peter A. Boncz , Martin L. Kersten, MIL primitives for querying a fragmented world, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.2, p.101-119, October 1999 [doi>10.1007/s007780050076]
• 7: Zhiyuan Chen , H. V. Jagadish , Flip Korn , Nick Koudas , S. Muthukrishnan , Raymond T. Ng , Divesh Srivastava, Counting Twig Matches in a Tree, Proceedings of the 17th International Conference on Data Engineering, p.595-604, April 02-06, 2001
• 8: Edith Cohen , Haim Kaplan , Tova Milo, Labeling dynamic XML trees, 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.543648]
• 9: Brian Cooper , Neal Sample , Michael J. Franklin , Gisli R. Hjaltason , Moshe Shadmon, A Fast Index for Semistructured Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.341-350, September 11-14, 2001
• 10: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 11: Fernandez, M., Marsh, J., and Nagy, M. 2002. XQuery 1.0 and XPath 2.0 Data Model. Tech. Rep. W3C Working Draft, World Wide Web Consortium. Aug. http://www.w3.org/TR/ query-datamodel.
• 12: Florescu, D. and Kossmann, D. 1999. A performance evaluation of alternative mapping schemes for storing XML data in a relational database. Tech. Rep. 3680. INRIA, Rocquencourt, France. May.
• 13: 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
• 14: Gottlob, G., Koch, C., and Pichler, R. 2002. Efficient algorithms for processing XPath queries. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB) (Hong Kong, China). Morgan-Kaufmann, San Francisco, Calif., 95--106.
• 15: 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]
• 16: Grust, T. and van Keulen, M. 2003. Tree awareness for relational database kernels: Staircase join. In Intelligent Search on XML, H. Blanken, H.-J. Schek, and G. Weikum, Eds. Lecture Notes in Computer Science, vol. 2818. Springer-Verlag, Heidelberg, Germany.
• 17: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 18: Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
• 19: Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170403]
• 20: 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]
• 21: Hans-Peter Kriegel , Marco Pötke , Thomas Seidl, Managing Intervals Efficiently in Object-Relational Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.407-418, September 10-14, 2000
• 22: 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
• 23: Olteanu, D., Meuss, H., Furche, T., and Bry, F. 2001. Symmetry in XPath. Tech. Rep. PMS-FB-2001-16. Institute of Computer Science, University of Munich, Munich, Germany.
• 24: Nick Roussopoulos , Daniel Leifker, Direct spatial search on pictorial databases using packed R-trees, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.17-31, May 1985, Austin, Texas, United States
• 25: SAX (Simple API for XML). http://sax.sourceforge.net/.
• 26: Schmidt, A., Waas, F., Kersten, M., Carey, M. J., Manolescu, I., and Busse, R. 2002. XMark: A Benchmark for XML Data Management. In Proceedings of the 28th International Conference on Very Large Databases (VLDB) (Honk Kong, China). Morgan-Kaufmann, San Francisco, Calif., 974--985.
• 27: Jayavel Shanmugasundaram , Kristin Tufte , Chun Zhang , Gang He , David J. DeWitt , Jeffrey F. Naughton, Relational Databases for Querying XML Documents: Limitations and Opportunities, Proceedings of the 25th International Conference on Very Large Data Bases, p.302-314, September 07-10, 1999
• 28: 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
• 29: Yuqing Wu , Jignesh M. Patel , H. V. Jagadish, Estimating Answer Sizes for XML Queries, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.590-608, March 25-27, 2002
• 30: 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:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases; Query processing

General Terms:
Performance, Theory

Keywords:
Main-memory databases, XML, XML indexing, XPath