A Survey of XML Tree Patterns <s> Time complexity <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> Time complexity <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> BIB002 </s> A Survey of XML Tree Patterns <s> Time complexity <s> A common problem of XML query algorithms is that execution time and input size grows rapidly as the size of XML document increases. In this paper, we propose a version-labeling scheme and TwigVersion algorithm to address this problem. The version-labeling scheme is utilized to identify all repetitive structures in XML documents, and the Version Tree is constructed to hold such version information. To process a query, TwigVersion generates a filter through the created Version Tree, and the final answer to the query can be retrieved from the database easily through the filtering process. Both theoretical proof and experimental results reported in this paper demonstrate that the concise structure of Version Tree and the reduced input size make TwigVersion outperform the existing approaches. <s> BIB003 </s> A Survey of XML Tree Patterns <s> Time complexity <s> Tree pattern matching is a fundamental problem that has a wide range of applications in Web data management, XML processing, and selective data dissemination. In this paper we develop efficient algorithms for the tree homeomorphism problem, i.e., the problem of matching a tree pattern with exclusively transitive (descendant) edges. We first prove that deciding whether there is a tree homeomorphism is LOGSPACE-complete, improving on the current LOGCFL upper bound. Furthermore, we develop a practical algorithm for the tree homeomorphism decision problem that is both space- and time-efficient. The algorithm is in LOGDCFL and space consumption is strongly bounded, while the running time is linear in the size of the data tree. This algorithm immediately generalizes to the problem of matching the tree pattern against all subtrees of the data tree, preserving the mentioned efficiency properties. <s> BIB004 </s> A Survey of XML Tree Patterns <s> Time complexity <s> As business and enterprises generate and exchange XML data more often, there is an increasing need for efficient processing of queries on XML data. Searching for the occurrences of a tree pattern query in an XML database is a core operation in XML query processing. Prior works demonstrate that holistic twig pattern matching algorithm is an efficient technique to answer an XML tree pattern with parent-child (P-C) and ancestor-descendant (A-D) relationships, as it can effectively control the size of intermediate results during query processing. However, XML query languages (e.g., XPath and XQuery) define more axes and functions such as negation function, order-based axis, and wildcards. In this paper, we research a large set of XML tree pattern, called extended XML tree pattern, which may include P-C, A-D relationships, negation functions, wildcards, and order restriction. We establish a theoretical framework about “matching cross” which demonstrates the intrinsic reason in the proof of optimality on holistic algorithms. Based on our theorems, we propose a set of novel algorithms to efficiently process three categories of extended XML tree patterns. A set of experimental results on both real-life and synthetic data sets demonstrate the effectiveness and efficiency of our proposed theories and algorithms. <s> BIB005
Time complexity is quite well documented for minimization approaches. Except the first, naive matching algorithms BIB001 , all optimized minimization algorithms, whether they take ICs into account or not, have a worst-case time complexity of O(n 2 ), where n is the size (number of nodes) of the TP. A notable exception is Chen and Chan's extension of ICs to FSBT constraints BIB002 that makes the matching problem more complex. Thus, their algorithms range in complexity, with respect to the combination of ICs that are processed, from O(n 2 ) (F and FS ICs) to O(n 3 · s + n 2 · s 2 ) (FSBT ICs), where s is the size of the set of element types in ICs. On the other hand, in papers about holistic approaches, complexity is often disregarded in favor of the class of TP a given algorithm is optimal for. The class of TP may be  : • AD: a TP containing only AD edges, which may begin with a PC edge; • PC: a TP containing only PC edges, which may begin with an AD edge; • one-branching node TP: a TP containing at most one branching node; • AD in branches TP: a TP containing only AD edges after the first branching node; • PC before AD TP: a TP where an AD edge is never found before a PC edge. Holistic approaches indeed all have the same worstcase time complexity. It is linear in the sum of all sizes of the input lists they process and the output list. However, since these approaches match twigs, they enumerate all root-to-leaf path matches. Thus, their complexity is actually exponential in n, i.e., it is O(d n ), where d is the size (number of nodes) of the input data tree  . Only Twig 2 Stack has a lower complexity, in O(d · b), where b = max(b 1 , b 2 ) with b 1 being the maximum number of query nodes with the same label and b 2 the maximum total number of children of query nodes with the same labels (b ≤ n)  ; as well as TreeMatch BIB005 , which has been experimentally shown to outperform Twig 2 Stack. Structural summary-based approaches (Section 4.2.3) have been experimentally shown to perform matching faster than previous holistic algorithms such as TwigStack and TJFast. However, they have neither been compared to one another, nor to TreeMatch. Moreover, their time complexity is expressed in terms of DataGuide degree and specific features such as the number of versions in TwigVersion BIB003 , so it is not easy to directly compare it to other holistic algorithms'. For instance, TwigVersion has a worst case time complexity of O(l v · n v + l p · e), where l v is the depth of version tree (annotated DataGuide) v, n v is the total number of versions on nodes of v whose tags appear in the leaf nodes of TP p, l p the depth of TP p, and e is the size of the edge set containing all edges that are on paths from nodes of v whose tags appear in the leaf nodes of p to the root node of v BIB003 . Finally, the complexity of tree homeomorphism matching is proved to be O(n · d · l p ) BIB004 .