基于模型检测的Twig模式最小化技术

发布时间：2017-08-12 05:37

  本文关键词：基于模型检测的Twig模式最小化技术

  更多相关文章： Twig模式最小化 模式约束 模型检测

【摘要】：随着互联网的飞速发展,可扩展标记语言XML凭借其跨平台性,兼容性高等诸多优点,成为了互联网数据存储与交换标准,XML数据库已被各大数据库厂商支持。随着大数据时代的到来,如何高效精准获取XML查询请求的结果,成为了新的挑战。Twig查询是XML查询的核心操作。近年来,针对Twig查询优化技术的研究成为了热点。其中,Twig模式最小化是Twig查询优化技术的一个重要方向。Twig模式查询匹配的效率与Twig模式本身的复杂程度关系密切。Twig模式最小化的目的就是查找并消除Twig模式中冗余的子查询。通常针对特定类型的XML数据,Twig模式中一些子查询变得冗余,这些特定的类型信息被称为模式约束。已有的基于模式约束的最小化的研究中,一方面,未考虑路径模式约束,而这种基于路径信息的模式约束,对Twig模式优化是有用的;另一方面,已有工作提出的模式约束提取方法,均为人工编写算法,不易扩展。为了解决上述问题,本文提出了一套模式约束集合,该集合包含路径模式约束。基于该模式约束集合,本文提出了一套优化规则集合,该规则集合可用于Twig模式最小化。为了实现模式约束的自动化识别,提高系统可扩展性,本文提出了一套基于模型检测的Twig模式最小化方法。定义了基于XML Schema的模型检测输入模型STM,并提出了XML Schema到STM的转化方法;同时,给出了模式约束集合的时态逻辑公式描述;并采用成熟的模型检测工具NuSMV,实现了模式约束的自动化识别。实验表明该系统实现了模式约束的自动化识别,通过使用文中的优化规则集合,达到了优化Twig模式中冗余的叶节点和中间节点的目的,提高了Twig模式的查询效率。
【关键词】：Twig模式最小化 模式约束 模型检测
【学位授予单位】：北京工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13
【目录】：

• 摘要4-5
• Abstract5-8
• 第1章 绪论8-14
• 1.1 课题背景8-9
• 1.2 相关研究9-11
• 1.2.1 Twig模式的研究现状9
• 1.2.2 Twig模式最小化的研究现状9-10
• 1.2.3 模型检测的研究现状10-11
• 1.3 本文的研究内容和主要贡献11
• 1.4 本文研究动机及研究意义11-12
• 1.5 课题来源12
• 1.6 本文构成12-14
• 第2章 背景知识14-20
• 2.1 XML模式14-15
• 2.1.1 XML模式定义语言14
• 2.1.2 XML Schema14-15
• 2.2 Twig模式15-16
• 2.3 Twig模式最小化16-17
• 2.4 模型检测17
• 2.5 本章小结17-20
• 第3章 基于模式约束的优化规则20-30
• 3.1 模式约束集合20-22
• 3.2 冗余节点优化规则集合22-25
• 3.3 优化规则调度算法25-26
• 3.4 举例26-28
• 3.5 本章小结28-30
• 第4章 基于模型检测的模式约束识别方法30-41
• 4.1 类型图30-31
• 4.2 基于类型图的XML Schema转换模型31-32
• 4.3 类型图到STM转换算法32-34
• 4.4 模式约束的时态逻辑公式表示34-40
• 4.5 本章小结40-41
• 第5章 系统设计与实现41-48
• 5.1 系统架构设计41
• 5.2 系统数据流图41-42
• 5.3 类体系42-43
• 5.4 重要的算法43-47
• 5.4.1 Twig模式条件算子43-46
• 5.4.2 优化动作算子46-47
• 5.5 本章小结47-48
• 第6章 实验48-52
• 6.1 实验方案48-49
• 6.2 实验结果49-51
• 6.3 本章小结51-52
• 结论52-54
• 参考文献54-58
• 攻读硕士学位期间取得的研究成果58-60
• 致谢60

，

本文编号：660030