On the efficient search of an XML twig query in large DataGuide trees

ABSTRACT

XML (Extensible Mark-up Language) has been embraced as a new approach to data modeling. Nowadays, more and more information is formatted as semi-structured data, e.g., articles in a digital library, documents on the web, and so on. Implementation of an efficient system enabling storage and querying of XML documents requires development of new techniques. Many different techniques of XML indexing have been proposed in recent years.

In the case of XML data, we can distinguish the following trees: an XML tree, a tree of elements and attributes, and a DataGuide, a tree of element tags and attribute names. Obviously, the XML tree of an XML document is much larger than the DataGuide of a given document. Authors often consider DataGuide as a small tree. Therefore, they consider the DataGuide search as a small problem. However, we show that DataGuide trees are often massive in the case of real XML documents. Consequently, a trivial DataGuide search may be time and memory consuming. In this article, we introduce efficient methods for searching an XML twig pattern in large, complex DataGuide trees.

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: Radim Bača , Michal Krátký, A cost-based join selection for XML twig content-based queries, Proceedings of the 2008 EDBT workshop on Database technologies for handling XML information on the web, March 25-25, 2008, Nantes, France [doi>10.1145/1416691.1416696]
• 3: 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]
• 4: 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
• 5: Ting Chen , Jiaheng Lu , Tok Wang Ling, On boosting holism in XML twig pattern matching using structural indexing techniques, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066209]
• 6: Zhiyuan Chen , Johannes Gehrke , Flip Korn , Nick Koudas , Jayavel Shanmugasundaram , Divesh Srivastava, Index Structures for Matching XML Twigs Using Relational Query Processors, Proceedings of the 21st International Conference on Data Engineering Workshops, p.1273, April 05-08, 2005 [doi>10.1109/ICDE.2005.231]
• 7: Chin-Wan Chung , Jun-Ki Min , Kyuseok Shim, APEX: an adaptive path index for XML data, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564706]
• 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: Paolo Ferragina , Roberto Grossi, A fully-dynamic data structure for external substring search, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.693-702, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225287]
• 10: D. Florescu and D. Kossmann. Storing and Querying XML Data using an RDMBS. IEEE Data Engineering Bulletin, 22(3):27--34, 1999.
• 11: 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
• 12: 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]
• 13: Torsten Grust , Maurice van Keulen , Jens Teubner, Staircase join: teach a relational DBMS to watch its (axis) steps, Proceedings of the 29th international conference on Very large data bases, p.524-535, September 09-12, 2003, Berlin, Germany
• 14: H. Jiang, H. Lu, W. Wang, and B. Ooi. XR-Tree: Indexing XML Data for Efficient Structural Join. In Proceedings of International Conference on Data Engineering, ICDE 2003, India. IEEE, 2003.
• 15: 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]
• 16: M. Krátký, R. Bača, and V. Snášel. Implementation of XPath Axes in the Multi-dimensional Approach to Indexing XML Data. In Proceedings of the 18th International Conference on Database and Expert Systems Applications, DEXA 2007, volume LNCS 4653/2007. Springer-Verlag, 2007.
• 17: M. Krátký, J. Pokorný, and V. Snášel. Implementation of XPath Axes in the Multi-dimensional Approach to Indexing XML Data. In Current Trends in Database Technology, EDBT 2004, volume LNCS 3268/2004. Springer-Verlag, 2004.
• 18: M. Krátký, T. Skopal, and V. Snášel. Multidimensional Term Indexing for Efficient Processing of Complex Queries. Kybernetika, Journal, 40(3):381--396, 2004.
• 19: 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
• 20: 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]
• 21: G. Miklau. University of Washington XML repository. http://www.cs.washington.edu/research/xmldatasets/.
• 22: Mirella M. Moro , Zografoula Vagena , Vassilis J. Tsotras, Tree-pattern queries on a lightweight XML processor, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 23: 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
• 24: S. S. Prakas and S. Madria. SUCXENT: An Efficient Path-Based Approach to Store and Query XML Documents. In Proceedings of Database and Expert Systems Applications, DEXA 2004, volume LNCS 3180/2004, pages 285--295. Springer-Verlag, 2004.
• 25: 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]
• 26: W3 Consortium. Extensible Markup Language (XML) 1.0, W3C Recommendation, 10 February 1998, http://www.w3.org/TR/REC-xml.
• 27: W3 Consortium. XQuery 1.0: An XML Query Language, W3C Working Draft, 12 November 2003, http://www.w3.org/TR/xquery/.
• 28: W3 Consortium. XML Path Language (XPath) Version 2.0, W3C Working Draft, 15 November 2002, http://www.w3.org/TR/xpath20/.
• 29: W3 Consortium. XML Schema Part 1: Structure, W3C Recommendation, 2 May 2001, http://www.w3.org/TR/xmlschema-1/.
• 30: 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]
• 31: Y. Wu, J. M. Patel, and H. Jagadish. Structural Join Order Selection for XML Query Optimization. In Proceedings of the 19th International Conference on Data Engineering, ICDE 2003, pages 443--454. IEEE Computer Society, 2003.
• 32: 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
• 33: Ning Zhang , Varun Kacholia , M. Tamer Özsu, A Succinct Physical Storage Scheme for Efficient Evaluation of Path Queries in XML, Proceedings of the 20th International Conference on Data Engineering, p.54, March 30-April 02, 2004

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms

Keywords:
DataGuide, DataGuide searching, XML data indexing, XML tree, XML twig pattern