A Survey of XML Tree Patterns <s> Fig. 1. Tree representation of XML documents and queries <s> Extensible markup language (XML) is emerging as a de facto standard for information exchange among various applications on the World Wide Web. There has been a growing need for developing high-performance techniques to query large XML data repositories efficiently. One important problem in XML query processing is twig pattern matching, that is, finding in an XML data tree D all matches that satisfy a specified twig (or path) query pattern Q. In this survey, we review, classify, and compare major techniques for twig pattern matching. Specifically, we consider two classes of major XML query processing techniques: the relational approach and the native approach. The relational approach directly utilizes existing relational database systems to store and query XML data, which enables the use of all important techniques that have been developed for relational databases, whereas in the native approach, specialized storage and query processing systems tailored for XML data are developed from scratch to further improve XML query performance. As implied by existing work, XML data querying and management are developing in the direction of integrating the relational approach with the native approach, which could result in higher query processing performance and also significantly reduce system reengineering costs. <s> BIB001 </s> A Survey of XML Tree Patterns <s> Fig. 1. Tree representation of XML documents and queries <s> An n type diffusion region and a p type diffusion region are formed in a region sandwiched between trenches arranged at a first main surface of a semiconductor substrate. A p type well is formed in the n- and p-type diffusion regions nearer the first main surface. A source n+ diffusion region is formed at the first main surface within the p type well. A gate electrode layer is formed opposite to the p type well sandwiched between the n type diffusion region and the source n+ diffusion region with a gate insulating layer disposed therebetween. The n- and p-type diffusion regions each have an impurity concentration distribution diffused from a sidewall surface of a trench. Thus, a fine, micron-order pn repeat structure can be achieved with sufficient precision and a high breakdown voltage semiconductor device is thus obtained which has superior on-state voltage and breakdown voltage as well as fast switching characteristics. <s> BIB002 </s> A Survey of XML Tree Patterns <s> Fig. 1. Tree representation of XML documents and queries <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> BIB003
Since the early 2000s, a tremendous amount of research has been based on, focusing on, or exploiting TPs for various purposes. However, few related reviews exist. Gou and Chirkova extensively survey querying techniques over persistently stored XML data BIB001 . Although the intersection between their paper and ours is not empty, both papers are complementary. We do not address approaches related to the relational storage of XML data. By focusing on native XML query processing, we complement Gou and Chirkova's work with specificities such as TP structure, minimization approaches and sample applications. Moreover, we cover the many matching optimization techniques that have appeared since 2007. Other recent surveys are much shorter and focus on a particular issue, i.e., twig queries BIB002 and holistic matching BIB003 . The aim of this paper is thus to provide a global and synthetic overview of more than ten years of research about TPs and closely related issues. For this sake, we first formally define TPs and related concepts in Section 2. Then, we present and discuss various alternative TP structures in Section 3. Since the efficiency of TP matching against tree-structured data is central in TP usage, we review the two main families of TP matching optimization methods (namely, TP minimization and holistic matching approaches), as well as tangential but nonetheless interesting methods, in Section 4. Finally, we briefly illustrate the use of TPs through actual TP-based developments in Section 5. We conclude this paper and provide insight about future TP-related research in Section 6.