A Survey of XML Tree Patterns <s> CONCLUSION <s> Query processing techniques for XML data have focused mainly on tree-pattern queries (TPQs). However, the need for querying XML data sources whose structure is very complex or not fully known to the user, and the need to integrate multiple XML data sources with different structures have driven, recently, the suggestion of query languages that relax the complete specification of a tree pattern. In order to implement the processing of such languages in current DBMSs, their containment problem has to be efficiently solved. In this paper, we consider a query language which generalizes TPQs by allowing the partial specification of a tree pattern. Partial tree-pattern queries (PTPQs) constitute a large fragment of XPath that flexibly permits the specification of a broad range of queries from keyword queries without structure, to queries with partial specification of the structure, to complete TPQs. We address the containment problem for PTPQs. This problem becomes more complex in the context of PTPQs because the partial specification of the structure allows new, non-trivial, structural expressions to be inferred from those explicitly specified in a query. We show that the containent problem cannot be characterized by homomorphisms between PTPQs, even when PTPQs are put in a canonical form that comprises all derived structural expressions. We provide necessary and sufficient conditions for this problem in terms of homomorphisms between PTPQs and (a possibly exponential number of) TPQs. To cope with the high complexity of PTPQ containment, we suggest a heuristic approach for this problem that trades accuracy for speed. An extensive experimental evaluation of our heuristic shows that our heuristic approach can be efficiently implemented in a query optimizer. <s> BIB001 </s> A Survey of XML Tree Patterns <s> CONCLUSION <s> Current streaming applications have stringent requirements on query response time and memory consumption because of the large (possibly unbounded) size of data they handle. Further, known query evaluation algorithms on streaming XML documents focus almost exclusively on tree-pattern queries(TPQs). However recently, requirements for flexible querying of XML data have motivated the introduction of query languages that are more general and flexible than TPQs. These languages are not supported by known algorithms. ::: ::: In this paper, we consider a language which generalizes and strictly contains TPQs. Queries in this language can be represented as dags enhanced with constraints. We explore this representation to design an original polynomial time streaming algorithm for these queries. Our algorithm avoids storing and processing matches of the query dag that do not contribute to new solutions (redundant matches). Its key feature is that it applies an eager evaluation strategy to quickly determine when node matches should be returned as solutions to the user and also to proactively detect redundant matches. We experimentally test its time and space performance. The results show the superiority of the eager algorithm compared to the only known algorithm for this class of queries which is a lazy algorithm. <s> BIB002 </s> A Survey of XML Tree Patterns <s> CONCLUSION <s> Querying XML data is based on the specification of structural patterns which in practice are formulated using XPath. Usually, these structural patterns are in the form of trees (Tree-Pattern Queries --- TPQs). Requirements for flexible querying of XML data including XML data from scientific applications have motivated recently the introduction of query languages that are more general and flexible than TPQs. These query languages correspond to a fragment of XPath larger than TPQs for which efficient non-main-memory evaluation algorithms are not known. ::: ::: In this paper, we consider a query language, called Partial Tree-Pattern Query (PTPQ) language, which generalizes and strictly contains TPQs. PTPQs represent a broad fragment of XPath which is very useful in practice. We show how PTPQs can be represented as directed acyclic graphs augmented with "same-path" constraints. We develop an original polynomial time holistic algorithm for PTPQs under the inverted list evaluation model. To the best of our knowledge, this is the first algorithm to support the evaluation of such a broad structural fragment of XPath. We provide a theoretical analysis of our algorithm and identify cases where it is asymptotically optimal. In order to assess its performance, we design two other techniques that evaluate PTPQs by exploiting the state-of-the-art existing algorithms for smaller classes of queries. An extensive experimental evaluation shows that our holistic algorithm outperforms the other ones. <s> BIB003
W E provide in this paper a comprehensive survey about XML tree patterns, which are nowadays considered crucial in XML querying and its optimization. We first compare TPs from a structural point of view, concluding that the richer a TP is with matching possibilities, the larger the subset of XQuery/XPath it encompasses, and thus the closer to user expectations it is. Secondly, acknowledging that TP querying, i.e., matching a TP against a data tree, is central in TP usage, we review methods for TP matching optimization. They belong to two main families: TP minimization and holistic matching. We trust we provide a good overview of these approaches' evolution, and highlight the best algorithms in each family as of today. Moreover, we want to emphasize that TP minimization and holistic matching are complementary and should both be used to wholly optimize TP matching. We eventually illustrate how TPs are actually exploited in several application domains such as system optimization, network routing or knowledge discovery from XML sources. We especially demonstrate the use of frequent TP mining and TP rewriting for various purposes. Although TP-related research, which has been ongoing for more than a decade, could look mature in the light of this survey, it is perpetually challenged by the ever-growing acceptance and usage of XML. For instance, recent applications require either querying data with a complex or only partially known structure, or integrating heterogeneous XML data sources (e.g., when dealing with streams). The keyword search-based languages that address these problems cannot be expressed with TPs BIB002 . Thus, TPs must be extended, e.g., by so-called partial treepattern queries (PTPQs) that allow the partial specification of a TP and are not restricted by a total order on nodes BIB002 , BIB001 . In turn, adapted matching procedures must be devised BIB003 , a trend that is likely to perpetuate in the near future. Moreover, we purposely focus on the core of TPrelated topics in this survey (namely, TPs themselves, matching issues and a couple of applications). There is nonetheless a large number of important topics that we could not address due to space constraints, such as TP indexing, TP-based view selection, TP for probabilistic XML and continuous TP matching over XML streams.