A Survey of XML Tree Patterns <s> Extended matching <s> Publisher Summary The content of an Active eXtensible Markup Language (AXML) document is dynamic, because it is possible to specify when a service call should be activated (for example, when needed, every hour, etc.), and for how long its result should be considered valid. Thus, this simple mechanism allows capturing and combining different styles of data integration, such as warehousing and mediation. To fully take advantage of the use of services, AXML also allows calling continuous services (that provide streams of answers) and services supporting intentional data (AXML document including service calls) as parameters and/or result. The latter feature leads to powerful, recursive integration schemes. The AXML framework is centered on AXML documents , which are XML documents that may contain calls to Web services. When calls included in an AXML document are fired, the latter is enriched by the corresponding results. <s> BIB001 </s> A Survey of XML Tree Patterns <s> Extended matching <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> BIB002 </s> A Survey of XML Tree Patterns <s> Extended matching <s> With the advent of XML as the de facto language for data publishing and exchange, scalable distribution of XML data to large, dynamic populations of consumers remains an important challenge. Content-based publish/subscribe systems offer a convenient design paradigm, as most of the complexity related to addressing and routing is encapsulated within the network infrastructure. To indicate the type of content that they are interested in, data consumers typically specify their subscriptions using a tree-pattern specification language (an important subset of XPath), while producers publish XML content without prior knowledge of any potential recipients. Discovering semantic communities of consumers with similar interests is an important requirement for scalable content-based systems: such "semantic clusters" of consumers play a critical role in the design of effective content-routing protocols and architectures. The fundamental problem underlying the discovery of such semantic communities lay in effectively evaluating the similarity of different tree-pattern subscriptions based on the observed document stream. In this paper, we propose a general framework and algorithmic tools for estimating different tree-pattern similarity metrics over continuous streams of XML documents. In a nutshell, our approach relies on continuously maintaining a novel, concise synopsis structure over the observed document stream that allows us to accurately estimate the fraction of documents satisfying various Boolean combinations of different tree-pattern subscriptions. To effectively capture different branching and correlation patterns within a limited amount of space, our techniques use ideas from hash-based sampling in a novel manner that exploits the hierarchical structure of our document synopsis. Experimental results with various XML data streams verify the effectiveness of our approach. <s> BIB003 </s> A Survey of XML Tree Patterns <s> Extended matching <s> Satisfiability is an important problem of queries for XML documents. This paper focuses on the satisfiability of tree pattern queries for Active XML(AXML for short) documents conforming to a given AXML schema. An AXML document is an XML document where some data is given explicitly and other parts are defined intensionally by means of embedded calls to Web services, which can be invoked to generate data. For the efficient evaluation of a query over an AXML document, one should check whether there exists an (A)XML document obtained from the original one by invoking some Web services, on which the query has a non-empty answer. An algorithm for checking satisfiability of tree pattern queries for AXML documents that runs polynomial time is proposed based on tree automata theory. Then experiments were made to verify the utility of satisfiability checking as a preprocessing step in queries procession. Our results show that the check takes a negligible fraction of the time needed for processing the query while often yielding substantial savings. <s> BIB004 </s> A Survey of XML Tree Patterns <s> Extended matching <s> ManyWeb applications are based on dynamic interactions between Web components exchanging flows of information. Such a situation arises for instance in mashup systems [22] or when monitoring distributed autonomous systems [6]. This is a challenging problem that has generated recently a lot of attention; see Web 2.0 [38]. For capturing interactions between Web components, we use active documents interacting with the rest of the world via streams of updates. Their input streams specify updates to the document (in the spirit of RSS feeds), whereas their output streams are defined by queries on the document. In most of the paper, the focus is on input streams where the updates are only insertions, although we do consider also deletions. We introduce and study two fundamental concepts in this setting, namely, satisfiability and relevance. Some fact is satisfiable for an active document and a query if it has a chance to be in the result of the query in some future state. Given an active document and a query, a call in the document is relevant if the data brought by this call has a chance to impact the answer to the query. We analyze the complexity of computing satisfiability in our core model (insertions only) and for extensions (e.g., with deletions). We also analyze the complexity of computing relevance in the core model. <s> BIB005
We review in this section two ways of "pushing" matching further on. The first one relates to checking the satisfiability of TPs against Active XML (AXML) documents BIB004 , BIB005 . AXML documents contain both data defined in extension (as in XML documents) and in intention, by means of Web service calls BIB001 . When a Web service is invoked, its result is inserted into the document. In this context, a priori checking whether a query (TP) is satisfiable, i.e., whether there exists any document the TP matches against, helps avoid unnecessary query computations. Although TP satisfiability is well studied BIB002 , with AXML documents, Web service calls may also return data that contribute to query results, which makes the problem even more complex. Here, some fact is satisfiable for an AXML document and a query if it can be in the query result in some future state BIB005 . As Miklau and Suciu did for containment testing (Section 4.1.1), Ma et al. use tree automata to represent both TPs and sets of AXML documents conforming to a given schema. Then, the product tree automaton helps decide whether a TP matches any document. Abiteboul et al. further test the relevance of Web service calls, i.e., whether the result can impact query answer BIB005 . The other example of matching enhancement lies in the context of building semantic communities, i.e., clusters of users with similar interests modeled as TPs. Chand et al. propose to replace equivalence by similarity in matching, which could more generally be used to approximate XML queries BIB003 , as TP relaxation (Section 4.3.2). Chand et al. formulate the TP similarity problem as follows. Let S be a set of TPs, D a set of data trees, and p, q ∈ S. The similarity of p and q is a function sim : S 2 → [0, 1] such that sim(p, q) is the probability that p matches the same subset of data from D as q. Note that, depending on the proximity metric, sim(p, q) may be different from sim(q, p).