A Survey of XML Tree Patterns <s> Expressiveness <s> XML has become ubiquitous, and XML data has to be managed in databases. The current industry standard is to map XML data into relational tables and store this information in a relational database. Such mappings create both expressive power problems and performance problems.In the T IMBER [7] project we are exploring the issues involved in storing XML in native format. We believe that the key intellectual contribution of this system is a comprehensive set-at-a-time query processing ability in a native XML store, with all the standard components of relational query processing, including algebraic rewriting and a cost-based optimizer. <s> BIB001 </s> A Survey of XML Tree Patterns <s> Expressiveness <s> XML is widely praised for its flexibility in allowing repeated and missing sub-elements. However, this flexibility makes it challenging to develop a bulk algebra, which typically manipulates sets of objects with identical structure. A set of XML elements, say of type book, may have members that vary greatly in structure, e.g. in the number of author sub-elements. This kind of heterogeneity may permeate the entire document in a recursive fashion: e.g., different authors of the same or different book may in turn greatly vary in structure. Even when the document conforms to a schema, the flexible nature of schemas for XML still allows such significant variations in structure among elements in a collection. Bulk processing of such heterogeneous sets is problematic.In this paper, we introduce the notion of logical classes (LC) of pattern tree nodes, and generalize the notion of pattern tree matching to handle node logical classes. This abstraction pays off significantly in allowing us to reason with an inherently heterogeneous collection of elements in a uniform, homogeneous way. Based on this, we define a Tree Logical Class (TLC) algebra that is capable of handling the heterogeneity arising in XML query processing, while avoiding redundant work. We present an algorithm to obtain a TLC algebra expression from an XQuery statement (for a large fragment of XQuery). We show how to implement the TLC algebra efficiently, introducing the nest-join as an important physical operator for XML query processing. We show that evaluation plans generated using the TLC algebra not only are simpler but also perform better than those generated by competing approaches. TLC is the algebra used in the T imber [8] system developed at the University of Michigan. <s> BIB002
TAX TPs and their derivatives (GTPs and APTs) do not translate into an XML query language, but they are implemented, through the TLC physical algebra BIB002 , in the TIMBER XML database management system BIB001 . TIMBER permits to store XML in native format and offers a query interface supporting both classical XQuery fragments and TAX operators. Note that TAX operators include a Group by construct that has no equivalent in XQuery. Translating TAX TPs for XML querying follows nine steps: 1) identify all TP elements in the FOR clause; 2) push formula F 's predicates into the WHERE clause; 3) eliminate duplicates with the help of the DISTINCT keyword; 4) evaluate aggregate expressions in LET clauses; 5) indicate tree variables to be joined (join conditions) via the WHERE clause; 6) enforce any remaining constraint in the WHERE clause; 7) evaluate RETURN aggregates; 8) order output nodes with the help of the ORDER BY clause; 9) project on the elements indicated in the RETURN clause. Similarly, Lakshmanan et al. test the satisfiability of TPs translated from XPath expressions and XQueries, and then express them back in XQuery and evaluate them within the XQEngine XQuery engine  . The other TPs we survey are used in various algorithms (containment and equivalence testing, TP rewriting, frequent TP mining...). Hence, their expressiveness is not assessed.