基于互关联后继树的XML索引技术  

XML Indexing Technology Based on IRST

作　　者：雷向欣[1] 胡运发[1] 杨智应[1] 刘勇[1] 张凯[1] 

机构地区：[1]复旦大学计算机与信息技术系,上海200433

出　　处：《计算机研究与发展》2005年第7期1261-1271,共11页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60473070);国家"八六三"高技术研究发展计划基金项目(2001AA115020)

摘　　要：提出了一种新的根树节点编码方法———基于叶序区间的节点编码(LOINS).编码方法只需对根树后序遍历一次即可完成,能实现常数时间内对任意两个树节点间前后代关系的判断.同时,结合互关联后继树模型(IRST)的标引性、可压缩性等特点,提出基于IRST的根树索引模型IsBaRTII,及对该模型空间优化的索引模型IsBaRTIII.IsBaRTII,II采用树节点名称(标签)及其在根树(XML文档树)中的出现计数索引节点间的父子关系和节点叶序区间编码,实现索引结构和节点编码的相互统一.IsBaRTII,II索引建立时间、空间代价小,可快速查询满足XPath表达式在XML文档树中的节点序列和路径.A new numbering scheme for labeling rooted trees based on leaf order interval numbering scheme (LOINS) is proposed. The nodes in a rooted tree can be encoded in once traversal of the tree, and the ancestor-descendantship among nodes can be determined in constant time based on LOINS. Furthermore, IsBaRTI-I, a novel index for rooted tree structure data model, is proposed which takes the advantages of IRST, such as indexing and compressibility. IsBaRTI-II, the space optimization version of IsBaRTI-I, is also introduced. IsBaRTI-I,II indexes the ancestor-descendantship among nodes and the LOINS number of node by the name (label) of the node and the count of its appearance in the rooted tree. In this way, indexing structure and numbering scheme becomes a unit unity. Theory analysis and experiment result illustrates that IsBaRTI-I,II needs more little time and capacity to be built; the node series and path matching XPath expressions can be obtained more quickly than the previous XML indexes through IsBaRTI-I,II.

关 键 词：XML XPATH 互关联后继树 索引 查询 

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