Abstract: Many XML query languages use tree patterns to navigate an XML document and select a set of element nodes.Since the efficiency of tree pattern matching against an XML tree-structured database depends on the size of the pattern，it is essential to identify and eliminate redundant nodes in the pattern and do so as quickly as possible.This paper studies tree pattern minimization in the presence of DTD.The SC to ESC that can express descendant relationships under DTD constraints is extend.This paper shows that minimization of tree pattern queries contain {ESC，/，//，[]，*} is EXPTIME，and，in particular，when tree pattern branches are limited，queries are PTIME.At last provide an algorithm for minimization of limited branched tree patterns and analyze its complexity.

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