A Survey of XML Tree Patterns <s> Fig. 12. Sample holistic matching <s> With the growing importance of semi-structure data in information exchange, much research has been done to provide an effective mechanism to match a twig query in an XML database. A number of algorithms have been proposed recently to process a twig query holistically. Those algorithms are quite efficient for quires with only ancestor-descendant edges. But for queries with mixed ancestor-descendant and parent-child edges, the previous approaches still may produce large intermediate results, even when the input and output size are more manageable. To overcome this limitation, in this paper, we propose a novel holistic twig join algorithm, namely TwigStackList. Our main technique is to look-ahead read some elements in input data steams and cache limited number of them to lists in the main memory. The number of elements in any list is bounded by the length of the longest path in the XML document. We show that TwigStackList is I/O optimal for queries with only ancestor-descendant relationships below branching nodes. Further, even when queries contain parent-child relationship below branching nodes, the set of intermediate results in TwigStackList is guaranteed to be a subset of that in previous algorithms. We complement our experimental results on a range of real and synthetic data to show the significant superiority of TwigStackList over previous algorithms for queries with parent-child relationships. <s> BIB001 </s> A Survey of XML Tree Patterns <s> Fig. 12. Sample holistic matching <s> Finding all the occurrences of a twig pattern in an XML database is a core operation for efficient evaluation of XML queries. Holistic twig join algorithm has showed its superiority over binary decompose based approach due to efficient reducing intermediate results. The existing holistic join algorithms, however, cannot deal with ordered twig queries. A straightforward approach that first matches the unordered twig queries and then prunes away the undesired answers is obviously not optimal in most cases. In this paper, we study a novel holistic-processing algorithm, called OrderedTJ, for ordered twig queries. We show that OrderedTJ can identify a large query class to guarantee the I/O optimality. Finally, our experiments show the effectiveness, scalability and efficiency of our proposed algorithm. <s> BIB002 </s> A Survey of XML Tree Patterns <s> Fig. 12. Sample holistic matching <s> Searching for all occurrences of a twig pattern in an XML document is an important operation in XML query processing. Recently a holistic method TwigStack. [2] has been proposed. The method avoids generating large intermediate results which do not contribute to the final answer and is CPU and I/O optimal when twig patterns only have ancestor-descendant relationships. Another important direction of XML query processing is to build structural indexes [3][8][13][15] over XML documents to avoid unnecessary scanning of source documents. We regard XML structural indexing as a technique to partition XML documents and call it streaming scheme in our paper. In this paper we develop a method to perform holistic twig pattern matching on XML documents partitioned using various streaming schemes. Our method avoids unnecessary scanning of irrelevant portion of XML documents. More importantly, depending on different streaming schemes used, it can process a large class of twig patterns consisting of both ancestor-descendant and parent-child relationships and avoid generating redundant intermediate results. Our experiments demonstrate the applicability and the performance advantages of our approach. <s> BIB003 </s> A Survey of XML Tree Patterns <s> Fig. 12. Sample holistic matching <s> Finding all the occurrences of a twig pattern in an XML database is a core operation for efficient evaluation of XML queries. A number of algorithms have been proposed to process a twig query based on region encoding labeling scheme. While region encoding supports efficient determination of structural relationship between two elements, we observe that the information within a single label is very limited. In this paper, we propose a new labeling scheme, called extended Dewey. This is a powerful labeling scheme, since from the label of an element alone, we can derive all the elements names along the path from the root to the element. Based on extended Dewey, we design a novel holistic twig join algorithm, called TJFast. Unlike all previous algorithms based on region encoding, to answer a twig query, TJFast only needs to access the labels of the leaf query nodes. Through this, not only do we reduce disk access, but we also support the efficient evaluation of queries with wildcards in branching nodes, which is very difficult to be answered by algorithms based on region encoding. Finally, we report our experimental results to show that our algorithms are superior to previous approaches in terms of the number of elements scanned, the size of intermediate results and query performance. <s> BIB004 </s> A Survey of XML Tree Patterns <s> Fig. 12. Sample holistic matching <s> XML (Extensible Mark-up Language) has been embraced as a new approach to data modeling. Nowadays, more and more information is formatted as semi-structured data, e.g., articles in a digital library, documents on the web, and so on. Implementation of an efficient system enabling storage and querying of XML documents requires development of new techniques. Many different techniques of XML indexing have been proposed in recent years. In the case of XML data, we can distinguish the following trees: an XML tree, a tree of elements and attributes, and a DataGuide, a tree of element tags and attribute names. Obviously, the XML tree of an XML document is much larger than the DataGuide of a given document. Authors often consider DataGuide as a small tree. Therefore, they consider the DataGuide search as a small problem. However, we show that DataGuide trees are often massive in the case of real XML documents. Consequently, a trivial DataGuide search may be time and memory consuming. In this article, we introduce efficient methods for searching an XML twig pattern in large, complex DataGuide trees. <s> BIB005 </s> A Survey of XML Tree Patterns <s> Fig. 12. Sample holistic matching <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
After merging these intermediate paths, we obtain the label paths below, which correspond to the witness trees represented on the right hand side of Figure 12 . • (2, 11, 2) (3, 4, 3) (7, 8, 3 On one hand, in order to reduce the search space, path summaries that exploit schema information may be used  . If a pattern subtree matches a data tree several times, TwigStack loads streams for all distinct paths, whether these streams contribute to the output or not. Path summaries help distinguish whether the occurrences of each pattern subtree are output elements or not. Those that do not are pruned. On the other hand, TwigStackList better controls the size of intermediate results by buffering parent elements in PC relationships in a main-memory list structure BIB001 . Thus, only AD relationships in branching edges  are handled by TwigStackList, and not in all edges as with TwigStack. OrderedTJ builds upon TwigStackList by handling order specifications in TPs BIB002 . OrderedTJ additionally checks the order conditions of nodes before outputting intermediate paths, with the help of a stack data structure. Since TwigStack and OrderedTJ partition data to streams according to their names alone, two new data streaming techniques are introduced in iTwigJoin BIB003 : the tag+level and prefix path schemes. In the OrderedTJ algorithm, only AD relationships in branching edges are taken into account. The tag+level scheme also takes PC relationships in all edges into account. The prefix path scheme further takes 1-branching into account. An eventual enhancement has been brought by Twig 2 Stack, which optimizes TwigStack by further reducing the size of intermediate results  . Twig 2 Stack associates each query node x with a hierarchical stack. A node x ′ is pushed into hierarchical stack HS[x] if and only if x ′ satisfies the subtwig query rooted at x. Matching can be determined when an entire sub-tree of x ′ is seen with respect to post-order data tree traversal. Baca et al. also fuse TwigStack and Twig 2 Stack along the same line, still to reduce the size of intermediate results BIB005 . Simply replacing the region encoding labeling scheme by the Dewey ID scheme would not particularly improve holistic matching approaches, since they would also need to read labels for all tree nodes. However, exploiting the extended Dewey labeling scheme allows further improvements. TJFast constructs, for each node x in the TP, an input stream T x BIB004 . T x contains the ordered extended Dewey labels of nodes of the same type as x. 1. A branching node is a node whose number of children is greater than one. All edges originating from a branching node are called branching edges BIB001 . As TwigStackList, TJFast assigns, for each branching node b, a set of nodes S b that are potentially query answers. But with TJFast, the size S b is always bounded by the depth of the data tree. TJFast+L further extends TJFast by including the tag+level streaming scheme  . Eventually, Lu et al. have recently identified a key issue in holistic algorithms, called matching cross BIB006 . If a matching cross is encountered, a holistic algorithm either outputs useless intermediate results and becomes suboptimal, or misses useful results and looses its matching power. Based on this observation, the authors designed a set of algorithms, collectively called TreeMatch, which use a concise encoding to present matching results, thus reducing useless intermediate results. TreeMatch has been proved optimal for several classes of queries based on extended TPs (Section 3.2.6).