带约束XPath查询的最小化
XML查询的效率与查询语句的规模密切相关，如何有效地降低查询语句的规模，是XML查询中的重要问题。本文研究了基于XPath片断XP”Ⅰ,Ⅱdescendant-or-self,Ⅱ”带约束的查询最小化问题。首先研究这个片断上不考虑完整性约束时的最小化问题。此时该片断上的树模式查询可以在O(n2)时间内最小化；然后讨论在required-child、required-descendant、require-parent和required-sibling四种常见的完整性约束时的情形，针对不同的约束提出了不同的算法，并给出了复杂性结果；存在required-parent约束时算法的时间复杂度为O(n4)，存在其它约束时的复杂度则为O(n2)。
Xpath查询 查询最小化 完整性约束 树模式查询
万常选 刘喜平
江西财经大学信息管理学院
国内会议
南昌
中文
128-135
2004-10-28（万方平台首次上网日期，不代表论文的发表时间）