Pierre Senellart
email: pierre@senellart.com

Serge Abiteboul
email: serge.abiteboul@inria.fr

On the Complexity of Managing Probabilistic XML Data

Keywords: F.2.0 [Analysis of Algorithms and Problem Complexity]: General; H.2.1 [Database Management]: Logical Design Algorithms, Theory XML, probabilistic databases, semi-structured databases, complexity

 compute the correct answer. A main contribution is a full complexity analysis of queries and updates. We also exhibit a decision procedure for the equivalence of probabilistic trees and prove it is in co-rp. Furthermore, we study the issue of removing less probable possible worlds, and that of validating a probabilistic tree against a DTD. We show that these two problems are intractable in the most general case.

INTRODUCTION

Many automatic tasks generate imprecise data, e.g., information extraction, natural language processing, data min-ing. Moreover, in many of these tasks, information is represented in a semi-structured way, either because of an inherent tree-like structure of the original information, or because it is natural to represent the derived knowledge in a hierarchical manner. We thus need the means to manage imprecise tree information gathered by the system during its entire life, and in particular evaluate queries and imprecise updates over such data. In [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF], we introduced a probabilistic tree model for managing imprecise tree data 1 . A main issue is the tractability of such a model. In this paper, we discuss theoretical aspects of the probabilistic tree model, focusing on complexity issues.

The original motivation of the present work will best illustrate how such issues naturally arise and the nature of the problem. We are interested in discovering resources in the Web and more particularly in the Hidden Web. When we discover a new data source, we have to understand its semantics for future use. This leads to some analysis of the source (classification, extraction, semantic tagging, linguistic tools, etc.) that is by nature imprecise. We represent the information (knowledge) we extract in an XML warehouse. The various tools interact with the warehouse via updates and queries. The updates introduce imprecision. The interested reader can find in [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF] a short description of the project. Updating and querying imprecise data is at its core, which motivated the present paper.

To model imprecise data, we use the probabilistic tree model introduced in [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF]. The purpose was to design a model for storing imprecise information, which was both expressive and concise. Probabilistic trees are unordered trees whose nodes are annotated by conjunctions of (possibly negated) event variables, in the style of conditions in [START_REF] Imieliński | Incomplete information in relational databases[END_REF]. Each event variable is assigned a probability value. In particular, every probabilistic update introduces a new event variable (independent from the previous ones) that captures the belief the system has in this particular update. The description of an implementation and scenarios of usage of such a model can be found in [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF], where we also show that it is as expressive as the extensive description of all possible worlds.

We identify a large class of queries for which simple variations of querying and updating algorithms from [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF] compute the correct answer, by using evaluation algorithms developed for precise data. A main contribution of the paper is a precise complexity analysis of queries and updates for probabilistic trees. A large class of queries can be evaluated in ptime. For updates, deletion may be intractable. (Observe that in settings we are interested in, based on tools gathering knowledge, deletions are rare.) We also propose a theoretical foundation for the probabilistic tree model. In particular, we obtain results on the equivalence of probabilistic trees, which can be determined in polynomial time with a probabilistic algorithm. We also study the issue of removing less probable possible worlds, and that of validating a probabilistic tree against a DTD. We show that these two problems are intractable in the most general case.

Section 2 presents the probabilistic tree model, recalling definitions and results from [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF]. It also introduces new material, in particular about the complexity of queries and updates. In Section 3, a notion of equivalence between two probabilistic trees is introduced, and its complexity is investigated. Other issues are investigated in Section 4. Variants of the probabilistic tree model are discussed in Section 5. Finally, the conclusion in Section 6 includes some related works. Appendix A contains technical details about updates that are not needed to follow the paper.

THE PROBABILISTIC TREE MODEL

In this section, we present the basics of the probabilistic tree model. Most of the definitions are from [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF], with some minor changes of notation. Some new material is also included. In particular, Propositions 1 and 2 are new; Theorem 1 is an extension of Theorem 2 from [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF] to a much more general class of queries.

We first introduce a tree data model and next, the probabilistic tree model.

Definition 1. A data tree t is a 4-tuple t = (A, E, r, ϕ)
where A is a finite set of nodes, E ⊆ A 2 a tree rooted in r ∈ A and ϕ associates a label from some countable set (say, the set of character strings) to each node in A.

Let t = (A, E, r, ϕ) and t ′ = (A ′ , E ′ , r ′ , ϕ ′ ) be two data trees. We say that t and t ′ are isomorphic (denoted t ∼ t ′ ) if there is a bijection ψ : A → A ′ such that:

(i) For s1, s2 ∈ A, (s1, s2)

∈ E ⇔ (ψ(s1), ψ(s2)) ∈ E ′ ; (ii) ψ(r) = r ′ ; (iii) ∀s ∈ A, ϕ ′ (ψ(s)) = ϕ(s).
The simple data model we use is inspired by XML but ignores a number of XML features such as the ordering, the distinction between attributes, labels and text. It should be observed that it adopts a multi-set semantics. To see that, consider for instance a data tree with a root node and two children with the same label. We see it essentially as different from a data tree with a root node and a single child with the same label. A model based on a pure set semantics is briefly considered in Section 5.

Syntax of Probabilistic Trees.

We next present the probabilistic tree model for representing probabilistic semi-structured information, that is based on annotating the nodes of a tree with probabilistic conditions in the style of the conditions in [START_REF] Imieliński | Incomplete information in relational databases[END_REF].

We assume the existence of a countable set W of event variables. Let W be a finite set of event variables. A condition over W is a (possibly empty) set of atomic conditions of the form w or ¬w (for w in W ). This set can also be seen as a conjunction of these atomic conditions. A probability distribution π for W assigns probabilities, i. , to the different event variables in W . We choose not to allow zero probabilities so that, in particular, updates with a zero probability will not be performed at all. But this is only a convention and could be changed without altering the results presented here. Formally, we have:

Definition 2.
A probabilistic tree (abbreviated as probtree) T is a 4-tuple (t, W, π, γ) where t = (A, E, r, ϕ) is a data tree, W ⊆ W is finite, π is some probability distribution over W , and γ assigns conditions over W to nodes in A-{r}.

An example of prob-tree is given in Figure 1. We now define the semantics of a prob-tree, introducing to do that, the notion of Possible World set.

Semantics of Probabilistic Trees. The real world with some uncertainty is modeled by a set of possible worlds, each with its own probability. More precisely, a possible world (PW) set S is a finite set of pairs (ti, pi) where (i) the ti are data trees with the same root label, and (ii) each pi is a positive real number with P n i=1 pi = 1. An example of a PW set is shown in Figure 2.

As different PW sets may represent the same abstract possible worlds, we need a notion of isomorphism between possible world sets. Let S = {(t1, p1) . . . (tn, pn)} and S ′ = {(t ′ 1 , p ′ 1 ) . . . (t ′ m , p ′ m )} be two possible world sets. We say that S and S ′ are isomorphic (denoted S ∼ S ′ ) if, for all data tree t appearing either in S or in S ′ :

X 1 i n t i ∼t pi = X 1 j m t ′ j ∼t p ′ j
This allows defining the notion of normalization of PW sets: A PW is normalized if it does not contain two possible worlds with isomorphic data trees. Every PW set can be normalized by assigning as the probability of each possible world the sum of the probabilities of possible worlds with isomorphic data trees.

We sometimes want to study subsets of PW sets. Observe that in such a subset the sum of the probabilities is not one. Such a subset arises naturally if we start from a PW set and introduce some additional integrity constraints that rule out some of the possible worlds. Another way to think about it is to cumulate the probabilities that were lost (those of the trees violating the constraint) and assign them to the tree consisting simply of a root. In other words, this comes down to interpreting the root-tree as inconsistent. With this in mind, we can see a subset of a possible world set as a possible world set as follows: . . (tn, pn)} be a strict subset of a PW set. Let p = P 1 i n pi < 1 and t the data tree consisting of a single node with the same label as root nodes in ti. By extension, we say that S is isomorphic to the possible world set S ∪ {(t, 1 -p)}, and we note S ∼ sub S ∪ {(t, 1 -p)}.

We are now ready to define the semantics of probabilistic trees in terms of possible worlds: Definition 4. Let T = (t, W, π, γ) be a prob-tree. For V ⊆ W , the value of T in the world V , denoted V (T ), is the subtree of t where all nodes conditioned by a '¬w' atom for w ∈ V or by a 'w' atom for w / ∈ V have been removed (as well as their descendants). The possible world semantics of T , denoted T , is the PW set defined by:

T = [ V ⊆W ˘`V (T ), Y w∈V π(w) Y w∈W -V
(1 -π(w)) ´Īn particular, the PW set shown in Figure 2 is (up to isomorphism) the semantics of the prob-tree of Figure 1. A result from [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF] is that the probabilistic tree model has the same expressive power as the possible worlds model. More precisely, for each PW set S, there exists a prob-tree T such that S ∼ T . The (quite straightforward) construction of this prob-tree uses as many event variables as there are possible worlds in S. Thus, the size of the resulting probtree is essentially the size of the original PW set. One could clearly hope to find more compact representations.

In order to guarantee conciseness of the probabilistic tree model, we may want to have a polynomial bound on the size of prob-trees whose semantics only involve data trees of bounded size (and with probabilities of bounded precision).

A model with such a polynomial bound, the so-called simple probabilistic model, is presented in [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF], but it is shown to be less expressive than the PW model. Actually, the following new result shows that neither the probabilistic tree model, nor any other model as expressive as the PW model, can guarantee such a bound:

Proposition 1.
Let M be a one-to-one mapping sending every normalized possible world set (with probabilities of bounded precision) to some integer (say, a binary representation of an element of a model). Then, the average size of M (S) (that is, log M (S)) for PW sets S in which every possible world has at most n nodes is at least exponential in n.

Proof. This results from a simple counting of the number of possible world sets involving only possible worlds with at most n nodes. Let us call this number σn. If we forget about the values of the probabilities and the labels of the nodes, we get that σn must be greater than the number of sets of unordered, unlabeled, rooted trees with at most n nodes. We have the following equality about the number an of unordered, unlabeled, rooted trees with exactly n nodes [START_REF] Otter | The number of trees[END_REF][START_REF] Knuth | The Art of Computer Programming[END_REF]:

an = α n-1 n p β/2πn + O(n -5/2 α n )
where α > 2 and β are two constants. We have therefore:

σn 2 P n i=1 an 2 an Ω(2 2 n )
Since σn is doubly exponential in n, an element of M (S) cannot be identified on average with less than Ω(2 n ) bits.

Queries and Updates.

We now look at the way to perform both queries and updates on prob-trees. The first step is to define more precisely the type of queries we consider. The goal is to be able to evaluate efficiently query answers. Indeed, in practice, one would ideally like to rely on a standard query processor to do most of the work. In [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF], some efficient query processing was exhibited for the class of tree-pattern queries with joins. After extending these results in a number of directions, we realized that a similar approach can be followed for the following very large class of queries, namely the locally monotone queries. To define it, we need the auxiliary notion of sub-datatree. Note that we only consider subtrees which have the same root as the original trees, obtained by pruning some of its branches.

Definition 5. Let t = (A, E, r, ϕ), t ′ = (A ′ , E ′ , r ′ , ϕ ′ ) be two data trees. t ′ is a sub-datatree of t (denoted t ′ t) if: (i) A ′ ⊆ A; (ii) if n1 ∈ A ′ and (n2, n1) ∈ E, n2 ∈ A ′ ; (iii) E ′ = E ∩ A ′2 ; (iv) r ′ = r; (v) ϕ ′ = ϕ |A ′ .
The set of all sub-datatrees of a data tree t is denoted Sub(t).

The sub-datatree relation is clearly a partial order, which justifies the notation t ′ t.

The queries we consider return subtrees of the data tree. This greatly simplifies the management of probabilities: Intuitively, we return pieces of the original tree, but always keep the path from these pieces to the root. This notion is defined formally next, together with the large class of queries for which we will be able to generalize the query evaluation algorithm of [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF]. Definition 6. A query Q is a function over the set of data trees, such that for each data tree t, Q(t) is a (possibly empty) set of sub-datatrees of t.

A query Q is locally monotone if either of the following two equivalent conditions holds:

(i) for any three data trees

u t ′ t, u ∈ Q(t) ⇐⇒ u ∈ Q(t ′ ) (ii) for any two data trees t ′ t, Q(t ′ ) = Q(t) ∩ Sub(t ′ )
Locally monotone queries are precisely the queries for which, given an algorithm to compute the query on data trees, we can compute easily the answers on a prob-tree.

A large class of queries are locally monotone, including treepattern queries with joins (which was the framework of [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF]), but excluding negative queries. We now present the way queries are defined on PW sets and prob-trees, and state that these two definitions are consistent. Definition 7. Let Q be a query and S = {(ti, pi)} a PW set. The result of Q for S, denoted Q(S), is

[ (t i ,p i )∈S [ t∈Q(t i ) {(t, pi)}
Observe that the answer to a query is not strictly speaking a possible world set, since the probabilities do not sum to 1. To obtain one, one might group all the answers for the same ti under a common root node.

Definition 8. Let Q be a locally monotone query. The result of Q on a prob-tree T = (t, W, π, γ), denoted Q(T ), is [ u∈Q(t) ˘`u, eval `[ n node of u γ(n) ´´w
here eval(cond) returns 0 if there is an event w such that both 'w' and '¬w' are in cond, and is otherwise defined as:

Y w∈cond π(w) • Y ¬w∈cond (1 -π(w))
The following result states the consistence between the way queries are performed on prob-trees and the possible world semantics.

Theorem 1. Let T be a prob-tree and Q be a locally monotone query. Then, with a little abuse of notation since the probabilities in Q(T ) and Q( T ) do not sum to 1, we have

Q(T ) ∼ Q( T ). Proof. Let Q(T ) = {(u1, p1) . . . (un, pn)} and Q(T ′ ) = {(u ′ 1 , p ′ 1 ) . . . (u ′ m , p ′ m )}.
For a data tree u, the proof is done in two steps:

1. If u appears in Q(T ), u appears in Q( T ) and

X 1 i n u i ∼u pi X 1 j m u ′ j ∼u p ′ j 2. If u appears in Q( T ), u appears in Q(T ) and X 1 i n u i ∼u pi X 1 j m u ′ j ∼u p ′ j
Both steps are technical but not complicated.

We have similar results for updates. For simplicity, we only consider here elementary operations (insertions and deletions); see [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF] for the extension to simultaneous arbitrary sets of insertions and deletions. Typically, one wants to perform an update operation based on the result of a query. An insertion will add to a data tree some subtree at positions specified by a query. A deletion will delete from a tree all nodes at positions specified by a query. It is easy enough to extend this notion of insertions and deletions to PW sets: The probabilistic updates, built from an update operation and a probability value, which is the confidence in the update operation, are simply performed on each possible world. We showed in [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF] how to perform updates on prob-trees in a consistent way with the possible world semantics. To facilitate the reading of the paper, technical details about updates are relegated to Appendix A.

In what follows, we assume given a locally monotone query language Lq and an algorithm to answer queries over trees that are "lifted" to queries/updates over prob-trees. We next analyze the complexity of the algorithms for querying and updating prob-trees. Observe that in the following proposition, the complexity of the operations on prob-trees is stated in terms of the complexity of the corresponding operation on data trees. So, for instance, since the data complexity of tree-pattern queries with join is ptime, an immediate consequence of the proposition is that over prob-trees, it is also ptime. More precisely, let | • | denote the size (number of nodes, of literals) of a prob-tree (or of a set of possible worlds), and time denotes the time it takes to evaluate the query or operation. Then the complexity of the algorithms presented for querying and updating, that is, an upper bound on the complexity of the associated problems (based on an algorithm to answer Lq queries), is as follows:

Proposition 2. Let T be a probabilistic tree with underlying data tree t. Let Q be a query over T , and iQ and dQ be respectively an insertion and deletion on T , with Q as defining query.

time(Q(T )) time(Q(t)) + O(|Q(t)| • |T |) time(iQ(T )) time(Q(T )) + O(|Q(t)| • |T |) |iQ(T )| |T | + O(|Q(t)| • |T |) time(dQ(T )) time(Q(T )) + O(|Q(t) • 2 |T | ) |dQ(T )| |T | + O(|Q(t)| • 2 |T | )
Proof. These follow from the analysis of the evaluation algorithms and from the definitions. The combinatorial explosion of deletions happens when a query has multiple results (essentially because, in this case, we need to express the negation of a disjunction of conjunctions in terms of a disjunction of conjunctions), and as we shall see in Theorem 3, this complexity is inherent to the problem of deletion in prob-trees.

EQUIVALENCE OF PROB-TREES

One defines the notion of equivalence between prob-trees directly based on data tree isomorphism. It essentially states that two prob-trees talk about the same event variables and that for each assignment of values to the event variables, they define the same possible world. Definition 9. Let T = (t, W, π, γ), T ′ = (t ′ , W, π, γ ′ ) be two prob-trees (over the same event variables and distribution). Then T and T ′ are structurally equivalent (denoted

T ≡struct T ′ ) if for each V ⊆ W, V (T ) ∼ V (T ′ ).
Note that an alternative definition of equivalence of probtrees, based on their possible world semantics, is discussed in Section 5. We have a simple complexity upper bound about structural equivalence: Proposition 3. Determining if two prob-trees (over the same event variables and distribution) are structurally equivalent is co-np.

Proof. The complement of this problem can be solved with the following np algorithm:

INPUT: two prob-trees T1 and T2 on the same event variable set W and with the same probability distribution π OUTPUT: true if T1 ≡struct T2 (a) Guess a subset V of W . (b) Compute V (T1) and V (T2) in linear time. (c) If V (T1) ∼ V (T2), return true. (Isomorphism of labeled unordered data trees can be determined in linear time, cf [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF] and the algorithm in the proof of Theorem 2.)

We will also show a more precise result in Theorem 2, that this problem is co-rp [START_REF] Papadimitriou | Computational Complexity[END_REF]. To do it, we will use some bridge to (i) the number of disjuncts satisfied by valuations of DNF formulas and (ii) multivariate polynomials.

Definition 10. Let ψ and ψ ′ be two propositional formulas in disjunctive normal form. We say that ψ and ψ ′ are count-equivalent, denoted ψ + ≡ ψ ′ , if, for any valuation ν of the variables appearing in ψ and ψ ′ , the same number of disjuncts is satisfied by ν in ψ and in ψ ′ .

We note that this is a stronger notion than simple propositional formula equivalence. For instance, the formulas A ∨ (A ∧ B) and A are equivalent but not count-equivalent. We indicate next how we can relate count-equivalence of formulas in DNF with equality of multivariate polynomials. Definition 11. Let ψ be a propositional formula in disjunctive normal form, over variables X1 . . . Xn. Let ψ ′ be a formula in DNF obtained from ψ by removing every disjunct containing incompatible conditions or False, and by removing duplicate atomic conditions from each disjunct and True from conjunctions with other literals. The characteristic polynomial of ψ, denoted P ψ , is the multivariate polynomial in X1 . . . Xn with integer coefficients, obtained from ψ ′ in the following manner: (i) Positive literals Xi are left as is. (ii) Negative literals ¬Xi are replaced by (1 -Xi). (iii) Disjunction is replaced by addition. (iv) Conjunction is replaced by multiplication. (v) True is replaced by 1 and False by 0. Lemma 1. Let ψ and ψ ′ be two propositional formulas in disjunctive normal form. Then, ψ + ≡ ψ ′ if and only if

P ψ = P ψ ′ .
Proof. One direction is obvious, i.e., if P ψ = P ψ ′ then ψ + ≡ ψ ′ . For that, just observe that the number of conjuncts satisfied by some valuation ν in ψ is the value of P ψ for this valuation. Now to consider the converse, first observe that P ψ and P ψ ′ are polynomials with degree at most 1 in every variable (this comes from the normalization of the formula in DNF used in Definition 11). Suppose that ψ + ≡ ψ ′ . Consider the development of P ψ :

P ψ (X1 . . . Xn) = X V ⊆ 1;n αV Y i∈V Xi
and similarly for P ψ ′ with coefficients α ′ V . We have, for each tuple (x1 . . . xn) of {0, 1} n ,

P ψ (x1 . . . xn) = P ψ ′ (x1 . . . xn), that is to say, X U ⊆{i|x i =1} αU = X U ⊆{i|x i =1} α ′ U .
We can then prove by induction on the cardinality of V that this implies that ∀V ⊆ 1; n , αV = α ′ V , which means that P ψ = P ψ ′ .

One can "clean" a probabilistic tree by removing (in linear time) superfluous atomic conditions, i.e., conditions implied by some condition on an ancestor; and pruning nodes with inconsistent conditions, i.e., conditions that are intrinsically inconsistent or that contradict condition imposed by an ancestor. We call such trees clean prob-trees. The following result gives an inductive definition of structural equivalence on clean prob-trees; the proof is straightforward.

Lemma 2. Let T = (t, W, π, γ) and T ′ = (t ′ , W, π, γ ′ ) be two clean prob-trees (over the same event variables and probability distribution).

Let u1 . . . un be representative elements of the n equivalence classes implied by structural equivalence over the subtrees of T and T ′ rooted at each child node of the root of T and T ′ , the condition on the root of which has been removed. For 1 i n, let ψi be the disjunction of the conditions attached to the children of the root of T whose subtree is structurally equivalent to ui, and let ψ ′ i be the same for T ′ . Then, T ≡struct T ′ if and only if ϕ(r) = ϕ(r ′ ) and, for each 1 i n, ψi

+ ≡ ψ ′ i .

This leads to our main result on structural equivalence:

Theorem 2. There is a ptime algorithm, that, given two prob-trees, always returns true if the prob-trees are structurally equivalent and returns false if the prob-trees are not structurally equivalent with probability at least 1/2 (that is, determining if two prob-trees are equivalent is a co-rp problem [START_REF] Papadimitriou | Computational Complexity[END_REF]).

Proof. The algorithm relies on Lemmas 1 and 2, and uses an algorithm derived from a classical algorithm for labeled tree isomorphism from [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF]. Moreover, we use the Schwartz-Zippel Lemma [START_REF] Schwartz | Fast probabilistic algorithms for verification of polynomial identities[END_REF][START_REF] Zippel | Probabilistic algorithms for sparse polynomials[END_REF], which states that the probability that a multivariate polynomial of degree d is zero on a point each coordinate of which is randomly chosen in some finite set S is d/|S|.

The algorithm is presented in Figure 3. We have the following lower bound for the probability that this algorithm is correct when it returns false:

" 1 - " N l |S| " m " N 3 n , where N l
is the number of literals of T and T ′ , and Nn the number of nodes. This probability is greater than 1/2 as soon as m and S are chosen such that |S|

N l m q 1-(1/2) 1/N 3 n .
Observe that determining whether a prob-tree is independent of some event variable is actually computationally as complex as deciding equivalence between prob-trees. Indeed, if T and T ′ are two prob-trees, determining if T is structurally equivalent to T ′ can be done by determining if the following tree is independent of w (a fresh variable):

INPUT: two prob-trees T and T ′ , a finite set S of integers, a positive integer m OUTPUT: true if T ≡struct T ′ ; false if T ≡struct T ′ with probability 1/2 (a) Clean T and T ′ . (b) Assign to all leaves of T and T ′ with the same label a fresh integer i (and do not assign the same integer to two leaves with different labels). (c) Assume inductively that all nodes of T and T ′ at a distance at most k from the leaves have been assigned an integer. For each pair (n, n ′ ) where n (resp. n ′ ) is a node of T (resp. T ′ ) at distance k + 1 from the leaves, and n and n ′ have the same label: (i) Compute the sets A and A ′ of the integers assigned to the children of n and n ′ . (ii) If A = A ′ , for each element i of A, compute the formulas in DNF ψi and ψ ′ i corresponding to the conditions on the children of n and n ′ assigned with i. Choose at random m points of S p , where p is the number of variables of P ψ i -P ψ ′ i , and evaluate this polynomial in these points. If all these evaluations return 0 for each i of A, assign the same integer value to n and n ′ (if one of them is already assigned an integer, take this integer as the assigned value for the other one, possibly doing some merging of values; otherwise, take a fresh integer). (d) Assign fresh integers to nodes at distance k + 1 from the leaves with no assigned integer, and go to the previous step with the next value of k. (e) If the roots have been been assigned the same integer, then return true else return false.

OTHER ISSUES ABOUT PROB-TREES

In this section, we consider three natural problems about probabilistic trees that all highlight some inherent complexity in dealing with imprecise data. First we show that some deletion may cause a combinatorial explosion. We then prove that similar phenomena arise when we try to restrict the possible worlds (i) to have at least a threshold probability and (ii) to be valid with respect to some DTD. The proofs are very similar.

Deletions. First we consider deletion. In this part, we will assume that our query language is expressive enough to express the following deletion: d0 = "If the root has a C-child, then delete all B-children of the root." (this is not a strong assumption, since it is for instance the case with simple tree pattern queries).

Theorem 3. For all n ∈ N, there exists a prob-tree T , of size O(n), such that for each prob-tree T ′ such that T ′ ≡struct d0(T ), the size of T ′ is Ω(2 n ).

Proof. Consider the following prob-tree T , which has n + 2 nodes and 2n event variables, each appearing only once (we take an arbitrary probability distribution π, say π(n) = 1/2 for all n):

A B C w (0) 1 , w (1) 1
. . . C

w (0) n , w (1) n
Let T ′ be a prob-tree such that T ′ ≡struct d0(T ). We assume that the deletion has a confidence of 1 (that is, it does not introduce a new event variable).

T ′ is necessarily some prob-tree of height 1 with root node A, and with a number of B and C children. Let Ψ be the set of conditions annotating nodes labeled by B. Observe that for all ψ ∈ Ψ, and for all 1 k n, either ¬w (0) k or ¬w

(1) k appears in ψ (otherwise, there is a possible world for T ′ where both B and C nodes appear, which is a contradiction with the definition of d0).

Let now {b1 . . . bn} be an arbitrary element of {0, 1} n . Let ν be the valuation of the event variables such that ∀1 k n, ν(w

(b k ) k ) = 0 and ν(w (1-b k ) k ) = 1. ν(T )
′ k = 1.
This leads to a contradiction, which means that to each element of {0, 1} n corresponds a different element of Ψ. T ′ has then more than 2 n different literals, which concludes the proof.

Threshold Probability. We consider next what happens

when some probability threshold is imposed on a probabilistic tree.

Given a prob-tree, one may want to eliminate the possible worlds that are too improbable. More precisely, consider a prob-tree T with T = {(t1, p1) . . . (tn, pn)}. Let us further assume that it is normalized, i.e., that there are no i, j distinct with ti ∼ tj. Suppose we fix some p for a minimum threshold on probability. Then we define

T p = {(ti, pi) ∈ T |pi p}
Unfortunately, there are cases where there is no compact prob-tree to represent T p : Theorem 4. For all n ∈ N, there exist a prob-tree T of size O(n) and a probability threshold p such that for each prob-tree T ′ such that T p ∼ sub T ′ , the size of T ′ is Ω(2 n ).

Proof. We use the following prob-tree, with 2n+1 nodes and 2n event variables, each appearing once; we take a uniform probability distribution π(wi) = 1/2n and a probability threshold p = 1/2:

A C1 w1 . . . C2n w2n
The proof is quite similar to that of Theorem 3, and uses the fact that `2n n ´= Ω(2 n ).

Validation. Finally we consider validity with respect to a DTD. A Document Type Definition for an XML document defines the constraints applying on the children of a node using a sequence operator ((A,B)), a disjunction operator ((A|B)) and several repetition operators ((A*), (A+), (A?)). As we consider only unordered trees, we do not consider the sequence operators. To simplify, we will not consider the disjunction operator either. The following definition of DTDs then simply states that a DTD gives a lower and upper bound for the number of occurrences of nodes with a given label n ′ as children of some node labeled by n. Definition 12. A Document Type Definition (DTD) D is a function over some finite subset N ′ of the set of labels N such that for all n ∈ N ′ , D(n) is a finite set of elements of N × 0; +∞ × 1; +∞ and, if (n1, p1, q1) ∈ D(n) and (n2, p2, q2) ∈ D(n), either n1 = n2 or (n1, p1, q1) = (n2, p2, q2).

We use the following notation, for n ∈ N ′ : D-(n)(n ′ ) and D+(n)(n ′ ) are respectively the unique p and q such that (n ′ , p, q) ∈ D(n) if such p and q exist; otherwise, we note D-(n)(n ′ ) = 0 and D+(n)(n ′ ) = 0. Definition 13. Let D be a DTD and t = (A, E, r, ϕ) a data tree. Let N ′ be the domain of D. We say that t satisfies D (denoted t |= D) if, for each s ∈ A such that ϕ(s) ∈ N ′ , and for each n ′ ∈ N :

D-(ϕ(s))(n ′ ) ˛{s ′ ∈ A | ϕ(s ′ ) = n ′ ∧ (s, s ′ ) ∈ E} D+(ϕ(s))(n ′ ) ˛{s ′ ∈ A | ϕ(s ′ ) = n ′ ∧ (s, s ′ ) ∈ E} Note
that we do not impose any condition on nodes of t whose label is not in the domain of the DTD. Given a probtree T and a DTD D, three natural questions naturally arise: We have the following complexity results about these questions:

Theorem 5.

1. The DTD Satisfiability problem is np-complete in the number of event variables (and linear in the number of nodes in the tree).

2. The DTD Validity problem is co-np-complete in the number of event variables (and linear in the number of nodes in the tree).

3. There are instances of the DTD Restriction problem in which the solution of the DTD Restriction problem is necessarily exponential in the size of the input.

Proof. The third part is proved in the same way as Theorem 4, with a DTD requiring that the node A has at most n children labeled by C. The Ci nodes are replaced by C nodes with a Di child in order to give them the same label while keeping them distinguishable.

For the first two parts, we use a reduction of SAT. The beginning of the construction is the same in both cases.

Let θ be a propositional logic formula, in conjunctive normal form (i.e., an input to the SAT problem). Let ψ1 . . . ψn be the terms of ¬θ in disjunctive normal form (the DNF of ¬θ is computed in a linear time from θ which is in CNF).

Let T be the following prob-tree:

˘(t, p) ∈ T | t |= D ¯ = ∅ ⇐⇒ ψ1 ∨ • • • ∨ ψn not a tautology ⇐⇒ θ is satisfiable
Since the construction of the reduction is linear in the size of θ, this proves that the DTD satisfiability problem is np-hard.

Moreover, here is a np algorithm for the DTD satisfiability problem, which concludes the proof of its npcompleteness: Guess a valuation ν of the event variables of T , and return true if ν(T ) satisfies the DTD (which can be checked in linear time).

Consider the DTD D: D

(A) = {(B, 1, +∞)}. ˘(t, p) ∈ T | t |= D ¯∼ T ⇐⇒ ψ1 ∨ • • • ∨ ψn tautology ⇐⇒ θ is not satisfiable
Since the construction of the reduction is linear in the size of θ, this proves that the validity problem is conp-hard. Moreover, here is a np algorithm for the complement of the validity problem, which concludes the proof of its co-np-completeness: Guess a valuation ν of the event variables of T and return true if ν(T ) does not satisfy the DTD.

Observe that the DTDs we used in the proof are all of constant size.

VARIANTS

In this section, we briefly consider variants of the probabilistic tree model presented up to here, and discuss their complexity. Namely, we consider (i) a tree model with set semantics, instead of our multi-set semantics; (ii) the notion of semantic equivalence (in place of structural equivalence); (iii) a probabilistic tree model where nodes are assigned arbitrary propositional formula (and not simply conjunctions) as conditions; and (iv) ordered trees.

Set Semantics. In this paper, we use a data model with a multi-set (or bag) semantics. One can consider instead a set semantics. One just has to redefine isomorphism between data trees inductively as follows. Let t, t ′ be two trees. They are isomorphic if their roots have the same label and if each subtree of the root of t is isomorphic to some subtree of the root of t ′ , and symmetrically. Most definitions of this paper can then be applied as is, relying on this new version of data tree isomorphism. The results about queries and updates remain, including the exponential complexity of deletions from Theorem 3 (the proofs are almost unchanged). An important difference, however, is for structural equivalence, for which there is now a simple way of proving co-np-completeness: Just observe that we no longer deal with count-equivalence, but with classical equivalence of propositional formulas.

Semantic Equivalence. Structural equivalence is only relevant for prob-trees that share the same event variables. If we want to compare prob-trees with different sets of events, we can define another kind of equivalence, through their possible world semantics: T and T ′ are semantically equivalent (denoted T ≡sem T ′ ) if T ∼ T ′ . The first natural question is that of the relation between structural and semantic equivalence.

Proposition 4. Let T = (t, W, π, γ), T ′ = (t ′ , W ′ , π ′ , γ ′ ) be two prob-trees, with W = W ′ and π = π ′ . Then (i) If T ≡struct T ′ , then T ≡sem T ′ ;

(ii) T ≡struct T ′ if and only if, for each probability distribution π ′′ over W , (t, W, π ′′ , γ) ≡sem (t ′ , W, π ′′ , γ ′ ).

Proof. (i) is obvious. Now suppose that for each π ′′ over W , (t, W, π ′′ , γ) ≡sem (t ′ , W, π ′′ , γ ′ ). To conclude the proof, it clearly suffices to show that T ≡struct T ′ . For each V ⊆ W , let πV be the probability distribution that maps w ∈ V to 1 and w ∈ W -V to 0. Then, if TV and T ′ V denote respectively the prob-trees obtained from T and T ′ by exchanging the original probability distribution π with πV , TV = {(V (T ), 1)} and T ′ V = {(V (T ′ ), 1)} and we have thus V (T ) = V (T ′ ).

Note that stricty speaking, we disallowed variables with 0 probability. So to be precise, we should use ε instead of 0 and 1 -ε instead of 1. If ε is chosen so that (1 -ε) n > 2 n ε (which is always possible for a sufficiently low value of ε), V (T ) and V (T ′ ) will be the elements of highest probability of, respectively, T and T ′ . Note that T ≡sem T ′ does not imply T ≡struct T ′ . For instance, if w1, w2, w3 verify π(w3) = π(w1) • π(w2), we have :

A B w1, w2 ≡sem ≡struct A B w3
Clearly, there is an exptime algorithm for determining if two prob-trees are semantically equivalent (just compute the possible world sets, normalize them, and check if they are isomorphic, which can be decided in quadratic time in the number of possible worlds). It is open whether the problem also belongs to a lower complexity class. Similarly, it is open whether Theorem 3 on the complexity of deletions still holds for semantic equivalence.

Arbitrary Propositional Formula. In prob-trees, the conditions we use are conjunctions of literals. A natural extension is to allow any propositional formula (including disjunctions) as conditions. A question is how this is affecting the complexity. First, one can show that the evaluation of boolean queries is np-complete (assuming the underlying query language over data tree is in ptime and includes, say, tree pattern queries). The fact that it is np is obvious, and there is a linear-time reduction of SAT to this problem. Then, the cost of an update operation is now ptime (again assuming the underlying language on data trees is ptime). Indeed, we can now simply annotate inserted or deleted nodes by complex formulas. In particular, Theorem 3 is no longer valid. So this model privileges updates (that are cheap) against queries (that are expensive). It is not adapted to the applications that motivated our work.

Order Semantics. By considering ordered trees, we would move closer to standard XML. The situation is more intricate and would require totally different techniques. The complexity is higher because of the inherent combinatorics that is introduced.

CONCLUSION

The topic of probabilistic databases has been intensively studied, see for instance [START_REF] De Rougemont | The reliability of queries[END_REF][START_REF] Cavallo | The theory of probabilistic databases[END_REF][START_REF] Barbará | The management of probabilistic data[END_REF][START_REF] Fuhr | A probabilistic relational algebra for the integration of information retrieval and database systems[END_REF], and [START_REF] Dalvi | Efficient query evaluation on probabilistic databases[END_REF][START_REF] Widom | Trio: A system for integrated management of data, accuracy, and lineage[END_REF] for more recent works. The idea of associating probabilistic formulas to data elements comes from the conditional tables of [START_REF] Imieliński | Incomplete information in relational databases[END_REF]. A work close in spirit to this one, but in the context of relational databases, is [START_REF] Abiteboul | On the representation and querying of sets of possible worlds[END_REF]; the tree structure and multi-set semantics we use have for consequence that the complexity results on tables of [START_REF] Abiteboul | On the representation and querying of sets of possible worlds[END_REF] do not apply to our model.

A relatively small number of works have dealt with the representation of probabilistic semi-structured data. In [START_REF] Dekhtyar | Semistructured probabilistic databases[END_REF], a semi-structured database is used to store complex probability distributions of data which is essentially relational. Works closer to ours are [START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF][START_REF] Hung | PXML: A probabilistic semistructured data model and algebra[END_REF][START_REF] Van Keulen | A probabilistic XML approach to data integration[END_REF]. Nierman et al. [START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF] describe a very simple model, which does not have full expressive power, and present strategies for efficient evaluations of logical queries. In [START_REF] Hung | PXML: A probabilistic semistructured data model and algebra[END_REF], a complex model, based on directed acyclic graphs, is developed, along with an algebraic query language. Finally, Keulen et al. [START_REF] Van Keulen | A probabilistic XML approach to data integration[END_REF] present an approach to data integration using probabilistic trees; their model is derived from the PW model, and allows both extensive descriptions of the possible worlds and node-based factorization. Querying and the way to present data inte-gration results on this model are also shown. None of these works touch upon the question of updates.

We have presented a theoretical foundation for the probabilistic tree model, a model for representing probabilistic semi-structured data. We have provided a complexity analysis of updates and queries over probabilistic trees, as well as a probabilistic decision procedure for prob-tree equivalence. We have shown that other operations on prob-trees are intractable, highlighting the inherent complexity of the model. Finally, we have discussed how variations in the model affect the complexity of the various problems.

The present work may be pursued in a number of directions. A first one is prob-tree simplification. One would often like to approximate a prob-tree to get a more compact representation, perhaps ignoring less probable worlds and some of the probabilistic events (some of the provenance/history). Also, probabilities can be used to rank results. It would be useful to have algorithms obtaining the most probable results first. Finally, it would be interesting to also handle aggregate functions. We believe the use of multi-sets simplifies this last issue.

Figure 1 :

 1 Figure 1: Example probabilistic tree

Figure 2 :

 2 Figure 2: Example Possible World set

Figure 3 :

 3 Figure 3: Probabilistic algorithm for structural equivalence

  is the subtree of T with only two nodes labeled by A and B. Therefore, ν(d0(T )) = d0(ν(T )) = ν(T ). This means that there exists ψ b 1 ...bn ∈ Ψ such that ν |= ψ b 1 ...bn . Assume now by contradiction there exist b1 . . . bn, b ′ 1 . . . b ′ n and 1 k n, such that ψ b 1 ...bn = ψ b ′ 1 ...b ′ n = ψ and b k = b ′ k . But we have already noted that ψ contains either ¬w (0) k or ¬w (1) k . In the former case, we cannot have either b k = 0 or b ′ k = 0; in the latter, we cannot have b k = 1 or b

  1. (DTD Satisfiability) ˘(t, p) ∈ T | t |= D ¯? = ∅ 2. (DTD Validity) ˘(t, p) ∈ T | t |= D ¯? ∼ T 3. (DTD Restriction) How to compute a prob-tree T ′ such that ˘(t, p) ∈ T | t |= D ¯∼sub T ′ .

1 .

 1 Consider the DTD D: D(A) = {(B, 0, 0)}.

In[START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF], we referred to it as the fuzzy tree model; we changed the terminology here at the request of the reviewers, in order to avoid confusion with works on fuzzy databases.

ACKNOWLEDGMENTS

We want to thank Luc Segoufin for his comments on this paper.

This work has been partially supported by the ANR projects WebContent and DocFlow.

APPENDIX A. UPDATES IN PROBABILISTIC TREES

In this section, we will present technical definitions on the kind of updates dealt with, and the way they are performed in probabilistic trees.

We will assume that a query Q defines, for each data tree t, and for each t ′ ∈ Q(t), a mapping µQ from some finite set NQ to the nodes of t ′ . If we consider the language of tree pattern queries, for instance, NQ will be the set of nodes of the query tree, and µQ will map a node of the query tree to the corresponding node in the result tree. Definition 14. An (elementary) update operation is a pair τ = (Q, v) where Q is a locally monotone query and v is either:

1. an insertion on NQ, that is, an expression i(n, t ′ ) where n ∈ NQ and t ′ is a tree to insert (as a child of the node mapped by n); 2. or a deletion on NQ, that is, an expression d(n) where n ∈ NQ (indicating the node to delete).

Queries are used to select the nodes of the trees where insertions or deletions are made. Intuitively, when one applies an update operation (say, a deletion) on a data tree t, it results in the deletion of a sub-datatree for each valuation of Q.

Definition 15. Let τ = (Q, v) be an update operation. Let t be a tree matched by Q, and let µQ 1 . . . µQ p the mappings of Q for t and each element of Q(t). Let n be the node of NQ appearing in v. The result of the operation τ on t, denoted τ (t), is:

), the result of the insertion of t ′ as a child of all µQ k (n) for 1 k p (possibly inserting t ′ multiple times at the same place);

A probabilistic update operation is a pair (τ, c) where τ is an update operation and c ∈]0; 1] is the confidence we have in the operation.

Definition 16. Let S = {(ti, pi)} be a PW set, (τ, c) a probabilistic update operation, τ = (Q, v). The result of (τ, c) on S, denoted (τ, c)(S), is the PW set:

We can define the result of an update operation on a probtree T = (t, W, π, γ). Consider the case where |Q(T )| = 1, that is, where the position of update operations is uniquely defined (the extension when |Q(T )| > 1 is straightforward and detailed in [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF]). Let u be the unique element of Q(T ) and cond = S n node of u γ(n); cond is the set of conditions to be applied to the inserted and deleted nodes. Let µQ be the mapping defined by Q for t and u, and n the element of NQ appearing in u. The result of (τ, c) on T , denoted (τ, c)(T ), is the prob-tree obtained from t by applying the insertion or deletion of τ in the following way.

Insertions are performed at the position µQ(n). If we denote condancestors the union of the conditions on the (strict) ancestors of n, t ′ is inserted and its root is assigned the condition {w} ∪ `cond -(γ(µQ(n)) ∪ condancestors)

´. Deletions are performed at the position mapped by Q on t. Let condancestors be the union of the conditions on the (strict) ancestors of µQ(n). Let condnew = {w} ∪ `cond -(γ(µQ(n)) ∪ condancestors) ´. The original µQ(n) node is replaced by as many copies as elements of condnew. Let now a1 . . . ap be the p elements of condnew. The first copy of µQ(n) is annotated with condition γ(µQ(n)) ∪ {¬a1}. The second copy of µQ(n) is annotated with condition γ(µQ(n))∪ {a1, ¬a2}. . . The last copy of µQ(n) is annotated with conditions γ(µQ(n)) ∪ {a1 . . . an-1, ¬an}.

Then, a result similar to Theorem 1 states that, for a probabilistic update operation (τ, c) and a prob-tree T , we have (τ, c)(T ) ∼ (τ, c)( T ), that is, the algorithm presented to perform updates on prob-trees is consistent with the possible world semantics.