论文题目: XML索引和过滤查询若干关键技术研究
论文类型: 博士论文
论文专业: 计算机软件与理论
作者: 雷向欣
导师: 胡运发
关键词: 模式,索引,查询,过滤,互关联后继树模型,叶序区间
文献来源: 复旦大学
发表年度: 2005
论文摘要: XML(eXtensible Markup Language)作为网络数据交换和信息集成的工具,以其自描述性、跨平台交换性等特点,成为新一代的网络语言。互联网上越来越多的结构化或半结构化的数据采用XML格式存储和交换,对XML数据的索引及过滤查询研究显得日益重要。 本文根据XML数据的自身特点和当前实际应用需求,就索引和过滤查询的一些关键技术进行了研究,具体包括XML文档索引查询技术研究、XML文档树节点编码研究、遵循不同模式XML数据集索引模型、集群式XPath查询优化、XML数据过滤查询技术研究、XML文档索引和过滤查询原型系统的实现等方面,所做的工作和取得的创新成果体现在以下五个方面: 1) 基于互关联后继树的XML文档索引技术研究 基于叶序区间编码方法(LOINS)与互关联后继树模型(IRST)为节点带有名称(标签)的根树建立索引模型。结合IRST的标引性、可压缩性等特点,本文提出了基于IRST的根树索引模型IsBaRTI-Ⅰ,及该模型的空间优化模型IsBaRTI-Ⅱ。IsBaRTI-Ⅰ,Ⅱ采用树节点名称(标签)及其在根树(XML文档树)中的出现计数索引节点间的父子关系和节点叶序区间编码,实现索引结构和节点编码的相互统一。理论和实验证明,在对XML路径表达式的查询处理中,和以往同类索引模型相比,IsBaRTI-Ⅰ,Ⅱ索引建立时间、空间代价小,而且可快速查询满足XPath表达式在XML文档树中的节点序列和路径。 2) XML文档树节点叶序区间动态编码研究 在XML索引上采用树节点编码可快速判断树节点间的前后代关系,树节点编码代价影响着索引的空间代价和驻留内存空间的难易程度。区别于以往同类索引模型研究仅仅注重提高查询效率的片面性,本文针对Web上XML文档特点,就本文索引技术中的树节点叶序区间编码和其它树节点编码方法,如:顺序标识区间编码、前缀编码等进行比较。相比其它树节点编码方法,本文提出的叶序区间编码方法编码长度代价小、编码灵活机动性强(可通过IsBaRTI-Ⅱ在索引结构中动态查找)。我们提出的根树索引模型IsBaRTI-Ⅱ动态查找叶序区间编码的平均时间代价随着S/H(S为根树Tr节点出度;H为Tr高度)递增而递减且趋近于1,而Web上XML文档树普遍具有的S>>H的特点为基于IsBaRTI-Ⅱ实现的XML索引模型动态查找叶序区间编码提供了实际应用可行性。就树节点叶序区间编码的维护,本文提出了基于XML模式扩展叶序区间编码的方法,降低XML文档树节点插入时的索引中节点编码维护代价,为基于叶序区间编码的XML索引模型提供了编码维护方案。
论文目录:
摘要
ABSTRACT
目录
第1章 绪论
1.1 研究目的与意义
1.1.1 研究背景
1.1.2 研究目的
1.1.3 研究理论价值
1.2 XML简介
1.2.1 XML及其相关技术标准
1.2.2 XML的应用
1.3 相关研究工作综述
1.3.1 XML查询研究的主要领域
1.3.2 XML文档索引查询
1.3.3 XML文档过滤查询
1.4 本文工作
1.4.2 研究内容
1.4.3 本文结构
第2章 基于互关联后继树的XML索引技术
2.1 引言
2.2 相关研究
2.2.1 树节点的编码
2.2.2 XML的索引方法
2.3 基于叶序区间的节点编码方法
2.4 根树的互关联后继树索引模型
2.5 算法
2.5.1 索引建立算法
2.5.2 基于IsBaRTI-I的路径连接算法
2.5.3 XPath表达式在XML中对应路径的查询算法
2.5.4 形如“a/*”和“a/b[n]”的XPath表达式查询
2.6 索引模型的空间优化
2.7 实验评价
2.7.1 索引的建立
2.7.2 XPath查询测试
2.8 小结
附录：XISS索引结构示意图
第3章 XML树节点叶序区间动态编码
3.1 引言
3.2 相关研究
3.3 编码长度代价
3.4 编码动态查找
3.5 编码动态维护
3.6 小结
第4章 XML数据集索引和集群式查询
4.1 引言
4.2 相关研究
4.3 XML模式信息的提取
4.4 基于互关联后继树和模式的XML索引模型
4.4.1 简化模式合并树
4.4.2 索引结构
4.4.3 索引维护
4.5 XPATH的解析及查询处理
4.5.1 XPath表达式的解析
4.5.2 XPath查询处理思路
4.5.3 XPath查询处理实现方法
4.6 集群式XPATH查询优化处理
4.6.1 集群式查询处理思路
4.6.2 集群式查询处理实现方法
4.7 实验评价
4.7.1 XML数据集
4.7.2 XPath表达式查询测试
4.7.3 集群式XPath查询处理测试
4.8 小结
第5章 基于叶序区间编码机制的XML过滤算法
5.1 引言
5.2 相关研究
5.3 基本概念
5.3.1 叶序区间长度编码
5.3.2 基于NFA的XML文档过滤模型
5.3.3 文档过滤模型的执行
5.4 基于叶序区间编码的XML过滤改进算法
5.4.1 NFA叶节点绑定查询提交表
5.4.2 文档过滤模型的改进执行过程
5.5 基于叶序区间长度编码的XML过滤改进算法
5.5.1 NFA节点叶序提交计数表
5.5.2 文档过滤模型的改进执行过程
5.6 实验评价
5.7 小结
第6章 XML索引和过滤查询原型系统
6.1 引言
6.2 一个集成的XML索引和过滤查询系统框架模型
6.3 原型系统
6.3.1 数据存储
6.3.2 系统设计及运行机制
6.4 小结
第7章 总结与展望
7.1 总结
7.2 进一步的工作
参考文献
参与的科研项目与发表的论文
1.参与的科研项目
2.发表的论文
致谢
论文独创性声明
发布时间: 2005-09-19
相关论文
- [1].基于关系数据库的XML数据存储、更新和检索[D]. 胥正川.复旦大学2003
- [2].XML引擎研究[D]. 向桂林.中国科学院研究生院（文献情报中心）2004
- [3].基于约束的XML数据库模式规范化研究[D]. 张忠平.复旦大学2004
- [4].XML约束在XML数据存储、发布和转换中的应用[D]. 王庆.复旦大学2004
- [5].XML数据库查询及其模式集成研究[D]. 徐德智.中南大学2004
- [6].XML路径表达式优化及其查询和过滤计算方法[D]. 朱茂盛.中国科学院研究生院（计算技术研究所）2004
- [7].XML路径查询处理关键技术研究[D]. 王静.中国科学院研究生院（计算技术研究所）2003