A Survey of XML Tree Patterns <s> Holistic tree pattern matching <s> XML queries typically specify patterns of selection predicates on multiple elements that have some specified tree structured relationships. The primitive tree structured relationships are parent-child and ancestor-descendant, and finding all occurrences of these relationships in an XML database is a core operation for XML query processing. We develop two families of structural join algorithms for this task: tree-merge and stack-tree. The tree-merge algorithms are a natural extension of traditional merge joins and the multi-predicate merge joins, while the stack-tree algorithms have no counterpart in traditional relational join processing. We present experimental results on a range of data and queries using the TIMBER native XML query engine built on top of SHORE. We show that while, in some cases, tree-merge algorithms can have performance comparable to stack-tree algorithms, in many cases they are considerably worse. This behavior is explained by analytical results that demonstrate that, on sorted inputs, the stack-tree algorithms have worst-case I/O and CPU complexities linear in the sum of the sizes of inputs and output, while the tree-merge algorithms do not have the same guarantee. <s> BIB001 </s> A Survey of XML Tree Patterns <s> Holistic tree pattern matching <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> BIB002
While TP minimization approaches (Section 4.1) wholly focus on the TP side of the matching process, holistic matching (also called holistic twig join BIB002 ) algorithms mainly operate on minimizing access to the input data tree when performing actual matching operations. The initial binary join-based approach for matching proposed by Al-Khalifa et al. BIB001 indeed produces large intermediate results. Holistic approaches casually optimize TP matching in two steps  : 1) labeling: assign to each node x in the data tree t an integer label label(x) that captures the structure of t (Section 4.2.1); 2) computing: exploit labels to match a twig pattern p against t without traversing t again (Section 4.2.2). Moreover, recent proposals aim at reducing data tree size by exploiting structural summaries in combination to labeling schemes. We review them in Section 4.2.3. Let us finally highlight that, given the tremendous number of holistic matching algorithms proposed in the literature, it is quite impossible to review them all. Hence, we aim in the following sections at presenting the most influential. The interested reader may further refer to Grimsmo and Bjørklund's survey BIB002 , which uniquely focuses on and introduces a nice history of holistic approaches.