Sequencing XML data and query twigs for fast pattern matching

ABSTRACT

We propose a new way of indexing XML documents and processing twig patterns in an XML database. Every XML document in the database can be transformed into a sequence of labels by prüfer's method that constructs a one-to-one correspondence between trees and sequences. During query processing, a twig pattern is also transformed into its Prüfer sequence. By performing subsequence matching on the set of sequences in the database and performing a series of refinement phases that we have developed, we can find all the occurrences of a twig pattern in the database. Our approach allows holistic processing of a twig pattern without breaking the twig into root-to-leaf paths and processing these paths individually. Furthermore, we show in the article that all correct answers are found without any false dismissals or false alarms. Experimental results demonstrate the performance benefits of our proposed techniques.

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: Berglund, A., Boag, S., Chamberlin, D., Fernandez, M. F., Kay, M., Robie, J., and Simon, J. 2002. XML path language (XPath) 2.0 W3C working draft 16. Tech. Rep. WD-xpath20-20020816, World Wide Web Consortium. (Aug.).
• 3: Boag, S., Chamberlin, D., Fernandez, M. F., Florescu, D., Robie, J., and Simon, J. 2002. XQuery 1.0: An XML Query Language W3C working draft 16. Tech. Rep. WD-xquery-20020816, World Wide Web Consortium. (Aug.).
• 4: Bray, T., Paoli, J., Sperberg-McQueen, C. M., and Maler, E. 2000. Extensible markup language (XML) 1.0 2nd Ed. W3C recommendation. Tech. Rep. REC-xml-20001006, World Wide Web Consortium. (Oct.).
• 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: Catherine Bow, B. H. and Bird, S. 2003. Towards a general model of Interlinear text. In Proceedings of EMELD Workshop. Lansing, MI.
• 7: Chien, S.-Y., Vagena, Z., Zhang, D., Tsotras, V. J., and Zaniolo, C. 2002. Efficient structural joins on indexed XML documents. In Proceedings of the 28th VLDB Conference. Morgan-Kaufmann, Hong Kong, China. 263--274.
• 8: 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
• 9: Paul F. Dietz, Maintaining order in a linked list, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.122-127, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802184]
• 10: 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
• 11: 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]
• 12: Grust, T., van Keulen, M., and Teubner, J. 2003. Staircase join: Teach a relational DBMS to watch its (axis) steps. In Proceedings of the 29th VLDB Conference. Morgan-Kaufmann, Berlin, Germany. 524--535.
• 13: 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
• 14: Jiang, H., Lu, H., Wang, W., and Ooi, B. C. 2003. XR-Tree: Indexing XML data for efficient structural joins. In Proceedings of the 19th IEEE International Conference on Data Engineering. IEEE Computer Society, Bangalore, India. 253--264.
• 15: Jiang, H., Wang, W., Lu, H., and Yu, J. X. 2003. Holistic twig joins on indexed XML documents. In Proceedings of the 29th VLDB Conference. Morgan-Kaufmann, Berlin, Germany. 273--284.
• 16: 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]
• 17: Exploiting Local Similarity for Indexing Paths in Graph-Structured Data, Proceedings of the 18th International Conference on Data Engineering, p.129, February 26-March 01, 2002
• 18: 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
• 19: 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
• 20: 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
• 21: Müller, K. 2004. Semi-automatic construction of a question treebank. In Proceedings of the 4th International Conference on Language Resources and Evaluation. Lisbon, Portugal.
• 22: Svetlozar Nestorov , Jeffrey D. Ullman , Janet L. Wiener , Sudarshan S. Chawathe, Representative Objects: Concise Representations of Semistructured, Hierarchial Data, Proceedings of the Thirteenth International Conference on Data Engineering, p.79-90, April 07-11, 1997
• 23: Prüfer, H. 1918. Neuer Beweis eines Satzes über Permutationen. Archiv für Mathematik und Physik 27, 142--144.
• 24: Praveen Rao , Bongki Moon, PRIX: Indexing And Querying XML Using Prüfer Sequences, Proceedings of the 20th International Conference on Data Engineering, p.288, March 30-April 02, 2004
• 25: UW XML Repository. 2002. http://www.cs.washington.edu/research/xmldatasets.
• 26: 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]
• 27: William D. Lewis. 2005. Personal communications. http://zimmer.csufresno.edu/ wlewis/.
• 28: XRel: a path-based approach to storage and retrieval of XML documents using relational databases, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.110-141, Aug. 2001 [doi>10.1145/383034.383038]
• 29: Zezula, P., Mandreoli, F., and Martoglia, R. 2004. Tree signatures and unordered XML pattern matching. In Proceedings of the 32nd International Conference on Current Trends in Theory and Practice of Computer Science. Springer, Merin, Czech Republic. 122--139.
• 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:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Markup languages

General Terms:
Algorithms, Languages, Theory

Keywords:
XML indexing, prüfer sequences, twig query processing