A cost-based join selection for XML twig content-based queries

ABSTRACT

XML (Extensible Mark-up Language) has been embraced as a new approach to data modeling. Nowadays, more and more information is formated 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 during recent years. If we consider some classes of indexing methods, we distinguish two kinds of joins for processing twig queries. The first join merges two sets retrieved from an inverted list. The second join applies the first query result in building the second query. Although authors propose improvements of their joins, there has not yet been a discussion about the advantages of applying various join operations. In this article, we propose a join selection based on the cost of a join. By choosing a more appropriate join operation, twig query processing efficiency is significantly improved.

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: Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
• 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: Flavius Frasincar , Geert-Jan Houben , Cristian Pau, XAL: an algebra for XML query optimization, Proceedings of the 13th Australasian database conference, p.49-56, January 01, 2002, Melbourne, Victoria, Australia
• 10: 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
• 11: Alan Halverson , Josef Burger , Leonidas Galanis , Ameet Kini , Rajasekar Krishnamurthy , Ajith Nagaraja Rao , Feng Tian , Stratis D. Viglas , Yuan Wang , Jeffrey F. Naughton , David J. DeWitt, Mixed mode XML query processing, Proceedings of the 29th international conference on Very large data bases, p.225-236, September 09-12, 2003, Berlin, Germany
• 12: W. H. Hanyu Li, Mong Li Lee. A Path-Based Labeling Scheme for Efficient Structural Join. In Proceedings of XSym 2005, pages 34--48. Springer--Verlag, 2005.
• 13: Theo Härder , Michael Haustein , Christian Mathis , Markus Wagner, Node labeling schemes for dynamic XML documents reconsidered, Data & Knowledge Engineering, v.60 n.1, p.126-149, January, 2007 [doi>10.1016/j.datak.2005.11.008]
• 14: Haifeng Jiang , Wei Wang , Hongjun Lu , Jeffrey Xu Yu, Holistic twig joins on indexed XML documents, Proceedings of the 29th international conference on Very large data bases, p.273-284, September 09-12, 2003, Berlin, Germany
• 15: 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.
• 16: 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.
• 17: 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
• 18: Jiaheng Lu , Tok Wang Ling , Chee-Yong Chan , Ting Chen, From region encoding to extended dewey: on efficient processing of XML twig pattern matching, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 19: 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]
• 20: N. May, M. Brantner, A. Böhm, C.-C. Kanne, and G. Moerkotte. Index vs. Navigation in XPath Evaluation. In Proceedings of Database and XML Technologies, XSym 2006, volume LNCS 4156/2006, pages 16--30. Springer--Verlag, 2006.
• 21: Neoklis Polyzotis , Minos Garofalakis, Structure and value synopses for XML data graphs, Proceedings of the 28th international conference on Very Large Data Bases, p.466-477, August 20-23, 2002, Hong Kong, China
• 22: Neoklis Polyzotis , Minos Garofalakis, XSKETCH synopses for XML data graphs, ACM Transactions on Database Systems (TODS), v.31 n.3, p.1014-1063, September 2006 [doi>10.1145/1166074.1166082]
• 23: Hanan Samet, Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 24: A. R. Schmidt and at al. The XML Benchmark. Technical Report INS-R0103, CWI, The Netherlands, April, 2001, http://monetdb.cwi.nl/xml/.
• 25: 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
• 26: 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.
• 27: 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]
• 28: M. van Keulen. Relational Approach to Logical Query Optimization of XPath. In Proceedings of the 1st Twente Data Management Workshop, TDM'04, pages 57--63, 2004.
• 29: W3 Consortium. XQuery 1.0: An XML Query Language, W3C Working Draft, 12 November 2003, http://www.w3.org/TR/xquery/.
• 30: W3 Consortium. XML Path Language (XPath) Version 2.0, W3C Working Draft, 15 November 2002, http://www.w3.org/TR/xpath20/.
• 31: 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
• 32: 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.
• 33: 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.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms

Keywords:
XML twig queries, content-based queries, cost-based join selection