An Index for Supporting XML Structural Join Efficiently and Effectively—CATI

Evaluating structural joins is a crucial operation for performance of XML queries. Proposed in this paper is a novel index CATI, namely, compact ancestor tree index, which can support XML structural join effectively. The basic idea of CATI is to extract ancestor node occurrences from a given ancestor-descendant query (A-D query) pattern or a twig query pattern to establish a compact ancestor tree, and all descendant occurrences of an ancestor node will be linked behind the direct ancestor node in the ancestor tree. Since the stack-tree based join algorithm is a widely used technique due to its excellent join efficiency, the performance of CATI is compared with stack-tree for A-D query and twig query via extensive experiments on a real XML test database. The experimental results show that the performance of the CATI based structural join has significant improvement gains over the stack-tree based join.