论文部分内容阅读
XPath是XML的基本查询语言，XPath查询最小化对于提高XML数据库的查询性能具有重要意义。但是，由于XPath查询最小化是一个coNP完备问题，大部分已有的算法局限于处理简单的XPath片段。本文从一个新的角度入手，综合考虑完备性和高效性，提出了一个新的查询最小化框架，与已有算法“面向结点”，即逐个删除冗余结点的解决思路不同，本文提出“面向树模式”的方式，即通过计算树模式的自同态映射，寻找目标结点集最小的自伺态映射，进而求解最小等价查询树的方法。该方法具有较高的效率，而且在一定情况下是完备的，尤其