Efficient Processing of XML Tree Pattern Queries

Yangjun Chen; Dunren Che

doi:10.20965/jaciii.2006.p0738

single-jc.php

« previous

JACIII Vol.10 No.5 pp. 738-743

doi: 10.20965/jaciii.2006.p0738

(2006)

Paper:

Views over last 60 days: 449

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(n²) 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] J. McHugh and J. Widom, “Query Optimization for XML,” Proceedings of the 25th VLDB Conference, Edinburgh, Scotland, 1999.
[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] P. T. Woo, “Minimizing Simple XPath Expressions,” WebDB 2001.
[4] G. Miklau and D. Suciu, “Containment and Equivalence for an XPath Fragment,” Proceedings of 21st ACM Symp., Principles of Database Systems, 2002.
[5] D. Chamberlin, J. Clark, D. Florescu, and M. Stefanescu, “XQuery1.0: An XML Query Language,”
http://www.w3.org/TR/query-datamodel/.
[6] A. Deutch, M. Fernandex, D. Florescu, A. Levy, and D. Suciu, “A Query Language for XML,” WWW’99.
[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] D. Che and K. Aberer, “Query Processing and Optimization in XML Structured-Document Databases,” The VLDB Journal (in press).
[9] S. Flesca, F. Furfaro, and E. Masciari, “On the Minimization of Xpath Queries,” Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003.
[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] C. Yu and L. Popa, “Constraint-Based XML Query Rewriting for Data Integration,” Proceedings of the ACM SIGMOD International Conference, Paris, France, 2004.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[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.

Efficient Processing of XML Tree Pattern Queries

Yangjun Chen* and Dunren Che**

Yangjun Chen^* and Dunren Che^**