JACIII Vol.10 No.5 pp. 738-743
doi: 10.20965/jaciii.2006.p0738


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

October 28, 2005
March 17, 2006
September 20, 2006
XML documents, tree pattern queries, Xpath expressions, query evaluation

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.

Cite this article as:
Yangjun Chen and Dunren Che, “Efficient Processing of XML Tree Pattern Queries,” J. Adv. Comput. Intell. Intell. Inform., Vol.10, No.5, pp. 738-743, 2006.
Data files:
  1. [1] J. McHugh and J. Widom, “Query Optimization for XML,” Proceedings of the 25th VLDB Conference, Edinburgh, Scotland, 1999.
  2. [2] S. Amer-Yahia et al., “Minimization of TPQs,” Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 497-508, 2001.
  3. [3] P. T. Woo, “Minimizing Simple XPath Expressions,” WebDB 2001.
  4. [4] G. Miklau and D. Suciu, “Containment and Equivalence for an XPath Fragment,” Proceedings of 21st ACM Symp., Principles of Database Systems, 2002.
  5. [5] D. Chamberlin, J. Clark, D. Florescu, and M. Stefanescu, “XQuery1.0: An XML Query Language,”
  6. [6] A. Deutch, M. Fernandex, D. Florescu, A. Levy, and D. Suciu, “A Query Language for XML,” WWW’99.
  7. [7] 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.
  8. [8] D. Che and K. Aberer, “Query Processing and Optimization in XML Structured-Document Databases,” The VLDB Journal (in press).
  9. [9] S. Flesca, F. Furfaro, and E. Masciari, “On the Minimization of Xpath Queries,” Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003.
  10. [10] 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.
  11. [11] C. Yu and L. Popa, “Constraint-Based XML Query Rewriting for Data Integration,” Proceedings of the ACM SIGMOD International Conference, Paris, France, 2004.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Mar. 05, 2021