论文部分内容阅读
目前大部分XML查询语言都使用树模式来匹配待查询的XML文档树以得到所需要的、与模式树相吻合的查询结果，此效率在很大程度上取决于XML模式树的大小，那么尽可能快速地查找并删除查询模式树中的冗余节点就变得十分重要。重点讨论DTD约束下树模式的最小化问题，将DTD兄弟约束SC拓展成扩展兄弟约束ESC，使其能够表达DTD约束中的祖先一后代关系；并指出只包含{ESC，／，//，[]，^＊}的查询树模式的最小化问题的复杂度是指数级的，且当模式树是分支受限的时候，其最小化问题的复杂度是多项式时间的；最后给出了一个多项