Minimization of tree pattern queries Sihem Amer-Yahia, SungRan Cho, Laks V. S. Lakshmanan, and Divesh Srivastava   View Paper (PDF)   Return to Schemas and Queries Abstract Tree patterns form a natural basis to query tree­structured data such as XML and LDAP. Since the efficiency of tree pattern matching against a tree­structured database depends on the size of the pattern, it is essential to identify and elim­ inate redundant nodes in the pattern and do so as quickly as possible. In this paper, we study tree pattern minimization both in the absence and in the presence of integrity con­ straints (ICs) on the underlying tree­structured database. When no ICs are considered, we call the process of mini­ mizing a tree pattern, constraint­independent minimization. We develop a polynomial time algorithm called CIM for this purpose. CIM's efficiency stems from two key prop­ erties: (i) a node cannot be redundant unless its children are, and (ii) the order of elimination of redundant nodes is immaterial. When ICs are considered for minimization, we refer to it as constraint­dependent minimization. For tree­ structured databases, required child/descendant and type co­occurrence ICs are very natural. Under such ICs, we show that the minimal equivalent query is unique. We show the surprising result that the algorithm obtained by first aug­ menting the tree pattern using ICs, and then applying CIM, always finds the unique minimal equivalent query; we refer to this algorithm as ACIM. While ACIM is also polynomial time, it can be expensive in practice because of its inher­ ent non­locality. We then present a fast algorithm, CDM, that identifies and eliminates local redundancies due to ICs, based on propagating ``information labels'' up the tree pat­ tern. CDM can be applied prior to ACIM for improving the minimization efficiency. We complement our analytical results with an experimental study that shows the effective­ ness of our tree pattern minimization techniques. DiSC'02 © 2003 Association for Computing Machinery