基于自动机的XPath查询模型研究

论文摘要

随着XML数据在互联网络上应用的不断增长，对庞大的XML数据流的查询正成为数据查询领域内研究的热点。XML流的查询问题主要归结到XPath的查询，而如何高效的处理XPath表达式中的谓词则是XPath查询研究中需要解决的关键问题。将自动机技术引入到XPath查询领域，解决谓词处理中的难题是目前国内外研究的重要方向之一。本文首先对自动机技术在XPath查询中的应用进行了研究，而后提出了一个基于交错自动机(AFA)的XPath处理模型XBA。XBA对AFA的转移函数进行了改写，充分利用AFA表达and／or语义的特性处理谓词，并采用逆向分析的方法构造转移函数，减少了自动机运行中产生的中间状态数。实验结果表明XBA可以提高XPath表达式中谓词处理的效率。在论文的最后，针对XPath表达式中由于出现表示节点间不确定语义的标识符“//”和“*”，而造成转换状态增加、降低查询效率的问题，提出了一种基于XML Schema的逻辑优化技术，它利用XML Schema的约束使XPath表达式确定化。理论分析和实验结果表明，优化后的XBA处理效率高于优化前的效率。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 研究的现实意义
• 1.3 国内外研究现状
• 1.4 本文所作工作
• 1.5 本文组织结构
• 2 XML及XML流
• 2.1 XML
• 2.2 XML流
• 2.3 XML的解析模型
• 3 XML查询规范
• 3.1 XPath
• 3.2 XQuery
• 4 基于自动机的XPath查询处理模型
• 4.1 自动机概述
• 4.2 自动机技术用于XPath查询
• 4.2.1 FSM
• 4.2.2 NFA
• 4.2.3 DFA
• 4.2.4 AFA
• 4.2.5 TA
• 5 基于AEA的XPath查询模型
• 5.1 模型提出
• 5.2 XBA构造及运行实例
• 5.2.1 构造单个XPath的XBA模型
• 5.2.2 构造多个XPath表达式的XBA模型
• 5.3 实现算法
• 5.4 实验结果及性能分析
• 5.4.1 实验数据和环境
• 5.4.2 性能分析
• 6 XPath查询优化
• 6.1 问题的提出
• 6.2 目前的研究
• 6.3 XML验证机制与模式
• 6.3.1 DTD与XML Schema
• 6.4 基于XML Schema的XPath重写优化
• 6.4.1 有向图
• 6.4.2 重写优化
• 6.4.3 实现算法
• 6.5 实验结果及性能分析
• 6.5.1 实验数据和环境
• 6.5.2 性能分析
• 7 总结与展望
• 参考文献
• 致谢
• 附录一 攻读学位期间发表的论文