A Survey of XML Tree Patterns <s> Containment and equivalence testing <s> We define the class of conjunctive queries in relational data bases, and the generalized join operator on relations. The generalized join plays an important part in answering conjunctive queries, and it can be implemented using matrix multiplication. It is shown that while answering conjunctive queries is NP complete (general queries are PSPACE complete), one can find an implementation that is within a constant of optimal. The main lemma used to show this is that each conjunctive query has a unique minimal equivalent query (much like minimal finite automata). <s> BIB001 </s> A Survey of XML Tree Patterns <s> Containment and equivalence testing <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> BIB002 </s> A Survey of XML Tree Patterns <s> Containment and equivalence testing <s> XPath is a simple language for navigating an XML tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of XPath. In addition to the basic operations (child, descendant, filter, and wildcard), we consider disjunction, DTDs and variables. W.r.t. variables we study two semantics: (1) the value of variables is given by an outer context; (2) the value of variables is defined existentially. We establish an almost complete classification of the complexity of the containment problem w.r.t. these fragments. <s> BIB003 </s> A Survey of XML Tree Patterns <s> Containment and equivalence testing <s> The containment and equivalence problems for various fragments of XPath have been studied by a number of authors. For some fragments, deciding containment (and even minimisation) has been shown to be in PTIME, while for minor extensions containment has been shown to be CONP-complete. When containment is with respect to trees satisfying a set of constraints (such as a schema or DTD), the problem seems to be more difficult. For example, containment under DTDs is CONP-complete for an XPath fragment denoted XP{[ ]} for which containment is in PTIME. It is also undecidable for a larger class of XPath queries when the constraints are so-called simple XPath integrity constraints (SXICs). In this paper, we show that containment is decidable for an important fragment of XPath, denoted XP{[ ], *, //}, when the constraints are DTDs. We also identify XPath fragments for which containment under DTDs can be decided in PTIME. <s> BIB004 </s> A Survey of XML Tree Patterns <s> Containment and equivalence testing <s> XPath expressions define navigational queries on XML data and are issued on XML documents to select sets of element nodes. Due to the wide use of XPath, which is embedded into several languages for querying and manipulating XML data, the problem of efficiently answering XPath queries has received increasing attention from the research community. As the efficiency of computing the answer of an XPath query depends on its size, replacing XPath expressions with equivalent ones having the smallest size is a crucial issue in this direction. This article investigates the minimization problem for a wide fragment of XPath (namely X Plsr), where the use of the most common operators (child, descendant, wildcard and branching) is allowed with some syntactic restrictions. The examined fragment consists of expressions which have not been specifically studied in the relational setting before: neither are they mere conjunctive queries (as the combination of “//” and “*” enables an implicit form of disjunction to be expressed) nor do they coincide with disjunctive ones (as the latter are more expressive). Three main contributions are provided. The “global minimality” property is shown to hold: the minimization of a given XPath expression can be accomplished by removing pieces of the expression, without having to re-formulate it (as for “general” disjunctive queries). Then, the complexity of the minimization problem is characterized, showing that it is the same as the containment problem. Finally, specific forms of XPath expressions are identified, which can be minimized in polynomial time. <s> BIB005
Let us first further formalize the definitions of containment and equivalence. Containment of two TPs p 1 and p 2 is defined as a node mapping relationship h : p 1 → p 2 such that BIB002 ,  : • h preserves node type, i.e., ∀x ∈ p 1 , x and h(x) must be of the same type. Moreover, if x is an output node, h(x) must be an output node too; • h preserves node relationships, i.e., if two nodes (x, y) are linked through a PC (respectively, AD) Fig. 10 . Simple minimization example relationship in p 1 , (f (x), f (y)) must also be linked through a PC (respectively, AD) relationship in p 2 . Note that function h is very similar to function f that matches a TP to a data tree (Section 2.1.7), but here, h is a homomorphism between two TPs BIB001 . Moreover, containment may be tested between a TP fragment and this TP as a whole. h is then an endomorphism. Finally, equivalence between two TPs is simply considered as two-way containment BIB002 , BIB005 . Formally, let p 1 and p 2 be two TPs. p 1 ≡ p 2 if and only if p 1 ⊆ p 2 and p 2 ⊆ p 1 . Miklau and Suciu show that containment testing is intractable in the general case  . They nonetheless propose an efficient algorithm for significant particular cases, namely TPs with AD edges and an output node. This algorithm is based on tree automata, the objective being to reduce the TP containment problem to that of regular tree languages. In summary, given two TPs p 1 and p 2 , to test whether p 1 ⊆ p 2 : • p 1 's nodes and edges are matched to deterministic finite tree automaton A 1 's states and transitions, respectively; • p 2 's nodes and edges are matched to alternating finite tree automaton A 2 's states and transitions, respectively; lang(A i ) is the language associated with automaton A i (i = {1, 2}). Similar approaches further test TP containment under Document Type Definition (DTD) constraints BIB003 , BIB004 . For instance, Wood exploits regular tree grammars (RTGs) to achieve containment testing BIB004 . Let D be a DTD and G 1 and G 2 RTGs corresponding to p 1 and p 2 , respectively. Then p 1 ⊆ p 2 if and only if