An efficient algorithm for tree pattern query minimization under broad integrity constraints

Abstract

Purpose

Tree pattern is at the core of XML queries. The tree patterns in XML queries typically contain redundancies, especially when broad integrity constraints (ICs) are present and considered. Apparently, tree pattern minimization has great significance for efficient XML query processing. Although various minimization schemes/algorithms have been proposed, none of them can exploit broad ICs for thoroughly minimizing the tree patterns in XML queries. The purpose of this research is to develop an innovative minimization scheme and provide a novel implementation algorithm.

Design/methodology/approach

Query augmentation/expansion was taken as a necessary first‐step by most prior approaches to acquire XML query pattern minimization under the presence of certain ICs. The adopted augmentation/expansion is also the course for the typical O(n⁴) time‐complexity of the proposed algorithms. This paper presents an innovative approach called allying to effectively circumvent the otherwise necessary augmentation step and to retain the time complexity of the implementation algorithm within the optimal, i.e. O(n²). Meanwhile, the graph simulation concept is adapted and generalized to a three‐tier definition scheme so that broader ICs are incorporated.

Findings

The innovative allying minimization approach is identified and an effective implementation algorithm named AlliedMinimize is developed. This algorithm is both runtime optimal – taking O(n²) time – and most powerful in terms of the broadness of constraints it can exploit for XML query pattern minimization. Experimental study confirms the validity of the proposed approach and algorithm.

Research limitations/implications

Though the algorithm AlliedMinimize is so far the most powerful XML query pattern minimization algorithm, it does not incorporate all potential ICs existing in the context of XML. Effectively integrating this innovative minimization scheme into a fully‐fledged XML query optimizer remains to be investigated in the future.

Practical implications

In practice, Allying and AlliedMinimize can be used to achieve a kind of quick optimization for XML queries via fast minimization of the tree patterns involved in XML queries under broad ICs.

Originality/value

This paper presents a novel scheme and an efficient algorithm for XML query pattern minimization under broad ICs.

Citation

Che, D. (2007), "An efficient algorithm for tree pattern query minimization under broad integrity constraints", International Journal of Web Information Systems, Vol. 3 No. 3, pp. 231-256. https://doi.org/10.1108/17440080710834265