Evgeny Kharlamov
email: kharlamov@inf.unibz.it

Werner Nutt
email: nutt@inf.unibz.it

Pierre Senellart
email: pierre.senellart@telecom-paristech.fr

Value Joins are Expensive over (Probabilistic) XML *

We address the cost of adding value joins to tree-pattern queries and monadic second-order queries over trees in terms of the tractability of query evaluation over two data models: XML and probabilistic XML. Our results show that the data complexity rises from linear, for join-free queries, to intractable, for queries with value joins, while combined complexity remains essentially the same. For treepattern queries with joins (TPJ) the complexity jump is only on probabilistic XML, while for monadic second-order logic over trees with joins (TMSOJ) it already appears for deterministic XML documents. Moreover, for TPJ queries that have a single join, we show a dichotomy: every query is either essentially join-free, and in this case it is tractable over probabilistic XML, or it is intractable. In this light we study the problem of deciding whether a query with joins is essentially join-free. For TMSOJ we prove that this problem is undecidable and for TPJ it is Π P 2 -complete. Finally, for TPJ we provide a conceptually simple criterion to check whether a given query is essentially join free.

INTRODUCTION

.

 settings. We focus here on the latter, which is particularly adapted in the case, common on the Web, when the information is not strictly constrained by a schema, or when it is inherently tree-like (mailing lists, parse trees of

natural language sentences, etc.). A number of works on probabilistic XML have dealt with query answering for a variety of models and query languages [START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF][START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF][START_REF] Abiteboul | Aggregate queries for discrete and continuous probabilistic XML[END_REF][START_REF] Benedikt | Probabilistic XML via Markov chains[END_REF]. On the other hand, queries with value joins, equating character data in different fragments of XML documents, have received far less attention, with the exception of [START_REF] Abiteboul | Aggregate queries for discrete and continuous probabilistic XML[END_REF]. This is despite the fact that value joins proved their importance in SQL: joins are at the core of SELECT-PROJECT-JOIN, the most used fragment of SQL. We propose in this article a general study of the complexity of query answering in both XML and probabilistic XML with hierarchical probabilistic dependencies [START_REF] Van Keulen | A probabilistic XML approach to data integration[END_REF][START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF] (see Section 2 for details).

The first work addressing join queries for probabilistic XML data is [START_REF] Abiteboul | Aggregate queries for discrete and continuous probabilistic XML[END_REF] where we showed that adding joins to tree-pattern queries (TP) significantly increases complexity of query answering. This is a data complexity [START_REF] Vardi | The complexity of relational query languages (extended abstract)[END_REF] result, i.e, we measured the complexity in the size of the input probabilistic XML data, and the query is assumed to be fixed, in contrast to combined complexity, where both the data and the query are parts of the input.

The complexity shift was shown by exhibiting a #P-hard query (see Section 3 for details), which shows that the whole class of tree-pattern queries with joins (TPJ), is intractable. Recall that for TP, and, indeed, for all of monadic second-order logic over trees (TMSO), which subsumes TP, query evaluation is linear in data complexity. This raises a number of questions about query language with joins, that this work aims at answering:

• What is the precise complexity of query evaluation, over XML and probabilistic XML, for TPJ and TMSO extended with joins (TMSOJ), both in data and combined complexity? • We say that a TMSOJ (resp., TPJ) query has an essential join if it is not equivalent to a TMSO (resp., TP query). A query without essential join is called an essentially join-free query. Is it possible to decide, given a TMSOJ or TPJ query, whether this query really has any essential join? • Is the fact that a query has an essential join responsible for making it hard? In other words, are all queries with essential joins hard to evaluate? The rest of the paper is devoted to answering these questions. In Section 2 we introduce deterministic and probabilistic data models, tree-pattern and monadic second-order queries, and review related work on query answering for these models. In Section 3 we extend the query models with joins. In Sections 4 and 5 we study the complexity of joins over XML and probabilistic XML as well as the complexity of deciding essential joins. Due to lack of space we omit some proofs that can be found in a technical report [START_REF] Kharlamov | Value joins are expensive over (probabilistic) XML (extended version)[END_REF].

PRELIMINARIES

We briefly define in this section the data model (see, e.g., [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF] for more details) and the query languages we use.

d PER :

[1] IT-personnel [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF] Rick [START_REF] Benedikt | Probabilistic XML via Markov chains[END_REF] name [START_REF] Benedikt | XPath leashed[END_REF] bonus [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF] person [START_REF] Ajtai | The closure of monadic NP[END_REF] person [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF] name [START_REF] Chang | A survey of Web information extraction systems[END_REF] bonus

[51] pda [41] Mary [START_REF] Stockmeyer | The polynomial-time hierarchy[END_REF] laptop

[31] pda

[32] 50 [START_REF] Thomas | Languages, automata, and logic[END_REF] 44 [START_REF] Trakhtenbrot | Impossibility of an algorithm for the decision problem in finite classes[END_REF] x x [START_REF] Abiteboul | Aggregate queries for discrete and continuous probabilistic XML[END_REF] IT-personnel [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF] Rick mux [START_REF] Gottlob | Conjunctive queries over trees[END_REF] John [START_REF] Benedikt | Probabilistic XML via Markov chains[END_REF] name [START_REF] Benedikt | XPath leashed[END_REF] bonus [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF] person [START_REF] Ajtai | The closure of monadic NP[END_REF] person mux [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF] name [START_REF] Chang | A survey of Web information extraction systems[END_REF] bonus

[51] pda mux det

[56] 15 [START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF] pda

[41] Mary 0.1 [START_REF] Stockmeyer | The polynomial-time hierarchy[END_REF] laptop [31] pda [32] 50 [START_REF] Rahm | A survey of approaches to automatic schema matching[END_REF] 25 [START_REF] Thomas | Languages, automata, and logic[END_REF] 44 [START_REF] Trakhtenbrot | Impossibility of an algorithm for the decision problem in finite classes[END_REF] 50 [54] 15

[55] 44 0.7 0.3 0.9 0.75 0.25 [START_REF] Deutsch | Containment and integrity constraints for XPath[END_REF] [21]

[52]

[53] P PER : Documents. We assume a countable set of labels ℒ. We model an XML document as an unranked, labeled, and unordered tree.

Results of this paper can be extended to ordered trees. We say that two documents 1 and 2 are equivalent, denoted 1 ∼ 2, if they share the same structure and labels, i.e., if there is a bijection between the nodes of 1 and 2 preserving the edges, root, and labels. EXAMPLE 1. Consider the document PER in Figure 1 (top-left) describing the personnel of an IT department and the bonuses for different projects. It indicates that Rick worked under two projects (laptop and pda) and got bonuses of 44 and 50 in the former project and 50 in the latter one. Identifiers are in brackets before labels.

We define a finite probability space of XML documents, or pxspace for short, as a pair (, Pr) with a set of pairwise nonequivalent documents and Pr mapping every document to a probability Pr()

such that  {Pr() | ∈ } = 1.
Probabilistic documents. Following [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF], p-documents are a general syntax for compactly representing px-spaces. Like a document, a p-document is a tree but is has two kinds of nodes: ordinary nodes, which have labels and are the same as in documents, and distributional nodes, which are used to define the probabilistic process for generating random documents. We consider in this work two kinds of distributional nodes, namely, mux (for mutually exclusive) and det (for deterministic). Other kinds of distributional nodes are studied in [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF], but as shown there, mux and det alone are enough to represent all px-spaces as p-documents, and mux-det p-documents can be seen as XML counterparts of the block-independent databases of Dalvi, Ré, and Suciu [START_REF] Dalvi | Probabilistic databases: Diamonds in the dirt[END_REF]. An important characteristic of these distributional nodes that will play a fundamental role in the tractability of query evaluation is the fact that they only describe local probabilistic dependencies in the tree. Formally, a p-document  is an unranked, unordered tree, with labels in ℒ ∪ {mux(Pr)} ∪ {det}. If a node is labeled with mux(Prv) then Prv assigns to each child ′ of a probability Prv( ′ ) with

 v ′ Prv( ′ ) ≤ 1.
We require the leaves and the root of a p-document to be ordinary nodes, that is, with labels in ℒ.

The class of all mux-det p-documents is denoted PrXML mux,det .

EXAMPLE 2. Figure 1 (right) shows a p-document

PER that has mux and det distributional nodes, shown on gray background. Node 52 is a mux node with two children 53 and 56, where Prn 52 (53) = 0.7 and Prn 52 (56) = 0.3.

A p-document

has as associated semantics a px-space  defined by the following random process. Independently for each mux(Prv) node, we select at most one of its children ′ and delete all other children with their descendants. We do not delete any of the children of det nodes. We then remove in turn each distributional node, connecting its ordinary children with their lowest ordinary ancestors. The result of this process is a random document , and the probability of a specific run is the product of all Prv( ′ ) for each chosen child ′ of a mux node ; when we choose no children for a mux node , we multiply by 1 - v ′ Prv( ′ ) instead. Since there may be several different ways to generate a document equivalent to , we define the probability Pr() of a random document as: Pr() :=  d∼ d . It is easy to see that if we select one representative of each equivalence class, we obtain a px-space. EXAMPLE 3. The only way to obtain a document equivalent to PER at Figure 1 from  PER is to choose: the left child of 11, the right child of 21, and the left one of 52. The probability of these choices, and the probability of PER, is 0.4725 = 0.75 × 0.9 × 0.7.

Queries over documents.

We now define two Boolean query languages over XML documents, namely monadic second-order queries and tree-pattern queries. We first define join-free versions of these query languages and add value joins in Section 3. A Boolean query over documents can be seen as a mapping from every XML document to either true or false. We thus say that a query is true in a document , or that is a model of , and we note |= . Given two queries and ′ , we say that is contained in ′ , denoted ⊑ ′ , if all models of are also models of ′ . Two Boolean queries are equivalent, denoted ≡ ′ , if ⊑ ′ and ′ ⊑ .

Monadic second-order queries. The first query language we consider is monadic second-order logic over trees (TMSO for short), a general query language that has the property of having linear data complexity, due to the fact that every TMSO query can be converted (in non-elementary time) into a deterministic bottom-up tree automaton [START_REF] Thomas | Languages, automata, and logic[END_REF]. TMSO is more expressive than other classical join-free XML query languages such as tree-pattern queries with Boolean operators [START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF] or navigational XPath [START_REF] Benedikt | XPath leashed[END_REF].

TMSO is the logic built up from: (i) unary predicates for labels: for every ∈ ℒ there is a unary predicate Label l (•); (ii) the binary child relation Ch(•, •); (iii) node variables; and (iv) monadic (i.e., unary) predicate variables via Boolean connectors, and first and second-order quantifiers ∃, ∃. Since we consider only Boolean queries, we assume all variables occurring in a TMSO query are bound by a quantifier. The semantics of TMSO is standard [START_REF] Thomas | Languages, automata, and logic[END_REF]. A descendant predicate Desc can be expressed in TMSO using the Ch predicate and quantifiers; we will use Desc when needed as if it were part of TMSO. The language TFO of first-order queries on trees is TMSO without any second-order quantifiers.

Tree-pattern queries. Monadic second-order logic is a very expressive query language on trees. The language of tree-pattern queries (TP), roughly the subset of navigational XPath with only child and descendant axes, has more limited expressive power, but, as we shall discuss, more efficient query evaluation algorithms. Let be a countable set of variables, disjoint from ℒ. A treepattern query is an unordered, unranked tree, with labels in ℒ ∪ , where edges are labeled either with child, or descendant types. A variable from may not be used twice in the same query (we will obviously remove this assumption when we introduce joins). Note that in TMSO variables denote nodes, while in TP, with a slight overloading, they denote (unknown) labels of nodes. A subquery of ∈ TP is any subtree of . A TP query is true in a document if and only if there is a mapping from the nodes of the query to the nodes of such that: (i) if is the root of , then () is the root of ; (ii) if , are two nodes of connected by a child edge, () is a child of (); (iii) if , are two nodes of connected by a descendant edge, () is a descendant of (); (iv) unless is labeled with a variable of , and () have the same labels. A mapping satisfying all these conditions is also called a homomorphism. EXAMPLE 4. Consider the query RBON in Figure 1 (bottomright) asking whether Rick has received any bonus, i.e., a bonus . Single lines denote child edges and double lines descendant edges.

Querying p-documents. Up to now, we have seen Boolean queries as Boolean functions over documents. Over a p-document, a Boolean query naturally yields a probability: the probability this query is true in the set of possible documents defined by this document. More formally, given a query and a p-document  , the semantics of over  is the probability (

) :=  d∈  d|=q Pr().
This definition yields an algorithm for computing the probability of a Boolean query over a p-document, given an algorithm for determining whether a query is true in a document: just enumerate all possible worlds, evaluate the query over each of these, and sum up the probability of documents satisfying the query. This algorithm is exponential-time, however, and it is often possible to be more efficient than that. EXAMPLE The complexity of join-free queries. Before reviewing the complexity of query answering for the aforementioned query languages, we make some preliminary remarks on complexity classes. Note first that for XML all problems are decision problems, i.e., to decide whether a query matches a document. In contrast, for p-documents all problems are computational, i.e., to compute the probability value. We thus need computational complexity classes such as FP (resp., FPSpace), the class of computational problems that can be solved by a Turing machine with output tape in polynomial time (resp., polynomial space), instead of the decision classes PTime or PSpace. The class #P is the class of computational problems that can be computed by counting the number of accepting runs of a nondeterministic polynomial-time Turing machine.

Following [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF], we say that a function is FP #P -hard if there is a polynomial-time Turing reduction (that is, a reduction with access to an oracle to the problem reduced to) from every function in FP #P to it. Hardness for #P is defined in a standard way using Karp (many-one) reductions. For example, the function that counts for a propositional 2-DNF formula its number of satisfying assignments is #P-complete.We note that the use of Turing reductions in the definition of FP #P -hardness implies that any #P-hard problem is also FP #P -hard. Therefore, to prove FP #P -completeness it is enough to show FP #P -membership and #P-hardness.

We summarize in Table 1 the results that were obtained in the literature on the complexity of query answering of TMSO and TP queries over documents and p-documents. In terms of data complexity, evaluating a Boolean query over a document or a p-document can be done in linear time; this is a consequence of the formulation of TMSO in terms of tree automata [START_REF] Thomas | Languages, automata, and logic[END_REF], together with the possibility of coding a p-document as a probabilistic tree automaton [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF][START_REF] Benedikt | Probabilistic XML via Markov chains[END_REF]. In terms of combined complexity, all computation can be made in polynomial space [START_REF] Benedikt | Probabilistic XML via Markov chains[END_REF] and TMSO evaluation is PSpace-hard [START_REF] Libkin | Elements of Finite Model Theory[END_REF]. For tree-pattern queries, the situation is more interesting: they can also be evaluated linearly in the query size [START_REF] Benedikt | XPath leashed[END_REF] on XML documents, but they become intractable over p-documents [START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF] under combined complexity.

QUERIES WITH VALUE JOINS

We explain now how to add joins to the query languages we have presented in the previous section. We motivate our study of these query languages with joins by noting that adding value joins to the language dramatically increases the complexity of query answering over probabilistic document.

We want to extend the ability of query languages on trees by allowing value joins, i.e., allowing to test for equality of the labels of nodes of the document. This is a very useful feature of query languages on trees, available in full in XPath 2.0, and, in a restricted form in XPath 1.0.

Joins add non-locality to the query language: it becomes necessary to remember the values of some nodes to compare them with the values of nodes elsewhere in the document. As we shall see, this has for consequence that tree-automata based techniques and their corresponding linear algorithms for query evaluation are no longer possible. Thus, joins cannot be expressed with a regular TMSO query; one could try to write some disjunction of Label l predicates, but in the general case of an infinite set of values this would require infinitely many of them. For instance, to test that nodes and have the same value:  v∈ℒ (Labelv() ∧ Labelv()) . Therefore, in order to express joins in MSO, an extra binary predicate SameL(•, •) is required, whose interpretation consists of pairs of nodes which have the same label, as defined by the preceding infinite disjunction. Since the joins considered are value joins, we further require that nodes whose labels are compared using the SameL predicate are document leaves, not internal nodes. Most results presented here extend to comparison of labels of internal nodes as well, with the exception of the dichotomy that we obtain in Section 5, as discussed there. The extension of TMSO with SameL is denoted TMSOJ. Similarly, TFOJ is the extension of TFO with SameL.

The language of tree-pattern queries with joins, TPJ, can be defined similarly but it is simpler to allow in the TP language a variable to be used multiple times. However, since we also consider only value joins, a variable used multiple times necessarily refers to a leaf in the documents and may consequently only appear as a leaf of the query. The class TPJ

(|| × ||) [5] PrXML mux,det (|  |) [8] FPSpace-complete [4] (|  |) [17] FP #P -complete [17]
Table 1: Complexity of query evaluation for join-free queries, with a document, a query, and  a p-document either the first person is not Rick, or there is no bonus of the same value for Rick and Mary: SBON(  PER) = Pr(PER) = 0.4725.

Our interest for joins comes from the following observation:

FACT 7 (LEMMA 9 OF [START_REF] Abiteboul | Aggregate queries for discrete and continuous probabilistic XML[END_REF]). There is a Boolean TPJ query with #P-hard data complexity over PrXML mux,det .

Recall that for TP, and, indeed, for all MSO queries, the same problem is linear in the data size. Thus, adding joins to the language significantly increases the complexity of query evaluation. In the next sections we have a closer look at this problem.

TREE-MSO QUERIES WITH JOINS

In the previous section we saw that joins in tree-pattern queries come with a high cost: worst-case data complexity of querying pdocuments goes from polynomial-time to #P-hard. In this section we investigate the cost of joins in TMSO queries.

Results of this section and the following one are summarized in Tables 2 (query evaluation) and 3 (deciding essential joins).

Querying p-documents. We first show that combined complexity of TMSOJ over p-documents remains as in the join-free case. PROPOSITION 8. Query evaluation for TMSOJ over PrXML mux,det is #P-hard in data complexity and FPSpace-complete in combined complexity.

PROOF. Hardness of data complexity comes form Fact 7. Hardness of combined complexity comes from the FPSpace-hardness of TMSO over PrXML mux,det [START_REF] Benedikt | Probabilistic XML via Markov chains[END_REF]. Let us now show the corresponding upper bound. Let  be a p-document and a TMSOJ query with different variables. Since every TMSOJ query can be transformed in prenex normal form in polynomial time, we assume that is in such a form and ′ is its matrix, i.e., the quantifier-free part of . We describe an FPSpace algorithm to evaluate over

. One enumerates all triples (, , ) with (1) a document ∈  ; (2) an assignment of first-order variables of to nodes of ; (3) an assignment of second-order variables of to sets of nodes of . For each triple one performs a polynomial time check whether , , |= ′ . This check is clearly polynomial time in the size of both the query and the document, since it boils down to checking that nodes of

given by and sets of nodes given by satisfy Ch, Label, and SameL conditions of ′ . The size of each triple (, , ) is polynomial in the size of both and . Indeed, || is bounded by |  |, and assignments and are vectors (of length bounded by ||) of node identifiers or sets of node identifiers of .

Querying documents. The hardness of query evaluation for TMSOJ over probabilistic data is not surprising, since it is inherited from the hardness of TPJ queries. What is slightly more surprising is, as we immediately show, that query answering becomes intractable even over deterministic data. PROPOSITION 9. Query evaluation for TMSOJ over XML is PSpace-complete in combined complexity. Moreover, for each ∈ N, there are queries 1 and 2 of TMSOJ such that query evaluation of 1 (resp., 2) over an XML document is Π P k -complete (resp.,

Σ P k - complete).
The combined complexity result is a direct consequence of the one for the join-free variant of the problem. To show the more interesting data complexity result, we present a way to encode arbitrary monadic second-order formulas on relational structures (MSO) into TMSOJ formulas on trees.

LEMMA 10. There are two linear-time functions and s.t. (i) for every finite relational structure , () is a document and (ii) for every sentence of MSO, () is a TMSOJ sentence such that () |= () if and only if |= .

PROOF. We start with . See an example of () in Figure 2, left, where we encode the relation = {⃗ 1, ⃗ 2}, for of arity 2, and ⃗ 1 = (, ), ⃗ 2 = (, ). To generalize, let be a finite structure over relations 1, . . . , n. Then () has a root labeled db with children, one for each relation i, labeled i. If i = {⃗ 1, . . . , ⃗ m}, then the node labeled i has children, one for each tuple ⃗ j, labeled ⃗ j. Every node labeled ⃗ j has arity(i) children, where the -th child is labeled , for ∈ {1, . . . , arity(i)}, and has only one child labeled with the value of the -th attribute of ⃗ j. The described function is obviously linear-time in the size of the input relation .

We now exhibit . Let be a second-order logic sentence. We first preprocess . Let be a join (first-order) variable of that has occurrences. Then x is where the -th occurrence of is substituted with a fresh variable i, quantification , where ∈ {∃, ∀}, is substituted with 1, . . . , m, and the resulting formula is conjuncted with the condition  m-1 i=1 (i = i+1). Application of this transformation to all join variables of yields a formula ′ where all joins are "moved" to equality conditions and ≡ ′ .

Let (1, . . . , n) be an atom of ′ , such that is not a second order variable in ′ , where, w.l.o.g, the terms 1, . . . , i are constants, and i+1, . . . , n are variables. Note that due to the preprocessing construction of ′ all the variables in i+1, . . . , n are different. Let , , , 1, . . . , n, i+1, . . . n be variables that do not occur in ′ . One substitutes in ′ every occurrence of the atom (1, . . . , n) with the following formula:

R(t 1 ,...,tn) (, R) = ∃1 . . . n∃i+1 . . . n Label db () ∧Ch(, R)∧LabelR(R)∧Ch(R, )∧  n  j=1 Ch(, j) ∧ Labelj(j)  ∧  i  j=1 Ch(j, j) ∧ Labelt j (j)  ∧  n  j=i+1 Ch(j, j)  ,
where is the same across all atoms of ′ and R is the same for all atoms with the predicate name . If 1, . . . , l are all the predicate names of ′ , then one adds to the resulting formula the prefix ∃∃R of the tree structure that the function above imposes on all (). One can easily construct such a . Finally, () = ′′ ∧ .

The described transformation is obviously linear time and translates second-order logic formulas over arbitrary relations into TMSOJ formulas. By construction, () |= () if and only if |= .

Note that the function from Lemma 10 applied to FO formulas returns TFOJ formulas. This property will be used later on to prove Theorem 11. We are now ready to prove Proposition 9. PROOF OF PROPOSITION 9. Combined complexity has been discussed. As shown by Ajtai, Fagin, and Stockmeyer in [START_REF] Ajtai | The closure of monadic NP[END_REF] (Theorem 11.2) there are MSO queries over graphs whose evaluation is monadic Σ P k -complete for every (monadic Σ P k is the class of MSO-expressible problems with a prefix of alternations of secondorder predicates starting with ∃, and an arbitrary first-order matrix, disregarding the number of alternations of first-order predicates); their negation is thus monadic Π P k -complete. This gives a Σ P k lower bound for MSO query evaluation over arbitrary structures. At the same time Lemma 10 allows to reduce the latter problem to the one of TMSOJ, which immediately gives us the lower bound for data complexity. The upper bound for data complexity follows from [START_REF] Stockmeyer | The polynomial-time hierarchy[END_REF] where Stockmeyer showed that monadic Σ P k is in Σ P k .

Deciding essential joins. As we saw, joins are expensive in TMSOJ for querying documents and p-documents. In contrast TMSO queries are tractable over both deterministic and probabilistic documents. What we study now is the problem of determining whether a TMSOJ query is essentially join-free and, consequently, can be evaluated efficiently. THEOREM 11. Deciding if a query has an essential join is undecidable for TFOJ and TMSOJ.

We will prove this theorem by reduction from finite satisfiability for first order logic formulas, which is known to be undecidable [START_REF] Trakhtenbrot | Impossibility of an algorithm for the decision problem in finite classes[END_REF].

The next lemma shows that TFO queries are insensitive to the multiplicity of constants that occur in the documents but not in the queries. We need the following notions. Let be a document where a label occurs times. We denote by a a document obtained from by replacing each occurrence of with a distinct fresh constant. A canonical document q for a TPJ query is a document that is obtained from by replacing every descendant edge with a child edge and by replacing each different variable with a fresh constant. For TP queries the proof follows from the fact that only nodes of labeled with variables can be mapped to the nodes of labeled with . For TFO queries the proof can be done by induction on . Now we can prove Theorem 11.

Query Language Deciding Joins

TMSOJ undecidable TFOJ undecidable TPJ Π P 2 -complete TPJ {/,[]} NP-complete
PROOF OF THEOREM 11. By reduction from finite satisfiability of first-order formulas over relational structures.

Let be an FO formula and () be the corresponding TFOJ formula constructed as described in Lemma 10. Consider the TPJ query in Figure 2, center; with a slight abuse of notation, we denote its TFOJ encoding also as . Assume that and () have no common labels. It is easy to see that has an essential join.

We now show that 1. If the TFOJ formula (() → ) has no essential joins, then is not finitely satisfiable. 2. If the TFOJ formula (() → ) has an essential join, then is finitely satisfiable. Assume () → has no essential joins, that is, (() → ) ≡ , where ∈ FO. If is finitely satisfiable, then there is a finite structure , s.t., |= . Let = () be the document computed from as described in Lemma 10. W.l.o.g. we can assume that has no labels occurring in . By this lemma, |= ().

Consider a new document 1, that is a combination of and q, a canonical document of , as in Figure 2, right, where does not occur in . Clearly 1 |= holds and consequently by Lemma 12, e 1 |= also holds. Since by construction e 1 |= (), we conclude e 1 |= . At the same time, since has a join variable, e 1 ̸ |= . We obtain a contradiction.

Assume () → has an essential join. If is not finitely satisfiable, then, due to Lemma 10, we conclude that () is not finitely satisfiable. Therefore, the implication () → is a tautology, expressible without joins, and consequently the implication has no essential joins. We obtain a contradiction.

The proof shows that the set of formulas with essential joins is not co-recursively enumerable. On the other hand, the set of finitely satisfiable FO formulas is recursively enumerable, but we do not know if this is also true of deciding essential joins: a TFOJ query has essential joins iff for every TFO query ′ , there exists a finite tree modeling of one but not the other. This alternation of quantifiers does not lend itself to a straightforward enumerability proof.

TREE-PATTERN QUERIES WITH JOINS

In the previous section we showed that joins increase worst-case data complexity of TMSO, while they do not affect combined complexity. What we do not know is whether all queries in TMSOJ not in TMSO are hard, or whether there are some queries with essential joins that are still tractable. A TPJ query is a basic join query if it has exactly one join variable and this variable occurs exactly twice. As we now show, in the case of basic join queries, every query that is not equivalent to a query in TP is FP #P -hard for probabilistic documents.

Querying documents. We first study data and combined complexity of TPJ query evaluation over deterministic documents. Recall that TP query answering over XML is polynomial in combined complexity. The situation changes for TPJ: we now show that evaluation of TPJ queries over XML is essentially the same as querying relational structures with conjunctive queries.

PROPOSITION 13. Query evaluation for TPJ over XML is PTime in data complexity and NP-complete in combined complexity.

Our proof is based on the observation that TPJ over XML behaves in the same way as the class of conjunctive queries over arbitrary relational structures. LEMMA 14. Let Σ = {Ch, Desc, Label}. Then there exist functions and computable in PTime such that (i) for every document , () is a relational structure over Σ and (ii) for every TPJ query , () is a conjunctive query over Σ, such that |= if and only if () |= ().

PROOF OF PROPOSITION 13. Lemma 10 restricted to conjunctive queries gives their encoding in TPJ and the NP-hardness of combined complexity, since the combined complexity of query evaluation over relational structures is NP-complete for conjunctive queries [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF]. NP-membership holds since one can guess a mapping from the nodes of a TPJ query to the nodes of a document and check in polynomial time that the mapping is a valuation.

It is known that data complexity of query evaluation for conjunctive queries is in PTime [START_REF] Immerman | Languages that capture complexity classes[END_REF]. Combining this result with Lemma 14 gives the data complexity for TPJ.

Gottlob et al. in [START_REF] Gottlob | Conjunctive queries over trees[END_REF] studied conjunctive queries over trees that are related to TPJ. In their setting joins can be done on identical nodes only, while we can join arbitrary nodes as long as they carry the same label. As we showed in Lemma 9, this allows us to encode queries about arbitrary relational structures into our query model and data model. Therefore, our Proposition 13 follows from wellknown results about relational conjunctive queries, which is not true for the results in [START_REF] Gottlob | Conjunctive queries over trees[END_REF].

Querying p-documents. We show that for basic join queries, there is a dichotomy between tractable and intractable queries. It is promising that this dichotomy has a very simple characterization, even more so when it is contrasted with the dichotomy of conjunctive queries over tuple-independent probabilistic databases [START_REF] Dalvi | The dichotomy of conjunctive queries on probabilistic structures[END_REF], where the condition for hardness is much more involved. THEOREM 15 (DICHOTOMY). For every basic join query , evaluation over PrXML mux,det is

• feasible in time linear if is essentially join-free;

• FP #P -complete in data complexity otherwise.

To show the data complexity upper bound we need the following lemma, that can be proved by adopting the techniques developed by Grädel, Gurevich, and Hirsch in [START_REF] Grädel | The complexity of query reliability[END_REF].

LEMMA [START_REF] Kharlamov | Value joins are expensive over (probabilistic) XML (extended version)[END_REF]. Let be a query language with polynomial-time data complexity over XML. Then is of FP #P data complexity over PrXML mux,det . PROOF OF THEOREM 15. Lemma 16 and Proposition 13 give the upper bound, while an extension of the proof for Lemma 9 [START_REF] Abiteboul | Aggregate queries for discrete and continuous probabilistic XML[END_REF] gives hardness by reduction from #2-DNF satisfiability.

We first exhibit a #P-hard TPJ query and then show how to generalize the construction to TPJ queries with just one variable that occurs twice. Consider the TPJ query in Figure 3 (left), that clearly has an essential join.

Consider an encoding of the 2-DNF formula:

= (1 ∧ ) ∨ (¬ ∧ 2) ∨ (¬ ∧ 3) ∨ (4 ∧ ¬)
as a p-document  ϕ in Figure 3 (left) that one can immediately generalize to arbitrary 2-DNF formulas. Observe that every ∈  ϕ has the same probability, say , and Pr(  ϕ |= ) = × , where is the number of satisfying assignments for . Thus, answering TPJ queries over PrXML mux,det is #P-hard.

We now show the #P-hardness using the same kind of reduction as for the query above. Let be a TPJ query with one variable occurring twice. To distinguish these two occurrences we refer to them as 1 (labeling a node 1 of ) and 2 (labeling 2). We now exhibit a p-document  ′ ϕ such that computation of Pr( ′ ϕ |= ) is #P-hard.  ′ ϕ is composed of two parts: the first one,  ′′ ϕ , is for the subqueries x 1 and x 2 of ′ related to 1 and 2, and the second one, , for the remaining part of ′ , that is, ′ without x 1 and x 2 . We now present x i 's, then  ′′ ϕ and finally . Let be the root of . Since in TPJ queries join variables label only leaves, there are two paths in : from to the leaf 1 and from to 2. These paths may share some nodes, thus, assume the node labeled is the least common ancestor of 1 and 2, see Figure 3 (right). Let x 1 be the maximal subquery of such that (i) its root is the child of , (ii) its root is between and 1. A query x 2 for 2 is defined analogously. Now observe that cannot be a parent of both 1 and 2 in , otherwise is not an essential join. Indeed, if is the parent of both 1 and 2, then by deleting one of the nodes labeled i one obtains a query equivalent to , which contradicts the essentialness of . Let 1 and 2 be documents such that 1 |= x 1 while 1 ̸ |= x 2 , and 2 |= 2 while 2 ̸ |= 1. Such i's always exist and can be constructed in EXPTime in the size of the i's due to Proposition 3 of [START_REF] Miklau | Containment and equivalence for a fragment of XPath[END_REF].

We modify 1 further as ′ 1 by adding a child node with a fresh label to all leaf nodes of 1 except for one given homomorphic image 1 of 1 from x 1 into 1. This will ensure that the value join will necessarily involve this specific node and not another one of 1, thanks to our condition that joins only match document leaves. We transform similarly 2 into ′ 2 . Assume is a proper ancestor (ancestor but not a parent) of either 1 or 2. Consider the p-document  ′′ ϕ obtained from  ϕ by (i) relabeling the root with , (ii) substituting every node labeled with the document ′ 1 (if 1 is empty, then is substituted with a det node), and (iii) every node labeled with ′ 2 (if 2 is empty, then is substituted with a det node). Here, substituting a node labeled with ′ 1 means the following. Let node be labeled . Then (i) a copy of ′ 1 is inserted below the parent of (that is, is replaced with ′ 1 ); (ii) for the homomorphic image 1 of 1 that has been previously chosen, we insert a new det node into ′ 1 as a sibling of i; and (iii) copy all children of below that det node. In a similar fashion, we substitute with ′ 2 . Let the query ′ be a obtained from by deleting x 1 and x 2 together with 1 and 2. Since is essential in , we have ′ ̸ ⊑ , q : a r q 1 q 2

x 1 x 2 P ϕ : q: hence, there is a document such that |= ′ and ̸ |= . Let be a homomorphism from ′ to and = ().

Finally, the p-document  ′ ϕ is obtained from by inserting at the node the subtrees of  ′′ ϕ rooted at its root. Observe that by construction of  ′ ϕ , the probability of every ′ ∈  ′ ϕ is again . We now show that Pr(  ′ ϕ |= ′ ) = × , where is the number of satisfying assignments for . Indeed, observe that in the query composed of x 1 and x 2 rooted at is an essential join. Moreover, this query can not be homomorphically embedded in (due to construction of ) and in a document ′′ ∈  ′′ ϕ in a way that none of 1 and 2 is mapped to i, for some clause (due to the fact that is essential). This gives us that for every ′ ∈  ′ ϕ : is a homomorphism from to ′ iff the label of (1) = (2) = i, for some clause . Thus, by construction of  ′ ϕ , there is a bijection between the set of worlds of  ′ ϕ that satisfy and the set of satisfying assignments of , which yields:

Pr(  ′ ϕ |= ) =  µ∈M Pr(()) =  µ∈M = • | |,
and concludes the proof.

It is open whether this dichotomy theorem can be extended to the general case of multiple variables with possibly more than two occurrences. Another important limitation of this result is that it only holds when join variables are required to be on query leaves (value joins). It is for instance easy to see that if two join variables label nodes in a parent-child relationship, the query can be evaluated efficiently even if the join is essential. This comes from the fact that given a p-document node, it is possible to deterministically get the label of its parent. In a more general setting where the label of internal nodes can be given by a probability distribution, the dichotomy proof can be adapted. Now we know that essential joins are an important criterion to determine whether queries are intractable. Thus, it is important to be able to detect whether a TPJ query is essentially join-free. In the next section we present a conceptually simple test for essential joins. Unfortunately, as we also show, this test is intractable.

Deciding essential joins. We define the core of a TPJ query , denoted cr(), as the TP query obtained from by replacing every occurrence of a join variable with a distinct fresh variable. THEOREM 17. A TPJ query has no essential joins iff ≡ cr().

To prove this we use the following fact due to Miklau and Suciu [START_REF] Miklau | Containment and equivalence for a fragment of XPath[END_REF]. Let be a TPJ query and the length of 's longest chain of nodes, where all nodes are labeled with wildcards (i.e., non-join variables) and all edges are child edges. Let ∈ ℒ be a label that does not occur in and a,q is the set of documents obtained from by (i) expanding every descendant-edge into a chain of child-edges of length at most + 1, (ii) labeling every node of these chains with , and (iii) substituting every variable with a fresh label. FACT 18 ([21]). Let 1 and 2 be TP queries and let be a label that does not occur in 1 and 2. Then 1 ⊑ 2 if and only if |= 2 for every document ∈ a,q 1 .

PROOF OF THEOREM 17. The if direction is obvious. For onlyif, assume ≡ for a TP query . We show that ≡ cr(). Since ⊑ cr() obviously holds, we will prove cr() ⊑ . Assume that has exactly one join variable, that is, there is exactly one variable occurring in more than once. Let be all nodes in labeled with .

Let and be fresh constants for both and . Consider the set of documents a,q, where, w.l.o.g., we assume that in every ∈ a,q all the nodes of are labeled with . By construction, for every ∈ a,q we have |= . Hence, |= also holds and, by Lemma 12, we obtain b |= . Let us collect all such b 's in b a,q , that is, b a,q = { b | ∈ a,q}. By construction b a,q = a,cr(q) , and we are in the conditions of Fact 18: 1 = cr() and 2 = are two TP queries such that for every ∈ a,cr(q) it holds |= . Hence, cr() ⊑ and, due to equivalence of and , we obtain cr() ⊑ .

The proof can be extended to the general case, when has more than one join variable, by iterating the construction above over all join variables.

We have a conceptually simple test for essential joins: it is sufficient to test that a query is equivalent to its core to guarantee that it is essentially join-free. The next theorem shows that this test is expensive for the class of queries with at least child navigation and branching. THEOREM 19. Deciding if a query has an essential join is Π P 2complete for TPJ and NP-complete for TPJ {/,[]} .

A proof can be done using similar construction as by Deutsch and Tannen in [START_REF] Deutsch | Containment and integrity constraints for XPath[END_REF] for the problem of query containment for XPath extensions.

CONCLUSION AND DIRECTIONS

We studied complexity of query evaluation over XML and probabilistic XML for tree-pattern and monadic second-order queries with joins. We also investigated the complexity of deciding essential joins. Our results are summarized in Tables 2 and3.

There are a number of open questions remaining in our study: a tight complexity bound for combined complexity of TPJ over PrXML, semi-decidability of essential joins for TMSOJ, and a criterion for deciding essential joins in TMSOJ.

Another major open question is whether the dichotomy of tractability for basic TPJ queries extend to arbitrary ones, still relying on the notion of essential join. If it does, we have a remarkable contrast with what happens for relational probabilistic data. Our dichotomy is conceptually very simple: it is sufficient to test that a query is equivalent to its core to guarantee that it is tractable, but this test itself is intractable in the query size. In the relational setting, Dalvi and Suciu proved a dichotomy for conjunctive queries [START_REF] Dalvi | The dichotomy of conjunctive queries on probabilistic structures[END_REF] over block-independent databases which guarantees tractability of queries, but involves a conceptually complicated, though polynomial-time testable, characterization of queries. We would like to understand better the connections between these dichotomy results, if any.

Continuing with the discussion after the proof of Theorem 15 on the dichotomy, another further direction to study is a more general form of joins in queries. In our query model we allow for joins on document leaves only, while one may also think of structural joins, that is, joins which can be imposed on the labels of intermediate nodes in trees and not only on the leaves. One way of preserving the results of this paper in the setting of both value and structural joins is to consider a slightly different data model. The current model allows for distributional nodes that define structural probabilistic alternatives, that is, it allows for distributions on children of nodes only. What we need are non-structural probabilistic alternatives, that is, distributional nodes that define alternatives of labels for a given node. For example, we should be able to express that a node of a document is labeled either with or .

Another direction is a more general study of joins in the context of both queries and data. Recall, when queries and probabilistic data are tree-shaped, query answering is tractable, while adding joins to queries makes it hard. An analogous situation happens when we add a form of joins in data, as it is done in [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF], where probabilistic XML is defined by means of probabilistic annotations (that are conjunctions of literals over Boolean random variables) on the nodes of documents. For such probabilistic data query answering becomes hard for tree-shaped queries: every TP query is either trivial, i.e., it retrieves just the root of the data, or it is FP #P -complete [START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF], and we again have a dichotomy. Note that the probabilistic data of [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF] is tree-shaped, but the dependencies between the annotations are graph structured. Another way of introducing joins in data is by considering data graphs, where MSO query answering is Σ P kcomplete [START_REF] Ajtai | The closure of monadic NP[END_REF]. To sum up, joins can be seen as a way to add graph structure either to queries, or to data (on the level of data itself or on the level of probabilistic dependancies), and we are missing a study that bridges these alternatives.

Figure 1 :

 1 Figure 1: Example p-document  PER, possible document PER of  PER, TP query RBON and TPJ query SBON

Figure 2 :

 2 Figure 2: Left: translation from a finite relational structure = {(, ), (, )} into a tree () (Lemma 10). Center: a TPJ query with an essential join (Theorem 11). Right: a document (Theorem 11).

Figure 3 :

 3 Figure 3: For Theorem 15. Left: a TPJ query with an essential join and a p-document  ϕ encoding = (1 ∧ ) ∨ (¬ ∧ 2) ∨ (¬ ∧ 3) ∨ (4 ∧ ¬). Right: a general pattern ′ of a TPJ query with an essential join.

  {/,[]} consist of TPJ queries without descendant edges.

			TMSO	TP
		Data	Combined	Data	Combined
	XML	(||) [25] PSpace-complete [20] (||) [25]

EXAMPLE 6. Consider the query SBON in Figure 1. The query asks whether Rick and Mary have received a bonus of the same value . Clearly, SBON is true in PER since Rick and Mary both received a bonus of 44. Evaluation of SBON over  PER returns true in only one world of  PER , PER, since in all other worlds

Table 2 :

 2 Complexity of query evaluation for queries with joins

		TMSOJ		TPJ
		Data	Combined	Data	Combined
	XML PrXML mux,det	Σ P k -complete, Π P k -complete ∀ ∈ N PSpace-complete #P-hard, in FPSpace FPSpace-complete	PTime FP #P -complete #P-hard, in FPSpace NP-complete

• • • ∃R l . The next step is to substitute in the resulting formula every occurrence of the equality condition ( = ) with the atom SameL(, ), which yields ′′ . Let be an encoding

Table 3 :

 3 Complexity of deciding essential joins LEMMA 12. Let be a TFO or TP query, a document and ∈ ℒ a label occurring in multiple times, but not occurring in . Then |= if and only if a |= .

* This work has been partially funded by ERC FP7 grant Webdam (agreement 226513).


Bogdan Cautis
email: cautis@telecom-paristech.fr

Evgeny Kharlamov
email: kharlamov@inf.unibz.it

Challenges for View-Based Query Answering over Probabilistic XML

This is the first and preliminary study on answering queries using views in a probabilistic XML setting. We formalize the problem and study it under the two possible semantics for XML query results: with node identifiers and in their absence. Accordingly, we consider rewrite plans that can exploit a single view, by means of compensation, and plans that can use multiple views, by means of intersection. Since in probabilistic settings queries return answers with probabilities, the problem of rewriting goes beyond the classical one of retrieving answers from views. For both semantics of XML queries, we show that, even if the XML answers can be retrieved, the computation of their probabilities might not be possible. We give restrictions that make probabilistic rewriting feasible in polynomial time, and present some initial hardness results for this problem.

Introduction

Uncertainty is ubiquitous in data and many applications must cope with this [START_REF] Kharlamov | Value joins are expensive over (probabilistic) XML[END_REF]: information extraction from the World Wide Web [START_REF] Chang | A survey of Web information extraction systems[END_REF], automatic schema matching in data integration [START_REF] Rahm | A survey of approaches to automatic schema matching[END_REF] are inherently imprecise. This uncertainty is sometimes represented as the probability that the data is correct, as with conditional random fields [START_REF] Lafferty | Conditional Random Fields: Probabilistic models for segmenting and labeling sequence data[END_REF] in information extraction, or uncertain schema mappings in information integration [START_REF] Dong | Data integration with uncertainty[END_REF]. In other cases, only confidence in the information is provided by the system, which can be seen after renormalization as an approximation of the probability. It is thus natural to manipulate such probabilistic information in a probabilistic database management system [START_REF] Dalvi | Probabilistic databases: Diamonds in the dirt[END_REF].

Recent work has proposed models for probabilistic data, both in the relational [START_REF] Widom | Trio: A system for integrated management of data, accuracy, and lineage[END_REF]8,[START_REF] Koch | MayBMS: A system for managing large uncertain and probabilistic databases[END_REF] and XML [START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF][START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF][START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF] settings. We focus here on the latter, which is particularly adapted for the Web. A number of studies on probabilistic XML have dealt with query answering for a variety of models and query languages [START_REF] Abiteboul | Aggregate queries for discrete and continuous probabilistic XML[END_REF][START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF][START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF][START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF][START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF]. At the same time, query optimization over probabilistic data has received little attention. In particular, the problem of answering queries using views, a key approach for optimization, has received no attention so far in both the relational and the semistructured settings. Probabilistic query evaluation could greatly benefit from such techniques, as it is often the case that computing probabilistic results is harder than in the deterministic setting.

Views over XML documents can be seen as fragments of data that may be available along with the nodes selected by the query. Over a p-document, the data fragments come Fig. 1. Example document d PER together with their probability. In the general setting, we are given a document d and a set of view queries v 1 , . . . , v n . Given a query q, the goal is to understand whether one can obtain q(d), the answers of q over d, by accessing view results v 1 (d), . . . , v n (d) only. For XML data, the problem was studied under the two possible semantics for XML query results: with persistent node identifiers or in their absence. For the latter case, only rewrite plans that rely on a single view, by means of compensation, are possible. For the former, plans using multiple views, by means of intersection and compensation, are exploitable. We consider both settings and alternatives for rewritings.

We present a preliminary study of the problem of answering queries using views in the probabilistic XML setting. We formalize the problem in Section 3 and we give a preliminary study of it for the two possible settings: in the absence of node Ids, in Section 4, and in their presence, in Section 5. We show that, in the probabilistic setting, the problem of answering queries using views becomes more complex and it does not reduce to its deterministic version. The reason is that query results now involve not only data trees, but also their probabilities. Hence probabilities should also be retrieved from probabilistic view results, by means of a probabilistic function computing them.

Even for the simpler setting (without Ids), the existence of the probabilistic function is not guaranteed by the existence of a data-retrieving rewriting. We present examples of views and queries for which such a function does not exist. Based on a notion of probabilistic independence between queries, we also isolate a class of queries and views for which this function, when it exists, can be found and computed efficiently. For rewritings with intersection, we provide a sufficient condition (also based on probabilistic independence) that guarantees that the probabilities of query answers can be computed as a product-like formula over the probabilities of the views appearing in the intersection. We also present an NP-hardness result for deciding whether a selection of probabilistically independent views for a rewriting is possible.

Preliminaries

We briefly define here the data and query model. Details can be found in [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF][START_REF] Cautis | Querying XML data sources that export very large sets of views[END_REF].

XML documents. We assume the existence of a countable set of labels L that subsumes both XML tags and values. We consider an XML document as an unranked, unordered rooted tree d modeled by a set of edges edges(d), a set of nodes nodes(d), a distinguished root node root(d) and a labeling function lbl, assigning to each node a label from L. We assume that each node n ∈ nodes(d) has a unique identifier.

[1] IT-personnel [8] Rick mux [START_REF] Abiteboul | Aggregate queries for discrete and continuous probabilistic XML[END_REF] John [START_REF] Lafferty | Conditional Random Fields: Probabilistic models for segmenting and labeling sequence data[END_REF] name [START_REF] Dong | Data integration with uncertainty[END_REF] bonus [START_REF] Chang | A survey of Web information extraction systems[END_REF] person [START_REF] Rahm | A survey of approaches to automatic schema matching[END_REF] person mux [START_REF] Dalvi | Probabilistic databases: Diamonds in the dirt[END_REF] Probabilistic documents. p-Documents give a general syntax for compactly representing px-spaces. Like a document, a p-document is a tree but with two kinds of nodes: ordinary nodes, which have labels and are the same as in documents, and distributional, which are used to define the probabilistic process for generating random documents. We consider three kinds of distributional nodes: ind (for independent), mux (for mutually exclusive), and det (for deterministic). Other kinds of distributional nodes are studied in [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF], but mux, det alone are enough to represent all px-spaces as p-documents [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF]. Definition 2. A p-document P is an unranked, unordered tree with a set of edges edges( P), nodes nodes( P), the root node root( P), and a labeling function lbl, assigning to each node v a label from L ∪ {ind(Pr), mux(Pr), det}. If lbl(v) is mux(Pr v ) or ind(Pr v ), then Pr v assigns to each child v ′ of v a probability Pr v (v ′ ), and if lbl(v) = mux(Pr v ), then also v ′ Pr v (v ′ ) ≤ 1. We require leaves and the root to be L-labeled. Example 3. Figure 2 shows a p-document P PER (where PER stands for personnel) that has mux and det distributional nodes, shown on gray background. Node n 52 is a mux node with two children n 54 and n 56 , where Pr n52 (n 54 ) = 0.7 and Pr n52 (n 56 ) = 0.3.

A p-document P has as associated semantics a px-space P defined by the following random process. Independently for each mux(Pr v ) (resp. ind(Pr v )) node, we select at most one (resp. some) of its children v ′ and delete all other children along with their descendants. We do not delete any of the children of det nodes. We then remove in turn each distributional node, connecting ordinary children of deleted distributional nodes with their lowest ordinary ancestors. The result of this process is a random document P. The probability of P, Pr(P), is the product of all (i) Pr v (v ′ ) for each chosen child Fig. 3. Example TP query q RBON and two TP views: Tree-Pattern queries. The language of tree-pattern queries (TP) is roughly the subset of navigational XPath with child, descendant navigation, predicates, without wildcards.

v 1 RBON and v 2 RBON v ′ of a mux or ind node v, (ii) 1 -Pr v (v ′ ) for each not chosen child v ′ of a ind node v, (iii) 1 -v ′ Pr v (v ′ )
Definition 5. A tree-pattern q is a non-empty, unordered, unranked rooted tree, with a set of nodes nodes(q) labeled with symbols from L, a node called the output node out(q) (i.e., tree-patterns are unary queries), and two types of edges: child edges, labeled by / and descendant edges, labeled by //. The root of q is denoted root(q).

Due to space limitations, we will often write tree-patterns q in XPath notation [START_REF] Benedikt | XPath leashed[END_REF], and denote this notation with xpath(q). We use lbl(q) as short notation for lbl(out(q)). We use the following graphical representation for tree-patterns: the main branch is the vertical path starting from the root, the output node is the last node of this path, and predicates are subtrees starting with side branches (see Figure 3). Example 6. Consider the query q RBON in Figure 3 (left) (where RBON stands for Rick's bonuses) asking whether Rick has received a bonus from the project laptop and a bonus from the project pda. In this representation, single lines denote child edges and double lines descendant edges. The other two queries v 1 RBON and v 2 RBON in Figure 3 (center and right) ask whether Rick has received a bonus on either of these projects. The output node in all the three queries is labeled with Rick.

The semantics of tree-patterns is given using embeddings. An embedding e of a TP query q into a document d is a function from nodes(q) to nodes(d) satisfying:

(i) e(root(q)) = root(d); (ii) for any n ∈ nodes(q), lbl(e(n)) = lbl(n); (iii) for any /-edge (n 1 , n 2 ) in q, (e(n 1 ), e(n 2 )) is an edge in d; (iv) for any //-edge (n 1 , n 2 ) in q, there is a path from e(n 1 ) to e(n 2 ) in d.
The result q(d) of applying a tree-pattern q to a document d is the set: q(d) := {e(out(q)) | e is an embedding of q into d} Example 7. Continuing with the three queries in Figure 3, they all return {n 8 } over the document d PER , since Rick has got bonuses from both of the requested projects.

Intersections of tree-patterns. We consider in this paper the extension TP ∩ of TP with respect to intersection, which denotes intersections of tree-pattern queries.

TP ∩ = {q 1 ∩ • • • ∩ q k | k ∈ N, q i ∈
TP, and lbl(root(q i )) = lbl(root(q j )), and lbl(out(q i )) = lbl(out(q j )) for i, j ∈ {1, . . . , k}}.

The result of a TP ∩ query q 1 ∩• • •∩q k over a document d is the set of nodes

k i=1 q i (d).
Query equivalence and containment. A pattern q 1 is contained in a pattern q 2 , denoted q 1 ⊑ q 2 , if q 1 (d) ⊆ q 2 (d) for every d. Also q 1 is equivalent to q 2 , q 1 ≡ q 2 , if q 1 ⊑ q 2 and q 2 ⊑ q 1 . We discuss how to check containment of TP ∩ queries in Section 5. For TP queries, containment can be decided using containment mappings [START_REF] Amer-Yahia | Tree pattern query minimization[END_REF][START_REF] Miklau | Containment and equivalence for a fragment of XPath[END_REF] which are similar to embeddings. Intuitively, a containment mapping from q 1 to q 2 is a function from nodes(q 1 ) to nodes(q 2 ) that respects the labels of nodes and maps any two nodes connected with /-edges to nodes connected with /-edges, while nodes connected with //-edges can be mapped to any connected nodes. Then for q 1 and q 2 in TP, q 2 ⊑ q 1 iff there is a containment mapping from q 1 to q 2 . Note that such a mapping can be computed in polynomial time. For example, observe that q RBON is contained in both v 1 RBON and v 2 RBON , while none of the latter two is contained in each other.

Querying p-documents. Up to now, we have seen queries as functions over XML documents outputting sets of nodes. Over a p-document P, a query q (TP or TP ∩ ) naturally yields a set of node-probability pairs (n, p), where n is a node of P, and p is the probability that q can be embedded into a random document P of P with some e such that e(out(q)) = n; this value will also be written as Pr(n ∈ q(P)). Formally:

q( P) := {(n, p) | ∃ d ∈ P : n ∈ q(d) and p = d∈ b P : n∈q(d) Pr(d)}.
It is known [START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF] Further notations. We introduce now some additional terminology for TP queries, which will be used in Sections 4 and 5, and can be skipped until then.

The main branch mb(q) of q is the path from root(q) to out(q), and the main branch nodes of q, mbn(q), are the nodes of mb(q). A prefix q p of q is any tree-pattern that can be build from q by setting root(q) as root(q p ), setting some node n ∈ mbn(q) as out(q p ), and removing from q all mbn(q) nodes below n along with their descendants. A suffix q s of q is any subtree of q rooted at a node of mbn(q). The rank of a main branch node is the distance from it to the root, i.e., the rank of root(q) is 1 and of out(q) is |mbn(q)|. The suffix of q rooted at the node of rank k is denoted q k . For any rank k, cut(q, k) denotes the prefix of q with k main branch nodes.

Problem Definition

We assume an infinite set of view names V disjoint from the set of labels L. By a view v we denote a tree-pattern query (that defines the view) together with its name v ∈ V. Let d be a document, q a TP-query, V a set of TP-views, and Q ∈ {TP, TP ∩ }. In the deterministic setting the problem of query answering using views is to find an alternative query plan q r in Q, called a rewriting, that can be used to answer q. Formally, a Q-rewriting q r of q using V is a query q r ∈ Q such that for every document d it holds that q r (D d V ) = q(d). Clearly, this implies that unfold V (q r ) ≡ q. The two alternatives, TP-rewritings and TP ∩ -rewritings, are respectively motivated by the two possible interpretations of XML query results. In an XML document, nodes have unique Ids used by internal operators (selections, unions, joins, etc.) to manipulate data during query evaluation. Queries can then either (i) output fresh Ids for the nodes of the result, or (ii) expose (preserve) in the result the original Ids from the document. The former case corresponds to what is called the copy semantics, under which the Ids of any document in D d V are disjoint from those of d and from those of any other document in D d V . Since one cannot know if nodes from results of different views are in fact copies of the same node in d, the only possible rewritings are those that access a single document from D d V and maybe navigate inside it. A rewriting q r ∈ TP will thus be of the form doc(v)/lbl(v)[p 1 ]/p 2 or doc(v)/lbl(v)[p 1 ]//p 2 , where v ∈ V and the (possibly empty) TP-queries p 1 , p 2 represent the compensation of v. In the latter case, every document in D d V preserves the original Ids, which will identify nodes across different documents in D d V . One can thus formulate and exploit more complex rewritings, as node Ids can be used to intersect (join by Id) results of different views over the same input data d. TP ∩ -rewritings q r extend TP-rewritings in that they can access several D d V documents at once, by first navigating in individual documents and then intersecting the result. Thus the form of TP ∩ -rewritings is i,j u ij , where each u ij is a TP-rewriting.

(v)/lbl(v)/ . . . . If V is a set of views defined over a document d, then D d V = {d v | v ∈ V }. Let q be a query in Q ∈ {TP, TP ∩ } that may use doc(v)/lbl(v) for v ∈ V , then unfold V (q) is the query in Q obtained by replacing in q each doc(v)/lbl(v
Probabilistic view-based rewriting. We generalize the definition of view extension to the probabilistic case: P v is a p-document rooted at a node labeled doc(v) whose contents is constructed as follows: (i) plug an unique ind-child below root( P v ), (ii) for each pair (α, β) in the set {( P ′ , p) | P ′ ⊆ P and (root( P ′ ), p) ∈ q( P)}, add α as subtree of this ind-node with the probability β. A set of p-documents D b P V for the set of views V and unfolding of a query over D b P V is defined as in the deterministic case. Example 10. Continuing with Example 9, extensions ( P PER ) v 1 RBON ( P PER ) v 2 RBON of the views over P PER are p-documents with three nodes: the roots are labeled respectively doc(v 1 RBON ) and doc(v 2 RBON ), with one child labeled ind, that in turns has one child with the id n 8 labeled Rick. The edge between the ind-node and its child is labeled 0.75 in both cases. The extension ( P PER ) v has the root labeled v, with one child labeled ind, and two p-subdocuments of P PER rooted under the ind node: one is the p-subdocument rooted at n 2 and the other one rooted at n 3 . Probabilities on the edges to n 2 and n 3 are 1.

Query answering using views in the probabilistic setting is more involved than in the deterministic one, since q( P) is a set of node-probability pairs. Therefore, rewrite plans should deal with two sub-problems: (i) to find a query in terms of views, that retrieves the nodes N of q( P) (this corresponds to deterministic rewriting plans) and (ii) to compute the probabilities for the nodes in N , using probabilities from D b P V . Both sub-problems require algorithms accessing p-documents D b P V only. More formally: Definition 11. Let q be a TP query, V be a set of TP views and Q ∈ {TP, TP ∩ }. A probabilistic Q-rewriting Q r = (q r , f r ) of q using V is a pair of (i) a deterministic Q-rewriting q r of q using V , and (ii) a probability function f r such that for every p-documents P and every node n of P it holds that f r (n, D b P V ) = Pr(n ∈ q(P)).

When D b P

V is clear from the context we will use f r (n) as short notation for f r (n, D b P V ). For given q and V , a probabilistic rewriting problem is to find Q r . The main challenge in solving this problem is to construct a probability function f r that, by definition, has access only to the p-documents in D b P V . In Sections 4 and 5 we respectively show that this is not always possible for TP and TP ∩ -rewritings.

TP-rewrite Plans

Here we discuss when probabilistic TP-rewrite plans do not exist and present cases for which they do exist and can be computed in polynomial time.

We first introduce some auxiliary notation. By d n we denote the subdocument of d rooted at n. We denote the p-subdocument of P rooted at a node n as P n . For TP queries q 1 and q 2 , compensation of q 1 with q 2 , denoted comp(q 1 , q 2 ), is a TP-query obtained by deleting the first symbol from xpath(q 2 ) and concatenating the rest to xpath(q 1 ). For instance, the result of compensating

q 1 = a/b with q 2 = b[c][d]/e is the concatenation of a/b and [c][d]/e, i.e., comp(q 1 , q 2 ) = a/b[c][d]/e.
Intuitively, view's compensation brings further navigation over the view's result P v , and a rewrite plan will be of the form q r = comp(doc(v)/lbl(v), q k ) such that its unfolding comp(v, q k ) is equivalent to q. Note that q r is over P v , its unfolding is over P while they yield the same result.

We remind the reader the main result for deterministic compensations [18]: Fact 12. Let q and V be TP-queries. Then there exists a deterministic TP-rewriting of q over V if and only if there is v ∈ V and k ∈ N such that comp(v, q k ) ≡ q.

This criterion can be verified in polynomial time [18]. Fact 12 says that, using just one view v from V , we can find all the nodes n ∈ q(d) by querying d v with q k , i.e., the data in d v suffices to extract all such n. This naturally extends to the probabilistic setting: we can find all the nodes n ∈ q( P) by querying P v with q k , i.e., the data in P v it suffices to extract all ns. Note that n is in the query result q(P) iff Pr(n ∈ q(P)) > 0.

Proposition 13. Let q and v be TP-queries and k ∈ N. Let q r = comp(doc(v)/lbl(v), q k ) be a deterministic TP-rewriting of q using v. Then for every p-document P it holds Pr(n ∈ q(P)) > 0 if and only if Pr(n ∈ q r (P v )) > 0.

Nonexistence of TP-rewrite Plans

Is information in P v also sufficient to extract the probabilities Pr(n ∈ q(P)) for nodes n ∈ q(P)? It turns out that the answer is negative. There are q and v for which a deterministic rewriting q r exists but not the probabilistic one, i.e. the function f r such that for every P it holds that f r (n) = Pr(n ∈ q(P)) does not exist. Thus the probabilistic rewriting problem crucially different from the deterministic one. We now present two example that will give insides on this phenomenon. Example 14. Consider the query q = a/b[c] and the view v = a[.//c]/b. We now show that there is no probabilistic rewriting (q r , f r ) for q over {v}. One can see that comp(v, q 2 ) = a[.//c]/b[c] is equivalent to q, hence, q r = comp(doc(v)/lbl(v), q 2 ). Consider now two p-documents P 1 and P 2 from Figure 4. Clearly, Pr(b ∈ q(P 1 )) = 0.65 × 0.5 and Pr(b ∈ q(P 2 )) = 0.5, and these probabilities are different. The function f r should compute the first probability 0.325 on a p-document ( P 1 ) v and 0.5 on ( P 2 ) v , hence f r should distinguish these p-documents. While one can see that these p-documents are indistinguishable by v:

( P 1 ) v = ( P 2 ) v . Hence, f r does not exist.
The problem raised in this example comes from the fact that in the unfolding of the rewriting a[.//c]//b[c] the predicate [.//c] coming from the view (i.e. located above the b-labeled node out(q)) and the predicate [c] coming from the compensation, (i.e. located below out(q)) may interact. Where the interaction is of the following kind: there is a document, e.g., d with the root a that has one child b, which in tern has one child c. that satisfies a[.//c]//b[c] but both c-nodes of the query should be mapped to the same c-node of d. In other words, the existence of a match for one predicate depends on the (non-)existence of a match of the other. We now introduce a condition of probabilistic independence that prevents such an interaction. This condition will be further used for both TP and TP ∩ -rewritings.

TP-queries q 1 and q 2 are independent, denoted q 1 ⊥q 2 , if for every P and n ∈ P:

Pr(n ∈ (q 1 ∩ q 2 )(P)) = [Pr(n ∈ q 1 (P)) × Pr(n ∈ q 2 (P))] ÷ Pr(n ∈ P).
Clearly, the view a[.//c]//b and the compensation b[c] from Example 14 are probabilistically dependent. Deciding probabilistic dependency is tractable: Proposition 15. For TP-queries the independence q 1 ⊥q 2 is decidable in polynomial time.

Observe that probabilistic independence between a view and its compensation in a deterministic rewriting does not guarantee existence of a probabilistic rewriting.

Example 16. Consider q = a//b[1]/b[2]/b//c and v = a//b[1]/b[2]/b.
Clearly, q 2 is a compensation for v and q r = comp(v, q 2 ) is a deterministic TP-rewriting for q and v. We now present two p-documents P 3 and P 4 that show the non-existence of a probability function f r , such that (q r , f r ) is a probabilistic TP-rewriting for q and v. Consider P 3 from Figure 4. where the upper index i on b indicates the i-th occurrence of a node labeled b in P 3 . Clearly, ( P 3 ) v is a p-document with the root that has one ind child, under which two p-documents: P b (3) with probability p 2 and P b (4) with p 1 are rooted. Consider now P 4 that is different from P 3 in that it has an ind-node instead of the mux-node. Clearly, ( P 3 ) v = ( P 4 ) v . Note that both P b (3) and P b (4) are deterministic documents, and in both ( P i ) v there is no information on whether p 1 and p 2 are coming from the same distributional node or not, and if they come from the same node, then there is no information on what type of this node is. At the same time, Pr(c ∈ q( P 3 )) = p 1 + p 2 , while Pr(c ∈ q( P 4 )) = p 1 + p 2 -p 1 × p 2 . That is, the probabilities are different and the result depends on the kind of the probabilistic relations in which p 1 and p 2 are involved, i.e., on whether they are for associated with the children of a mux or ind distributional node. If a probability computation function f r for q r exists then it should be able compute the latter two different probabilities from the same views v( P 3 ) and v( P 4 ), which is impossible since they have no information on the relationship between p 1 and p 2 .

Simple Queries and Restricted Compensations

We now provide a class of queries and a class of compensated queries for which deciding existence of probability rewriting is based on probabilistic independence.

A query q is simple if either its main branch has /-edges only, or all the nodes in mbn(q) \ out(q) reachable from (the first occurrence of) a //-edge have no predicates. Clearly, a query is not simple if it is of the form . . . // . . . [. . . ] . . . . The compensation of a view v with c is restricted if either v is simple, or mb(c) has no //-edges.

Let n ′ be the highest ancestor-or-self node of n occurring in v( P) and let k = |mb(v)|. We show that under some conditions on q r and v, the probability Pr(n ∈ q(P)) can rely on mappings to decide the equivalence: if q is first equivalently reformulated into the union of TP queries ∪ i q i , called its possible interleavings, and can be exponentially large in |Q|. Interleavings capture all the possible ways to order or coalesce the main branch nodes of queries participating in the intersection. Testing q ≡ Q is coNP-hard and boils down to testing q ≡ ∪ i q i , which in turn boils down to testing: if for some j: q ⊑ q j , and if for all i: q i ⊑ q. We conclude:

Corollary 18. Deciding existence of a probabilistic TP ∩ -rewriting for a TP query q and TP views V views is coNP-hard.

The equivalence problem was however shown in [START_REF] Cautis | Querying XML data sources that export very large sets of views[END_REF] to be in PTIME when q belongs to a restricted fragment of TP, called extended skeletons. As our focus in this paper is on polynomial time algorithms for view-based rewriting, it is thus natural to ask if view-based rewriting over probabilistic data remains tractable when input queries are extended skeletons and expose node Ids, while views are general TP queries.

Computing Probability Function f r for Mutually Independent TP ∩ Views

We start with the assumption that a deterministic rewriting q r has been found. Without loss of generality, let us assume that q r consists only of intersected views (no compensations of views). Let v 1 , . . . , v k be the TP views of q r . Towards building the probability component of the rewrite plan, f r , we give some intuition first: for a given node n ∈ q(P), since each view v i gives a probability, n ∈ v i (P), and since we are interested in the probability of the intersection thereof, we might be tempted to try what is arguably the most intuitive definition for f r , the one which would simply combine by multiplication the probabilities Pr(n ∈ v i (P)). But there are two issues with this straightforward f r candidate.

Regarding the first issue, a basic principle in probability theory is that the joint probability of several events equals the product of the individual probabilities only when these events are independent. For instance, for a given node n ∈ P, are Pr(n ∈ a[1](P)] and Pr(n ∈ a[2](P)] independent? The answer is obviously negative, and we can readily construct P instances over which both values are non-zero but the probability of Pr(n ∈ a [START_REF] Kharlamov | Value joins are expensive over (probabilistic) XML[END_REF][2](P)]) = 0. We have introduced the notion of query independence in the previous section, denoted v i ⊥v j , which guarantees that the existence of some embedding of v i in a given document does not depend on the existence (or non-existence) of some embedding of v j in this document. We will see now that for pairwise independent views a function f r is based on multiplication of these views' probabilities.

Regarding the second issue, for each node n that appears in q( P) and, consequently, appears in each v 1 ( P), . . . , v k ( P), we have k probability values Pr(n ∈ v i (P)). Furthermore, each value Pr(n ∈ v i (P)) can be seen as the product of two distinct terms:

(i) the probability of n appearing in a possible world of P, denoted Pr(n ∈ P), (ii) the probability of n being selected by v i in a possible world in which n is known to appear, denoted in the following Pr(n ∈ v i (P) | n ∈ nodes(P)). Note that the first term is independent of any particular view as it only depends on the document itself We can thus write for each v i and each pair (n, p i ) ∈ v i (P) that

p i = Pr(n ∈ P) × Pr(n ∈ v i (P) | n ∈ nodes(P)).
Given a deterministic rewriting q r of q formed by pairwise independent views v 1 , . . . , v k , for a node n ∈ q(P)), we would thus have as the overall product the following:

i Pr(n ∈ v i (P)) = Pr(n ∈ P) k × i Pr(n ∈ v i (P) | n ∈ nodes(P)). (2)
Observe that in Equation 2 we account for the probability Pr(n ∈ P) too many times, once for each view that participates in the rewrite plan. But we should instead account for it only once. Hence, by dividing Equation 2with Pr(n ∈ P) k-1 , we obtain f r :

f r (n) := Pr(n ∈ P) × i Pr(n ∈ v i (P) | n ∈ nodes(P)). (3)
Each independent view v i gives us Pr(n ∈ v i (P) | n ∈ nodes(P)), while there is now one missing ingredient in Equation 3: Pr(n ∈ P). We can compute this value only if there is a view v i ∈ V subsuming mb(q), i.e., mb(q) ⊑ v i . Summing up we conclude: Theorem 19. Let q be a TP-query, V a set of pairwise independent TP-views s.t. there is v ∈ V satisfying mb(q) ⊑ v. Let q r be a TP ∩ -rewriting of q over V . Then (q r , f r ) with the f r as in Equation 3is a probabilistic TP ∩ -rewriting of q over V .

The next theorem shows that for //-free q and V ′ it is hard to decide the existence of V ⊆ V ′ of pairwise independent views (by reduction from k-dimensional perfect matching). Thus, deciding whether the result of Theorem 19 is applicable even for //free TP queries and views is intractable. This also implies that for extended skeletons it is hard to find TP ∩ -rewritings using the probability function as in Equation 3.

Theorem 20. Let q and views V be both of TP and without //-edges, deciding whether a TP ∩ -rewriting of q using only pairwise independent views from V exists is NP-hard.

Conclusion

This is the first study on answering queries using views over probabilistic XML. The main challenge of this problem is to find probability-retrieving functions that can access only view results, while able to compute the probabilities of XML answers. So far we studied two cases of TP and TP ∩ -rewritings where these functions exist under the assumption of probabilistic independence for queries and views. In the TP case, our setting allows for polynomial time query answering in the size of both data and query. In the TP ∩ case, our setting allows for polynomial time query answering in the size of data, while it is intractable in the number of views. Recall that (direct) query answering for probabilistic XML model considered here is also polynomial in data and intractable in query complexity [START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF]. Moreover, query answering techniques of [START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF] are based on an expensive dynamic programming approach. At the same time, in our TP ∩ setting, probability computation is done by means of the f r function (Equation 3) that requires to compute probabilities that a node n occurs in p-documents. This computation is both conceptually and computationally easier than dynamic programming. It requires to collect the probabilities occurring on the way from the root of a p-document to the node n, and to multiply them. Hence, a practical implication of our study is that query answering using TP ∩ -views in our restricted setting should be more efficient than direct query evaluation q( P). As for the TP setting, reasoning over the views is tractable, while view-based query answering may require navigation in a view result P v , which in practice is often considerably smaller than P. As for the future work, one extension is to broaden the setting and to understand how one can cope with probabilistic dependences in queries and views. Another extension concerns data: p-documents studied in this paper have local probabilistic dependences, while there are models allowing for more complex probabilistic interactions between remote fragments of data [START_REF] Senellart | On the complexity of managing probabilistic XML data[END_REF]. For these types of XML data, query answering is intractable and we would like to see under which conditions we can gain tractability by relying on views.

Fig. 2 .

 2 Fig. 2. Example p-document P PER Example 1. Consider the document d PER in Figure 1 (where PER stands for personnel) describing the personnel of an IT department and the bonuses distributed for different projects. The document d PER indicates that Rick worked under two projects (laptop and pda) and got bonuses of 44 and 50 in the former project and 25 in the latter one. Identifiers are written inside square brackets and labels are next to them, e.g., the node n 4 is labeled name, i.e., lbl(n 4 ) = name. We define a finite probability space of XML documents, or px-space for short, as a pair (D, Pr) with D a set of documents and Pr mapping every document d to a probability Pr(d) such that {Pr(d) | d ∈ D} = 1.

  Deterministic view-based rewriting. Let d be a document and v a view. A (deterministic) view extension of v over d, denoted d v , is a document obtained by connecting to a root node labeled doc(v) all the documents from the set {d ′ | d ′ ⊆ d and root(d ′ ) ∈ v(d)}. Such a document can be queried by TP-queries of the form doc

2 Fig. 4 .

 24 Fig. 4. p-Documents to show non-existence of TP-rewritings (Examples 14 and 16)

  for all children of each mux node v for which no children were chosen. Note that for any P ∈ P there is a unique way to generate it. Looking again at Figures1 and 2, one can obtain the document d PER from P PER by choosing: the left child of the mux node n 11 , the right child of the mux node n 20 , and the right one of child of the mux node n 52 . The marginal probability of these choices (and the probability of d PER ), is 0.135 = 0.75 × 0.6 × 0.3.

	Example 4.

  ) with the definition of v. Example 9. Two views v 1 RBON and v 2 RBON are in Figure 3. Their extensions over d PER are, respectively, documents (d PER ) v 1 RBON and (d PER ) v 2 RBON each with two nodes: the root labeled, respectively, with doc(v 1 RBON ) and doc(v 2 RBON ), and with one child n 8 labeled Rick in both cases. Let v be v 2 RBON without the node labeled Rick and with the output node person. Then (d PER ) v has the root labeled doc(v) to which two subdocuments of d PER are connected: a subdocument rooted at n 2 and one at n 3 .

Acknowledgements. We are grateful to the anonymous reviewers for their comments. The second author is supported by the ERC FP7 grant Webdam (agreement n. 226513).

INPUT : TP query q and views V OUTPUT: Set of TP-rewritings R R := ∅, Prefs := {(q1, vi) | vi ∈ V, q1 is a lossless prefix of q, mb(q1) ≡ mb(vi), q1 ⊑ vi}; for each (q1, vi) ∈ Prefs do

// vi w/o predicates of node at rank k q ′ := comp(cut(mb(q), k), q k ) // q w/o predicates of nodes at rank 1, . . . , k -

Algorithm 1: TPrewrite for finding TP-rewritings q r for which f r are as in Eq. 1 that a node n occurs in q's result is the probability Pr(n ∈ q r (P v )) that n can be found by q r in q r ( P v ), divided by the probability Pr(n ′ ∈ v k (P n ′ v )) that n ′ verifies the predicates of v found on its output node out(v). The following theorem is the main result of this section, where for

) is v without all predicates of the node at rank k (i.e., the output node), and q ′ = comp(cut(mb(q), k), q k ) is q without all predicates of main branch nodes of rank in {1, . . . , k -1}.

Theorem 17. Let v be a TP-view, q a TP-query, and k = |mb(v)|. Let q r be a restricted TP-rewriting of q over v. If v ′ ⊥ v ′′ and v ′′ ⊥ q ′ hold, then for every n ∈ q(P) and its highest ancestor-or-self node n ′ ∈ v(P):

We summarize this section with a polynomial time algorithm TPrewrite (see Algorithm 1), that takes an the input a TP query q and a set of views V and returns all possible TP-rewritings q r , for which the probability functions f r are as in Equation 1.

In the algorithm we use so-called lossless prefixes: q 1 is a lossless prefix of q, if q 1 is a tree-pattern obtained from q by setting out(q 1 ) as some node of mbn(q).

TP ∩ -rewrite Plans

First we discuss how to decide equivalence between TP and TP ∩ queries and then provide a restriction on views for which probability functions f r exist and tractable.

Equivalence and containment for TP ∩

Since Q in TP ∩ is a rewriting for q in TP iff unfold V (Q) ≡ q, deciding whether a TP query q is equivalent to a TP ∩ query Q is crucial in our setting. It is known [START_REF] Cautis | Querying XML data sources that export very large sets of views[END_REF] that one