Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

With the growing importance of semi-structure data in information exchange, much research has been done to provide an effective mechanism to match a twig query in an XML database. A number of algorithms have been proposed recently to process a twig query holistically. Those algorithms are quite efficient for quires with only ancestor-descendant edges. But for queries with mixed ancestor-descendant and parent-child edges, the previous approaches still may produce large intermediate results, even when the input and output size are more manageable. To overcome this limitation, in this paper, we propose a novel holistic twig join algorithm, namely <i>TwigStackList</i>. Our main technique is to look-ahead read some elements in input data steams and cache limited number of them to <i>lists</i> in the main memory. The number of elements in any list is bounded by the length of the longest path in the XML document. We show that <i>TwigStackList</i> is I/O optimal for queries with only ancestor-descendant relationships below branching nodes. Further, even when queries contain parent-child relationship below branching nodes, the set of intermediate results in <i>TwigStackList</i> is guaranteed to be a subset of that in previous algorithms. We complement our experimental results on a range of real and synthetic data to show the significant superiority of <i>TwigStackList</i> over previous algorithms for queries with <i>parent</i>-<i>child</i> relationships.

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: A. Berglund , S. Boag , D. Chamberlin, M. F. Fernandez, M. Kay, J. Robie, J. Simeon "XML Path Language (XPath) 2.0" W3C Working Draft 22 August 2003
• 3: S. Boag, D. Chamberlin, M. F. Fernandez, D. Florescu J. Robie , J. Simeon "Xquery 1.0: An XML QueryW3C" Working Draft 22 August 2003
• 4: N. Bruno, N. Koudas, and D. Srivastava. "Holistic twig joins: Optimal XML pattern matching" Technical Report Columbia University March 2002
• 5: 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]
• 6: Yi Chen , Susan B. Davidson , Yifeng Zheng, BLAS: an efficient XPath processing system, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007577]
• 7: B. Choi, M. Mahoui, D. Wood "On the Optimality of Holistic Algorithms for Twig Queries" DEXA 2003 pages 28--37
• 8: 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
• 9: H. Jiang, W. Wang, H. Lu and J.X. Yu "Holistic twig joins on indexed XML documents" In Proceedings of VLDB 2003 pages 273--284
• 10: H. Jiang, H. Lu, W. Wang, B. C. Ooi "XR-Tree: Indexing XML Data for Efficient Structural Joins" In Proceedings of ICDE 2003, pages 253--263
• 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: 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
• 13: 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]
• 14: Y. Wu, J. M. Patel, H. V. Jagadish "Structural Join Order Selection for XML Query Optimization" ICDE 2003 pages 443--454
• 15: XML-benchmark http://monetdb.cwi.nl/xml
• 16: University of Washington XML Repository. Available from http://www.cs.washington.edu/research/xmldatasets/
• 17: 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 [doi>10.1145/375663.375722]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Performance

Keywords:
XML, holistic twig pattern matching