A Survey of XML Tree Patterns <s> Discussion <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> Discussion <s> Tree patterns are fundamental to querying tree-structured data like XML. Because of the heterogeneity of XML data, it is often more appropriate to permit approximate query matching and return ranked answers, in the spirit of Information Retrieval, than to return only exact answers. In this paper, we study the problem of approximate XML query matching, based on tree pattern relaxations, and devise efficient algorithms to evaluate relaxed tree patterns. We consider weighted tree patterns, where exact and relaxed weights, associated with nodes and edges of the tree pattern, are used to compute the scores of query answers. We are interested in the problem of finding answers whose scores are at least as large as a given threshold. We design data pruning algorithms where intermediate query results are filtered dynamically during the evaluation process. We develop anoptimization that exploits scores of intermediate results to improve query evaluation efficiency. Finally, we show experimentally that our techniques outperform rewriting-based and post-pruning strategies. <s> BIB002 </s> A Survey of XML Tree Patterns <s> Discussion <s> XML and XQuery semantics are very sensitive to the order of the produced output. Although pattern-tree based algebraic approaches are becoming more and more popular for evaluating XML, there is no universally accepted technique which can guarantee both a correct output order and a choice of efficient alternative plans.We address the problem using hybrid collections of trees that can be either sets or sequences or something in between. Each such collection is coupled with an Ordering Specification that describes how the trees are sorted (full, partial or no order). This provides us with a formal basis for developing a query plan having parts that maintain no order and parts with partial or full order.It turns out that duplicate elimination introduces some of the same issues as order maintenance: it is expensive and a single collection type does not always provide all the flexibility required to optimize this properly. To solve this problem we associate with each hybrid collection a Duplicate Specification that describes the presence or absence of duplicate elements in it. We show how to extend an existing bulk tree algebra, TLC [12], to use Ordering and Duplicate specifications and produce correctly ordered results. We also suggest some optimizations enabled by the flexibility of our approach, and experimentally demonstrate the performance increase due to them. <s> BIB003
In this section, we discuss and compare the TPs surveyed in Sections 3.1 and 3.2. For this sake, we introduce four comparison criteria. • Matching power: Matching encompasses two dimensions. Structural matching guarantees that only subtrees of the input data tree that map the TP are output. Matching by value is verifying formula F . We mean by matching power all the matching options (edge annotations, logical operator nodes, formula extensions...) beyond these basics. Improving matching power helps filter data more precisely. • Node reordering capability: Order is important in XML querying, thus modern TPs should be able to alter it BIB003 . We mean by node reordering capability the ability of a TP to modify output node order when matching against any data tree. Note that node reordering could be classified as a matching capability, but the importance of ordering witness trees leads us to consider it separately. • Expressiveness: Expressiveness states how a logical TP, i.e., a TP under its schematic form, translates into the corresponding physical implementation. The physical form of a TP may be either expressed with an XML query language (XQuery, generally), or an implementation within an XML database offering query possibilities. Using a TP for other purposes but querying, e.g., in optimization algorithms, is not accounted toward expressiveness. Note that a TP that cannot be expressed in physical form is usually considered useless. • Supported optimizations: TPs are an essential element of XML querying BIB001 , BIB002 . Hence, many optimization approaches translate XML queries into TPs, optimize them, and then translate them back into optimized queries. Optimizing a TP increases its matching power. This criterion references the different kinds of optimizations supported by a given TP. TP comparison with respect to matching power, node reordering capability, expressiveness and supported optimizations follows (Sections 3.3.1, 3.3.2, 3.3.3 and 3.3.4, respectively), and is synthesized in Section 3.3.5. In this section, we discuss and compare the TP matching optimization approaches surveyed in Sections 4.1, 4.2 and 4.3; except TP relaxation, whose goal is quite different (i.e., augmenting user satisfaction rather than matching efficiency). Choosing objective comparison criteria is pretty straightforward for algorithms. Time and space complexity immediately come to mind, though they are diversely documented in the papers we survey. We could also retain algorithm correctness as a comparison criterion, although proofs are quite systematically provided by authors of matching optimization approaches. Thus, we only notice here that none of the minimization algorithms reviewed in Section 4.1 actually test the equivalence of minimal TP p min to original TP p. More precisely, containment (i.e., p min ⊆ p) is checked a posteriori, but the minimization process being assumed correct, equivalence is not double-checked. Algorithm comparison with respect to complexity follows (Sections 4.4.1 and 4.4.2), and is synthesized in Section 4.4.3, where we also further discuss the complementarity between TP minimization and holistic approaches.