Print

基于自动机的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 总结与展望
  • 参考文献
  • 致谢
  • 附录一 攻读学位期间发表的论文

    • 相关论文文献

    本文来源: https://www.lw50.cn/article/4693894b78a61589041057f1.html