Minimization of tree pattern queries with constraints

ABSTRACT

Tree pattern queries (TPQs) provide a natural and easy formalism to query tree-structured XML data, and the efficient processing of such queries has attracted a lot of attention. Since the size of a TPQ is a key determinant of its evaluation cost, recent research has focused on the problem of query minimization using integrity constraints to eliminate redundant query nodes; specifically, TPQ minimization has been studied for the class of forward and subtype constraints (FT-constraints). In this paper, we explore the TPQ minimization problem further for a richer class of FBST-constraints that includes not only FT-constraints but also backward and sibling constraints. By exploiting the properties of minimal queries under FBST-constraints, we propose efficient algorithms to both compute a single minimal query as well as enumerate all minimal queries. In addition, we also develop more efficient minimization algorithms for the previously studied class of FT-constraints. Our experimental study demonstrates the effectiveness and efficiency of query minimization using FBST-constraints.

REFERENCES

• 1: The protein sequence database mark-up language. http://pir.georgetown.edu/pirwww/xml/psdml.dtd.
• 2: The DBLP XML records. http://dblp.uni-trier.de/xml/.
• 3: The Mondial database. http://www.dbis.informatik.uni-goettingen.de/Mondial/.
• 4: Serge Abiteboul , Peter Buneman , Dan Suciu, Data on the Web: from relations to semistructured data and XML, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 5: 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
• 6: Geert Jan Bex , Frank Neven , Thomas Schwentick , Karl Tuyls, Inference of concise DTDs from XML data, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 7: U. Brandes, M. Eiglsperger, I. Herman, M. Himsolt, and M. Marshall. GraphML progress report: Structural layer proposal. LNCS, 2002.
• 8: S. Flesca , F. Furfaro , E. Masciari, On the minimization of Xpath queries, Proceedings of the 29th international conference on Very large data bases, p.153-164, September 09-12, 2003, Berlin, Germany
• 9: Georg Gottlob , Christoph Koch , Reinhard Pichler, Efficient algorithms for processing XPath queries, ACM Transactions on Database Systems (TODS), v.30 n.2, p.444-491, June 2005 [doi>10.1145/1071610.1071614]
• 10: S. Hinkelman. Business integration - information conformance statements (bi-ics). IBM, 2005.
• 11: G. Miklau. The XML data repository. 2002. http://www.cs.washington.edu/research/xmldatasets/.
• 12: Gerome Miklau , Dan Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM (JACM), v.51 n.1, p.2-45, January 2004 [doi>10.1145/962446.962448]
• 13: F. Neven and T. Schwentick. On the complexity of XPath containment in the presence of disjunction, DTD, and variables. LMCS, 2(3), 2006.
• 14: 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]
• 15: A. R. Schmidt , Florian Waas , Martin L. Kersten , D. Florescu , I. Manolescu , M. J. Carey , R. Busse, The XML benchmark project, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2001
• 16: M. Schmidt, S. Scherzinger, and C. Koch. Combined static and dynamic analysis for effective buffer minimization in streaming XQuery evaluation. In ICDE, 2007.
• 17: W3C. XML path language (XPath). 1999. http://www.w3.org/TR/xpath.
• 18: W3C. XQuery 1.0: An XML query language. 2001. http://www.w3.org/TR/xquery.
• 19: P. T. Wood. Minimising simple XPath expressions. In WebDB, 2001.
• 20: 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.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance

Keywords:
chase, integrity constraints, query minimization, simulation, tree pattern queries, xml, xpath