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

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

作　　者：于亚新[1] 王国仁[1] 张海宁[1] 李建新[1] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110004

出　　处：《计算机研究与发展》2007年第1期111-118,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60573089)

摘　　要：结构化连接的效率直接影响着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的结构化连接.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 ancestordescendant 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.

关 键 词：XML 结构化连接 紧凑祖先树索引 祖先后代查询 TWIG查询 Stack—Tree 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]