Efficient Processing of XML Tree Pattern Queries
Yangjun Chen* and Dunren Che**
*Department of Applied Computer Science, University of Winnipeg, 515 Portage Avenue, Winnipeg, Manitoba R3B 2E9, Canada
**Department of Computer Science, Southern Illinois University, Carbondale, IL 62901, USA
In this paper, we present a polynomial-time algorithm for TPQ (tree pattern queries) minimization without XML constraints involved. The main idea of the algorithm is a dynamic programming strategy to find all the matching subtrees within a TPQ. A matching subtree implies a redundancy and should be removed in such a way that the semantics of the original TPQ is not damaged. Our algorithm consists of two parts: one for subtree recognization and the other for subtree deletion. Both of them needs only O(n2) time, where n is the number of nodes in a TPQ.
-  J. McHugh and J. Widom, “Query Optimization for XML,” Proceedings of the 25th VLDB Conference, Edinburgh, Scotland, 1999.
-  S. Amer-Yahia et al., “Minimization of TPQs,” Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 497-508, 2001.
-  P. T. Woo, “Minimizing Simple XPath Expressions,” WebDB 2001.
-  G. Miklau and D. Suciu, “Containment and Equivalence for an XPath Fragment,” Proceedings of 21st ACM Symp., Principles of Database Systems, 2002.
-  D. Chamberlin, J. Clark, D. Florescu, and M. Stefanescu, “XQuery1.0: An XML Query Language,”
-  A. Deutch, M. Fernandex, D. Florescu, A. Levy, and D. Suciu, “A Query Language for XML,” WWW’99.
-  S. Al-Khalifa, H. V. Jagadish, N. Koudas, J. M. Patel, D. Srivastava, and Y. Wu, “Structural Joins: A Primitive for Efficient XML Query Pattern Matching,” Proceedings of the 18th International Conference on Data Engineering, 2002.
-  D. Che and K. Aberer, “Query Processing and Optimization in XML Structured-Document Databases,” The VLDB Journal (in press).
-  S. Flesca, F. Furfaro, and E. Masciari, “On the Minimization of Xpath Queries,” Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003.
-  D. Lee and W. W. Chu, “Constraints-preserving Transformation from XML Document Type Definition to Relational Schema,” Proceedings of the 19th International Conference on Conceptual Modeling, pp. 323-338, 2000.
-  C. Yu and L. Popa, “Constraint-Based XML Query Rewriting for Data Integration,” Proceedings of the ACM SIGMOD International Conference, Paris, France, 2004.