【作者】 范颖捷；

【导师】 胡运发；

【作者基本信息】 复旦大学 ， 计算机软件与理论， 2008， 博士

【摘要】 随着Internet的快速发展,XML已成为Web数据表示和交换的新标准,越来越多的信息处理系统采用XML文档作为信息存储、交换和发布的载体。与此同时,XML文档结构和用户查询需求也变得越来越复杂,包含大量引用边的图结构XML文档,以及仅包含部分路径信息和关键词的XML IR(Information Retrieval)查询变得越来越普遍,这给XML索引与查询技术提出了严峻的挑战。目前XML索引技术的研究主要集中在3个方面:一是面向XML有向树的节点记录类索引;二是面向XML有向图的结构摘要类索引(即XML结构索引);三是XML数据与全文数据的联合索引。与节点记录类索引相比,后两类索引的研究相对薄弱,索引的整体性能还比较低,离实际应用还存在较大的距离。针对XML结构索引目前存在的主要问题:索引创建时间较长、空间开销较大、查询效率较低以及分支路径查询研究较为薄弱,本文提出了三种高效的结构索引;针对XML数据与全文数据的联合索引目前存在的主要问题:缺少XML数据与全文数据的统一索引模型以及配套的高效协同查询机制,本文提出了一种高效的基于统一索引模型的XML联合索引。本文的研究内容和创新工作主要有以下4点:(1)支持简单路径查询的半动态XML结构索引研究本文在互关联后继树(IRST)的基础上,引入一种新型的相似性约束条件——k阶相似关系,以及结构索引的相似性归并思想,提出了一种基于互关联后继树且支持简单路径查询的高效半动态结构索引——IRST(k)-index,并给出相关算法和理论证明。该索引以互关联后继树为实现方式,以k阶相似关系为相似性约束条件,能高效地查询简单路径表达式。经实验验证,与国际上同类索引相比,该索引的创建速度更快、查询效率更高、空间开销更小。(2)支持分支路径查询的半动态XML结构索引研究本文在IRST(k)-index的基础上,引入一种新型的相似性约束条件——k-l阶相似关系,以及前向、后向相似度的概念,提出了一种基于互关联后继树且支持分支路径查询的高效半动态结构索引——IRST(k,l)-index,并给出相关算法和理论证明。该索引以互关联后继树为实现方式,以k-l阶相似关系为相似性约束条件,能高效地查询分支路径表达式。经实验验证,与国际上同类索引相比,该索引的创建速度更快、查询效率更高、空间开销更小。(3)支持分支路径查询的全动态XML结构索引研究本文在M(k)-index的基础上,引入k-l阶互模拟关系以及前向、后向相似度的概念,提出了一种支持分支路径查询的高效全动态结构索引——MBF(k,l)-index,并给出相关算法和理论证明。该索引以k-l阶互模拟关系为相似性约束条件,不仅能高效地查询分支路径表达式,还能利用频繁查询路径的查询结果来监督和指导索引优化的全过程,从而有效地避免了无关索引和数据节点的过度分裂。经实验验证,与国际上同类索引相比,该索引的查询效率更高、空间开销更小。(4)XML数据与全文数据的联合索引技术研究本文在互关联后继树的基础上,提出了一种XML树型结构与全文数据的统一索引模型——基于后继模式树的互关联区间后继树,建立了一套XML文档的树型结构与文本节点的联合索引机制——XML联合索引,并给出该索引的倒向创建算法和协同查询算法。经实验验证,与国际上同类索引相比,该索引的膨胀比更小、查询效率更高。更多还原

【Abstract】 With the rapid development of Intemet,more and more information processing systems adopt XML documents as carriers for storing,exchanging,and publishing information.XML has become the de facto standard for data representation and exchange on the web.Meanwhile the structure of XML documents and query demand of web users are becoming more complicated.Graph-structured XML documents containing many reference edges and XML IR(i.e.,Information Retrieval) queries with incomplete paths and keywords are getting increasingly commonplace.Thus,XML index and query technologies meet the serious challenge.We classify XML indexes into three categories,node-record-style index for tree-structured XML data,structural-summary-style index(i.e.,structural index) for graph-structured XML data,and XML-FullText-united index.Compared with noderecord-style index,research on the latter two kinds of indexes is relatively weak,and their overall performance is low.A long distance still exists between their current level and actual application.The problems for existing structural indexes are mainly as follows: long create time,large space size,low query performance,and weak research on branching path query.To solve these problems,we propose three efficient structural indexes.In addition,the problem for existing XML-FullText-united indexes is mainly as follows:lack of united index model for XML data and full-text,and its efficient collaborative query mechanism.Therefore,we propose an efficient XML-FullText-united index.Our primary works are as follow:(1) Research on semi-dynamic structural index supporting simple path query.On the basis of Inter-Relevant Successive Trees(IRST),we introduce k-similarity,a new equivalence relation and the idea of similarity merging originated from structural index,and propose IRST(k)-index,an efficient IRST-based semi-dynamic structural index supporting simple path query.Moreover,the related algorithms and theoretical proving are presented.The IRST(k)-index,which uses k-similarity as equivalence relation and is realized by IRST,can evaluate simple path expressions efficiently.Compared with the same kind of indexes,our experiment results show that IRST(k)-index performs more efficiently in terms of space consumption and query performance,while using much less construction time.(2) Research on semi-dynamic structural index supporting branching path query.We introduce k-l-similarity,a new equivalence relation and the notions of backward and forward similarities into IRST(k)-index,and propose IRST(k,l)-index,an efficient IRST-based semi-dynamic structural index supporting branching path query.In addition, the related algorithms and theoretical proving are presented.The IRST(k,l)-index,which uses k-l-similarity as equivalence relation and is implemented by IRST,can evaluate branching path expressions efficiently.Compared with the same kind of indexes,our experiment results show that IRST(k,l)-index performs more efficiently in terms of space consumption and query performance,while using significantly less construction time.(3) Research on full-dynamic structural index supporting branching path query.We introduce the notions of k-l-bisimulation,forward similarity,and backward similarity into M(k)-index,and propose MBF(k,l)-index,an efficient full-dynamic structural index supporting branching path query.Moreover,the related algorithms and theoretical proving are presented.The MBF(k,l)-index,which uses k-l-bisimulation as equivalence relation,can evaluate branching path expressions efficiently.To avoid the over-refinement of irrelevant index and data nodes,the index makes use of the query results of frequent used path expressions(FUP) to refine itself.Compared with the same kind of indexes,our experiment results show that MBF(k,l)-index performs more efficiently in terms of space consumption and query performance.(4) Research on united index for XML data and full-text.On the basis of Inter-Relevant Successive Trees(IRST),we propose a united index model for XML tree structure and full-text,Inter-relevant Interval Successive Trees based on Successive Pattern Trees,and establish a united index mechanism for tree structure and text nodes in XML documents,XML united index.Moreover,the backward construction algorithm and collaborative query algorithm are presented.Compared with the same kind of indexes,our experiment results show that XML united index performs more efficiently in terms of expansion ratio and query performance.更多还原