A Survey of XML Tree Patterns <s> Synthesis <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> BIB001 </s> A Survey of XML Tree Patterns <s> Synthesis <s> Finding all distinct matchings of the query tree pattern is the core operation of XML query evaluation. The existing methods for tree pattern matching are decomposition-matching-merging processes, which may produce large useless intermediate result or require repeated matching of some sub-patterns. We propose a fast tree pattern matching algorithm called TreeMatch to directly find all distinct matchings of a query tree pattern. The only requirement for the data source is that the matching elements of the non-leaf pattern nodes do not contain sub-elements with the same tag. The TreeMatch does not produce any intermediate results and the final results are compactly encoded in stacks, from which the explicit representation can be produced efficiently. <s> BIB002 </s> A Survey of XML Tree Patterns <s> Synthesis <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> BIB003 </s> A Survey of XML Tree Patterns <s> Synthesis <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> BIB004 </s> A Survey of XML Tree Patterns <s> Synthesis <s> Twig joins are key building blocks in current XML indexing systems, and numerous algorithms and useful data structures have been introduced. We give a structured, qualitative analysis of recent advances, which leads to the identification of a number of opportunities for further improvements. Cases where combining competing or orthogonal techniques would be advantageous are highlighted, such as algorithms avoiding redundant computations and schemes for cheaper intermediate result management. We propose some direct improvements over existing solutions, such as reduced memory usage and stronger filters for bottom-up algorithms. In addition we identify cases where previous work has been overlooked or not used to its full potential, such as for virtual streams, or the benefits of previous techniques have been underestimated, such as for skipping joins. Using the identified opportunities as a guide for future work, we are hopefully one step closer to unification of many advances in twig join algorithms. <s> BIB005 </s> A Survey of XML Tree Patterns <s> Synthesis <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> BIB006
We recapitulate in Table 1 the characteristics of all TPs surveyed in this paper with respect to our comparison criteria. In summary, matching options in TPs are numerous and it would probably not be easy to set up a metric to rank them. The best choice, then, seems to select a TP variant that is adapted to the user's or designer's needs. However, designing a TP that pulls together most of the options we survey is certainly desirable to maximize matching power. With respect to output node ordering, we consider the ord order parameter introduced in APTs the simplest and most efficient approach. A list of ordered elements can indeed be associated with any TP, whatever the nature of the input data tree (ordered or unordered). However, it would be interesting to generalize the ord specification to other, possibly more complex, operators beside Select and Join, the two only operators benefiting from ordering in APTs. Expressiveness is a complex issue. Translating XML queries into TPs is indeed easier than translating TPs back into an XML query plan. XQuery, although the standard XML query language, suffers from limitations such as the lack of a Group by construct. Thus, it is more efficient to implement TPs and exploit them to enrich XML querying in an ad-hoc environment such as TIMBER's. We think that the richer the pattern, with matching options, ordering specifications, possibility to associate with many operators (and other options if possible), the more efficient querying is, in terms of user need satisfaction. Finally, minimization, relaxation, containment, equivalence and satisfiability issues lead the TP community to optimize these tasks. However, most TPs used in this context are basic, unlike TPs targeted at matching optimization, which allows optimizing XML queries wherein are translated optimized TPs. In short, the best-optimized TP must be minimal, satisfiable, and offer as many matching options as possible. In the light of this synthesis, we can notice again that TP minimization and holistic approaches have developed along separate roads. Papers related to one approach seldom refer to the other. Indeed, these two families of approaches cannot be compared, e.g., in terms of raw complexity, since TP minimization operates on TPs only, while holistic approaches optimize the actual matching of a TP against a data tree. TP minimization is actually implicitly considered as preprocessing TPs before matching BIB002 . We nonetheless find it surprising that nobody has ever combined TP minimization to holistic matching in a single framework to benefit from optimization of both data tree access and TP size. Eventually, Table 2 clearly outlines the history and outcome of the families of algorithms we survey. With respect to PT minimization algorithms, unless elaborated ICs (i.e., FSBT ICs) are needed, the choice should clearly fall on an approach whose time complexity is O(n 2 ), such as the coverage-based approaches BIB001 , BIB003 . With respect to holistic matching, the raw efficiency of algorithms is not always easy to compare, especially between the latest descendants of Twigstack and structural summary-based approaches such as TwigVersion BIB004 or S 3  , for both complexity and experimental studies remain partial as of today. The types of TPs (Section 4.4.1) for which an approach is optimal thus remains a primary criterion. However, we agree with Grimsmo and Bjørklund in stating that a global holistic approach, i.e., an approach that encompasses all kinds of TPs, is most desirable BIB005 . In this respect, TreeMatch BIB006 appears as the most comprehensive solution as of today.