XML数据查询中值匹配查询代价估计

论文摘要

近年来,XML(Extensible Markup Language)己经成为互联网上数据发布和数据交换的事实标准并受到越来越多的关注。虽然XML查询技术己经取得一些研究成果,但由于XML文档自身的特点,XML查询技术在理论上和实现上都还存在很多难点。本文对XML查询技术进行深入研究,对XML数据查询算法研究现状、发展以及应用进行了分析和总结。特别是分析了XML查询优化技术的XML统计数据模型、XML数据在数据库中的存储、XML数据的解析和查询处理的方法。目前已经提出了多种XML数据查询的方法,但是对于复杂的XML数据分布还考虑不周全,使得操作效率很低。本文分别从一维选择估计和多维选择估计两个方面详细阐述了选择估计技术,结合实际中XML的特点,提出了用多维直方图统计XML数据,并取得了简化操作的结果。XML数据中的值信息分布不仅与其他值信息分布相关,还与XML数据中的结构信息相关,而且当XML数据结构比较复杂时,会形成高维元素,导致存储量和错误率大幅上升,因此本文提出了用离散余弦转换方法(DCT)处理XML数据统计,并根据XML数据的高相关性,扩展了DCT到高维,得到了高维DCT方程。使得查询统计的错误率大大减小,并且在时间和空间上都有很大的节省。对一种方法的提出,要考虑详细周全的实验验证,在试验中所有的数据都被生成在(0,l)n正态分布中,合成的数据大小为50k,维数范围从2到10维,从一般分布、Zipf分布和集簇分布,三个数据分布分别来验证(1)存储需求和选择性估计时间;(2)维数和查询大小的影响;(3)数据分布影响。实验结果:1)以前的方法不能支持多维选择性估计,特别是三维以上时候错误率很大。本文提出的方法支持高维选择性估计精度高。2)提出的方法节省时间和空间。3)提出的方法消除了估算的选择的周期性重建统计的消耗,因为它可以反映动态数据更新并且立即统计。4)提出的方法使用了余弦计算,使得问题简单化,计算快速,并且因为离散余弦变换支持相邻的桶之间的篡改,使得能够快速准确的估计计算。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 XML 的提出
• 1.1.2 XML 数据的特征
• 1.2 本领域发展概况
• 1.2.1 直方图对XML 统计的研究
• 1.2.2 查询代价估计问题
• 1.3 本文研究内容
• 第二章 多维直方图处理XML 数据
• 2.1 XML 数据模型
• 2.1.1 OEM 模型
• 2.1.2 DOM 模型
• 2.2 XML 查询语言
• 2.2.1 XPath
• 2.2.2 XQuery
• 2.3 XML 文档在数据库中的存储
• 2.3.1 当前数据库的 XML 文档存储方式
• 2.3.2 混合型XML 存储结构
• 2.4 XML 解析器
• 2.5 多维直方图处理XML 数据的提出
• 2.6 多维直方图及直方图压缩
• 2.6.1 多维直方图
• 2.6.2 压缩直方图
• 2.7 本章小结
• 第三章 DCT 方法处理高维直方图
• 3.1 一维选择估计
• 3.2 多维选择估计
• 3.3 离散余弦变换方法及其高维扩展
• 3.3.1 离散余弦变换（DCT）的定义
• 3.3.2 DCT 的扩展
• 3.4 本章小结
• 第四章 DCT 处理直方图实验
• 4.1 选择性估计的范围查询以及维数和查询范围的影响
• 4.1.1 选择性估计的范围查询
• 4.1.2 维数和查询大小的影响
• 4.2 存储需求和选择性估计时间
• 4.3 数据分布及其影响
• 4.3.1 数据分布
• 4.3.2 数据分布影响
• 4.4 动态数据更新
• 4.5 实验总结
• 第五章 总结与展望
• 5.1 总结
• 5.2 未来的方向
• 参考文献
• 致谢
• 研究生期间发表的论文