A Survey of XML Tree Patterns <s> Supported optimizations <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> Supported optimizations <s> In this paper, we investigate the complexity of deciding the satisfiability of XPath 2.0 expressions, i.e., whether there is an XML document for which their result is nonempty. Several fragments that allow certain types of expressions are classified as either in PTIME or NP-hard to see which type of expression make this a hard problem. Finally, we establish a link between XPath expressions and partial tree descriptions which are studied in computational linguistics. <s> BIB002 </s> A Survey of XML Tree Patterns <s> Supported optimizations <s> XPath and XQuery (which includes XPath as a sublanguage) are the major query languages for XML. An important issue arising in efficient evaluation of queries expressed in these languages is satisfiability, i.e., whether there exists a database, consistent with the schema if one is available, on which the query has a non-empty answer. Our experience shows satisfiability check can effect substantial savings in query evaluation. ::: ::: We systematically study satisfiability of tree pattern queries (which capture a useful fragment of XPath) together with additional constraints, with or without a schema. We identify cases in which this problem can be solved in polynomial time and develop novel efficient algorithms for this purpose. We also show that in several cases, the problem is NP-complete. We ran a comprehensive set of experiments to verify the utility of satisfiability check as a preprocessing step in query processing. Our results show that this check takes a negligible fraction of the time needed for processing the query while often yielding substantial savings. <s> BIB003 </s> A Survey of XML Tree Patterns <s> Supported optimizations <s> We consider Boolean combinations of data tree patterns as a specification and query language for XML documents. Data tree patterns are tree patterns plus variable (in)equalities which express joins between attribute values. Data tree patterns are a simple and natural formalism for expressing properties of XML documents. We consider first the model checking problem (query evaluation), we show that it is DP-complete in general and already NP -complete when we consider a single pattern. We then consider the satisfiability problem in the presence of a DTD. We show that it is in general undecidable and we identify several decidable fragments. <s> BIB004 </s> A Survey of XML Tree Patterns <s> Supported optimizations <s> We study the satisfiability problem associated with XPath in the presence of DTDs. This is the problem of determining, given a query p in an XPath fragment and a DTD D, whether or not there exists an XML document T such that T conforms to D and the answer of p on T is nonempty. We consider a variety of XPath fragments widely used in practice, and investigate the impact of different XPath operators on the satisfiability analysis. We first study the problem for negation-free XPath fragments with and without upward axes, recursion and data-value joins, identifying which factors lead to tractability and which to NP-completeness. We then turn to fragments with negation but without data values, establishing lower and upper bounds in the absence and in the presence of upward modalities and recursion. We show that with negation the complexity ranges from PSPACE to EXPTIME. Moreover, when both data values and negation are in place, we find that the complexity ranges from NEXPTIME to undecidable. Furthermore, we give a finer analysis of the problem for particular classes of DTDs, exploring the impact of various DTD constructs, identifying tractable cases, as well as providing the complexity in the query size alone. Finally, we investigate the problem for XPath fragments with sibling axes, exploring the impact of horizontal modalities on the satisfiability analysis. <s> BIB005
Approaches purposely proposing TPs (i.e., algebraic approaches) are much fewer than approaches using TPs to optimize XML querying. Moreover, even algebraic approaches such as TAX do address optimization issues. Since XML queries are easy to model with TPs, researchers casually translate any XML query in TPs, which are then optimized and implemented in algorithms, XML queries or any other optimization framework. Hence, the biggest interest of the TP community lies in enriching and optimizing matching. Matching opportunities offered by TAX TPs, optional edges of GTPs, annotations, ordering specification and duplicate elimination of APTs, and extended TPs aim to achieve more results and/or better precision. GTP and APT matching characteristics prove their efficiency in TIMBER BIB001 . Finally, satisfiability is an issue related to containment, a concept used in minimization approaches. Satisfiability means that there exists a database, consistent with the schema if one is available, on which the user query, represented by a TP, has a non-empty answer BIB003 , BIB002 , BIB004 , BIB005 .