有效支持XML结构化连接的索引——CATI

结构化连接的效率直接影响着XML查询的性能,目前对XML的结构化连接大多都是基于编码的方法.介绍了一种全新的有效支持XML结构化连接的树索引CATI(compact ancestor tree index)CATI的基本思想是,对于给定的一个祖先后代查询(A-D查询)或Twig查询,遍历XML文档,找出所有的祖先A的实例,用以建立CATI的主干;对于每个A实例,找出它的直接后代D的实例链接在它的后面.因为经典的结构连接算法Stack-Tree算法效率较高且使用较广,因此应用基于CATI的结构连接算法和基于Stack-Tree的结构连接算法就A-D查询和Twig查询做了大量实验.实验结果表明,基于CATI的结构化连接在一般查询情况下性能明显优于基于Stack-Tree的结构化连接.

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.