A heuristic approach for checking containment of generalized tree-pattern queries

ABSTRACT

Query processing techniques for XML data have focused mainly on tree-pattern queries (TPQs). However, the need for querying XML data sources whose structure is very complex or not fully known to the user, and the need to integrate multiple XML data sources with different structures have driven, recently, the suggestion of query languages that relax the complete specification of a tree pattern. In order to implement the processing of such languages in current DBMSs, their containment problem has to be efficiently solved.

In this paper, we consider a query language which generalizes TPQs by allowing the partial specification of a tree pattern. Partial tree-pattern queries (PTPQs) constitute a large fragment of XPath that flexibly permits the specification of a broad range of queries from keyword queries without structure, to queries with partial specification of the structure, to complete TPQs. We address the containment problem for PTPQs. This problem becomes more complex in the context of PTPQs because the partial specification of the structure allows new, non-trivial, structural expressions to be inferred from those explicitly specified in a query. We show that the containent problem cannot be characterized by homomorphisms between PTPQs, even when PTPQs are put in a canonical form that comprises all derived structural expressions. We provide necessary and sufficient conditions for this problem in terms of homomorphisms between PTPQs and (a possibly exponential number of) TPQs. To cope with the high complexity of PTPQ containment, we suggest a heuristic approach for this problem that trades accuracy for speed. An extensive experimental evaluation of our heuristic shows that our heuristic approach can be efficiently implemented in a query optimizer.

REFERENCES

• 1: World Wide Web Consortium Site. (W3C), http://www.w3c.org
• 2: Sihem Amer-Yahia , SungRan Cho , Laks V. S. Lakshmanan , Divesh Srivastava, Minimization of tree pattern queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.497-508, May 21-24, 2001, Santa Barbara, California, United States
• 3: Sihem Amer-Yahia , SungRan Cho , Divesh Srivastava, Tree Pattern Relaxation, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.496-513, March 25-27, 2002
• 4: Sihem Amer-Yahia , Laks V. S. Lakshmanan , Shashank Pandit, FleXPath: flexible structure and full-text querying for XML, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007581]
• 5: M. Benedikt and I. Fundulaki. XML subtree queries: Specification and composition. In DBPL, 2005.
• 6: Li Chen , Elke A. Rundensteiner, XQuery containment in presence of variable binding dependencies, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060789]
• 7: Sophie Cluet , Pierangelo Veltri , Dan Vodislav, Views in a Large Scale XML Repository, Proceedings of the 27th International Conference on Very Large Data Bases, p.271-280, September 11-14, 2001
• 8: Sara Cohen , Jonathan Mamou , Yaron Kanza , Yehoshua Sagiv, XSEarch: a semantic search engine for XML, Proceedings of the 29th international conference on Very large data bases, p.45-56, September 09-12, 2003, Berlin, Germany
• 9: A. Deutsch and V. Tannen. Containment and integrity constraints for xpath. In KRDB, 2001.
• 10: Xin Dong , Alon Y. Halevy , Igor Tatarinov, Containment of nested XML queries, Proceedings of the Thirtieth international conference on Very large data bases, p.132-143, August 31-September 03, 2004, Toronto, Canada
• 11: Daniela Florescu , Donald Kossmann , Ioana Manolescu, Integrating keyword search into XML query processing, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.119-135, June 2000
• 12: Sudipto Guha , H. V. Jagadish , Nick Koudas , Divesh Srivastava , Ting Yu, Approximate XML joins, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564725]
• 13: V. Hristidis, Y. Papakonstantinou, and A. Balmin. Keyword Proximity Search on XML Graphs. In ICDE, pages 367--378, 2003.
• 14: Yaron Kanza , Yehoshua Sagiv, Flexible queries over semistructured data, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.40-51, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375558]
• 15: Laks V. S. Lakshmanan , Hui Wang , Zheng Zhao, Answering tree pattern queries using views, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 16: Laks V. S. Lakshmanan , Ganesh Ramesh , Hui Wang , Zheng Zhao, On testing satisfiability of tree pattern queries, Proceedings of the Thirtieth international conference on Very large data bases, p.120-131, August 31-September 03, 2004, Toronto, Canada
• 17: Yunyao Li , Cong Yu , H. V. Jagadish, Schema-free XQuery, Proceedings of the Thirtieth international conference on Very large data bases, p.72-83, August 31-September 03, 2004, Toronto, Canada
• 18: Ziyang Liu , Yi Chen, Identifying meaningful return information for XML keyword search, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247518]
• 19: Gerome Miklau , Dan Suciu, Containment and equivalence for an XPath fragment, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543623]
• 20: Frank Neven , Thomas Schwentick, XPath Containment in the Presence of Disjunction, DTDs, and Variables, Proceedings of the 9th International Conference on Database Theory, p.315-329, January 08-10, 2003
• 21: Dan Olteanu, Forward node-selecting queries over trees, ACM Transactions on Database Systems (TODS), v.32 n.1, p.3-es, March 2007 [doi>10.1145/1206049.1206052]
• 22: Dan Olteanu , Holger Meuss , Tim Furche , François Bry, XPath: Looking Forward, Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers, p.109-127, March 24-28, 2002
• 23: Yannis Papakonstantinou , Vasilis Vassalos, Query rewriting for semistructured data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.455-466, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 24: Neoklis Polyzotis , Minos Garofalakis , Yannis Ioannidis, Approximate XML query answers, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007599]
• 25: Prakash Ramanan, Efficient algorithms for minimizing tree pattern queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564726]
• 26: Albrecht Schmidt , Martin L. Kersten , Menzo Windhouwer, Querying XML Documents Made Easy: Nearest Concept Queries, Proceedings of the 17th International Conference on Data Engineering, p.321-329, April 02-06, 2001
• 27: Dimitri Theodoratos , Theodore Dalamagas , Antonis Koufopoulos , Narain Gehani, Semantic querying of tree-structured data sources using partially specified tree patterns, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099729]
• 28: Dimitri Theodoratos , Theodore Dalamagas , Pawel Placek , Stefanos Souldatos , Timos Sellis, Containment of Partially Specified Tree-Pattern Queries, Proceedings of the 18th International Conference on Scientific and Statistical Database Management, p.3-12, July 03-05, 2006 [doi>10.1109/SSDBM.2006.16]
• 29: Dimitri Theodoratos , Stefanos Souldatos , Theodore Dalamagas , Pawel Placek , Timos Sellis, Heuristic containment check of partial tree-pattern queries in the presence of index graphs, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183679]
• 30: Dimitri Theodoratos , Xiaoying Wu, Assigning semantics to partial tree-pattern queries, Data & Knowledge Engineering, v.64 n.1, p.242-265, January, 2008 [doi>10.1016/j.datak.2007.07.002]
• 31: P. T. Wood. Minimising Simple XPath Expressions. In WebDB, pages 13--18, 2001.
• 32: Peter T. Wood, Containment for XPath Fragments under DTD Constraints, Proceedings of the 9th International Conference on Database Theory, p.300-314, January 08-10, 2003

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

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

General Terms:
Experimentation, Languages, Management

Keywords:
partial tree-pattern query, query containment, xml