single-jc.php

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

Paper:

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

Received:
October 28, 2005
Accepted:
March 17, 2006
Published:
September 20, 2006
Keywords:
XML documents, tree pattern queries, Xpath expressions, query evaluation
Abstract

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:
Y. Chen and D. Che, “Efficient Processing of XML Tree Pattern Queries,” J. Adv. Comput. Intell. Intell. Inform., Vol.10, No.5, pp. 738-743, 2006.
Data files:
References
  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,”
    http://www.w3.org/TR/query-datamodel/.
  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, IE9,10,11, Opera.

Last updated on Aug. 19, 2019