Serge Abiteboul
email: serge.abiteboul@inria.fr

Benny Kimelfeld
email: kimelfeld@us.ibm.com

Yehoshua Sagiv
email: sagiv@cs.huji.ac.il

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

On the Expressiveness of Probabilistic XML Models

Keywords: XML, Probabilistic databases, Probabilistic XML, Expressiveness, Updates

Various known models of probabilistic XML can be represented as instantiations of the abstract notion of p-documents. In addition to ordinary nodes, pdocuments have distributional nodes that specify the possible worlds and their probabilistic distribution. Particular families of p-documents are determined by the types of distributional nodes that can be used as well as by the structural constraints on the placement of those nodes in a p-document. Some of the resulting families provide natural extensions and combinations of previously studied probabilistic XML models.

.

Introduction

Many automatic tasks, particularly on the Web, generate uncertain data. Examples of these tasks include information extraction, natural-language processing and data mining. Moreover, in many of these tasks, information is described in a semistructured model, because representation by means of a hierarchy is natural, especially when the source (e.g., XML or HTML) is already in this form. Uncertain hierarchical information can be formalized in terms of a probabilistic XML space, that is, a probability distribution over a set of ordinary XML documents. A number of probabilistic XML models [START_REF] Senellart | On the complexity of managing probabilistic XML data[END_REF][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] Hung | Probabilistic interval XML[END_REF][START_REF] Van Keulen | A probabilistic XML approach to data integration[END_REF][START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF][START_REF] Senellart | Comprendre le Web caché. Understanding the Hidden Web[END_REF] have been proposed for facilitating a succinct description of those spaces. In addition to the models themselves, various problems of managing probabilistic XML data have been studied, such as query evaluation [START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF][START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF][START_REF] Kimelfeld | Matching twigs in probabilistic XML[END_REF][START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF], algebraic manipulation [START_REF] Hung | PXML: A probabilistic semistructured data model and algebra[END_REF] and updates [START_REF] Senellart | On the complexity of managing probabilistic XML data[END_REF][START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF].

For developing a system that manages probabilistic XML, a proper data model should be chosen; to do that, two questions have to be addressed. First, what kind of information is it desired to represent (e.g., how do different uncertain data items correlate)? Second, which management tasks does the system need to perform? As a concrete example, van Keulen et al. [START_REF] Van Keulen | A probabilistic XML approach to data integration[END_REF] use a specific model to represent the result of integrating two XML documents (where uncertainty essentially follows from heuristics for entity resolution). One may want to use the model of [START_REF] Van Keulen | A probabilistic XML approach to data integration[END_REF] for representing similar data, but then, will one be able to (efficiently) realize the algebra of [START_REF] Hung | PXML: A probabilistic semistructured data model and algebra[END_REF] or evaluate twig queries using the algorithm of [START_REF] Kimelfeld | Matching twigs in probabilistic XML[END_REF]? The answer is not obvious, given the differences among the three data models.

A simple way of bridging the different models and techniques is to devise translations between the models. That is, given a probabilistic XML document represented in one model, we translate it into another model, and then manage the result using techniques devised for the latter model. Moreover, for this process to be practical, the translation should be efficient. As we later show, it may be the case that a translation between two specific models exists, but it necessarily entails a major blowup in the size of the data. Thus, understanding the ability to efficiently translate between the different models, which is a goal set by this work, has a central role in choosing the suitable model for a system and analyzing the implications of a specific choice. Moreover, if one already has an implemented system based on a specific model and yet wishes to use it for data of a different model, then translations are essentially the only way to go.

Another important property of a probabilistic XML model is the ability to represent interesting evolution of the probabilistic data. So, in addition to comparing the expressive power of probabilistic XML models (i.e., in terms of efficient translations), we study the ability of the models to handle updates. More particularly, we consider insertion and deletion of data items that are done at elements specified by queries. Conceptually, these operations are done on the possible worlds. We investigate the ability to apply these updates directly to a probabilistic XML document and the cost thereof. We do it in the context of specific models.

We begin with presenting a unified view of these different models in terms of p-documents that are trees with two types of nodes: ordinary and distributional. A p-document can be thought of as a probabilistic process that generates a random XML document in a conceptually simple way. Namely, each distributional node v chooses a subset of its children. 1 Therefore, each distributional node of a p-document should specify the probability distribution of choosing a subset of its children in the above random process. There are several types of distributional nodes that differ from one another in how they specify probabilities and in certain properties thereof.

We consider five types of distributional nodes: det for deterministic 2 (each child is chosen with probability 1); ind for independent (the choices of distinct children are independent); mux for mutually exclusive (at most one child can be chosen); exp for explicit (the probability of choosing each subset of children is explicitly given unless it is zero); and cie for conjunction of independent events (each child is chosen according to a conjunction of probabilistically independent events, which can be used globally throughout the p-document).

We define different families of p-documents in terms of the types of distributional nodes that are allowed. PrXML C , where C ⊆ {ind, mux, det, exp, cie}, denotes the family of p-documents that use the types appearing in the subset C. We also consider additional families by imposing the restriction that there are no hierarchies consisting entirely of distributional nodes (i.e., a distributional node cannot have a distributional child).

PrXML C

| h denotes the family of p-documents that use the types of C and have no distributional hierarchies. We later show that practically all the probabilistic XML models that have been proposed in the literature can be defined in this way.

We thoroughly investigate the expressive power of the above families. To define expressiveness properly, one should realize that we are not interested in a pdocument per se, but rather in the probability space (over XML documents) that it describes. Thus, two pdocuments are equivalent if they define the same probability space (called px-space in this paper). Consequently, a family F 2 is (at least) as expressive as F 1 if for every p-document of F 1 , there is an equivalent pdocument of F 2 (if the opposite direction does not hold, then F 2 is more expressive). Practically, however, F 2 subsumes F 1 only if we can find an efficient algorithm, such that given a p-document of F 1 , it computes an equivalent p-document of F 2 . So, our emphasis is on efficient translators between families of p-documents. Furthermore, we consider two types of translators: otranslators and v-translators. The former is based on the object semantics (i.e., two p-documents are equivalent if they describe identical px-spaces), whereas the latter subscribes to the value semantics (that is, equivalence means isomorphic px-spaces).

Figure 5.7 summarizes our results about efficient otranslations, which are obtained in Section 5. This figure is complete in the sense that if there is no directed path from a family F 1 to a family F 2 , then there is no efficient o-translation from F 1 to F 2 . Note that if there is an efficient o-translation, then there is also an efficient v-translation (but the converse is not necessarily true). We show that in many cases, if there is no efficient otranslation (between two specific families F 1 and F 2 of our framework), then there is no efficient v-translation as well. However, the existence of efficient v-translations (in the absence of efficient o-translations) remains an open problem in some cases. Thus, Figure 5.7 is not complete with respect to v-translations, but it gives a fairly good picture.

We partially deal with the above open problems of Section 5 in Section 6, where we consider p-documents with the restriction of a fixed bound on the degree of distributional nodes. For instance, for a fixed integer b ≥ 2, the family PrXML {exp} ∆≤b is the subset of PrXML {exp} comprising the p-documents such that every distributional node has at most b children. We consider (o-and v-) translations between families of pdocuments under this restriction (e.g., can we efficiently change a p-document to meet this restriction while preserving equivalence?). In particular, we show that for all b 2 > b 1 ≥ 2, there is an efficient v-translation from PrXML ) to PrXML {ind,mux} ; interestingly, these are the only cases for which we show that there are efficient v-translations, but o-translations do not exist at all. We also investigate whether families of p-documents are closed under updates. An update is naturally defined on the px-space associated with a p-document, but we would like to perform it efficiently on the pdocument itself (without introducing additional types of distributional nodes). We consider tractability of updates under both the object semantics and the value semantics, but now the main difference between the two is in the language defining updates, which is richer in the case of the value semantics. We show that under the object semantics, updates are tractable in all "reasonable" models. Under the value semantics, insertions (even just those defined by single-path queries) are intractable in PrXML {exp} , but can be done efficiently in PrXML {cie} provided that they are defined by monotone queries.

After presenting some preliminaries in Section 2, we introduce p-documents in Section 3. Five types of distributional nodes are defined in Section 4, and we show that they extend the models of probabilistic XML that have been described in the literature. In Sections 5 and 6, we present results on translations between models. Updates are the subject of Section 7.

This paper extends work reported in [START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF][START_REF] Senellart | On the complexity of managing probabilistic XML data[END_REF]. In particular, it expands the results of [START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF] on expressiveness of probabilistic XML models. A companion paper [START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF] extends the results of [START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF] (and some of those reported in [START_REF] Kimelfeld | Matching twigs in probabilistic XML[END_REF]) about query evaluation over probabilistic XML models.

Preliminaries

We represent (probabilistic) data by unordered, unranked, labeled trees. Given a tree T , the set of nodes and the set of edges are denoted by V (T ) and E (T ), respectively. Note that E (T ) ⊆ V (T ) × V (T ). We use root(T ) to denote the root of

T . If (n 1 , n 2 ) ∈ E (T ), then n 2 is a child of n 1 , which in turn is the parent of n 2 .
A leaf of T is a node without any children. Suppose that there is a path from node n 1 to node n 2 . We say that n 2 is a descendant of n 1 , whereas n 1 is an ancestor of n 2 . Note that every node is both a descendant and an ancestor of itself. If n 1 = n 2 , then n 2 is a proper descendant of n 1 , which in turn is a proper ancestor of n 2 . We say that the tree T ′ is a subtree of the tree

T if V (T ′ ) ⊆ V (T ) and E (T ′ ) ⊆ E (T ). If T ′ also contains the root of T , then it is an r-subtree of T .
An XML document (a document for short) is a tree with a label attached to each node. We do not distinguish here between a tag and a value. Our notion of a label is meant to capture both. Usually, we use d to denote documents, and u, v and w to denote nodes of documents. The label of a node v is denoted by lbl (v). As an example, Figure 2.1 (bottom-right) depicts a document d. Each node is represented as [i]l, where i is a unique identifier and l is a label. For instance, the label of Node 19 is "manager" while that of Node 14 is "Emma." In the figures, labels corresponding to values (rather than tags) are in italic font.

Two documents d 1 and d 2 are isomorphic, denoted by d 1 ∼ d 2 , if one can be obtained from the other by replacing nodes with some other nodes while preserving labels (but not identifiers). Formally,

d 1 ∼ d 2 if there is a bijection ϕ : V (d 1 ) → V (d 2 ), such that (1) for all v ∈ V (d 1 ) it holds that lbl (v) = lbl (ϕ(v)), and (2) for all v 1 , v 2 ∈ V (d 1 ) we have that (v 1 , v 2 ) ∈ E (d 1 ) if and only if (ϕ(v 1 ), ϕ(v 2 )) ∈ E (d 2 ).

Probabilistic XML and p-Documents

A probabilistic XML space (abbr. px-space) is a probability distribution over a space of ordinary documents. Formally, it is a pair (D, p), where D is a nonempty, finite set of documents and p : D → R + maps every document d ∈ D to a positive real number p(d), such that d∈D p(d) = 1. ind [START_REF] Senellart | Comprendre le Web caché. Understanding the Hidden Web[END_REF]departments [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF]John [START_REF]W3C: XML Path language (XPath)[END_REF]manager [START_REF] Li | PEPX: a query-friendly probabilistic XML database[END_REF]dept.

[18]dept.

[17]L [START_REF] Green | Models for incomplete and probabilistic information[END_REF]size [START_REF] Dalvi | Management of probabilistic data: foundations and challenges[END_REF]manager [START_REF] Senellart | On the complexity of managing probabilistic XML data[END_REF]division [START_REF] Li | PEPX: a query-friendly probabilistic XML database[END_REF]dept.

[3]sales [START_REF]W3C: XQuery Update facility[END_REF]L [START_REF] Koch | MayBMS: A system for managing large uncertain and probabilistic databases[END_REF]Emma ind ind [START_REF] Senellart | Comprendre le Web caché. Understanding the Hidden Web[END_REF]departments

[18]dept.

[2]division [START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF]company [START_REF] Li | PEPX: a query-friendly probabilistic XML database[END_REF]dept. mux [START_REF] Imielinski | Incomplete information in relational databases[END_REF]Mary [START_REF]W3C: XML Path language (XPath)[END_REF]manager [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF]L [START_REF] Green | Models for incomplete and probabilistic information[END_REF]size mux [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF]John [START_REF] Dalvi | Management of probabilistic data: foundations and challenges[END_REF]manager [START_REF] Koch | MayBMS: A system for managing large uncertain and probabilistic databases[END_REF]Emma [START_REF] Koch | MayBMS: A system for managing large uncertain and probabilistic databases[END_REF]Emma [START_REF]W3C: XQuery Update facility[END_REF]L [START_REF] Green | Models for incomplete and probabilistic information[END_REF]size [START_REF] Dalvi | Management of probabilistic data: foundations and challenges[END_REF]manager [START_REF] Cohen | Incorporating constraints in probabilistic XML[END_REF]Emma Typically, a px-space contains a large number of documents, so it is usually impractical to use its explicit representation (i.e., D and p). In this section, we show how to represent a px-space by means of a p-document, which is (a description of) a probabilistic process that generates a random document; that is, this process generates a document d ∈ D with probability p(d).

Formally, a p-document is a tree P that consists of two types of nodes. Ordinary nodes have labels (namely, they are regular XML nodes), and they may appear in documents. Distributional nodes are only used for defining the probabilistic process that generates random documents (but they do not actually occur in those documents). We denote by V ord ( P) and V dst ( P) the disjoint sets of ordinary and distributional nodes of P, respectively. The root and leaves of P are required to be ordinary nodes.

⊓ ⊔

In Section 4, we define several types of distributional nodes. For now, it is sufficient to realize that each distributional node v has a probability distribution over (subsets of) its children. In the probabilistic process that generates a random document, a subset of the children of v is randomly chosen according to the distribution specified for v.

The Probabilistic Process of a p-Document

A random document of a p-document P is generated in two steps. In the first step, one subset of children is randomly chosen for each distributional node. Note that choices made for different nodes could be dependent. All the unchosen children and their descendants (even descendants that have been chosen by their own parents) are deleted. The result is an r-subtree s of P.

The second step removes all the distributional nodes. If an ordinary node u no longer has a parent, then the new parent of u is the lowest node that is both ordinary and a proper ancestor of u. The resulting document is ordinary and denoted by doc(s).

In terms of formal probability theory, a p-document defines the probability space that comprises the documents obtained by all the combinations of choosing for each distributional node, a subset of its children (and then removing distributional nodes, as described above). As explained in Section 4, the probability of each combination depends on the types of the distributional nodes and the probability distributions specified for those nodes (moreover, it also depends on the probabilistic dependencies that exist among those nodes).

The above pair of steps for generating a random document can be described by two random variables as follows. Let Σ( P) denote the set of all the r-subtrees s of P, such that every ordinary node u of s has the same set of children in both s and P. The first step above chooses an r-subtree s ∈ Σ( P), and we use the random variable P Σ to denote that choice (i.e., s). The second step generates the document doc(P Σ ), and this document is denoted3 by the random variable P. Note that P is deterministically determined by P Σ .

Note that the operation doc(•) is not necessarily oneto-one; that is, two different r-subtrees s 1 and s 2 may yield the same document. This follows from two facts: A distributional node can have a distributional child, and an empty subset of children might be selected for a distributional node.

Let s ∈ Σ( P) be given. Pr(P Σ = s) is the probability that each distributional node of s chooses the exact set of children that it has in s. Thus, the probability of a random document d is given by

Pr (P = d) = s∈Σ( P), doc(s)=d Pr P Σ = s .
Note that Pr(P = d) could be 0. In particular, the above equation implies that Pr(P = d) = 0 if d cannot be obtained from P, that is, there is no s ∈ Σ( P) such that Pr(P Σ = s) > 0 and d = doc(s). For example, if d has a node that does not appear in P, then Pr(P = d) = 0.

⊓ ⊔

The possible worlds of a p-document P are all the documents with a nonzero probability, i.e., documents d, such that Pr (P = d) > 0. We use pwd ( P) to denote the set of all the possible worlds. Clearly, d∈pwd(d)

Pr (P = d) = 1 .
To conclude, a p-document P defines the px-space (D, p), where D is the set pwd ( P) and p is the function Pr(P = •). We use P to denote this px-space.

Isomorphism and Equivalence

Two px-spaces (D 1 , p 1 ) and (D 2 , p 2 ) are isomorphic, denoted by (D 1 , p 1 ) ∼ (D 2 , p 2 ), if they are identical up to isomorphism, that is, for all documents d,

d ′ ∈D1|d ′ ∼d p 1 (d ′ ) = d ′ ∈D2|d ′ ∼d p 2 (d ′ ) .
In words, for all documents d, the probability that a document of (D 1 , p 1 ) is isomorphic to d is equal to the probability that a document of (D 2 , p 2 ) is isomorphic to d.

Two p-documents are equivalent if they define the same px-space. There are two variants of equivalence depending on whether two px-spaces are deemed the same based on equality or isomorphism. The first notion of equivalence follows the object-based semantics, whereas the second uses the value-based semantics.

Types of Distributional Nodes

To obtain a concrete p-document, we should specify for each distributional node v, the probability distribution of choosing a subset of the children of v. We define five types of distributional nodes, each with a different way of describing that probability distribution.

Type ind (for independent ). A node v of type ind specifies for every child w, the probability p v (w) of choosing w; this choice is independent of any other choice of children (of either v or other distributional nodes). Hence, the probability of choosing a subset C of children of v is

w∈C p v (w) w∈ C(1 -p v (w)) ,
where C is the set of children of v that are not in C.

Type mux (for mutually exclusive). A node v of type mux specifies the probabilities p v (w 1 ), . . . , p v (w k ) for its children w 1 , . . . , w k , respectively. Node v chooses at most one child w i with the probability p v (w i ), independently of the other distributional nodes. We require that k i=1 p v (w i ) ≤ 1. The probability that v chooses none of its children is 1 -

k i=1 p v (w i ).
Type det (for deterministic). A node v of type det always chooses all of its children, namely, each child is chosen with probability 1.

Type exp (for explicit ). A node v of type exp specifies probabilities p v (W 1 ), . . . , p v (W l ), where the W i are some (but not necessarily all of the) distinct subsets of the children of v. Node v chooses exactly one subset W i with the probability p v (W i ), independently of the other distributional nodes. Note that one of the W i may be empty. We require that l i=1 p v (W i ) = 1. Type cie (for conjunction of independent events). In a given p-document, nodes of this type are associated with independent random Boolean variables e 1 , . . . , e m , called events. For each event e i , the p-document specifies the probability p(e i ) that e i is true. A node v of type cie specifies for every child w, a conjunction

α v (w) = a 1 ∧ • • • ∧ a kw (k w > 0)
, where each a j is either e i or ¬e i for some 1 ≤ i ≤ m. Note that different conjunctions can share common events, and the number of events in α v (w) (i.e., k w ) may vary from one child of v to another. Before generating a document, values for e 1 , . . . , e m are randomly determined. A child w is chosen if its corresponding conjunction α v (w) is true.

Note that if the type of a distributional node v is one of the first four (i.e., ind, mux, det or exp), then v randomly picks children independently of the probabilistic choices made by the other distributional nodes of the p-document. But different distributional nodes of type cie can correlate their choices by sharing events.

Example 4.1 The p-document P of Figure 2.1 has ind and mux nodes. The probability specified for each child is shown next to the edge that leads to that child. We now describe how to compute the probability Pr(S = s) of the document s ∈ Σ( P) that is shown in the bottomleft part of Figure 2.1. Each mux node of s chooses exactly one child with the probability specified for that child. The probabilities of the choices made by the ind nodes are as follows. Node 9 chooses its only child with probability 0.8. Node 10 chooses both children with probability 0.7 • 0.65 = 0.455. And Node 23 chooses the empty set of children with probability 1 -0.8 = 0.2. Pr(S = s) is the product of the probabilities of the choices made by all the distributional nodes.

⊓ ⊔

A node v of a p-document is useless if there is no r-subtree s of P, such that Pr P Σ = s > 0 and v appears in s. One can efficiently find all the useless nodes of a p-document and delete them (as well as their descendants). If, as a result, a distributional node has no ordinary descendants, then it is also removed. In practice, it is not necessary to remove useless nodes; however, we assume that p-documents do not have useless nodes, because it is needed in some of the proofs.

We denote by PrXML {type 1 ,type 2 ,...} the family of all the p-documents, such that the types of their distributional nodes are among those listed in the superscript. For example, the p-documents of PrXML {ind,mux} use only ind and mux nodes.

In the following, our complexity analysis makes an implicit assumption that numbers (e.g., probabilities of the form p v (w i ) or p(e i ) specified in p-documents) are represented in a way that the basic arithmetic operations (e.g., computing the product or sum of a series of numbers) can be performed efficiently.

Hierarchy of Distributional Nodes

The straightforward way of using a distributional node is when both its parent and children are ordinary nodes. In this case, the role of the distributional node is to choose ordinary children for its ordinary parent. Sometimes, however, we can obtain more complex distributions (over the probability space of documents) by constructing hierarchies of distributional nodes.

If every distributional node of a p-document P has only ordinary children, we say that P is distributionalhierarchy free (abbr. DHF). As an example, consider Figure 2.1. The p-document P is not DHF, because Node 10 is the child of Node 9 and both are distributional nodes. If F is a set of p-documents, then F | h denotes the restriction of F to its DHF p-documents.

In Section 5, we show that in some families of pdocuments, we can express more px-spaces by allowing hierarchies of distributional nodes.

Previously Studied Models

The family PrXML {ind,mux} is the same as the ProTDB documents of [START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF]. The probabilistic XML model5 of [START_REF] Van Keulen | A probabilistic XML approach to data integration[END_REF] is a subset of PrXML {mux,det} , where mux nodes (called "probability nodes") have as children only det nodes (called "possibility nodes") and det nodes have only ordinary children (called "XML nodes").

The model of probabilistic XML that was investigated in [START_REF] Senellart | On the complexity of managing probabilistic XML data[END_REF][START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF] (hierarchies make a difference in this case). The same is true for the probabilistic XML model underlying the "PEPX" system [START_REF] Li | PEPX: a query-friendly probabilistic XML database[END_REF].

The work of [START_REF] Hung | PXML: A probabilistic semistructured data model and algebra[END_REF] introduced a model of probabilistic XML graphs, where each node explicitly specifies the probability distribution over its possible sets of children. Restricting their XML graphs to trees yields a sub-family of PrXML {exp} | h (a lack of hierarchies is significant when only exp nodes are allowed). The same is true for [START_REF] Hung | Probabilistic interval XML[END_REF] if we restrict their intervals to points.

With respect to probabilistic relational models [START_REF] Dalvi | Management of probabilistic data: foundations and challenges[END_REF][START_REF] Widom | Trio: A system for integrated management of data, accuracy, and lineage[END_REF][START_REF] Koch | MayBMS: A system for managing large uncertain and probabilistic databases[END_REF], the comparison is more delicate because there has been a lot of research in this direction, some of it not relevant here. (In particular, a large part deals with query processing or the origins of imprecision.) From a modeling viewpoint, one can easily represent a relation as an XML tree with a node for each tuple and a node for each entry in a tuple. Distributional nodes can then be used to specify probabilities on tuples and on values inside tuples. For the relational model, the notion of probabilistic possible worlds has also been used and many representation systems have been proposed. The block-independent model of [START_REF] Dalvi | Management of probabilistic data: foundations and challenges[END_REF] (which is an incomplete representation system) can be translated into the family PrXML {ind,mux} in a straightforward way. Other probabilistic relational models (in particular, [START_REF] Widom | Trio: A system for integrated management of data, accuracy, and lineage[END_REF]) can be seen as probabilistic versions of the conditional tables of [START_REF] Imielinski | Incomplete information in relational databases[END_REF]. (In that direction, one most elaborate work is that of [START_REF] Green | Models for incomplete and probabilistic information[END_REF].) In some sense, the PrXML {cie} model generalizes this idea to trees, and the main features of corresponding probabilistic relational models can accordingly be represented in this probabilistic XML model. For instance, the lineage of Trio [START_REF] Widom | Trio: A system for integrated management of data, accuracy, and lineage[END_REF] can naturally be encoded as independent events. 6 A general study of the translation of existing probabilistic relational models into probabilistic XML models is an interesting issue, but beyond the scope of this paper.

Translations Between Families of P-Documents

The previous section described several families of pdocuments. In this section, we compare the expressive power of these families. We first formalize the notion of expressive power.

Translators

Consider two (infinite) sets F 1 and F 2 of p-documents. We say that

F 1 is o-translatable to F 2 , denoted by F 1 ⊑ o F 2 , if each document of F 1 is o-equivalent to some document of F 2 . That is, for each document P1 ∈ F 1 , there exists a document P2 ∈ F 2 , such that P1 ≡ o P2 . An o-translator from F 1 to F 2 is
an algorithm that receives as input a P1 ∈ F 1 and generates an o-equivalent P2 ∈ F 2 . If there is an efficient o-translator from F 1 to F 2 (i.e., a translator that runs in polynomial time in the size of its input P1 ), then F 1 is efficiently o-translatable to F 2 , denoted by

F 1 ⊑ poly o F 2 . If F 1 ⊑ o F 2 and F 2 ⊑ o F 1 , then we write F 1 ≡ o F 2 . Similarly, F 1 ≡ poly o F 2 means
that there are efficient o-translators in both directions.

We use analogous definitions and notation for the notion of v-translation. As an example, F 1 ⊑ poly v F 2 means that there is an efficient v-translator that receives as input a P1 ∈ F 1 and generates a P2 ∈ F 2 , such that P1 ≡ v P2 .

The Types ind, mux and det

In this section, we consider the three types ind, mux and det. We first study the families that use only one of these three types.

Using Each Type Individually

Using only distributional nodes of type det is, obviously, meaningless in the sense that the resulting pdocument is deterministic. Formally, the px-space defined by a p-document P of the family PrXML {det} consists of only one document, namely, doc( P). Consequently, PrXML {det} ≡ poly o PrXML {} , which means that the family PrXML {det} is trivially o-translatable to any other family (among those we consider).

Next, we show that hierarchy is not required in the family PrXML {mux} . by repeatedly eliminating each distributional node u that has a distributional parent, until there is no such node (and, thus, the p-document is DHF). The elimination process is the following. Consider two distributional nodes u and v of P, such that v is the parent of u (and, of course, both u and v are of type mux). Let w 1 , . . . , w k be the children of u. We remove u from P and connect every w i to v (i.e., w i becomes a child of v). For all 1 ≤ i ≤ k, the probability

p v (w i ) is set to p v (u) • p u (w i ).
Observe that each step of the elimination process preserves o-equivalence; hence, this transformation is correct.

⊓ ⊔ Unlike PrXML {mux} , hierarchy is essential in the family PrXML {ind} . In particular, the following lemma shows that PrXML {ind} is not v-translatable (and, hence, not o-translatable) to PrXML

{ind} | h (regardless of efficiency). Lemma 5.2 PrXML {ind} ⊑ v PrXML {ind} | h .
Proof Let P denote the p-document of PrXML {ind} that is depicted in Figure 5.1(a). Note that the ordinary nodes w 1 and w 2 of P are labeled with a and b, respectively. We will prove that there is no DHF p-document of PrXML {ind} | h that is v-equivalent to P. Suppose, by way of contradiction, that P′ is such a p-document. Observe that none of the probabilities specified in P′ is zero, because there are no useless nodes. Therefore, P′ has a possible world that includes all of its ordinary nodes. Consequently, the assumption P′ ≡ v P implies that P′ must have the following three properties. First, the root of P′ has exactly two ordinary descendants. Second, one of these two nodes, denoted by u a , is labeled with a and the other, denoted by u b , is labeled with b. Third, neither one of u a and u b is an ancestor of the other (because some possible world of P contains both w 1 and w 2 as siblings). Note that each of u a and u b is either a child or a grandchild of the root, because P′ is DHF. It follows that the probabilistic events "P ′ includes the label a" and "P ′ includes the label b" are independent. However, this is not the case for P, because the probability that P includes both a and b is 0.5 3 whereas the probabilities of the events "P includes a" and "P includes b" are both 0.5 2 . This contradicts the v-equivalence of P and P′ .

⊓ ⊔

Next, we consider the relationships between families that use different types of distributional nodes. The first lemma below gives a negative result, namely, p-documents with only mux nodes and no hierarchies are not v-translatable to p-documents that use only ind nodes. The second lemma states a positive result for the opposite direction; that is, p-documents with only ind nodes and no hierarchies are efficiently o-translatable (and v-translatable) to p-documents that use only mux nodes. Each v i is a child of u and the parent of

Lemma 5.3 PrXML

w i . For 1 ≤ i ≤ k, we define p vi (w i ) = p v (w i ). ⊓ ⊔
The following lemma shows that the previous result no longer holds if we allow hierarchies of ind nodes; furthermore, PrXML {ind} is not even v-translatable to PrXML {mux} .

Lemma 5.5 PrXML {ind} ⊑ v PrXML {mux} .
Proof Recall the proof of Lemma 5.2 and, in particular, consider again the p-document P (which is depicted in Figure 5.1(a)). To derive a contradiction, we use Lemma 5.1 and assume that PrXML The root r of P′ cannot have ordinary children, because there is a possible world of P that consists of a single node. Hence, all the children of r are mux nodes and each of them has only ordinary children (because P′ is DHF).

The same label (i.e., either a or b) cannot appear under two distinct mux children of r, or else some possible world of P′ contains more than one occurrence of that label. Let u a and u b be the mux nodes of P′ that have, among their children, all the nodes with the labels a and b, respectively. If u a and u b are distinct, then the probabilistic events "P ′ includes the label a" and "P ′ includes the label b" are independent. Hence, as in the proof of Lemma 5.2, this contradicts the assumption that P ≡ v P′ . If u a = u b , then no possible world of P′ contains both a and b which, again, contradicts P ≡ v P′ .

⊓ ⊔

The following theorem summarizes this section.

Theorem 5.6 The following hold.

Combinations of the Types ind, mux and det

We now consider the families that use at least two of the types ind, mux and det. Observe that the type det is a special case of ind (i.e., each child is chosen with probability 1). Therefore, adding the type det does not change the expressive power of a family that is allowed to use ind nodes. In particular, PrXML {ind,mux} ≡ poly o PrXML {ind,mux,det} . (Recall that PrXML {ind,mux} is the same as the ProTDB model [START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF].)

We first show that under the value-based semantics, the family P ∈ PrXML {mux,det} can represent every pxspace consisting of documents that have the same label in their roots. Formally, a px-space (D, p) is root consistent if for every two documents PrXML {ind,mux} is trivial, because a det node is a special case of an ind node (i.e., every child is chosen with probability 1). For the other direction, PrXML {ind,mux} ⊑ poly o PrXML {mux,det} , let P be a p-document of PrXML {ind,mux} . We efficiently transform P into a p-document of PrXML {mux,det} while preserving o-equivalence as described next. Consider an ind node v of P, and let w 1 , . . . , w k be the children of v. We replace v and its children with the subtree shown in Figure 5.3. That is, v is replaced with a new det node v ′ that has k new mux nodes u 1 , . . . , u k as children. For each u i , the node w i is the only child of u i and it is chosen with probability p v (w i ).

d 1 , d 2 ∈ D, it holds that lbl (root(d 1 )) = lbl (root(d 2 )). • • • • • • • • • u mux det wn,1 w 1,k 1 det w1,
⊓ ⊔ Now, we consider the need for hierarchies of distributional nodes when combining two or more of the three types ind, mux and det. Note that PrXML

{ind,det} | h ≡ poly o PrXML {ind} | h
, so this case has been studied in the previous section. Also observe that PrXML . The following lemma shows that in pdocuments without hierarchies of distributional nodes, ind is not needed if mux is used. , is trivially true.

{ind,mux,det} | h ≡ poly o det • • • w3 w2 w1 • • • w1 w2 w3 w k mux mux mux mux • • • ind v v ′ w k

⊓ ⊔

The following theorem is an immediate corollary of Lemmas 5.5, 5.8 and 5.9.

Theorem 5.10 The following hold.

1. PrXML {ind,mux,det} ≡ poly o PrXML {ind,mux} ≡ poly o ≡ poly o PrXML {mux,det} ⊑ v PrXML {mux} . 2. PrXML {ind,mux,det} | h ≡ poly o PrXML {mux} | h .
In the remainder of this section, we omit the specification of the type det in a family that uses the type ind, because the first can be thought of as a special case of the second.

The Type exp

We now consider the family PrXML {exp} . Observe that the type mux is a special case of exp; that is, a mux node chooses with nonzero probability only singletons and possibly the empty set. Similarly, a node of type det is an exp node that chooses the set of all of its children with probability 1. In the proof of Lemma 5.8, we showed how an ind node is emulated by mux and det nodes. Thus, we get the following result, which implies that PrXML {exp} generalizes PrXML {ind,mux} . As shown later in Lemma 5.14, this generalization is strict, namely, there is no o-translation from PrXML {exp} (or even PrXML Next, we consider the need for hierarchies of distributional nodes in PrXML {exp} . The following theorem shows that one can always eliminate hierarchies from a p-document of PrXML {exp} (while preserving o-and v-equivalence), but it may cause an exponential blowup even if all the exp nodes actually emulate ind nodes. A particular consequence is that the models of [START_REF] Hung | PXML: A probabilistic semistructured data model and algebra[END_REF][START_REF] Hung | Probabilistic interval XML[END_REF], restricted to trees with point probabilities, are not as general as PrXML {exp} . This theorem also shows that if a p-document of PrXML {ind,mux,exp} is DHF, then it can be efficiently o-translated to a p-document of PrXML {exp} without an exponential blowup (c) A p-document that cannot be o-translated to PrXML {cie} without introducing hierarchies of distributional nodes (note that the construction in the proof of Lemma 5.11 does not have this property).

Theorem 5.12 The following hold. , and that can be done by repeatedly applying the following transformation to a P ∈ PrXML {exp} . Consider an ordinary node u of P that has some exp children as well as exp grandchildren. Let T (u) be the maximal subtree of P, such that the root is u, all the interior nodes are distributional and all the leaves are ordinary. We replace T (u) with T ′ (u), as shown in Figure 5.4(a). That is, we remove all the interior nodes of T (u), add a new exp node v as the only child of u, and each leaf of T (u) becomes a child of v.

For each subset W of the children of v, we define

p v (W ) = Pr(W is the set of children of u in P | u ∈ V (P)).
Observe that the above translation is, in general, inefficient, since exponentially many probabilities are computed (i.e., for each of the subsets of the children of u).

For Part 2, the proof of Lemma 5.4 shows how, in a DHF p-document, we can transform an ind node to several mux nodes without creating a hierarchy, and a mux node is a special case of an exp node.

To prove Part 3, consider the p-document P ∈ PrXML {ind} of Figure 5.4(b). Nodes v and u of P choose each of their children with probability 1/2. The ordinary nodes w 1 , . . . , w n have n distinct labels l 1 , . . . , l n , respectively.

Suppose that some P′ ∈ PrXML

{exp} | h
satisfies P′ ≡ v P. The children of root( P′ ) are exp nodes and the grandchildren are ordinary nodes, because some possible world of P comprises just the root r. Each child of an exp node belongs to some subset with nonzero probability, because there are no useless nodes.

If children of distinct exp nodes have the same label l i , then there is a document d ∈ pwd ( P′ ) that has two occurrences of l i , which cannot happen in any document of pwd ( P), in contradiction to P′ ≡ v P. Therefore, each label occurs under exactly one exp child of root( P′ ). Now, suppose that the labels l i and l j (i = j) occur below two distinct exp nodes of P′ . Hence, the probabilistic events "P ′ includes the label l i " and "P ′ includes the label l j " are independent. However, this is not the case in documents of pwd ( P), because if l i appears in a document d ∈ pwd ( P), it means that node u of P has been chosen, and therefore, the probability that l j also appears in d is 1/2 and not 1/4. Consequently, P′ has only one exp node.

Since every subset of the labels occurs in some possible world of P, it follows that 2 n probabilities are specified by the exp node of P′ . Therefore, the size of this specification is exponential in the size of P.

Part 4 follows from Part 3 and Lemma 5.11. ⊓ ⊔

The Type cie

We now discuss the expressive power of PrXML {cie} . The following theorem proves that this family generalizes PrXML {ind,mux} ; a later result in this section shows that the generalization is strict. Moreover, hierarchies of distributional nodes are not needed in PrXML {cie} . Proof We transform a p-document P of the family PrXML {ind,mux,cie} to a document of PrXML {cie} as follows. We consider every node v of P, such that the type of v is either ind or mux; let w 1 , . . . , w k be the children of v. First, we change the type of v to cie and introduce k new events e 1 , . . . , e k . If v is an ind node, then for all 1 ≤ i ≤ k, we define p(e i ) = p v (w i ) and α v (w i ) = e i . If v is a mux node, then no w i satisfies p v (w i ) = 0, because there are no useless nodes, and so we do the following. For all 1

≤ i ≤ k, we define α v (w i ) = e i ∧ ¬e i-1 ∧ • • • ∧ ¬e 1 and specify the probabilities p(e 1 ) = p v (w 1 ), p(e 2 ) = p v (w 2 )/(1 -p v (w 1 )) and, in general, p(e i ) = p v (w i ) • i-1 j=1 (1 -p(e j )) -1 .
Hence, the probability that α v (w i ) is true is p v (w i ). To show that the probabilities are well defined, we prove that p(e i ) < 1 for 1 ≤ i < k. (We also have to show that p(e k ) ≤ 1 and this is proved similarly.) Suppose otherwise and consider the smallest l, such that p(e l ) ≥ 1 or equivalently

p v (w l ) ≥ l-1 j=1 (1- p(e j )). 1 -l-1 j=1 (1 -p(e j ))
is the probability that at least one of the events e 1 , . . . , e l-1 is true or, equivalently, exactly one of α v (w 1 ), . . . , α v (w l-1 ) is true. The α v (w i ) are disjoint events and therefore 1 -

l-1 j=1 (1 - p(e j )) = l-1 j=1 p v (w j ). Since we assumed that p v (w l ) ≥ l-1 j=1 (1 -p(e j )), it follows that l j=1 p v (w j ) ≥ 1, in contradiction to p v (w l+1 ) > 0.
We showed that PrXML {ind,mux,cie} ⊑ poly o PrXML {cie} . For proving PrXML {cie} ⊑ poly o PrXML {cie} | h , we use the following transformation. If u is a cie node that has a cie child v, then we remove v, connect each child w i of v directly to u and define α u (w i ) = α u (v) ∧ α v (w i ). ⊓ ⊔ By Proposition 5.7 and Theorem 5.13, every family of p-documents is v-translatable to PrXML {cie} . However, this particular translation creates a p-document that is linear in the combined size of all the possible worlds. So, when this v-translation is from PrXML {exp} , it involves an exponential blowup. Whether PrXML {exp} can be efficiently v-translated to PrXML {cie} is an open problem. In any case, the following lemma shows that under the object-based semantics, PrXML {cie} does not even generalize PrXML , such that no P in PrXML {cie} satisfies P′ ≡ o P. The existence of P′ is a consequence of the following inequality that holds for all p-documents P ∈ PrXML {cie} and all ordinary nodes w 1 and w 2 of P, such that w 1 and w 2 appear together in at least one document d of pwd ( P).

Pr (w 1 , w 2 ∈ V (P))

≥ Pr (w 1 ∈ V (P)) • Pr (w 2 ∈ V (P)) (5.1)
That is, the probability that both nodes exist in a possible world is at least as high as the product of the probabilities that each one exists. Clearly, there is a pdocument in PrXML

{exp} | h
that violates this inequality, e.g., the one depicted in Figure 5.4(c). We prove the above inequality by showing how to calculate the probability of the event "a possible world of P contains a set of ordinary nodes U ."

Let U be a set of ordinary nodes of P, such that all the nodes of U appear together in at least one document of pwd ( P). Consider the minimal r-subtree p(U ) of P that contains all the nodes of U . Let A(U ) be the set of all the literals (i.e., events or negated events) that appear in the conjunctions α v (w), where w is a node of p(U ). A(U ) does not contain both an event e and its negation ¬e, because pwd ( P) has a document that contains all the nodes of U . Therefore, the probability that all the nodes of U appear in a random document is the product of the probabilities that the literals of A(U ) are true. Hence, the inequality follows because

A({w 1 , w 2 }) = A({w 1 }) ∪ A({w 2 }). ⊓ ⊔
We now discuss whether PrXML {exp} generalizes the family PrXML {cie} . Proposition 5.7 and the first part of Theorem 5.12 imply that PrXML {cie} is v-translatable to PrXML Proof We use the same proof for both parts. For all n > 2, let Pn be the p-document of PrXML {cie} depicted in Figure 5.5. Pn has 2n + 3 ordinary nodes and n events e 1 , . . . , e n , each with probability 1/2. The root r has two ordinary children labeled with a and a ′ . In addition, each of the two nodes labeled with a and a ′ has n ordinary grandchildren labeled with a 1 , . . . , a n and a ′ 1 , . . . , a ′ n , respectively. Note that if the event e i is true, then the two nodes labeled with a i and a ′ i are chosen; conversely, if e i is false, then none of these two nodes is chosen.

• • • • • • an a ′ 1 a ′ n a a ′
For n > 2, let P′ n be a minimal p-document of PrXML {ind,mux,exp} , such that P′ n ≡ v Pn . We will show that P′ n has at least 2 n ordinary nodes, thereby proving that PrXML {cie} is neither efficiently v-translatable nor o-translatable to the family PrXML {ind,mux,exp} .

First, we show that all the distributional nodes of P′ n appear in a hierarchy immediately below the root. That is, no distributional node is a descendant of an ordinary node that is labeled with either a or a ′ . Suppose that this is not so. Namely, there is a distributional node v that is a descendant of an ordinary node u that is labeled with a (the symmetric case where u is labeled with a ′ is handled similarly).

If in all the possible worlds that contain u, the set of labels appearing in the children of u is the same, then v (possibly with some other nodes) can be eliminated while preserving v-equivalence, contradicting the assumption that P′ n is minimal. (Note that this argument includes the case where no possible world contains u.) Hence, there is a label a j and two possible worlds d 1 and d 2 , such that the following holds. Both d 1 and d 2 contain u, but only in d 1 does the label a j appear among the children of u.

Every possible world of Pn that includes the label also has the label a ′ j . Hence, d 1 has a node u ′ j that is labeled with a ′ j . It follows that in P′ n , the least common ancestor of u and u ′ j must be a proper ancestor of u, because Pn has no node labeled with a ′ j that appears as a descendant of a node labeled with a.

Let s 1 and s 2 be two r-subtrees of P′ n such that doc(s 1 ) = d 1 and doc(s 2 ) = d 2 . We construct an rsubtree s of P′ n as follows. Distributional nodes that are not descendants of u choose children as in s 1 , whereas the descendants of u choose their children as in s 2 . Note that distinct distributional nodes of P′ n choose their children independently of one another, because none of them is of type cie. Hence, the resulting random document d = doc(s) has a nonzero probability. Clearly, d has the label a ′ j but not the label a j , contradicting P′ n ≡ v Pn . This contradiction proves that all the distributional nodes of P′ n appear above all the nodes labeled with either a or a ′ , that is, in a hierarchy immediately below the root. It thus follows that for all possible worlds d of . By Theorem 5.13, this family is at least as general as the family PrXML {ind,mux,cie} . However, the following theorem shows that it does not generalize PrXML {exp} (under the object-based semantics). Since the o-translator ϕ is efficient, we can choose a fixed value for n so that the following holds. For all exp nodes v of the p-document ϕ( Pn ), the number of subsets in the specification of v is smaller than 2 n .

Observe that the root of ϕ( Pn ) has only distributional nodes as children, because there is a possible world of Pn that comprises just the root. Since ϕ( Pn ) is DHF, every one of these distributional nodes has only ordinary children. All these children are leaves, because random documents of Pn have a height of at most one, ϕ( Pn ) has no useless nodes, and a distributional node cannot be a leaf.

If a random document d of Pn includes w i , then the probability that it also includes w j (i = j) is 0.5. But the prior probability of including w j is just (0.4 + 0.05)• 0.5 2 = 0.1125. Therefore, the random variable P n has the following property. For all 1 ≤ i < j ≤ n, the two events "P n includes node w i " and "P n includes node w j " are probabilistically dependent. By symmetry, a similar property holds for all u i and u j (i = j).

Yet another similar property of P n is the following. For all 1 ≤ i, j ≤ n, the two events "P n includes node w i " and "P n includes node u j " are probabilistically dependent. To see why, observe that the existence of w i in P n decreases the probability of the event 7 "P n includes node u j ," because it forces node v of Pn to choose both w and u (with the low probability 0.05) in order for u j to be in P n . Now, suppose that the root r of ϕ( Pn ) has a child y of type exp. If r has a second child y ′ , then an ordinary descendant of y and an ordinary descendant of y ′ are probabilistically independent, in contradiction to the above properties of Pn . Hence, y is the only child of r. Note that for all subsets S of {w 1 , . . . , w n } ∪ {u 1 , . . . , u n }, there is a possible world of Pn with S as the set of leaves. Therefore, the specification of y must include 2 2n subsets, which contradicts our choice of n.

It thus follows that ϕ( Pn ) does not contain exp nodes and, therefore, is in PrXML {cie} . Recall that the proof of Lemma 5.14 shows that Equation (5.1) holds for all p-documents P of PrXML {cie} . We now derive a contradiction by showing that the following inequality holds (note that some possible world of Pn includes both w 1 and u 1 ).

Pr (w 1 , u 1 ∈ V (P n )) < < Pr (w 1 ∈ V (P n )) • Pr (u 1 ∈ V (P n ))
The left side is 0.05 • 0.5 3 = 0.00625. Each multiplicand on the right side is (0.4 + 0.05) • 0.5 2 , so their product is 0.01265625. ⊓ ⊔ 7 An exact calculation shows that the prior and posterior probabilities of this event are 0.1125 and 1/18, respectively.

It is not known whether PrXML {exp} is efficiently v-translatable to PrXML {exp,cie} | h .

Overview

Figure 5.7 shows the efficient o-translations that exist between the families of p-documents that have been discussed in this section. This figure is complete in the sense that if there is no directed path from a family F 1 to F 2 , then there is no efficient o-translator from F 1 to F 2 . As shown in Figure 5.7, the family PrXML {exp,cie} is the most general, and the families PrXML Recall that an o-translation is also a v-translation. In addition, we have shown that every family F of p-documents is v-translatable to PrXML {mux,det} and, hence, also to PrXML {exp} and PrXML {cie} . However, the family PrXML {cie} is not efficiently v-translatable to PrXML {mux,det} , or even to PrXML {ind,mux,exp} ; namely, such a v-translation causes an exponential blowup.

We also considered the need for hierarchies of distributional nodes. We showed that such hierarchies are not required in the case of either PrXML {cie} or PrXML {mux} . However, for the families PrXML {ind} , PrXML {ind,mux} , PrXML {mux,det} and PrXML {exp} , these hierarchies properly increase the expressive power, in the sense that there are no efficient v-or o-translations that can eliminate them (note that in some of these cases, there are no translations regardless of efficiency). In the case of PrXML {exp,cie} , we only proved that there is no efficient o-translation that eliminates hierarchies (and for v-translation, it is open).

For the families of p-documents considered thus far, the results of this section determine for every pair F 1 and F 2 whether or not there is an efficient o-translation from F 1 to F 2 . When there is no efficient o-translation, then it is often the case that there is no efficient vtranslation as well (although an inefficient v-translation usually exists). However, in some cases, the existence of an efficient v-translation is left as an open problem. The main unsolved question is whether the family PrXML {exp} (or even PrXML ) can be efficiently v-translated to PrXML {mux,det} , or even to PrXML {cie} . In the next section, we partially solve this problem by showing the existence of an efficient v-translation (but no o-translations) from PrXML {exp} to PrXML {mux,det} under the assumption of a fixed upper bound on the out-degree of exp nodes (or on the maximal number of distributional nodes on any path from the root to a leaf).

Distributional Nodes with Bounded Degrees

In this section, we restrict families of p-documents by imposing a bound on the number of children that a distributional node may have. We study the effect of this bound on the expressive power. The combination of this restriction with a lack of distributional hierarchies is beyond the scope of this paper.

Let F be a family of p-documents and b ≥ 2 be an integer. We denote by F ∆≤b the subset of F that comprises all the p-documents P, such that each distributional node v ∈ V dst ( P) has b or fewer children. For example, in a p-document P of PrXML {exp} ∆≤2 , every distributional node is of type exp and has either one or two children (recall that every distributional node must have at least one child). Note that there is no bound on the number of children of an ordinary node.

The following theorem shows that for the families that do not include the type exp, the bound 2 is enough. Proof Observe that for each of the four parts, the direction ⊒ poly o is trivial. To prove the opposite direction, let P be a p-document of the family on the left-hand side of one of the four parts. We describe an efficient process that preserves o-equivalence and does the following. Given a distributional node v ∈ V dst ( P) that has k > 2 children, the process replaces v with three distributional nodes of the same type and degrees 1, 2 and k -1. By repeatedly applying this process, we get an o-equivalent p-document, such that each distributional node has one or two children. Note that this is sufficient for proving Parts 1, 2 and 4. For Part 3, we first apply the above process to the given p-document of PrXML {ind,mux} , and then use the o-translation (into the family PrXML {mux,det} ) that is described in the proof of Lemma 5.8. Note that this translation does not increase the maximal out-degree of distributional nodes; hence, the end result is a p-document of PrXML {mux,det} ∆≤2

. The process of replacing v is illustrated in Figure 6.1. The children of v are denoted by w 1 , . . . , w k . In the subtree that replaces v, the root is the distributional node v ′ and it has two distributional children u and u k . The children of u are w 1 , . . . , w k-1 , and the only child of u k is w k . Note that the nodes w 1 , . . . , w k , as well as the whole subtrees under them, are not changed. Recall that v ′ , u and u k have the same type as v. In the remainder of the proof, we give additional details of this construction according to the type of v. v is of type ind. In this case, v ′ chooses both of its children with probability 1 (as if it is a det node). The probabilities of choosing the children w 1 , . . . , w k are unchanged, that is,

p u k (w k ) = p v (w k ) and p u (w i ) = p v (w i ) for 1 ≤ i ≤ k -1.
v is of type mux. Let p = p v (w k ). Node v ′ chooses (the mutually exclusive) u and u k with probabilities (1p) and p, respectively. Node u k chooses w k with probability 1. Finally, for 1 ≤ i ≤ k -1, we set p u (w i ) to p v (w i )/(1p). Note that p < 1 since there are no useless nodes and v has more than one child.

v is of type cie. This case is handled similarly to the case where v is of type ind. In particular, α v ′ (u) and α v ′ (u k ) are true (i.e., empty conjunctions),

α u k (w k ) = α v (w k ) and α u (w i ) = α v (w i ) for 1 ≤ i ≤ k -1. ⊓ ⊔ Next,
\ {w i }, that is, p v (W \ {w i }) = 1
b+1 . For i = j, the events "P does not include w i " and "P does not include w j " are probabilistically depen- dent. To see why, observe that w i must appear in P if w j is absent. By using this property, we will show that no p-document of PrXML {exp} ∆≤b is o-equivalent to P. Suppose, by way of contradiction, that a p-document P0 ∈ PrXML {exp} ∆≤b is o-equivalent to P. It is easy to show that r is the root of P0 and W comprises exactly all the leaves of P0 (since P0 has no useless nodes). We will prove that there is a probability greater than 0 that all the nodes of W appear in the random document P 0 , thereby deriving a contradiction to the o-equivalence of P0 and P, because the probability that P contains all of W is 0. Let u a be the least common ancestor of W in P0 . Note that u a has at least two children. If u a is the root r, then there are two distinct leaves w i and w j in W , such that each one is a descendant of a different child of r. Hence, the events "P 0 does not include w i " and "P 0 does not include w j " are probabilistically independent, which is the opposite of the above property of P. Therefore, P0 ≡ o P implies that u a is not r, so u a is a distributional node. Consequently, u a has at most b children. Since all the b + 1 nodes of W are descendants of u a , there is a child u c of u a that has two or more descendants that are in W . Let W c ⊆ W be the set of ordinary descendants of u c . Since u a has more than one child, u c has at most b descendants from W . It follows that 2 ≤ |W c | ≤ b. By the definition of P, the probability that P contains all the nodes of W c (and, possibly, additional nodes of W ) is greater than 0. Consequently, the probability that P 0 contains W c is greater than 0, because P0 ≡ o P. Note that for P 0 to contain W c , the r-subtree P Σ 0 must contain W c and u c . We conclude the following.

v ′ w1 w k-1 w2 • • • w2 • • • w k w k-1 w k v u u k w1
0 < Pr W c ⊆ V (P Σ 0 ) = Pr W c ∪ {u c } ⊆ V (P Σ 0 ) = = Pr u c ∈ V (P Σ 0 ) × × Pr W c ⊆ V (P Σ 0 ) | u c ∈ V (P Σ 0 )
In particular, the following holds.

Pr W c ⊆ V (P Σ 0 ) | u c ∈ V (P Σ 0 ) > 0 (6.1)
We arbitrarily choose w c ∈ W c , and denote by W c the set (W \ W c ). Observe that W c ∪ {w c } has at most b nodes. So, again, the probability that P Σ 0 contains W c ∪{w c } is greater than 0 and, since w c is a descendant of u c , the r-subtree P Σ 0 must contain u c in order to contain w c . Thus, the following holds.

0 < Pr W c ∪ {w c } ⊆ V (P Σ 0 ) ≤ ≤ Pr W c ∪ {u c } ⊆ V (P Σ 0 ) (6.2)
We now consider the probability that P 0 (or, equivalently, that P Σ 0 ) contains all the nodes of W .

Pr W ⊆ V (P Σ 0 ) = Pr W ∪ {u c } ⊆ V (P Σ 0 ) = = Pr W c ∪ {u c } ⊆ V (P Σ 0 ) × × Pr W c ⊆ V (P Σ 0 ) | W c ∪ {u c } ⊆ V (P Σ 0 ) (6.3)
The random process of constructing P Σ 0 and the fact that P0 has no cie nodes imply the following. Given the condition that P Σ 0 includes u c , the events "P Σ 0 contains W c " and "P Σ 0 contains W c " are probabilistically independent. In particular, the following holds.

Pr W c ⊆ V (P Σ 0 ) | W c ∪ {u c } ⊆ V (P Σ 0 ) = = Pr W c ⊆ V (P Σ 0 ) | u c ∈ V (P Σ 0 ) (6.4)
From Equations (6.1), (6.2), (6.3) and (6.4), we conclude the following.

Pr W ⊆ V (P Σ 0 ) = Pr W c ∪ {u c } ⊆ V (P Σ 0 ) × × Pr W c ⊆ V (P Σ 0 ) | W c ∪ {u c } ⊆ V (P Σ 0 ) = = Pr W c ∪ {u c } ⊆ V (P Σ 0 ) × × Pr W c ⊆ V (P Σ 0 ) | u c ∈ V (P Σ 0 ) > 0
As explained above, this yields a contradiction. By Proposition 5.7, every p-document of PrXML {exp} can be v-translated to PrXML {mux,det} , but the size of the result is linear in the number of possible worlds of P. In this section, we present two v-translations that are efficient for important sub-classes of PrXML {exp} .

⊓ ⊔ um • • • • • • W1 mux v ′ v • • • exp w k-1 w k w2 w1 • • • det • • • W2 • • • • • • det • • • Wm u1 u2 W1, . . . , Wm Pv T • • • det
SimpleTrans and GreedyTrans are two v-translations that traverse the p-document top down and operate as follows. Whenever an exp node v is visited, the subtree of P that is rooted at v is replaced with a different subtree that has a root of type mux. In SimpleTrans, this operation is called simple replacement, and in Greedy-Trans, it is called greedy replacement. The details of these replacements are described below. Consider a p-document P ∈ PrXML {exp} . Let v be an exp node of P with the set of children W = {w 1 , . . . , w k }. Suppose that v specifies nonzero probabilities for the subsets W 1 , . . . , W m of W . Note that m j=1 p v (W j ) = 1. By Pv we denote the subtree of P rooted at v and consisting of all the descendants of v. Similarly, for 1 ≤ i ≤ k, the subtree Pi of P is the one rooted at w i and comprising all the descendants of w i .

The simple replacement is illustrated in Figure 6.3. It replaces Pv with the tree T that is constructed as follows. The root of T is a mux node that has m det children u 1 , . . . , u m . For all 1 ≤ j ≤ m and w i ∈ W j , we create a copy of Pi and make it a subtree of u j .

The greedy replacement is more complicated. It is illustrated in Figure 6.4 and defined as follows. First, we choose the node w i of W that has the maximal number of descendants (i.e., Pi has the maximal number of nodes among P1 , . . . , Pk ). By renaming if necessary, we assume that this node is w k . The sets W k and W ¬k , and the number p k are defined as follows.

W k def = {W j \ {w k } | 1 ≤ j ≤ m ∧ w k ∈ W j } W ¬k def = {W j | 1 ≤ j ≤ m ∧ w k / ∈ W j } p k def = 1 - Wj ∈W ¬k p v (W j )
In other words, W k comprises all the sets W ′ , such that w k / ∈ W ′ and W ′ ∪ {w k } is given a nonzero probability by v; W ¬k is the set of all the W j that do not include w k ; and p k is the probability that v chooses w k (possibly in addition to other nodes). The tree Pv is replaced with the tree T that consists of four new distributional nodes v ′ , u ′ , u k and u ¬k , as well as copies of P1 , . . . , Pk . Note that u k and u ¬k are of type exp and they will be handled by GreedyTrans in due course. The full details are given below.

The root of T is the mux node v ′ . The children of v ′ are u ′ and u ¬k , and they are chosen with probabilities p k and 1p k , respectively. The type of u ′ is det and one of its two children is For 1 ≤ i ≤ k -1, one copy of Pi becomes a subtree of u k and a second copy-a subtree of u ¬k . Pk becomes a subtree of u ′ .

u k . w2 u ′ w k w k-1 exp • • • v mux v ′ exp det • • • w k-1 w2 w1 w k Pv T W ¬k W k u k • • • w k-1
As mentioned above, the type of both u k and u ¬k is exp. Node u ¬k specifies the probability p v (W j )/(1p k ) for each W j ∈ W ¬k . Node u k specifies the probability

p v (W ′ ∪ {w k })/p k for each subset W ′ ∈ W k .
An exception to the above construction is when k = 1 or p k = 1 (note that p k > 0, because there are no useless nodes). An exp node with a single child is actually a mux node, so GreedyTrans does nothing at node v if k = 1. If p k = 1, then u ¬k and its descendants are not added to T .

The distributional depth of a p-document P is defined as the maximal number of distributional nodes along any path from the root to a leaf. The next proposition shows that SimpleTrans is efficient if the distributional depth of P is bounded by a constant. Note that the number of possible worlds can still be exponential in the size of P even if this bound is 2. Formally, for a natural number h, we denote by PrXML {exp} ↓≤h the set of all p-documents P ∈ PrXML {exp} , such that the distributional depth of P is at most h. Proof Consider a p-document P ∈ PrXML {exp} ↓≤h having N nodes. Let M be the smallest integer, such that for all distributional nodes v of P, there are at most M subsets in the specification of v. Clearly, both N and M are not larger than the size of P.

We extend earlier notation so that Pv , as well as the subtrees P1 , . . . , Pk rooted at the children of v, are defined for all the nodes of P (rather than just exp nodes). In addition, let N v and N i be the numbers of nodes of the subtrees Pv and Pi , respectively. G( Pv ) denotes the number of nodes in the result of applying SimpleTrans to Pv .

We prove the following claim by a bottom-up induction on P: If the distributional depth of the subtree Pv is bounded by c, then G( Pv ) ≤ (M +1) c N v . This claim implies that G( P) ≤ (M + 1) h N , thereby proving the proposition.

For the basis of the induction, the subtree Pv is just a leaf (and hence v is an ordinary node). So, SimpleTrans does not change Pv and, consequently, the induction hypothesis holds, because 1 ≤ (M + 1) 0 .

For the inductive step, there are two cases to consider. First, if v is an ordinary node, then SimpleTrans does not change v. Hence, by applying the induction over which SimpleTrans results in an exponential blowup hypothesis to P1 , . . . , Pk , we get the following.

G( Pv ) =1 + k i=1 G( Pi ) ≤ ≤ 1 + k i=1 (M + 1) c N i ≤ ≤ 1 + (M + 1) c i=1 N i ≤ (M + 1) c N v
The second line, in the above equation, follows from the induction hypothesis. The last inequality follows from 1

+ i=1 N i = N v .
If v is a distributional node, then SimpleTrans replaces v with at most 1 + M nodes and replicates each Pi at most M times. In the equation below, the second line follows from the induction hypothesis (note that the distributional depth of each Pi is at most c -1).

G( Pv ) ≤ 1 + M + M k i=1 G( Pi ) ≤ ≤ 1 + M + M k i=1 (M + 1) c-1 N i ≤ ≤ (M + 1) c (1 + k i=1 N i ) = (M + 1) c N v ⊓ ⊔
Next, we show that SimpleTrans is not an efficient v-translation from PrXML {exp} ∆≤2 . In proof, for all n > 0, let Pn be the p-document shown in Figure 6.5. When applying SimpleTrans to Pn , the resulting document has a depth of 2n + 1. It can be easily verified that the number of mux nodes at depth 2n -1 of the result is 2 n-1 . As opposed to SimpleTrans, the following lemma shows that GreedyTrans is an efficient v-translation from PrXML Proof In this proof, G( P) denotes the number of nodes in the result of applying GreedyTrans to P. Clearly, GreedyTrans does not introduce exp nodes with specifications that are larger than the maximal specification in the source document. So, it suffices to prove that the following holds for all p-documents P ∈ PrXML {exp} ∆≤b . For all subtrees Pv of P, it holds that G( Pv ) is polynomial in |V ( Pv )| (i.e., the number of nodes of Pv ). Let c > 1 be the smallest (fixed) integer, such that (1

-1 b+1 ) c-1 ≤ 1/2. We prove by induction on |V ( Pv )| that G( Pv ) ≤ 2|V ( Pv )| c -1 for all subtrees Pv .
For the basis of the induction, we assume that v is a leaf. In this case, GreedyTrans does not change Pv , and hence, G( Pv ) = 1, as required.

For the inductive step, we consider a node v of some P ∈ PrXML {exp} ∆≤b . Recall that P1 . . . , Pk denote the subtrees rooted at the children of Pv , and Pk has the maximal number of nodes among these subtrees.

There are two cases to consider. First, if v is an ordinary node, then the following equation holds, where the second line follows from the induction hypothesis.

G( Pv ) ≤ 1 + k i=1 G( Pi ) ≤ ≤ 1 + k i=1 (2|V ( Pi )| c -1) ≤ ≤ 2 k i=1 |V ( Pi )| c ≤ ≤ -1 + 2(1 + k i=1 |V ( Pi )| c ) ≤ ≤ -1 + 2(1 + k i=1 |V ( Pi )|) c = = 2|V ( Pv )| c -1
In the second case, v is an exp node, and we apply the greedy replacement as illustrated in Figure 6.4. If k = 1, then nothing is done at node v, so the proof is the same as in the case where v is an ordinary node. If k > 1, then after applying GreedyTrans to v, we continue recursively with the subtrees Pu ¬k , Pu k and Pk (the transformation does nothing when visiting the det node u ′ ). Each of these three subtrees has fewer nodes than Pv , so the induction hypothesis implies the following.

G( Pv ) ≤ 2 + G( Pu ¬k ) + G( Pu k ) + G( Pk ) (6.5)
Note that if p k = 1, then G( Pu ¬k ) = 0. The proof below holds also in this case. Let r k be the ratio N k /N . Then r k ≥ 1/(b + 1). For each of Pu k and Pu ¬k , the number of nodes is at most N -N k = (1r k )N . The number of nodes of Pk is r k N . We now continue with Equation (6.5) and get the following. Note that the fifth inequality below uses r k ≥ 1/(b + 1), which was shown above.

G( Pv ) ≤ 2 + G( Pu ¬k ) + G( Pu k ) + G( Pk ) ≤ ≤ 2 + 2 • (2((1 -r k )N ) c -1) + 2(r k N ) c -1 ≤ ≤ -1 + 2 • 2(1 -r k ) c N c + 2r c k N c ≤ ≤ -1 + 2 • 2(1 -r k ) c N c + 2r k N c ≤ ≤ -1 + 2 • 2 1 - 1 b + 1 c-1 (1 -r k )N c + + 2r k N c Recall that c satisfies 1 -1 b+1 c-1 ≤ 1/2. Therefore, G( Pv ) ≤ 2(1 -r k )N c + 2r k N c -1 = 2N c -1 , as required. ⊓ ⊔
As a result, we get the following corollary. We conclude with the following theorem. Another perspective on the expressiveness of probabilistic XML models is to consider their ability for capturing updates. A main question is whether the result of an update is expressible in some model. Another issue is how complex it is to compute a representation of this result. As is natural in the context of probabilistic data, we consider probabilistic updates, that are conditioned by a certain confidence in the operation. Typically, a probabilistic database could be the result of a number of successive probabilistic updates on an initial ordinary document.

As with o-translations and v-translations, we consider here two kinds of probabilistic updates: o-updates, based on object identity, and v-updates, based on value equality. For simplicity, we consider here only elementary updates, that is, updates consisting of a single insertion or deletion. The extension to arbitrary updates is not too involved, and is discussed in [START_REF] Senellart | Comprendre le Web caché. Understanding the Hidden Web[END_REF].

Object-Based Updates

In a real-life system, o-updates are obtained for instance when a user clicks on a node to attach an annotation to it or to delete it. Such an update is thus directly specified on an object. The system may, for instance, attach a confidence to that update depending on the expertise of the particular user. More formally: Definition 7.1 A probabilistic o-update operation is a pair τ = (o, c) where 0 < c ≤ 1 is the confidence in the operation, and o is either:

1. an o-insertion, that is, an expression ι(v, F ) where v is a node identifier and F is a document forest; 2. an o-deletion, that is, an expression δ(v) where v is a node identifier.

If c = 1, τ is said to be deterministic.

In the following, we assume that all nodes to be inserted (that is, all nodes of the document forest F in expressions ι(v, F )) are fresh nodes that do not appear in any document where F will be inserted.

The semantics of a deterministic update on a document is clear. (In the case it speaks of a non-existing node, the update is simply ignored.) Formally: Definition 7.2 Let τ = (o, 1) be a deterministic oupdate operation and d a document. The result of the operation τ on d, denoted τ (d), is defined as follows:

1. d is unchanged if v / ∈ V (d) (for o = ι(v, F ) or o = δ(v)); 2. if o = ι(v, F ) and v ∈ V (d), each tree in F is in- serted as a child of v; 3. if o = δ(v) and v ∈ V (d), v is deleted (unless v is the root of d, in which case d is left unchanged).
More interestingly, we now define the semantics of an o-update operation on a px-space. Intuitively, a probabilistic o-update (o, c) performs the update on a document with probability c, and does nothing with probability 1c. We now consider the expressiveness of the different families of p-documents, which were presented in Section 4, with respect to probabilistic o-updates. The general question is, given a family of p-documents F and a probabilistic o-update operation τ , is the result of τ on the px-space associated with a p-document of F always representable as a p-document of F ? We define this next while taking tractability into consideration. Definition 7.4 Let F be a family of p-documents. We say that F is closed under (respectively, deterministic) o-updates if for each (respectively, deterministic) o-update τ and for each P ∈ F , there exists a P′ ∈ F such that τ ( P ) = P′ . We say that F is tractably closed under o-updates if there exists a polynomial-time algorithm that, given a p-document P ∈ F and an oupdate operation τ , returns a p-document P′ ∈ F such that P′ = τ ( P ).

We can now study the closure of concrete families of p-document under o-updates, and the tractability of o-updates: if u is a det, ind, mux, or cie node, we do not change anything (in the case of mux, it means that the probability of not choosing any of the children of u increases by the amount p u (v)); -if u is an exp node, we set p ′u (W ) = p u (W )+ p u (W ∪ {v}). Then it is easy to see that P′ ∈ F and P′ = (o, 1)( P ). 2. Let F be such a family and P ∈ F . Let (o, c) be an o-update. We build P′ from P as follows:

if o = ι(v, F ) or o = δ(v), and v / ∈ V ( P), then P′ = P;

if o = ι(v, F ) with v an ordinary node of P, then we add as child of v an ind node v 1 that has for child another ind node v 2 that has for children the forest F , and we set p ′v1 (v 2 ) = c and p ′v2 (w k ) = 1 for all w k roots of F ; -if o = δ(v) with v a non-root node of P, we insert between v and its parent an ind note v ′ such that p ′v ′ (v) = 1c. If the parent of v is distributional, then the specifications of the probabilities are modified by replacing v with v ′ . Then P′ is obviously an element of F and we can check that P′ = τ ( P ). In other words, all reasonable probabilistic XML models are tractably closed under o-updates. However, value-based updates may in practice often be viewed as more "natural". We consider them next.

Value-Based Updates

Suppose we want to annotate all addresses in a document. We use a query to recognize addresses. We then update all the nodes returned by the query. In general, a value-based update uses a locator query to locate the objects to update and then applies the update to all the objects. For example, the locators that are embedded in the XML update languages XUpdate [START_REF]W3C: XQuery Update facility[END_REF] and XQuery Update [18] rely on XPath [START_REF]W3C: XML Path language (XPath)[END_REF] and XQuery [START_REF]W3C: XQuery 1.0: An XML query language[END_REF] queries, respectively. We consider simple query languages described later. First, we define queries abstractly. Definition 7.7 A locator query Q is defined as a function that maps each document d to a set of pairs (d ′ , v ′ ) where d ′ is an r-subtree of d and v ′ is a locator, that is, a node in d ′ . We assume that applying the same query to isomorphic documents yields isomorphic answers.

We can now define v-updates in terms of queries. Definition 7.8 A probabilistic v-update operation is a pair τ = (o, c) where 0 < c ≤ 1 is the confidence in the operation, and o is either:

1. a v-insertion, that is, an expression ι(Q, F ) where Q is a query and F is a document forest (to be inserted as children of the nodes mapped by Q); 2. a v-deletion, that is, an expression δ(Q) where Q is a query (indicating the nodes to delete).

If c = 1, τ is said to be deterministic.

Observe that again our updates are probabilistic. The locator query may introduce uncertainty, e.g., the system may make errors in recognizing addresses.

As in the discussion of Section 7.1 about o-updates, we consider the following two issues with respect to various families of p-documents: closure under v-updates, and the complexity of computing a representation of the result of an update. We first define the semantics of deterministic v-updates on ordinary documents. Definition 7.9 Let τ = (o, 1) be a (deterministic) vupdate operation and d a document. The result of the operation τ on d, denoted τ (d), is the result of applying o to d:

1. if o = ι(Q, F ), each tree in F is inserted as a child of each v ′ such that some (d ′ , v ′ ) ∈ Q(d) (possibly inserting F multiple times at the same place); 2. if o = δ(Q), each v ′ such that some (d ′ , v ′ ) ∈ Q(d) is deleted.
The definition of the result of a v-update operation on a px-space is a straightforward adaptation of Definition 7.3 for o-updates. Closure under v-updates, however, uses px-space isomorphism instead of equality: Definition 7.10 Let F be a family of p-documents. We say that F is closed under v-updates (respectively, deterministic v-updates) for the class of queries Q if, for any v-update (respectively, deterministic v-update) τ = (o, c) with o defined by a query Q ∈ Q, for each P ∈ F , there exists a P′ ∈ F such that τ ( P ) ∼ P′ . We say F is tractably closed under v-updates for the class Q if there is an algorithm that returns such a P′ given P in time polynomial in the size of P. 8We next introduce three classes of queries that we will consider for closure and tractability results. The first one is the class of tree-pattern queries, e.g., queries of the form a[b/c][d]. This is one of the most studied classes of queries for XML. We use here for simplicity a restricted notion of tree-pattern queries, without descendant edges (the // of XPath). This class can be extended in a straightforward manner. But, as we shall see, even simple branching as considered here leads to negative results. We also consider a simpler class, namely that of restricted single-path queries, e.g., queries of the form /a/b/c. Finally, we consider a more abstract class, namely the "locally monotone queries" that includes the tree-pattern queries. We will show for that class a very strong positive result (the tractable closure of PrXML {cie} under v-insertions defined by locally monotone queries).

Definition 7.11

1. A tree-pattern query Q is defined by an underlying tree-pattern d Q (which is simply an ordinary document) and a locator node

v Q ∈ V (d Q ).
, v ′ ) ∈ Q(d 2 ). Now let (d ′ , v ′ ) ∈ Q(d 2 ) with d ′ an r-subtree of d 1 . By 3i, (d ′ , v ′ ) ∈ Q(d 1 )
. This concludes the proof of the implication. 3ii ⇒ 3i. Let d 1 , d 2 and d 3 be three documents such that d 1 is an r-subtree of d 2 and d 2 an r-subtree of

d 3 . Suppose first that (d 1 , v ′ ) ∈ Q(d 3 ). As d 1 is an r- subtree of d 2 , by 3ii, (d 1 , v ′ ) ∈ Q(d 2 ). Now suppose (d 1 , v ′ ) ∈ Q(d 2 ). By 3ii, (d 1 , v ′ ) ∈ Q(d 3 ).
Locally monotone queries actually generalize treepattern queries: Proposition 7.12 Every tree-pattern query is locally monotone.

Proof We prove (ii) of Definition 7.11. Let Q be a treepattern query defined by the pattern d Q and locator v Q . Let d 1 and d 2 be two documents, such that d 1 is an r-subtree of

d 2 . Let (d ′ , v ′ ) ∈ Q(d 1 ). By definition, d ′ is an r-subtree of d 1 . As there is a homomorphism from d Q to d ′ mapping v Q to v ′ and d ′ is an r-subtree of d 2 , (d ′ , v ′ ) ∈ Q(d 2 ). Now let (d ′ , v ′ ) ∈ Q(d 2 ) be an r-subtree of d 1 . Then there is a homomorphism from d Q to d ′ mapping v Q to v ′ , so (d ′ , v ′ ) ∈ Q(d 1 ). ⊓ ⊔
We showed in [START_REF] Senellart | Comprendre le Web caché. Understanding the Hidden Web[END_REF] that tree-pattern queries with descendant edges and value joins (both positive and negative) are still locally monotone. On the other hand, a simple query such as "Return the root if all its children are labeled by l" is not locally monotone because the universal quantifier involves some form of negation. We present now basic results about closure under v-updates and tractability. then maps these identifiers to nodes of P). τ o is defined by a node v. If this node is not in P, then τ o ( P ) = P . Otherwise, let Pv be the relabeling of P by ϕ and d the minimal r-subtree of doc( P′ ) containing the node labeled by ϕ(v) (this is obviously a single path). Let τ v be the v-update corresponding to τ o where the locator v is replaced by the restricted single-path query d with locator the node labeled by ϕ(v). Since F is closed under v-updates, there is a document P′ v such that P′ v = τ v ( Pv ). Observe now that if one apply ϕ -1 to the labels of the nodes of τ v ( Pv ) to get back original nodes of P, one obtains exactly τ o ( Pv ) since τ o and τ v both perform the same update at the same place. Let now P′ be the p-document obtained from P′ v by applying ϕ -1 to the labels to get back original nodes of P. Then P′ = τ o ( P ). Note that this construction might not be polynomial even if F is tractably closed under v-updates for the class of restricted single-path queries, since the query defining τ v is not fixed. 2. Suppose F is closed under deterministic o-updates.

Let P ∈ F and τ v = (o v , c v ) be a deterministic v-update defined by restricted single-path query Q. Let S be the set of answers of Q on doc( P). Since Q is a single-path query the number of elements in |S| is at most the number of ordinary nodes in P.

For each {(d ′ , v ′ )} ∈ S, we define the deterministic o-update τ

(d ′ ,v ′ ) o
that performs the same update operation as τ v except that the locator query is replaced by v ′ . We apply now the o-updates τ

(d ′ ,v ′ ) o
for each {(d ′ , v ′ )} sequentially on P , yielding a px-space (D ′ , p ′ ). Observe that the ordering of these o-updates is not significant and that (D ′ , p ′ ) is exactly τ v ( P ). As F is closed under deterministic o-updates, there is a P′ ∈ F such that P′ = (D ′ , p ′ ). The construction of P′ from P is polynomial if F is tractably closed under o-updates (we use here the bound on |S|). 3. Suppose F 1 is closed under v-updates. Let P2 ∈ F 2 and τ be a v-update. Since F 2 ⊑ v F 1 , there exists P1 ∈ F 1 such that P1 ∼ P2 . As F 1 is closed under v-updates, there exists P′ 1 ∈ F 1 such that P′ 1 ∼ τ ( P1 ). Since F 1 ⊑ v F 2 , there exists P′ 2 ∈ F 2 such that P′ 2 ∼ P′ 1 . Then P′ 2 ∼ τ ( P2 ), and F 2 is closed under v-updates. The other direction is obtained by symmetry. 4. This is proved as in 3, since P1 , P′ 1 and P′ 2 can be obtained in polynomial time from, respectively, P2 , P1 and P′ 1 (observe that the query defining τ remains fixed). 5. This is a direct consequence of Proposition 5.7. ⊓ ⊔ We now consider the tractability of v-updates for families such as PrXML {exp} and PrXML {cie} . The following result shows that, at least for v-insertions, the ability of expressing complex dependencies through cie nodes makes a difference in the complexity of updates. with type i any of the types of distributional nodes defined in Section 4, except cie, is not tractably closed under deterministic v-insertions defined by single-path queries. 2. PrXML {cie} is tractably closed under v-insertions defined by locally monotone queries, as long as computing query results can be done in polynomial time. 9 = Ω(2 n ) using Stirling's formula. 2. This has been proved in [START_REF] Senellart | Comprendre le Web caché. Understanding the Hidden Web[END_REF]. As the proof requires a number of intermediate results (especially on the possibility of applying locally monotone queries directly to p-documents of PrXML {cie} ), we only describe here the general idea. Given a v-insertion τ defined by a query Q and a p-document P, we apply Q directly to doc( P), keeping for each query result r the set of event conjunctions cond r on nodes appearing in the query result. Then, for each query result r, the nodes to be inserted are inserted at the place indicated by the locator, under a fresh cie node, with the conjunction of cond r as the condition. Because Q is locally monotone, it can be shown that this process yields a p-document P′ such that P′ ∼ τ ( P ). Besides, it is obviously a polynomial-time process, as long as Q takes polynomial time on doc( P).

⊓ ⊔

It is an open issue whether PrXML {cie} is tractably closed under arbitrary v-updates (including deletions) defined by tree-pattern queries. We have shown in [START_REF] Senellart | Comprendre le Web caché. Understanding the Hidden Web[END_REF], however, that v-updates are intractable in PrXML {cie} if we impose the result of an update to be expressed with the same events as in the original document (this is usually what we want when updating PrXML {cie} pdocuments, since this allows the keeping of lineage or provenance information, each event being a trace of the update that introduced it).

Conclusion

Under the object-based semantics, PrXML {exp,cie} is the most expressive family (among those studied) and has two crucial properties. It is tractably closed under oupdates, and all the other families can be efficiently o-translated into it (but the converse is not true). Under the value-based semantics, PrXML {exp,cie} remains the most expressive. Notwithstanding, other families, including PrXML {ind,mux} , PrXML {exp} and PrXML {cie} , are as expressive as PrXML {exp,cie} . V-translations from PrXML {cie} into either PrXML {ind,mux} or PrXML {exp} may entail an exponential blowup in the size of the p-document. It is unknown whether there are efficient v-translations from PrXML {exp} into PrXML {ind,mux} and PrXML {cie} . Nonetheless, p-documents of PrXML {exp} with a bounded distributional depth or out-degree can be efficiently v-translated into the other two families. As for updates, v-insertions (defined by locally monotone queries) are tractable for PrXML {cie} , but not for PrXML {exp} . Therefore, under the value-based semantics, PrXML {cie} has the advantage in terms of insertions, the ability to efficiently translate into it, and the power to express correlations between different distributional nodes. However, tree-pattern queries with projection can be evaluated efficiently (under data complexity) in the family PrXML {ind,mux} [START_REF] Kimelfeld | Matching twigs in probabilistic XML[END_REF], and even in PrXML {exp} [START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF][START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF], but (except for trivial cases) they are #P-hard in PrXML {cie} [START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF][START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF]. Thus, the choice of a probabilistic XML model hinges on a trade-off between efficient query processing and the ability to capture complex correlations.

We conclude by discussing some extensions. In [START_REF] Cohen | Incorporating constraints in probabilistic XML[END_REF], the family PrXML {exp} is enriched with constraints that make it possible to express correlations between distributional nodes, without sacrificing the efficiency of query evaluation; however, update tractability is still open. In [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF], p-documents are extended by allowing order among siblings. Alternatively, one might consider two p-documents to be the same if there are homomorphisms in both directions; the effect on translatability and updates is left for future work. Finally, it is important to study the complexity of some additional problems, such as testing equivalence of p-documents and enumerating all random documents that have probability above a given threshold. In particular, it would be interesting to find out how these complexities depend on the types of distributional nodes being used.

Fig. 2 .

 2 Fig. 2.1 A p-document P, an r-subtree s ∈ Σ( P) and the document d = doc(s)

Example 3 . 1

 31 Figure 2.1 (top) depicts a p-document P. Distributional nodes are shown as rounded-corner rect-angles. The types of those nodes are denoted by words inside the rectangles (e.g., ind and mux), and they will be discussed in Section 4.1.

Example 3 . 2

 32 Consider again Figure 2.1. Recall that the p-document P is discussed in Example 3.1. The bottom part of the figure depicts two trees. The one on the left is an r-subtree s ∈ Σ( P), and the one on the right is the document d = doc(s). It can be easily shown that s is the only r-subtree of Σ( P) that generates d and, consequently, Pr(P = d) = Pr(P Σ = s). The computation of the probability on the right-hand side will be explained in Section 4.1.

Lemma 5 . 1

 51 PrXML {mux} ≡ poly o PrXML {mux} | h . Proof Let P ∈ PrXML {mux} be given. We efficiently transform P into an o-equivalent p-document P′ ∈ PrXML {mux} | h

Fig. 5 . 1

 51 Fig. 5.1 (a) A p-document of PrXML {ind} that cannot be v-translated to PrXML {ind} | h (b) O-translating PrXML {ind} | h to PrXML {mux}

  is v-equivalent to P. All the probabilities specified in P′ are nonzero, because there are no useless nodes.

Fig. 5 . 3

 53 Fig. 5.3 Transforming an ind node into a hierarchy of det and mux nodes

Proof

  The proof ofLemma 5.4 shows that if both the parent and the children of an ind node v are ordinary, then v can be emulated by some mux nodes without introducing hierarchies. Therefore, PrXML

  {exp} | h ) to the family PrXML {ind,mux} . Lemma 5.11 PrXML {ind,mux,exp} ≡ poly o PrXML {exp} .

Fig. 5 .

 5 Fig. 5.4 (a) Transforming a hierarchy of exp nodes into a single exp node (b) A p-document of PrXML {ind} that cannot be v-translated to PrXML {exp} | h

Theorem 5 . 13

 513 PrXML {ind,mux,cie} ≡ poly o PrXML {cie} | h .

  to PrXML {cie} (and, by Theorem 5.13, neither to PrXML {ind,mux,cie} ). Lemma 5.14 PrXML {exp} | h ⊑ o PrXML {ind,mux,cie} . Proof By Theorem 5.13, it suffices to show that there is a p-document P′ ∈ PrXML {exp} | h

. 1 .

 1 But this is not an efficient v-translation. The next theorem shows that an efficient v-translation does not exist. Moreover, regardless of efficiency, there is no o-translation. Theorem 5.15 The following hold. PrXML {cie} ⊑ poly v PrXML {ind,mux,exp} . 2. PrXML {cie} ⊑ o PrXML {ind,mux,exp} .

Fig. 5 .

 5 Fig. 5.5 A p-document of PrXML {cie} that can be neither efficiently v-translated nor o-translated to PrXML {ind,mux,exp}

Fig. 5 . 6

 56 Fig. 5.6 A p-document of PrXML {exp,ind} that cannot be efficiently o-translated to PrXML

Theorem 5 . 16

 516 PrXML {exp} ⊑ poly o PrXML {exp,cie} | h . Proof We assume, by way of contradiction, that there is an efficient o-translator from the family PrXML {exp} to PrXML {exp,cie} | h . Hence, Lemma 5.11 implies that there is also an efficient o-translator ϕ from PrXML {exp,ind} to PrXML {exp,cie} | h . Let Pn be the p-document of Figure 5.6. The index n denotes the number of children of each of the nodes w and u.

Fig. 5 . 7

 57 Fig. 5.7 Efficient o-translations between families of p-documents

  Figure 5.7 shows the efficient o-translations that exist between the families of p-documents that have been discussed in this section. This figure is complete in the sense that if there is no directed path from a family F 1 to F 2 , then there is no efficient o-translator from F 1 to F 2 . As shown in Figure5.7, the family PrXML {exp,cie} is the most general, and the families PrXML {exp} and PrXML {exp,cie} | h are just below PrXML {exp,cie} . The family PrXML {cie} is right below PrXML {exp,cie} | h .Recall that an o-translation is also a v-translation. In addition, we have shown that every family F of p-documents is v-translatable to PrXML {mux,det} and, hence, also to PrXML {exp} and PrXML {cie} . However, the family PrXML {cie} is not efficiently v-translatable to PrXML {mux,det} , or even to PrXML {ind,mux,exp} ; namely, such a v-translation causes an exponential blowup.We also considered the need for hierarchies of distributional nodes. We showed that such hierarchies are not required in the case of either PrXML {cie} or PrXML {mux} . However, for the families PrXML {ind} , PrXML {ind,mux} , PrXML {mux,det} and PrXML {exp} , these hierarchies properly increase the expressive power, in the sense that there are no efficient v-or o-translations that can eliminate them (note that in some of these cases, there are no translations regardless of efficiency). In the case of PrXML {exp,cie} , we only proved that there is no efficient o-translation that eliminates hierarchies (and for v-translation, it is open).For the families of p-documents considered thus far, the results of this section determine for every pair F 1

Proposition 6 . 1 1 . 3 .. 4 .

 61134 The following hold. PrXML {ind} ≡ poly o PrXML {ind,mux} ≡ poly o PrXML {mux,det} ∆≤2 PrXML {cie} ≡ poly o PrXML {cie} ∆≤2 .

2 .

 2 we consider the type exp. If b 2 ≥ b 1 ≥ 2, then PrXML {exp} ∆≤b1 ⊑ poly o PrXML {exp} ∆≤b2 trivially holds. The next lemma shows that the opposite direction does not hold. That is, Proposition 6.1 cannot be extended to the type exp and, moreover, raising the bound b increases the expressive power of PrXML {exp} ∆≤b under the o-semantics. Lemma 6.2 PrXML {exp} ∆≤b+1 ⊑ o PrXML {exp} ∆≤b holds for all b ≥ Proof Consider the p-document P ∈ PrXML {exp} ∆≤b+1 that is depicted in Figure 6.2. The root r of P has a single child v which is an exp node, and v has b + 1 ordinary children w 1 , . . . , w b+1 . Let W = {w 1 , . . . , w b+1 }. For all 1 ≤ i ≤ b + 1, node v specifies the probability 1/(b + 1) for the set W

Fig. 6 . 1 Fig. 6 .

 616 Fig. 6.1 Reducing the degree of a distributional node

Fig. 6 . 3

 63 Fig. 6.3 Simple replacement

Fig. 6 . 4

 64 Fig. 6.4 Greedy replacement

Proposition 6 . 3

 63 Let h ≥ 0 be a constant. The algorithm SimpleTrans is an efficient v-translation from the family PrXML {exp} ↓≤h to PrXML {mux,det} . Hence, we have that PrXML {exp} ↓≤h ⊑ poly v PrXML {mux,det} .

Fig. 6 . 5

 65 Fig. 6.5 An example of a series of p-documents of PrXML {exp} ∆≤2

Theorem 6 . 4

 64 {exp} ∆≤b to PrXML {mux,det} , for all b ≥ 2. Let b ≥ 2 be a constant. GreedyTrans is an efficient v-translation from the family PrXML {exp} ∆≤b to PrXML {mux,det} .

  Let N = |V ( Pv )| and N i = |V ( Pi )|. Note that N = 1 + k i=1 N i . Since v has k children, it follows that k ≤ b and the sum 1 + k i=1 N i has at most b + 1 operands. We have assumed that Pk has the largest number of nodes among Pi , . . . , Pk . Therefore, N k ≥ N/(b + 1).

Corollary 6. 5

 5 PrXML {exp} ∆≤b ⊑ poly v PrXML {mux,det} for all constants b ≥ 2.

Theorem 6 . 6 1 . 2 . 20 Proof For Part 1 ,

 6612201 For all constants b 2 > b 1 ≥ 2, the following hold. PrXML {ind,mux} ⊑ poly o PrXML {exp} ⊑ o PrXML {exp} ∆≤b2 ⊑ o ⊑ o PrXML {exp} ∆≤b1 ⊑ o PrXML {ind,mux} . 3. PrXML {ind,mux} ≡ poly v PrXML {ind,mux} ⊑ poly o PrXML {exp} ∆≤b1 follows from Part 3 of Proposition 6.1 and the fact that mux and det nodes can be viewed as special cases of exp nodes. The rest of the o-translations are trivial. For Part 2, Lemma 6.2 implies both PrXML {exp} ⊑ o PrXML {exp} ∆≤b2 and PrXML {exp} ∆≤b2 ⊑ o PrXML {exp} ∆≤b1 . As for the third result of Part 2, it is a consequence of the following observation. In the proof of Lemma 5.14, we showed an example of a p-document P ∈ PrXML {exp} that cannot be o-translated to PrXML {ind,mux,cie} (see Figure 5.4(c)), and P belongs to PrXML {exp} ∆≤2 . Therefore, PrXML {exp} ∆≤b1 ⊑ o PrXML {ind,mux} . Finally, Part 3 follows from Corollary 6.5, Part 3 of Proposition 6.1 and Lemma 5.8.

Definition 7 . 3

 73 Let (D, p) be a px-space and τ = (o, c) an o-update operation. The result of the operation τ on (D, p) is the px-space (D ′ , p ′ ) where D ′ = D ∪ {(o, 1)(d) | d ∈ D} and for each d ′ ∈ D ′ : p ′ (d ′ ) = p(d ′ ) × (1c) + d∈D (o,1)(d)=d ′ (p(d) × c).

Theorem 7. 14 1.

 14 Every family of the form PrXML {type 1 ,type 2 ,...} or PrXML {type 1 ,type 2 ,...} | h

Proof 1 .

 1 With the exception of such families as PrXML {} that are not even closed under o-updates, PrXML {ind} | h is efficiently v-translatable to each considered family F . For one such F , and for an arbitrary positive integer n, let P be the efficient v-translation in F of the p-document of PrXML {ind} | h shown in Figure 7.1(a). We only show here node labels, not node identifiers. Let τ be the deterministic v-insertion defined by the single-path pattern of Figure7.1(b), that inserts a single node labeled by c as a child of the root node a. Suppose that P′ is a p-document of F such that P′ ∼ τ ( P ). We proceed very similarly to the proof of Theorem 5.15: as the number of existing c nodes needs to be correlated with the number of existing b i nodes, all distributional nodes appearing below a b child must yield possible worlds with a fixed number of b ′ children and must thus appear above all nodes labeled by b ′ . This means that, for a given value of k (say, k = n/2, assuming n is even), each possible choice of k b i nodes among n must 9 This is especially the case for tree-pattern queries, whose data complexity is polynomial-time.

Fig. 7 .

 7 Fig. 7.1 A p-document (a) of PrXML {ind} | h on which a v-insertion defined by single-path pattern (b) can result in exponential blowup

is PrXML {cie} | h . In the next section, we show that adding hierarchies of distributional nodes to PrXML

	{cie} | h	is not needed (that is, every p-document of
	PrXML {cie} can be efficiently translated to a p-document of PrXML {cie} | h ). The "simple probabilistic trees" of [7]
	are actually the family PrXML	{ind} | h

1 .

 1 PrXML {mux} ≡ poly PrXML {mux} ⊑ v PrXML {ind} and PrXML {mux} ⊒ v PrXML {ind} . 5. PrXML

	o	PrXML {mux} | h	.
	{ind} | h PrXML 2. PrXML {ind} ⊑ v PrXML 3. PrXML {det} ≡ poly o {det} . | h 4. {ind} | h ⊑ poly	o ≡ poly	PrXML {} .

o PrXML {mux} .

  Transforming a px-space into a hierarchy of det and mux nodes Proposition 5.7 For all the root-consistent px-spaces (D, p), there exists a p-document P ∈ PrXML {mux,det} such that (D, p) ∼ P . As a special case, for every subset C ⊆ {ind, mux, det, exp, cie}, it holds that PrXML C ⊑ v PrXML {mux,det} . Proof Let (D, p) be a px-space, where D = {d 1 , . . . , d n }. For each i, let w i,1 , . . . , w i,ki be the k i children of the root of d i . We construct the p-document P shown in Figure 5.2. Namely, u is a new node that has the same label as the roots of d 1 , . . . , d n , and its only child is a new mux node. Each d i becomes a subtree of the mux node after replacing its root with a new det node, which is chosen by the mux node with probability p(d i ). Clearly, (D, p) is isomorphic to P . The following lemma shows that just by adding det nodes to the family PrXML {mux} , we get the expressive power of all the three types det, ind, and mux. This lemma and Part 4 of Theorem 5.6 imply that PrXML {mux,det} ⊑ v PrXML {mux} . PrXML {mux,det} ≡ poly

	Fig. 5.2 Lemma 5.8	1	p(d1)	p(dn)	w n,kn

⊓ ⊔ Note that the above proof constructs a p-document having a size that is linear in the given px-space (D, p). o PrXML {ind,mux} . Proof PrXML {mux,det} ⊑ poly o

1 .

 1 PrXML {ind,mux,exp} ≡ o PrXML

		{exp} | h	.
	2. PrXML 3. PrXML {ind} ⊑ poly {ind,mux,exp} | h v 4. PrXML {exp} ⊑ poly v	o ≡ poly PrXML PrXML {exp} | h {exp} | h . {exp} PrXML | h	.

. Proof We first prove Part 1. By Lemma 5.11, it is sufficient to show that PrXML {exp} is o-translatable to the family PrXML {exp} | h

  {exp,ind} that cannot be efficiently o-translated to PrXML

	{exp,cie}
	| h
	Pn , the subtree rooted at the node labeled with a must
	appear as is in P′ n . But there are 2 n different possible worlds, yielding 2 n such subtrees. Therefore, P′ n has
	more than 2 n ordinary nodes.	⊓ ⊔
	Finally, we consider the expressive power of exp and
	cie without hierarchies of distributional nodes, namely, {exp,cie} PrXML | h

  Proposition 7.5 1. Every family of the form PrXML {type 1 ,type 2 ,...} or PrXML {type 1 ,type 2 ,...} | h (with type i any of the types of distributional nodes defined in Section 4) is tractably closed under deterministic o-updates. 2. Every family of the form PrXML {ind,type 2 ,type 3 ,...of p-documents such that PrXML {} ⊑ o F ⊑ o PrXML {mux} is not closed under o-updates.if o = ι(v, F ) with v an ordinary node of P, then we insert F as children of v in P; -if o = δ(v) with v a non-root node of P, we delete v from P; additionally, if v is a child of a distributional node u, we adjust the probability of choosing its siblings:

	} is
	tractably closed under o-updates. 3. PrXML {exp} | h and PrXML {exp,cie} are tractably closed | h under o-updates.
	4. A family F Proof
	1. Let F be such a family and P ∈ F . Let (o, 1) be a deterministic o-update. Let P′ be the result of
	applying o directly to the tree P, as follows:
	-if o = ι(v, F ) or o = δ(v), and v / ∈ V ( P), then P′ = P;

  [START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF]. Let P be a document of either family. We can apply the update τ as in Part 2 above, yielding a document P′ ∈ PrXML {ind,exp,cie} in which ind nodes have either a single child or are in effect det nodes. Either way, they can be transformed in polynomial time into exp nodes with probabilities specified for at most two subsets of children (the empty set and the full set), or into cie nodes. As already seen in the proof of Theorem 5.13, a hierarchy of cie nodes can be merged into a single cie node in polynomial time. There only remains the case of a hierarchy of exp nodes, with a succession of at most three exp nodes, two of which with probabilities specified for at most two subsets of children. This can be merged into a single exp node, with probabilities specified for at most 4k subsets, where k is the number of specifications of the third exp node. 4. Let P be a trivial p-document consisting of only one node u. This is a p-document of PrXML {} and thus of F . Let τ = (ι(u, F ), 0.5) be an o-update, where F is a forest that comprises only two nodes w and w ′ and no edges. Then τ ( P ) = ({d 1 , d 2 }, p) where d 1 is a single-node tree and d 2 is a three-node tree, with p(d 1 ) = 0.5 and p(d 2 ) = 0.5. There is no possible way to represent this px-space in PrXML {mux} since the absence of siblings w and w ′ is correlated.⊓ ⊔Observe that for every two familiesF 1 and F 2 of p-documents, if F 1 ≡ o F 2 ,then F 1 is closed under o-updates if and only if F 2 is closed under o-updates. Similarly, for F 1 and F 2 two families of p-documents, if F 1 ≡ poly PrXML {ind} , PrXML {mux,det} , PrXML {cie} , PrXML {exp} , PrXML {exp,cie} , PrXML

	o	F 2 , then F 1 is tractably closed under o-
	updates if and only if F 2 is tractably closed under o-
	updates. Note also that an immediate consequence of
	Proposition 7.5 and of the o-translations between fam-
	ilies of p-documents obtained in Section 5 is the fol-
	lowing characterization of the families closed under o-
	updates:
	Corollary 7.6 The following families are all tractably
	closed under o-updates:
		{exp} | h	and PrXML {exp,cie} | h	.
	However, PrXML {mux} and PrXML {ind} | h under o-updates.	are not closed

  For a document d, Q(d) is the set of all pairs {d ′ , v ′ } such that d ′ is an r-subtree of d, there is a homomorphism from d Q to d ′ , and v ′ is the image of v Q by this homomorphism. 2. A single-path query is a tree-pattern query such that the underlying tree-pattern is a single path without branching. A restricted single-path query Q is a single-path query whose locator node is the terminal node v Q of the path. 3. A query Q is locally monotone if either of the following two equivalent conditions holds: (i) For any three documentsd 1 , d 2 and d 3 such that d 1 is an r-subtree of d 2 and d 2 is a rsubtree of d 3 , (d 1 , v) ∈ Q(d 2 ) ⇐⇒ (d 1 , v) ∈ Q(d 3 ); (ii) For any two documents d 1 and d 2 such that d 1 is an r-subtree of d 2 , Q(d 1 ) is the subset of elements of Q(d 2 ) that are r-subtrees of d 1 .The previous definition is well-defined because 3i and 3ii are equivalent as we briefly argue next: 3i ⇒ 3ii. Let d 1 and d 2 be two documents such that d 1 is an r-subtree of d 2 . Let (d ′ , v ′ ) ∈ Q(d 1 ). By definition of queries, d ′ is an r-subtree of d 1 . By 3i, (d ′

  Let F 1 and F 2 be two families of p-documents such that F 1 ≡ v F 2 . Then, F 1 is closed under v-updates if and only if F 2 is closed under v-updates. 4. Let F 1 and F 2 be two families of p-documents closed under v-updates for some class of queries Q, such that F 1 ≡ poly v F 2 . Then F 1 is tractably closed under v-updates for the class of queries Q if and only if F 2 is tractably closed under v-updates for the class of queries Q. 5. Any family F that satisfies PrXML {mux,det} ⊑ v F is closed under v-updates for any class of queries.

	Proposition 7.13 1. Let F be a family of p-documents that is closed with respect to relabeling of ordinary nodes. If F is closed under v-updates (respectively, determinis-tic v-updates) for the class of restricted single-path queries, then it is closed under o-updates (respec-tively, deterministic o-updates). 2. If F is a family of documents (tractably) closed un-der deterministic o-updates, then it is (tractably) closed under deterministic v-updates for restricted single-path queries. 3. Proof 1. Suppose F is closed under v-updates (the proof is the same for deterministic v-updates) for the class of restricted single-path queries. Let P ∈ F and τ o be an o-update. Let ϕ be a function that maps each ordinary node of P to a unique label (ϕ -1

This is an oversimplification-see Section 3.1 for the precise details.

It may seem that using det nodes is redundant, but actually they increase the expressive power when used together with some of the other types.

Note that P denotes a p-document, whereas P (i.e., without the tilde) is the random variable that denotes a document generated from P by the two-step probabilistic process.

By definition, if a node of a p-document exists in two different documents, then it has the same label in both.

In the probabilistic documents of[START_REF] Van Keulen | A probabilistic XML approach to data integration[END_REF], the root is distributional. We can assume that a dummy ordinary node is added for compliance with the definition of p-documents.

Note that Trio allows annotating tuples with arbitrary propositional formulas. An efficient translation into a PrXML {cie} tree requires such formulas to be in DNF. Allowing arbitrary formulas as conditions on distributional nodes makes query processing less efficient, as discussed in[START_REF] Senellart | Comprendre le Web caché. Understanding the Hidden Web[END_REF].

We consider only here the data complexity, i.e., the query is not considered to be part of the input.

The work of Abiteboul and Senellart was supported by the Agence Nationale de la Recherche under grant Docflow O6-MDCA-005, and by the Webdam Grant of the European Research Council.

Some of the work of Benny Kimelfeld was done while he was at

The Hebrew University.

The work of Kimelfeld and Sagiv was supported by The Israel Science Foundation (Grant 893/05).