论文部分内容阅读
XML查询的效率与查询语句的规模密切相关，如何有效地降低查询语句的规模，是XML查询中的重要问题。本文研究了基于XPath片断XP[Ⅰ,Ⅱdescendant-or-self,Ⅱ]带约束的查询最小化问题。首先研究这个片断上不考虑完整性约束时的最小化问题。此时该片断上的树模式查询可以在O(n2)时间内最小化；然后讨论在required-child、required-descendant、require-parent和required-sibling四种常见的完整性约束时的情形，针对不同的约束提出了不同的算法，并给出了复杂性结果；存在required-parent约束时算法的时间复杂度为O(n4)，存在其它约束时的复杂度则为O(n2)。