A Survey of XML Tree Patterns <s> Labeling phase <s> In this paper we present the data manipulation facility for a structured English query language (SEQUEL) which can be used for accessing data in an integrated relational data base. Without resorting to the concepts of bound variables and quantifiers SEQUEL identifies a set of simple operations on tabular structures, which can be shown to be of equivalent power to the first order predicate calculus. A SEQUEL user is presented with a consistent set of keyword English templates which reflect how people use tables to obtain information. Moreover, the SEQUEL user is able to compose these basic templates in a structured manner in order to form more complex queries. SEQUEL is intended as a data base sublanguage for both the professional programmer and the more infrequent data base user. <s> BIB001 </s> A Survey of XML Tree Patterns <s> Labeling phase <s> With the advent of XML as a standard for data representation and exchange on the Internet, storing and querying XML data becomes more and more important. Several XML query languages have been proposed, and the common feature of the languages is the use of regular path expressions to query XML data. This poses a new challenge concerning indexing and searching XML data, because conventional approaches based on tree traversals may not meet the processing requirements under heavy access requests. In this paper, we propose a new system for indexing and storing XML data based on a numbering scheme for elements. This numbering scheme quickly determines the ancestor-descendant relationship between elements in the hierarchy of XML data. We also propose several algorithms for processing regular path expressions, namely, (1) -Join for searching paths from an element to another, (2) -Join for scanning sorted elements and attributes to find element-attribute pairs, and (3) -Join for finding Kleene-Closure on repeated paths or elements. The -Join algorithm is highly effective particularly for searching paths that are very long or whose lengths are unknown. Experimental results from our prototype system implementation show that the proposed algorithms can process XML queries with regular path expressions by up to an or <s> BIB002 </s> A Survey of XML Tree Patterns <s> Labeling phase <s> XML employs a tree-structured data model, and, naturally, XML queries specify patterns of selection predicates on multiple elements related by a tree structure. Finding all occurrences of such a twig pattern in an XML database is a core operation for XML query processing. Prior work has typically decomposed the twig pattern into binary structural (parent-child and ancestor-descendant) relationships, and twig matching is achieved by: (i) using structural join algorithms to match the binary relationships against the XML database, and (ii) stitching together these basic matches. A limitation of this approach for matching twig patterns is that intermediate result sizes can get large, even when the input and output sizes are more manageable.In this paper, we propose a novel holistic twig join algorithm, TwigStack, for matching an XML query twig pattern. Our technique uses a chain of linked stacks to compactly represent partial results to root-to-leaf query paths, which are then composed to obtain matches for the twig pattern. When the twig pattern uses only ancestor-descendant relationships between elements, TwigStack is I/O and CPU optimal among all sequential algorithms that read the entire input: it is linear in the sum of sizes of the input lists and the final result list, but independent of the sizes of intermediate results. We then show how to use (a modification of) B-trees, along with TwigStack, to match query twig patterns in sub-linear time. Finally, we complement our analysis with experimental results on a range of real and synthetic data, and query twig patterns. <s> BIB003 </s> A Survey of XML Tree Patterns <s> Labeling phase <s> XML is quickly becoming the de facto standard for data exchange over the Internet. This is creating a new set of data management requirements involving XML, such as the need to store and query XML documents. Researchers have proposed using relational database systems to satisfy these requirements by devising ways to "shred" XML documents into relations, and translate XML queries into SQL queries over these relations. However, a key issue with such an approach, which has largely been ignored in the research literature, is how (and whether) the ordered XML data model can be efficiently supported by the unordered relational data model. This paper shows that XML's ordered data model can indeed be efficiently supported by a relational database system. This is accomplished by encoding order as a data value. We propose three order encoding methods that can be used to represent XML order in the relational data model, and also propose algorithms for translating ordered XPath expressions into SQL using these encoding methods. Finally, we report the results of an experimental study that investigates the performance of the proposed order encoding methods on a workload of ordered XML queries and updates. <s> BIB004 </s> A Survey of XML Tree Patterns <s> Labeling phase <s> Efficient evaluation of XML queries requires the determination of whether a relationship exists between two elements. A number of labeling schemes have been designed to label the element nodes such that the relationships between nodes can be easily determined by comparing their labels. With the increased popularity of XML on the Web, finding a labeling scheme that is able to support order-sensitive queries in the presence of dynamic updates becomes urgent. We propose a new labeling scheme that take advantage of the unique property of prime numbers to meet this need. The global order of the nodes can be captured by generating simultaneous congruence values from the prime number node labels. Theoretical analysis of the label size requirements for the various labeling schemes is given. Experiment results indicate that the prime number labeling scheme is compact compared to existing dynamic labeling schemes, and provides efficient support to order-sensitive queries and updates. <s> BIB005 </s> A Survey of XML Tree Patterns <s> Labeling phase <s> We introduce a hierarchical labeling scheme called ORDPATH that is implemented in the upcoming version of Microsoft® SQL Server™. ORDPATH labels nodes of an XML tree without requiring a schema (the most general case---a schema simplifies the problem). An example of an ORDPATH value display format is "1.5.3.9.1". A compressed binary representation of ORDPATH provides document order by simple byte-by-byte comparison and ancestry relationship equally simply. In addition, the ORDPATH scheme supports insertion of new nodes at arbitrary positions in the XML tree, their ORDPATH values "careted in" between ORDPATHs of sibling nodes, without relabeling any old nodes. <s> BIB006 </s> A Survey of XML Tree Patterns <s> Labeling phase <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> BIB007 </s> A Survey of XML Tree Patterns <s> Labeling phase <s> XPath expressions define navigational queries on XML data and are issued on XML documents to select sets of element nodes. Due to the wide use of XPath, which is embedded into several languages for querying and manipulating XML data, the problem of efficiently answering XPath queries has received increasing attention from the research community. As the efficiency of computing the answer of an XPath query depends on its size, replacing XPath expressions with equivalent ones having the smallest size is a crucial issue in this direction. This article investigates the minimization problem for a wide fragment of XPath (namely X Plsr), where the use of the most common operators (child, descendant, wildcard and branching) is allowed with some syntactic restrictions. The examined fragment consists of expressions which have not been specifically studied in the relational setting before: neither are they mere conjunctive queries (as the combination of “//” and “*” enables an implicit form of disjunction to be expressed) nor do they coincide with disjunctive ones (as the latter are more expressive). Three main contributions are provided. The “global minimality” property is shown to hold: the minimization of a given XPath expression can be accomplished by removing pieces of the expression, without having to re-formulate it (as for “general” disjunctive queries). Then, the complexity of the minimization problem is characterized, showing that it is the same as the containment problem. Finally, specific forms of XPath expressions are identified, which can be minimized in polynomial time. <s> BIB008 </s> A Survey of XML Tree Patterns <s> Labeling phase <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> BIB009 </s> A Survey of XML Tree Patterns <s> Labeling phase <s> Labeling schemes lie at the core of query processing for many XML database management systems. Designing labeling schemes for dynamic XML documents is an important problem that has received a lot of research attention. Existing dynamic labeling schemes, however, often sacrifice query performance and introduce additional labeling cost to facilitate arbitrary updates even when the documents actually seldom get updated. Since the line between static and dynamic XML documents is often blurred in practice, we believe it is important to design a labeling scheme that is compact and efficient regardless of whether the documents are frequently updated or not. In this paper, we propose a novel labeling scheme called DDE (for Dynamic DEwey) which is tailored for both static and dynamic XML documents. For static documents, the labels of DDE are the same as those of dewey which yield compact size and high query performance. When updates take place, DDE can completely avoid re-labeling and its label quality is most resilient to the number and order of insertions compared to the existing approaches. In addition, we introduce Compact DDE (CDDE) which is designed to optimize the performance of DDE for insertions. Both DDE and CDDE can be incorporated into existing systems and applications that are based on dewey labeling scheme with minimum efforts. Experiment results demonstrate the benefits of our proposed labeling schemes over the previous approaches. <s> BIB010 </s> A Survey of XML Tree Patterns <s> Labeling phase <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> BIB011
The aim of data tree labeling schemes is to determine the relationship (i.e., PC or AD) between two nodes of a tree from their labels alone  . Many labeling schemes have been proposed in the literature. We particularly focus in this section on the region encoding (or containment) and the Dewey ID (or prefix) labeling schemes that are used in holistic approaches. However, other approaches do exist, based on a treetraversal order BIB002 , prime numbers BIB005 or a combination of structural index and inverted lists  , for instance. The region encoding scheme BIB003 labels each node x in a data tree t with a 3-tuple (start, end, level), where start (respectively, end) is a counter from the root of t until the start (respectively, the end) of x (in depth first), and level is the depth of x in t. For example, the data tree from Figure 2 (a) is labeled in Figure 11 , with the region encoding scheme label indicated between Fig. 11 . Sample data tree labeling parentheses. In Figure 11 , node x(title = "Maktub") is labeled    . start = 3 because x is the first child of the node with start = 2; end = 4 because x has no children (thus end = start + 1); and level = 3 (level 1 being the root's). Now, let x and x ′ be two nodes labeled (S, E, L) and (S ′ , E ′ , L ′ ), respectively. Then: • x ′ is a descendant of x if and only if S < S ′ and E ′ < E; • x ′ is a child of x if and only if S < S For example, in Figure 11 , node (author = "Jack") labeled BIB009 BIB011  ) is a descendant from the node book labeled (12, 25, 2) and a child of node authors labeled BIB001 BIB008  . The Dewey ID scheme BIB004 labels tree nodes as a sequence. The root node is labeled ǫ (empty). Its children are labeled 0, 1, 2, etc. Then, at any subsequent level, the children of node x are labeled label(x).0, label(x).1, label(x).2, etc. More formally, for each nonroot element x ′ , label(x ′ ) = label(x).i, where x ′ is the i th child of x. Thus, each label embeds all ancestors of the associated node. For example, in Figure 11 , the Dewey ID label is featured on the right hand side of the "/", for each node. Node (author = "Jack"), labeled 1.1.1, is the second child of the node labeled 1.1 (i.e., authors), and a descendant of the node labeled 1 (i.e., the right hand side book). The Dewey ID scheme has been extended to incorporate node names BIB007 , by exploiting schema information available in a DTD or XML schema. Encoding node names along a path into a Dewey label provides not only the labels of the ancestors of a given node, but also their names. Moreover, the Dewey ID scheme suffers from a high relabeling cost for dynamic XML documents where nodes can be arbitrarily inserted and deleted. Thus, variant schemes, namely ORD-PATH BIB006 and Dynamic DEwey (DDE) BIB010 , have been devised to dynamically extend the domain of label component values, so that no global relabeling is required. The main difference between the region encoding and Dewey ID labeling schemes lies in the way structural relationships can be inferred from a label. While region encoding necessitates two nodes to determine whether they are related by a PC or AD relationship, Dewey IDs directly relate to ancestors and thus only require to know the current node's label. A Dewey ID-labeled data tree is also easier to update than a region encoded data tree  .