支持XML数据查询的F&B索引结构的研究

论文摘要

XML(可扩展标记语言),作为网络上数据表示和信息交换的工具,以其自描述性、独立于平台等特点,已经成为新一代的网络语言。随着XML的广泛应用,XML上的索引及其相关技术的研究就显得十分重要。本文以解决XML最重要的结构索引——F&B索引在实际应用中的问题为目标,就F&B索引的创建、存储、执行查询等问题进行了研究。本文的工作及主要贡献包括如下几个方面:首先,从节省内存空间的角度出发,针对XML树模型和有向无环图模型,分别提出了新的F&B索引创建算法SAJ和SAM。理论分析表明树模型上的SAJ算法的空间性能优于现有的算法,有向无环图模型上的SAM算法的时间、空间性能均优于现有的算法。实验结果表明这两个算法是正确、高效的,并且有良好的可扩展性。其次,着眼于F&B索引使用中占用内存空间过大的问题,基于聚簇的思想,提出了一种新的基于磁盘的F&B索引结构——EDF&B索引,大大节省了使用F&B索引所占用的空间代价。实验结果表明,该索引结构的冗余量很小适合实际应用。最后,将现有的F&B索引查询处理算法扩展到EDF&B索引上,提出了基于EDF&B索引的新的查询处理算法,并用实验验证了该算法的高效性和EDF&B索引的有效性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究的目的与意义
• 1.1.1 目的
• 1.1.2 意义
• 1.2 XML 简介
• 1.2.1 XML 及其相关标准
• 1.2.2 XML 及其相关标准
• 1.3 相关工作
• 1.4 本文工作及结构
• 第2章 XML 及F&B 索引预备知识
• 2.1 XML 简介
• 2.1.1 语义标签
• 2.1.2 格式规范的XML
• 2.2 XML 数据模型
• 2.3 XML 查询
• 2.4 F&B 索引的结构性质
• 2.4.1 结构索引
• 2.4.2 F&B 关系
• 2.4.3 F&B 索引
• 2.5 本章小结
• 第3章 树模型上F&B 索引创建算法
• 3.1 引言
• 3.2 预备知识
• 3.2.1 数据模型
• 3.2.2 基于FB 关系的F&B 索引
• 3.3 F&B 索引的创建算法SAJ
• 3.3.1 定义及符号说明
• 3.3.2 SAJ 算法
• 3.3.3 SAJ 算法的分析
• 3.4 实验结果及分析
• 3.4.1 F&B 索引构建所需空间
• 3.4.2 F&B 索引构建时间
• 3.4.3 SAJ 算法可扩展性
• 3.4.4 实验小结
• 3.5 本章小结
• 第4章 有向无环图模型上F&B 索引创建算法
• 4.1 引言
• 4.2 预备知识
• 4.2.1 XML 有向无环图模型
• 4.2.2 XML 有向无环图的流模型
• 4.2.3 F&B 索引
• 4.2.4 PT 算法
• 4.3 SAM 算法
• 4.3.1 SAM 算法概览
• 4.3.2 扫描和划分
• 4.3.3 合并
• 4.3.4 构建F&B 索引
• 4.4 SAM 算法的分析
• 4.4.1 SAM 算法的正确性
• 4.4.2 SAM 算法的复杂性分析
• 4.5 实验
• 4.5.1 实验配置
• 4.5.2 比较实验
• 4.5.3 可扩展性实验
• 4.6 本章小结
• 第5章 磁盘F&B 索引及其查询处理算法
• 5.1 基于磁盘的F&B 索引
• 5.1.1 基本存储结构
• 5.1.2 索引大小测评
• 5.2 基于遍历的BFS 和DFS 算法
• 5.3 基于区间编码的RangeFetch 算法
• 5.4 基于集合交运算的SegSJ 算法
• 5.5 自底向上的BTU 算法
• 5.6 实验及其分析
• 5.6.1 同其他系统性能比较
• 5.6.2 BTU 算法同其它遍历方法的比较
• 5.7 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢