XPath query evaluation based on the stack encoding

ABSTRACT

The twig join, which is used to find all occurrences of a twig pattern in an XML database, is a core operation for XML query processing. A great many strategies for handling this problem have been proposed and can be roughly classified into two groups. The first group decomposes a twig pattern (a small tree) into a set of binary relationships between pairs of nodes, such as parent-child and ancestor-descendant relations; and transforms a tree matching problem into a series of simple relation look-ups. The second group decomposes a twig pattern into a set of paths. Among all this kind of methods, the approach based on the so-called stack encoding by Bruno et. al. [2] is very interesting, which can represent in linear space a potentially exponential (in the number of query nodes) number of matching paths. However, the available processes for generating such compressed paths suffer some redundancy and can be significantly improved. In this paper, we analyze this method and show that the time complexities of path generation in its two main procedures: PathStack and TwigStack can be reduced from O(m² ·n) to O(m ·n), where m and n are the sizes of the query tree and document tree, respectively. Experiments have been done to compare ours and some existing startegies, which shows that using our method much less time is needed to generate matching paths.

REFERENCES

• 1: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of the 18th International Conference on Data Engineering, p.141, February 26-March 01, 2002
• 2: 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]
• 3: D. D. Chamberlin, J. Clark, D. Florescu and M. Stefanescu. "XQuery1.0: An XML Query Language," http://www.w3.org/TR/query-datamodel/.
• 4: Donald D. Chamberlin , Jonathan Robie , Daniela Florescu, Quilt: An XML Query Language for Heterogeneous Data Sources, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.1-25, May 18-19, 2000
• 5: Songting Chen , Hua-Gang Li , Junichi Tatemura , Wang-Pin Hsiung , Divyakant Agrawal , K. Selçuk Candan, Twig²Stack: bottom-up processing of generalized-tree-pattern queries over XML documents, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 6: A. Dutch, M. Fernandes, D. Florescu, A. Levy, D. Suciu. "A Query Language for XML," WWW'99.
• 7: D. Florescu and D. Kossman, Storing and Querying XML data using an RDMBS, IEEE Data Engineering Bulletin, 22(3):27--34, 1999.
• 8: 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
• 9: 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
• 10: U. of Washington, The Tukwila System, available from http://data.cs.washington.edu/integration/tukwila/.
• 11: U. of Wisconsin, The Niagara System, available from http://www.cs.wisc.edu/niagara/.
• 12: 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]
• 13: Haixun Wang , Xiaofeng Meng, On the Sequencing of Tree Structures for XML Indexing, Proceedings of the 21st International Conference on Data Engineering, p.372-383, April 05-08, 2005 [doi>10.1109/ICDE.2005.98]
• 14: World Wide Web Consortium. XML Path Language (XPath), W3C Recommendation, Version 1.0, November 1999. See http://www.w3.org/TR/xpath.
• 15: World Wide Web Consortium. XQuery 1.0: An XML Query Language, W3C Recommendation, Version 1.0, Dec. 2001. See http://www.w3.org/TR/xquery.
• 16: 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
• 17: U. of Wisconsin, The Niagara System, available from http://www.cs.wisc.edu/niagara/.
• 18: XMARK: The XML-benchmark project, http://monetdb.cwi.nl/xml, 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems; Trees

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Algorithms, Design

Keywords:
XML databases, XML pattern matching, paths, trees, twig joins