xml索引与查询的若干关键技术研究

《xml索引与查询的若干关键技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、XML索引与查询的若干关键技术研究ResearchontheKeyTechniquesforXMLIndexandQuery范颖捷导师指导小组成员胡运发教授施伯乐教授胡运发教授葛家翔教授陶晓鹏副教授摘要⋯⋯．．．⋯．⋯．．．．⋯⋯．⋯⋯⋯．．．．⋯⋯．．⋯．．．．⋯⋯．．．．．⋯⋯．．．．⋯⋯．．⋯．⋯．．．．．．⋯⋯．．．⋯．．⋯．⋯⋯．．．⋯I—fIL】EISTRACT⋯⋯⋯．⋯⋯⋯⋯⋯⋯．．⋯⋯⋯⋯⋯⋯⋯⋯．⋯⋯⋯．．⋯⋯．⋯⋯⋯⋯．．．⋯⋯．⋯⋯⋯．⋯⋯⋯．III第一章绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

2、⋯⋯⋯⋯⋯⋯l1．1研究背景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。l1．2研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯21．2．1XML规范与数据⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．21．2．2XML数据模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯31．2．3XML查询模式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．31．2．3．1XMLCR查询模式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯31．2．3．2ⅪⅥL取查询模式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．41．2．4实现XMLCR查询模式的索引技术⋯⋯⋯

3、⋯⋯⋯⋯⋯⋯⋯⋯。61．2．4．1面向XML有向树的节点记录类索引⋯⋯⋯⋯⋯⋯⋯．61．2．4．2面向XML有向图的结构摘要类索引⋯⋯⋯⋯⋯⋯．．101．2．5实现XMLIR查询模式的索引技术⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．131．3存在的问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。141．4本文的研究内容与主要贡献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．151．5本文的组织结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．16第二章支持简单路径查询的半动态XML结构索引⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯182．1引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

4、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．182．2背景知识及相关工作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯202．2．1XML数据模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯202．2．2简单路径表达式及相关概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．2l2．2．3支持简单路径查询的XML结构索引⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯212．2．4面向全文的互关联后继树模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯232．3面向XML数据图的互关联后继树模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．242．4IRST(k)．Index的理论模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

5、。282．4．1IRST(k)．Index的定义和基本理论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯282．4．2IRST(k)．Index的理论创新之处⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯352．5IRST(k)．Index创建算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯362．5．1算法描述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．362．5．2算法复杂度及性能分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．392．6IRST(k)．Index查询算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯40目录2．6．1算法描述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

6、⋯⋯⋯⋯⋯⋯⋯⋯．402．6．2算法复杂度及性能分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．4l2．7IRST(k)．Index更新算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．432．7．1子图增加算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．432．7．2边增加算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。442．8实验结果及分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯452．8．1实验数据集与代价模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯462．8．2IRST(k)．Index创建时间的实验结果与分析⋯⋯⋯⋯⋯⋯⋯⋯482

7、．8．3IRST(k)．Index空间开销的实验结果与分析⋯⋯⋯⋯⋯⋯⋯。492．8．4IRST(k)．Index查询开销的实验结果与分析⋯⋯⋯⋯⋯⋯⋯。502．9本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。5l第三章支持分支路径查询的半动态XML结构索引⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯533．1引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．533．2背景知识及相关工作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。543．2．1XML数据模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯543．2．

8、2分支路径表达式及相关概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。543．2．3支持分支路径查询的XML结构索引⋯⋯⋯⋯⋯⋯⋯⋯⋯。563．3面向XML数据图的互关联后继树模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．573．4IRST(k,／)-Index的基本理论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．603．5IRST(k,0．Ind