论文部分内容阅读
XML是W3C组织提出的一种标记语言，被广泛应用于跨平台之间的数据交互。而Twig模式查询作为XML查询的一种自然的表达方式，由于其在XML查询过程中的核心地位受到了广泛的关注。为了提高查询效率，人们对Twig模式优化进行了大量的研究，优化方法大致上可以分为两类，第一类是从提高Twig模式匹配的算法效率出发，利用辅助数据结构和相关的编码技术，加快Twig模式查询过程的匹配速度；第二类是通过修改查询本身，即所谓的查询重写技术来优化Twig模式，通用的做法是对于给定的Twig模式，通过将Twig模式查询转换为一个等价的但是具有更高查询效率的形式，例如Twig模式最小化。Twig模式最小化通常要考虑DTD、XML Schema中的约束，当前的工作中，针对不同的约束有着不同的优化裁剪方法，这些裁剪策略大都针对具体的XML查询处理平台，难以对同一个查询表达式执行多种优化裁剪，而且当发现新的优化方法时，必须重新设计或修改算法，算法本身的正确性也只能依赖设计者手动检查和修正，针对这一问题，本文提出了一个通用的Twig模式优化方案，该方案并不产生新的优化方法和规则，而是提出了统一的优化规则描述语言ORS及其平台，根据ORS语言描述的优化规则以及待处理的Twig模式，系统会自动地输出该Twig模式的优化裁剪动作。该研究的重要意义在于：一方面简化了Twig模式优化裁剪的过程；另一方面把形式化方法和理论运用到Twig模式查询优化上，借助模型检查及谓词逻辑的理论和工具，以及对规则描述语言ORS语法和语义的严格定义确保了生成的优化动作的正确性。