基于区间编码的XML索引结构的有效结构连接  

Indexing XML Data Based on Region Coding for Efficient Processing of Structural Joins

作　　者：万常选[1] 刘云生[2] 徐升华[1] 刘喜平[1] 林大海[1] 

机构地区：[1]江西财经大学信息管理学院,南昌330013 [2]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机学报》2005年第1期113-127,共15页Chinese Journal of Computers

基　　金：江西省自然科学基金项目 (0 4110 0 9);江西省教育厅科技项目 (赣财教[2 0 0 3 ] 73号 )资助 .

摘　　要：该文给出了一个XML树数据模型的形式化定义 .将编码方案、逆序列表和路径索引的思想相结合 ,提出了一种改进的XML数据的索引结构 ;给出了两个实现双亲 /孩子关系和拥有关系的结构连接算法 ,它们最多只需要对参与连接的两个列表分别进行一次扫描 ,并且能够根据双亲结构信息等利用B+ 树索引尽可能多地跳过不需要参与连接的元素结点 .实验结果表明 ,该文给出的基于XML索引结构实现双亲 /孩子关系和拥有关系的结构连接算法是高效的、健壮的 .Firstly, this paper gives a formal definition of XML tree data model in context environment. Secondly, it proposes an improved index structure to retrieve XML data based on the idea of the numbering scheme, the inverted list and the path index. This index structure can process XQuery path expressions via two methods: Stepwise structural join method and path method. Furthermore, it enables us to quickly determine ancestor/descendant relationships and parent/child relationships between any pair of nodes in the XML trees, thus can efficiently process containment joins in XQuery path expression queries and keyword searches. Finally, this paper presents two algorithms for processing structural joins of parent/child relationship and holding relationship, which lead to optimal join performance by avoiding scanning on each list joined repeatedly and omitting the examination of elements, which do not participate in the join, via B+-tree index based on parent's information and etc. Experimental results have showed that the structural join algorithms for processing parent/child relationships and holding relationships based on the proposed XML index structure are effective, efficient and robust.

关 键 词：XML数据模型 XML索引结构 区间编码 结构连接 拥有关系 

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