A Survey of XML Tree Patterns <s> Unconstrained minimization <s> The paper introduces a model of the Web as an infinite, semi-structured set of objects. We reconsider the classical notions of genericity and computability of queries in this new context and relate them to styles of computation prevalent on the Web, based on browsing and searching. We revisit several well-known declarative query languages (first-order logic, Datalog, and Datalog with negation) and consider their computational characteristics in terms the notions introduced in this paper. In particular, we are interested in languages or fragments thereof which can be implemented by browsing, or by browsing and searching combined. Surprisingly, stratified and well-founded semantics for negation turn out to have basic shortcomings in this context, while inflationary semantics emerges as an appealing alternative. <s> BIB001 </s> A Survey of XML Tree Patterns <s> Unconstrained minimization <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> Unconstrained minimization <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> BIB003 </s> A Survey of XML Tree Patterns <s> Unconstrained minimization <s> With the rapid growth of XML-document traffic on the Internet, scalable content-based dissemination of XML documents to a large, dynamic group of consumers has become an important research challenge. To indicate the type of content that they are interested in, data consumers typically specify their subscriptions using some XML pattern specification language (e.g., XPath). Given the large volume of subscribers, system scalability and efficiency mandate the ability to aggregate the set of consumer subscriptions to a smaller set of content specifications, so as to both reduce their storage-space requirements as well as speed up the document-subscription matching process. In this paper, we provide the first systematic study of subscription aggregation where subscriptions are specified with tree patterns (an important subclass of XPath expressions). The main challenge is to aggregate an input set of tree patterns into a smaller set of generalized tree patterns such that: (1) a given space constraint on the total size of the subscriptions is met, and (2) the loss in precision (due to aggregation) during document filtering is minimized. We propose an efficient tree-pattern aggregation algorithm that makes effective use of document-distribution statistics in order to compute a precise set of aggregate tree patterns within the allotted space budget. As part of our solution, we also develop several novel algorithms for tree-pattern containment and minimization, as well as "least-upper-bound" computation for a set of tree patterns. These results are of interest in their own right, and can prove useful in other domains, such as XML query optimization. Extensive results from a prototype implementation validate our approach. <s> BIB004 </s> A Survey of XML Tree Patterns <s> Unconstrained minimization <s> Efficient query optimization is critical to the performance of query processing in a database system. The same is true for XML databases and queries. XML queries naturally carry a tree-shaped search pattern which usually contains redundancies. Efficient minimization of the tree patterns of XML queries forms an integral and important part of XML query optimization. This short paper sketchily presents the algorithms we developed for XML tree pattern query minimization that outperform previous approaches. <s> BIB005 </s> A Survey of XML Tree Patterns <s> Unconstrained minimization <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> BIB006
The first TP minimization algorithm, Constraint Independent Minimization (CIM) BIB002 , eliminates redundant nodes from TP p by exploiting the concept of images. Let there be a node x ∈ p. Its list of images, denoted images(x), is composed of nodes For example, let us consider TP p from Figure 10 . Without regarding node order, let us check leaf node $5 for redundancy. parent($5) = $4, images($4) = {$2}, descendants($2) = {$3}, where descendants(x) is the set of descendants of node x. $3 bears the same type as $5 (author), thus $5 is deleted. Similarly, $4 is then found redundant and deleted, outputting p min in Figure 10 . Further testing $1, $2 and $3 does not detect any new redundant node. Moreover, deleting another node from p min would break the equivalence between p and p min . Hence, p min is indeed minimal. All minimization algorithms subsequent to CIM retain its principle while optimizing complexity. One strategy is to replace images by more efficient relationships, i.e., coverage  , BIB005 , also called simulation BIB003 . Let p be the TP to minimize, and x, y ∈ p two of its nodes. If y covers x (x y) BIB001 : • the types of x and y must be identical; • if x has a child (respectively descendant) node x ′ , y must have a child (respectively descendant) node y ′ such that x ′ y ′ . cov(x) denotes the set of nodes that cover x. cov(x) = x if x is an output node. Then, the minimization process tests node redundancy in a top-down fashion as follows: ∀x ∈ p, ∀x ′ ∈ children(x) (respectively descendants(x)), if ∃x ′′ ∈ children(x) (respectively descendants(x)) such that x ′′ ∈ cov(x ′ ), then x ′ and the subtree rooted in x ′ are deleted. children(x) (respectively descendants(x)) is the set of direct children (respectively, all descendants) of node x. Another strategy is to simply prune subtrees recursively BIB004 . The subtree rooted at node x, denoted subtree(x), is minimized in two steps: 2) ∀x ′ ∈ children(x) (remaining children of x), minimize subtree(x ′ ). A variant proceeds similarly, by first searching in a TP p for any subtree p i redundant with sp, where sp is p stripped of its root BIB006 . Formally, the algorithm tests whether p − sp i ⊆ p i . Redundant subtrees are removed. Then, the algorithm is recursively executed on unpruned subtrees sp i .