A Survey of XML Tree Patterns <s> Tree pattern rewriting <s> Peer data management systems (PDMS) offer a flexible architecture for decentralized data sharing. In a PDMS, every peer is associated with a schema that represents the peer's domain of interest, and semantic relationships between peers are provided locally between pairs (or small sets) of peers. By traversing semantic paths of mappings, a query over one peer can obtain relevant data from any reachable peer in the network. Semantic paths are traversed by reformulating queries at a peer into queries on its neighbors.Naively following semantic paths is highly inefficient in practice. We describe several techniques for optimizing the reformulation process in a PDMS and validate their effectiveness using real-life data sets. In particular, we develop techniques for pruning paths in the reformulation process and for minimizing the reformulated queries as they are created. In addition, we consider the effect of the strategy we use to search through the space of reformulations. Finally, we show that pre-computing semantic paths in a PDMS can greatly improve the efficiency of the reformulation process. Together, all of these techniques form a basis for scalable query reformulation in PDMS.To enable our optimizations, we developed practical algorithms, of independent interest, for checking containment and minimization of XML queries, and for composing XML mappings. <s> BIB001 </s> A Survey of XML Tree Patterns <s> Tree pattern rewriting <s> We study the query answering using views (QAV) problem for tree pattern queries. Given a query and a view, the QAV problem is traditionally formulated in two ways: (i) find an equivalent rewriting of the query using only the view, or (ii) find a maximal contained rewriting using only the view. The former is appropriate for classical query optimization and was recently studied by Xu and Ozsoyoglu for tree pattern queries (TP). However, for information integration, we cannot rely on equivalent rewriting and must instead use maximal contained rewriting as shown by Halevy. Motivated by this, we study maximal contained rewriting for TP, a core subset of XPath, both in the absence and presence of a schema. In the absence of a schema, we show there are queries whose maximal contained rewriting (MCR) can only be expressed as the union of exponentially many TPs. We characterize the existence of a maximal contained rewriting and give a polynomial time algorithm for testing the existence of an MCR. We also give an algorithm for generating the MCR when one exists. We then consider QAV in the presence of a schema. We characterize the existence of a maximal contained rewriting when the schema contains no recursion or union types, and show that it consists of at most one TP. We give an efficient polynomial time algorithm for generating the maximal contained rewriting whenever it exists. Finally, we discuss QAV in the presence of recursive schemas. <s> BIB002 </s> A Survey of XML Tree Patterns <s> Tree pattern rewriting <s> Contained rewriting and maximal contained rewriting of tree pattern queries using views have been studied recently for the class of tree patterns involving /, //, and []. Given query Q and view V , it has been shown that a contained rewriting of Q using V can be obtained by finding a useful embedding of Q in V . However, for the same Q and V , there may be many useful embeddings and thus many contained rewritings. Some of the useful embeddings may be redundant in that the rewritings obtained from them are contained in those obtained from other useful embeddings. Redundant useful embeddings are useless and they waste computational resource. Thus it becomes important to identify and remove them. In this paper, we show that the criteria for identifying redundant useful embeddings given in a previous work are neither sufficient nor necessary. We then present some useful observations on the containment relationship of rewritings, and based on which, a heuristic algorithm for removing redundant useful embeddings. We demonstrate the efficiency of our algorithm using examples. <s> BIB003
Query rewriting is casually used when views, whether they are materialized or not, are defined over data. Rewriting a query Q that runs against a database D is formulating a query Q ′ that runs against a view V built from D such that Q and Q ′ output the same result. When data are tree-structured, views are predefined TPs. Then, Q ′ is found among so-called useful embeddings (UEs) of Q in V ; the problem being to prune redundant, useless UEs BIB003 . The heuristics that address this issue BIB003 ,  , BIB002 rely on containment testing (Section 4.1.1) to output a minimal set of UEs. Query rewriting is also notably used in Peer Data Management Systems (PDMSs). In a PDMS, each peer is associated with a schema that represents the peer's domain of interest, as well as semantic relationships to neighboring peers. Thus, a query over one peer can obtain relevant data from any reachable peer in the PDMS. Semantic paths are traversed by reformulating queries at a peer into queries on its neighbors, and then to the neighbors' neighbors, recursively. In the Piazza PDMS BIB001 , data is modeled in XML, peer schemas in XML Schema, and queries in a subset of XQuery. Thus, query reformulation optimization strongly relates to TP matching optimization. For instance, one query may follow multiple paths in a PDMS, and thus may induce redundant reformulations, i.e., redundant queries on the peers. Pruning queries help reduce such redundancy. Pruning requires checking query containment (Section 4.1.1) between a previously obtained reformulation and a new one. The reformulating process may also introduce redundant subexpressions in a query, leading to query minimization (Section 4.1).