A Survey of XML Tree Patterns <s> Minimization under integrity constraints <s> Tree patterns forms 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 eliminate 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 constraints (ICs) on the underlying tree-structured database. When no ICs are considered, we call the process of minimizing a tree pattern, constraint-independent minimization. We develop a polynomial time algorithm called CIM for this purpose. CIM's efficiency stems from two key properties: (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 augmenting 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 inherent 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 pattern. CDM can be applied prior to ACIM for improving the minimization efficiency. We complement our analytical results with an experimental study that shows the effectiveness of our tree pattern minimization techniques. <s> BIB001 </s> A Survey of XML Tree Patterns <s> Minimization under integrity constraints <s> We consider the problem of minimizing tree pattern queries (TPQ) that arise in XML and in LDAP-style network directories. In [Minimization of Tree Pattern Queries, Proc. ACM SIGMOD Intl. Conf. Management of Data, 2001, pp. 497-508], Amer-Yahia, Cho, Lakshmanan and Srivastava presented an O(n4) algorithm for minimizing TPQs in the absence of integrity constraints (Case 1); n is the number of nodes in the query. Then they considered the problem of minimizing TPQs in the presence of three kinds of integrity constraints: required-child, required-descendant and subtype (Case 2). They presented an O(n6) algorithm for minimizing TPQs in the presence of only required-child and required-descendant constraints (i.e., no subtypes allowed; Case 3). We present O(n2), O(n4) and O(n2) algorithms for minimizing TPQs in these three cases, respectively, based on the concept of graph simulation. We believe that our O(n2) algorithms for Cases 1 and 3 are runtime optimal. <s> BIB002 </s> A Survey of XML Tree Patterns <s> Minimization under integrity constraints <s> Tree pattern queries (TPQs) provide a natural and easy formalism to query tree-structured XML data, and the efficient processing of such queries has attracted a lot of attention. Since the size of a TPQ is a key determinant of its evaluation cost, recent research has focused on the problem of query minimization using integrity constraints to eliminate redundant query nodes; specifically, TPQ minimization has been studied for the class of forward and subtype constraints (FT-constraints). In this paper, we explore the TPQ minimization problem further for a richer class of FBST-constraints that includes not only FT-constraints but also backward and sibling constraints. By exploiting the properties of minimal queries under FBST-constraints, we propose efficient algorithms to both compute a single minimal query as well as enumerate all minimal queries. In addition, we also develop more efficient minimization algorithms for the previously studied class of FT-constraints. Our experimental study demonstrates the effectiveness and efficiency of query minimization using FBST-constraints. <s> BIB003
Taking ICs into account in the minimization process is casually achieved as follows. 1) Augment the TP to minimize with nodes and edges that represent ICs. This is casually achieved with the classical chase technique  . For instance, if we had a book → author IC (nodes of type "book" must have a child of type "author"), we would add one child node of type author to each of the nodes $2 and $4 from Figure 10 . Note that augmentation must only apply to nodes from the original TP, and not to nodes previously added by the chase. 2) Run any TP minimization algorithm, without testing utilitarian nodes introduced in step #1 for redundancy, so that ICs hold. 3) Delete utilitarian nodes introduced in step #1. This process has been applied onto the CIM algorithm, to produce ACIM (Augmented CIM) BIB001 , as well as on its coverage-based variants BIB002 ,  ,  . Since the size of an augmented TP can be much larger than that of the original TP, an algorithm called Constraint Dependant Minimization (CDM) also helps identify and prune all TP nodes that are redundant under ICs BIB001 . CDM actually acts as a filter before ACIM is applied. CDM considers a TP leaf x ′ of type T ′ redundant and removes it if one of the following conditions holds. • parent(x ′ ) = x (respectively ancestor(x ′ ) = x) of type T and there exists an IC T → T ′ (respectively T ⇒ T ′ ). • parent(x ′ ) = x (respectively ancestor(x ′ ) = x) of type T , ∃x ′′ /parent(x ′′ ) = x (respectively ancestor(x ′′ ) = x) of type T ′′ , and there exists an IC T ′ = T ′′ (respectively, there exists one of the ICs An alternative simulation-based minimization algorithm also includes a similar prefilter, along with an augmentation phase that adds to the nodes of cov(x) their ancestors instead of using the chase BIB002 . Finally, the scope of ICs has recently been extended to include not only forward and subtype (FT) constraints (as defined in Section 4.1), but also backward and sibling (BS) constraints BIB003 : • each node of type A (e.g., author) must have a parent (respectively, ancestor) of type B (e.g., book), i.e., A ← B (respectively, A ⇐ B); • each node of type A (e.g., book) that has a child of type B (e.g., editor) must also have a child of type C (e.g, address), i.e., if A → B then A → C. Under FBST constraints, several minimal TPs can be achieved (vs. one only under FT constraints), which allows further optimizations of the chase augmentation and simulation-based minimization processes.