Michael Benedikt
email: michael.benedikt@comlab.ox.ac.uk

Evgeny Kharlamov
email: kharlamov@inf.unibz.it

Dan Olteanu
email: dan.olteanu@comlab.ox.ac.uk

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

Probabilistic XML via Markov Chains *

We show how Recursive Markov Chains (RMCs) and their restrictions can define probabilistic distributions over XML documents, and study tractability of querying over such models. We show that RMCs subsume several existing probabilistic XML models. In contrast to the latter, RMC models (i) capture probabilistic versions of XML schema languages such as DTDs, (ii) can be exponentially more succinct, and (iii) do not restrict the domain of probability distributions to be finite. We investigate RMC models for which tractability can be achieved, and identify several tractable fragments that subsume known tractable probabilistic XML models.

We then look at the space of models between existing probabilistic XML formalisms and RMCs, giving results on the expressiveness and succinctness of RMC subclasses, both with each other and with prior formalisms.

INTRODUCTION

Uncertainty is inherently ubiquitous in today's data, and can take the shape, for instance, of measurement errors in scientific experiments or sensor readings [START_REF] Ré | Event queries on correlated probabilistic streams[END_REF] or typographical errors in manually entered data [START_REF] Antova | 10 10 6 worlds and beyond: Efficient representation and processing of incomplete information[END_REF].

The clear demand has spurred much research activity around managing uncertain relational data, using a wide range of models and processing techniques, e.g., [START_REF] Ré | Event queries on correlated probabilistic streams[END_REF][START_REF] Antova | 10 10 6 worlds and beyond: Efficient representation and processing of incomplete information[END_REF]. Uncertain XML data has also received attention, e.g., [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF][START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF], albeit less than in the relational case. XML is nevertheless the de facto model for Web data, and uncertainty is commonplace in a Web context: It arises from unreliability of Web data sources, errors in automated Web information extraction tools, or imprecision in integration of XML data from sources of varying structures and vocabularies.

Existing models for uncertain XML have emerged as generalizations of concrete documents with additional structure to capture uncertainty. This paper discusses a different ap-proach, adapting existing probabilistic word models to XML. We adapt Recursive Markov Chains (RMCs) [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF] and restrictions thereof to define probabilistic distributions over XML documents. RMCs are extensions of the standard Markov chains, i.e., of graphs with edges labeled with probabilities and that define processes evolving via independent choices at nodes. The extension consists of a notion of subroutine and the runs of RMCs have a natural hierarchical structure, and thus are interpretable as nested words or trees.

The motivation behind our investigation is threefold. Firstly, we argue that RMCs are a more natural formalism to model probability distributions over XML documents than existing representation systems proposed in the literature, called hereafter PrXML [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF]. Previous PrXML systems are designed to represent finite probability spaces, where the sizes of the representation and of each represented XML document have the same order of magnitude. RMCs capture these systems, yet they can do much more. We study a space of RMC representation systems that are wide, i.e., they do not impose a bound on the width of represented documents, and also deep in that they do not restrict the depth of the documents. This ability to represent XML documents whose sizes are not bounded by the size of the representation makes RMCs more succinct and more expressive than existing PrXML systems, and is the key ingredient needed to express probabilistic versions of XML schema languages such as DTDs.

Secondly, PrXML does not represent the limit of tractable query evaluation. The largest prior class of tractable queries is the model PrXML exp that has tractable evaluation for queries in the expressive query language of Monadic Second-Order logic (MSO) [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF]. Though unrestricted RMCs are not known to be MSO-tractable, we show that important restrictions are tractable under fixed-cost arithmetic and others are tractable in the usual bit-cost arithmetic model. Our work thus provides models that are much more expressive and succinct than prior classes, but retain tractability.

Thirdly, by looking at RMCs we connect questions on probabilistic XML to the rich set of tools and techniques available from the study of computational issues surrounding Markov models. This allows existing results and algorithms to be applied. Techniques for learning and analyzing variants of RMCs have been developed in several communities: hidden Markov models and stochastic context-free grammars are variants studied within machine learning and computational linguistics, while probabilistic automata have been investigated from the point of view of verification.

Our aim in this work is to understand and quantify the inherent tension between three fundamental aspects of prob-abilistic XML representation systems: expressiveness, succinctness, and tractability of query evaluation. To this end, we provide a map of restrictions to the RMC model that exhibit different levels of expressiveness, succinctness, and tractability. At one end of this map we find PrXML models from the literature [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF] that are fully tractable, yet narrow and shallow, i.e., they bound the depth and the width of the represented XML documents, and only have a finite number of possible worlds. At the other end, we have unrestricted RMCs that are wide and deep, with infinitely many possible worlds, and where tractability of query evaluation would require a fundamental breakthrough in numerical evaluation. In between, we define RMC restrictions that remain narrow and shallow, yet trade full tractability for succinctness, or remain fully tractable even if they can be exponentially more succinct than existing PrXML models. Also, we show there are fully tractable RMC restrictions that are wide and shallow, and therefore strictly more expressive than PrXML. Moreover, we find wide and deep models that preserve tractability under fixed-cost arithmetic.

To sum up, the contributions of this paper are as follows. (i) We first show how recursive Markov chains can be turned into a representation system for probabilistic XML that allows arbitrarily deep and wide documents, and that most existing probabilistic XML models are restrictions of RMCs (Section 3). (ii) We then propose restrictions of the general RMC model for which MSO tractability (with respect to data complexity) can be achieved. In particular, we show in Section 4 that the so-called hierarchical Markov chains are tractable under fixed-cost arithmetic, and tree-like Markov chains are tractable in the usual bit-cost arithmetic. The latter result subsumes early MSO tractability results given in [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF]. (iii) We explore the space of representation systems within our tractable fragments, comparing their expressiveness and succinctness (Section 5). The yardstick particularly useful to differentiate among them is the ability to represent succinctly wide documents, deep documents, and probability spaces with worlds that have probabilities double-exponentially close to 1. (iv) The tractability results mentioned above are for data complexity and MSO. In Section 6, we complement them with combined complexity results for our RMC-based models and three query languages: tree-pattern queries, forward navigational XPath, and MSO.

PRELIMINARIES

XML documents (or documents for short) are ordered, unranked, labeled trees. Given a document d, the set of nodes and the set of child edges are denoted by V(d) and C(d) respectively. We use ≺ to denote the strict total order over nodes of a document, root(d) for the root of d, L for the finite set of labels, and lbl(v) ∈ L for the label of a node v. We do not distinguish between labels and values here. The notions of child, parent, leaf, descendant, ancestor have their standard meaning.

Two documents d1 and d2 are isomorphic, denoted d1 ∼ d2, if one can be obtained from the other by replacing nodes with some other nodes while preserving labels and the order of the nodes. Formally, d1 ∼ d2 if there is a bijection ϕ : V(d1) → V(d2), such that for all v1, v2 ∈ V(d1), (i) lbl(v1) = lbl(ϕ(v1));

(ii) (v1, v2) ∈ C(d1) if and only if (ϕ(v1), ϕ(v2)) ∈ C(d2); and (iii) v1 ≺ v2 if and only if ϕ(v1) ≺ ϕ(v2).
We define a probabilistic XML space (or px-space for short) as a probability distribution over a set of non-isomorphic documents, called the domain.

A probabilistic XML representation system, or probabilistic XML model, is a pair (S, • ) where S is a set of representations S, (e.g. p-documents, RMCs, as presented later) and

• , the possible-world semantics of S, is a function mapping every element of S to a px-space. If there is no ambiguity on the possible-word semantics, we simply write S.

A system S is deep if there exists S ∈ S such that for all k 1, there is a document in the domain of S whose height (i.e., maximum distance from the root to a leaf) is at least k; otherwise, it is shallow. A system S is wide if there exists S ∈ S such that for all k 1, there is a document in the domain of S whose width (i.e., number of leaves) is at least k; otherwise it is narrow. Assuming all representations of a system S have a finite set of labels (which is the case of all those discussed in this work), they have finite domain if and only if S is both shallow and narrow.

Let S, S ′ be two systems. We say that S is translatable to S ′ , denoted S ⊑ S ′ , if, for every S ∈ S, there exists S ′ ∈ S ′ such that the probability distributions given by the px-spaces S and S ′ are the same (up to document isomorphism). If there is a polynomial-time procedure to obtain a representation in S ′ for every representation in S, we say that S is efficiently translatable to S ′ and denote S ⊑ poly S ′ . If S ⊑ S ′ and S ′ ⊑ S then we denote S ≡ S ′ . Similarly, if S ⊑ poly S ′ and S ′ ⊑ poly S, then S ≡ poly S ′ .

Given a representation S in a system, a query q over S is a function mapping every document d in the domain of S to a Boolean. We write d |= q for q(d) = true. The quantitative probabilistic evaluation problem for a query q and a representation S, is to determine the probability that q maps documents in S to true: Pr(S |= q) = (d,p)∈ S , d|=q p.

A query language L is a collection of queries. A system S is tractable for L if for any q ∈ L there is a polynomialtime algorithm that takes as input S ∈ S and outputs the solution to the quantitative evaluation problem for q and S. Following [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF], ra-tractability is tractability in case of fixedcost rational arithmetic, i.e., all arithmetic operations over rationals take unit time, no matter how large the numbers.

Monadic second-order logic over documents (MSO) is the logic built up from unary predicates for the labels, the binary descendant relation Descendant, the ordering relation ≺, and free unary predicate variables, via Boolean operators and first and second-order quantifiers ∃x, ∃S. The semantics of MSO is standard [START_REF] Thomas | Languages, automata, and logic[END_REF]. MSO is a natural logic for documents, since any MSO formula can be converted into a bottom-up tree automaton that accepts a document if and only if the document satisfies the formula. It is more expressive than other XML query languages such as tree-pattern queries with Boolean operators [START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF] or XPath.

We want to reinterpret probabilistic models on words to get distributions over documents. To this effect, we use a standard encoding of a document d with labels in L as a (well-formed) string over the language Tag(L), which consists of the symbols, called tags, l and /l for each l ∈ L.

We define the XML representation systems PrXML mux,det and PrXML exp , whose elements are called p-documents [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF]. A p-document is a document with two types of nodes. Distributional nodes are only used to define the probabilistic process that generates random documents-they do not actually occur in the output of the process. Ordinary nodes have labels and may appear in the generated documents. We require the leaves and the root to be ordinary nodes. Formally, a p-document is an unranked, ordered, labeled tree. Each node has a unique identifier v and a label µ(v) in L∪{exp(Pr)}∪{mux(Pr)}∪{det}. We consider distributional nodes that define discrete probability distributions Pr over the subsets of their children. In the case of mux nodes, we impose that all subsets have cardinality less than or equal to 1, that is, we select either no children at all, or a single child. A det node deterministically chooses all its children.

The semantics of a p-document P, denoted P , is the px-space obtained from the following randomized three-step process (see [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF] for a more detailed presentation): (i) Independently for each exp(Pr) node, we select a subset of its children (according to the corresponding probability distribution Pr) and delete the other children and the entire subtrees underneath. Independently for each mux(Pr) node, we select either zero or one child (according to Pr) and delete the other children and the entire subtrees underneath. We do not delete any children of det nodes. The probability of this run of the process is defined as the product of all choices. (ii) We then remove each distributional node, connecting each ordinary node with its closest ordinary ancestor. (iii) The resulting px-space is formed of arbitrary representatives of each isomorphism class of the documents obtained after step (ii). The probability of a document is the sum of probabilities of every run that generated an isomorphic image of it. Note that because we consider all possible runs, the order of the choice made in step (i) is irrelevant.

We denote classes of p-documents by PrXML with the allowed types of distributional nodes as superscripts. We recall the following results from [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF]: PrXML mux cannot represent all finite distributions of documents, yet PrXML mux,det can, and PrXML mux,det ⊑ poly PrXML exp . Also, PrXML exp is tractable for MSO [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF].

RECURSIVE MARKOV CHAINS

We now adapt recursive Markov chains from [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF] to the context of document generation, and study their relationship with prior probabilistic XML models. For each u that is neither a call port nor exit node we have {v|(u,pu,v ,v)∈δ i } pu,v = 1. We distinguish one component in A, say A0, as the initial component, and within that component an initial node a0 ∈ N en 0 and a set of final nodes F0 ⊆ N ex 0 . We also require that no box in the RMC is mapped to A0, and that µ(A0) = ε.

Definition 1. A recursive Markov chain A, is a tuple A = (A0, • • • , A k , µ),
RMCs can be depicted graphically as follows: The components are represented as rectangles containing Markov chains with inner rectangles corresponding to boxes. The name of the component each box is mapped to is given inside the box. In the following figures, the initial component is the one at the top-left, and it has a single initial node and a single final node. The name of a component is given above the rectangle, along with its label.

Example 2. Figure 1 partially shows an RMC Aex with four components D, P , N , and T . For instance, the label of D is µ(D) = directory. D either calls P with probability 0.8 or exits with probability 0.2, and this choice can occur again after returning from the call. The components N : name and T : phone are not depicted; both have a single edge going from the entrance to the exit with probability 1.

The δ-transitions for D are: (a0, 1, u1), (u1, 0.2, t), also (u1, 0.8, (P, en)), and ((P, ex), 1, u1), where t is the exit node, u1 is the only node pointed to by a0, (P, en) is the call port for box P , and (P, ex) is the return port for box P .

Intuitively, a run of an RMC generates a document d in a top-down fashion where a call of a box (corresponding to a component) labeled l inside another box (corresponding to a component) labeled l ′ generates a node l in d that is a child of l ′ . If a box is labeled ε, then it generates nothing, though calls within its component may still generate labels. We next formalize this via an alternative description of RMCs.

A vertex of Ai is either a node in Ai, a call port, or a return port. Let Vi denote the set of all vertices of Ai. Thus, the transition relation δi is a set of probability-weighted directed edges on Vi. Let V = i Vi, and N , B, Y , and δ be the unions of the corresponding sets. We denote by qu,ex the probability that starting with u one eventually reaches an exit ex in the same component as u.

Definition 3. An RMC A defines a global (denumerable)

Markov chain MA = (St, ∆) as follows:

The

global states St ⊆ B * × V × (Tag(L) ∪ {ε})
of MA are triples of the form (β, u, α), where β is a (possibly empty) sequence of boxes from B that represents the stack of pending recursive calls, u is the current vertex of A, and α is an optional tag.

The function ∆ defines probability-weighted directed edges between global states ∆ : The initial global state is st0 = (A0, a0, µ(A0) ) and the final ones are (A0, q f , /µ(A0) ) for each q f ∈ F0.

(St × St) → [0, 1]: (i) If (u, pu,v, v) ∈ δ,
MA can be seen as an "unfolding" of A. This construction indeed forms a Markov chain in the usual sense: The sum of outgoing probabilities from each global state is 1.

Example 4. The δ-transitions of Aex induce, for instance, these global ∆-transitions: (ε, a0, directory )

1 → (D, u1, ε), (D, u1, ε) 0.8 → (D, (P, en), ε), (D, (P, en), ε) 1 → (DP, en, person ), (DP, ex, ε) 1 → (D, (P, ex), /person ).
The notions of path between two states of MA and state reachability are standard. Since the choices at any two nodes are independent of each other, the probability Pr(p) of a path p is the product of all transition probabilities along p. With every global state g = (β, (b, ex), α), we set LabOf(g) = α. Given a path p, we let LabOf(p) = p0 . . . pn be the string in Tag(L) * formed by concatenating each LabOf(pi), treating ε as the empty string. Given two global states st, st ′ the probability of transitioning from st to st ′ is defined as:

Pr(st, st ′ ) = path p from st to st ′ Pr(p).
The probability of a string α ∈ Tag(L) * is

Pr(α) = final global state st path p from st 0 to st with LabOf(p)=α
Pr(p) .

The total probability of all finite strings that reach a final state may be strictly less than one: this can happen because strings reach states from which it is impossible to reach a final state, or because with non-zero probability the computation of the Markov chain never returns to a global state with no pending boxes. As shown in [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF], one can compute in PSPACE the probability that an RMC generates a finite string. In the case that this is non-zero, we normalize the probability of any string by this number, thus gaining a probability space on strings. For the tractable classes of RMCs we will study later in this work, the computation of this probability is also tractable.

For a given RMC A, let us denote by L(A) the set of strings that have non-zero probability. It is easy to see that any α ∈ L(A) is a well-formed encoding of a document. Consequently, the set of all documents corresponding to L(A) together with the corresponding probabilities define a px-space associated to A that we denote by A . The corresponding probabilistic XML model is denoted RMC.

Example 5. Consider an encoding of the XML skeleton of a directory with two persons, each with two phone numbers: Existing probabilistic XML models such as PrXML mux,det can be efficiently translated to RMCs. Section 5 discusses efficient translations of other PrXML models into RMC. Proposition 6. PrXML mux,det ⊑ poly RMC.

directory
It is known that verifying MSO properties of RMCs over strings is in PSPACE (this follows from [START_REF] Etessami | Algorithmic verification of recursive probabilistic state machines[END_REF]). Results later in the paper show that the same holds for verifying MSO properties of random documents represented by RMCs.

Unfortunately, even for basic problems, RMCs are not known to be tractable. Computing reachability probabilities in RMCs is as difficult as the square-root sum problem, a well-known problem in numerical computation [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF]. SQRT-SUM asks, given natural numbers k and d1, • • • , dn, whether i √ di k. SQRT-SUM is known to be in PSPACE, but its containment even in NP is unknown and has been a long-standing open problem. In [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF] it is shown even approximating the probability of termination of an RMC to within a fixed rational is as hard as the square-root sum problem. Hence tractable query evaluation for this model would require a breakthrough in numerical computation.

TRACTABLE RMC FRAGMENTS

In this section, we propose restrictions of the RMC probabilistic XML model for which some form of tractability of MSO can be achieved. We first show ra-tractability for the class of hierarchical RMCs [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF], which are wide and shallow. We then show full tractability for tree-like RMCs, which are also wide and shallow. The latter generalizes an existing result on tractability of the PrXML mux,det model [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF], which is narrow and shallow and less expressive than tree-like RMCs.

Hierarchical RMCs.

Definition 7. An RMC A is hierarchical if none of its components can eventually call itself, i.e., in MA all states of the form (βbγb, u, α) (where b is a box, β and γ are sequences of boxes) are unreachable for any u and α.

For example, Aex is hierarchical. We denote by HMC the probabilistic XML representation system given by hierarchical RMCs. By forbidding recursion across components, HMC is shallow. However, it can be wide, since it allows paths from return ports to call ports within components.

Theorem 8. HMC is ra-tractable for MSO. This is a non-trivial extension of a result from [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF] which states that computing transition probabilities in HMCs is ra-tractable. The algorithm, detailed in Appendix C, uses the construction of a product automaton of a pushdown automaton equivalent to the HMC and a streaming tree automaton representing the MSO query. We even show a stronger result: ra-tractability for the more expressive, deep representation system PLRMC of piecewise-linear RMCs introduced in [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF] (see Appendix C for details).

Tree-like Markov chains. How can we move from tractability in a unit-cost arithmetic model to full tractability? For our representation systems, this move corresponds to a transition to exponentially less succinct systems. This is the case of HMC, which is ra-tractable, and a fully tractable yet less succinct subclass of it called TLMC. In short, the latter can be obtained from the former by forbidding call sharing. Recall that the call graphs of hierarchical Markov chains are acyclic. Call sharing means that several boxes can call (i.e., be mapped to) the same component. It follows from the definition that there is no recursion. This defines a shallow and wide probabilistic model, TLMC, that is a restriction of HMC. The RMC Aex is a tree-like RMC. Note also that the translation of PrXML mux,det into RMC used in the proof of Proposition 6 (see the appendix) produces a tree-like Markov chain, whose components are moreover acyclic. An example of RMC that is not tree-like is given in Theorem 3.2, part (4) of [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF] (see also Figure 5 in the appendix).

The global Markov chain defined by a tree-like Markov chain A is finite, and its size is linear in the size of A. A consequence of this is that all reachability probabilities have polynomial size and can be computed in polynomial time as for standard Markov chains. The same automata-based algorithm as in the proof of Theorem 8 reduces calculating the probability of MSO queries over TLMC to calculating reachability probabilities; by combining these two insights, we get an algorithm for efficiently calculating query probabilities: Theorem 10. TLMC is tractable for MSO.

Unordered models. The existing literature on probabilistic XML models usually assumes unordered documents. We can see RMC, and all other models presented in this paper, as unordered models. Specifically, let A ∈ RMC and L(A) be the set of generated strings; the unordered interpretation of A is the set of unordered documents d (with probability Pr(d)) for which there exists α ∈ L(A) a possible encoding of d under any ordering (Pr(d) is then the sum of probabilities of all such α's). We note that the data complexity results obtained in the ordered setting extend to the unordered one: Proposition 11. Let S be any ordered probabilistic XML representation system, and q any MSO query that does not make use of the order predicate ≺. The complexity of the quantitative evaluation problem for q and S ∈ S is the same as the complexity of the quantitative evaluation problem for q and the unordered interpretation of S.

BETWEEN P-DOCUMENTS AND RMCS

In the previous section we have shown the existence of tractable restrictions of RMCs. We now explore the space of models in between PrXML and RMC. RMC models extend PrXML in expressiveness in several dimensions. Clearly RMC is deep while PrXML is shallow, it is wide while PrXML is narrow. In addition, in RMCs a component may be called from multiple places, while in PrXML the topology is a tree: a node has a single parent. Finally, by allowing multiple exits in components, RMC allows a state to be passed upward from child to parent, while in PrXML the processing is completely top-down (this is analogous to the distinction in attribute grammars between synthesized and inherited attributes). Summing up, we focus on four dimensions: 1. depth, 2. width, 3. sharing, 4. number of exits.

These dimensions, as well as RMC restrictions that are distinguished thereby, are shown in Figure 2. The left part shows the first three dimensions. In terms of depth the models can be either wide or shallow, where shallowness corresponds syntactically to being hierarchical. In terms of width the models can be either wide or narrow, and narrowness can be syntactically enforced by requiring the RMC to be acyclic, i.e., every component is an acyclic graph.

In the following we denote the acyclic subclasses of HMC and TLMC as AHMC and TLAMC, respectively. In terms of sharing the models can either allow reuse of components in multiple boxes or not. Finally, the models can be either 1-exit or multi-exit, where an RMC is 1-exit if each of its components has one exit node, and multi-exit otherwise. We denote the fact that all the RMCs in a class are 1exit with the 1-prefix. Observe that the ability to pass information up corresponds to being multi-exit. We use two cubes to represent the fourth dimension: the central cube in Figure 2 covers 1-exit classes and the rightmost one covers the corresponding multi-exit classes.

Note the empty corners of the cubes, labeled [none]: Deep models without sharing cannot be obtained as RMC restrictions, and deep models can also generate wide documents, since RMC components can be labeled with ε. The arrows in Figure 2 indicate that the pointing model is a restriction of the pointed one.

The main message of the figure is the insights into the trade-off between succinctness and tractability of MSO, at least for the models considered:

(i) Tractability degrades to ra-tractability by adding sharing. As seen further, this amounts to a gain in succinctness by being able to represent worlds with probabilities doubly exponentially small. (ii) Neither the width nor the number of exits influences tractability. As we see further in this section (and in Figure 3), for some classes of RMCs multiple exits exponentially increase succinctness. (iii) Going from shallow to deep affects tractability.

We now investigate in detail the relationship of the classes in the cubes with each other, and with known PrXML models.

1-exit vs. Multi-exit Models. One question is whether multi-exit models can be more succinct than 1-exit ones. As we state next, it is the case, except for tree-like RMCs.

Proposition 12. 1. TLAMC ≡ poly 1-TLAMC and TLMC ≡ poly 1-TLMC. 2. Let S be one of AHMC, HMC or RMC. Then S ≡ 1-S but S ≡ poly 1-S does not hold.

In the appendix we give an efficient algorithm for transforming multi-exit RMCs to single-exit ones that preserves acyclicity: the idea is roughly to replace one multi-exit component with several copies, one for each exit, with the probability of going into the original component distributed among the copies. There is no blow-up in the size of the structures, the only issue is to be able to calculate the probability of entering each copy-this can be done efficiently for TLMC using the efficient model-checking algorithm for TLMC, but cannot be done for the less tractable HMC models.

We note that 1-exit RMCs are important due to their close relationship with stochastic context-free grammars (SCFGs) [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF], which have been much studied in connection with computational linguistics. Parse trees of a SCFG together with their probabilities can be seen as a probabilistic space of XML documents, which gives a way to adopt SCFGs as a probabilistic XML representation system. Due to lack of space we do not present the SCFGs formally, and refer the reader to [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF]. As shown there, there are linear transformations from SCFGs to 1-exit RMCs and vice-versa. These results carry over to SCFG as probabilistic XML representation systems. That is: SCFG ≡ poly 1-RMC. This extends to 1-AHMC ≡ poly HSCFG, where HSCFG denotes the shallow (i.e. non-recursive) variant of SCFGs.

Tree-Like vs. Shared. While multiple exits do not always increase succinctness, the situation is different for sharing. We first discuss sharing for RMCs and then proceed to PrXML. Note that sharing in the former case is different in nature from the one in the latter case.

For RMCs, sharing means that a component can be called from multiple places and this adds succinctness: Proposition 13. TLMC ⊑ poly 1-HMC, but it does not hold that 1-HMC ⊑ poly TLMC.

Proof. 1-HMC can express px-spaces with doubly exponentially small probabilities of documents that are not computable in polynomial time (a p-document from Example 6.1 in [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF] can be translated into such a one-exit hierarchical Markov Chain). At the same time, TLMC expresses px-spaces where the probability of every document is computable in polynomial time. The reason is any TLMC can be expanded in polynomial time into a regular Markov chain, where reachability probabilities correspond to probabilities of documents generated by the original TLMC. Moreover, reachability probabilities in regular Markov chains can be computed by solving a system of linear equations, hence in polynomial time. Therefore, 1-HMC is at least exponentially more succinct than TLMC, while both models have the same expressive power since it is possible to expand a hierarchical Markov chain into a tree-like one by duplicating components used more than once as boxes.

Similarly (it can be shown with the same example from [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF]), 1-AHMC is exponentially more succinct than TLAMC.

For PrXML, sharing comes from a generalization of PrXML exp and PrXML mux,det models (Section 2) and consists in introducing sharing of nodes in the trees. We now investigate their place in the hierarchy of RMC subclasses that we have introduced.

P-documents with sharing, PrDAG, are defined as rooted directed acyclic graphs (DAGs) with the possibility of having multiple edges between two given nodes and a total ordering on the edges outgoing from a given node, that make use of both ordinary and distributional nodes, as with regular p-documents. The semantics of a p-document with sharing is defined as the semantics of the regular p-document obtained by repeatedly duplicating subtrees whose root has more than one incoming edge until a tree is obtained. That is, for any node that has n incoming edges in the DAG we introduce n copies of it in the corresponding p-document, one per edge. As with p-documents, we denote with, for example, PrDAG mux,det the class of p-documents with sharing that use only mux and det distributional nodes. It turns out that PrDAG exp is more succinct than PrXML exp . Proposition 14. PrXML exp ⊑ poly PrDAG exp , but it does not hold that PrDAG exp ⊑ poly PrXML exp . This already follows from [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF], where a partial form of sharing (allowing duplicated edges) has been noted, in particular, to make the probability of a possible world potentially doubly exponentially small, which requires an exponential size to be represented.

The following shows that all shallow and narrow models with sharing and no passing of information bottom up are equally expressive and succinct.

Proposition 15. PrDAG mux,det ≡ poly PrDAG exp ≡ poly HSCFG.

Note that all these models occupy the back, bottom, left corner in the middle cube of Figure 2. Translation between these models is relatively straightforward and can be done in linear time.

PrXML vs. subclasses of RMC. We finally give a precise characterization of the PrXML mux,det position in the hierarchy of models. Given that PrXML mux,det models are shallow, narrow, and tree-like, one might think they occupy the lowest point in the lattice, and are hence essentially the same as TLAMC. Surprisingly, this is not the case: Theorem 16. PrXML mux,det ⊑ poly 1-TLAMC, but it does not hold that 1-TLAMC ⊑ poly PrXML exp . The key is that TLAMC processes can still pass a limited amount of information over long distances in a tree, while PrXML cannot.

Figure 3 summarizes the expressive power and relative succinctness of the various models introduced in this article. The solid (resp., dashed) arrows indicate there is a polynomial-time (resp., only exponential-time) translation from the pointing model to the pointed one. The left-hand side shows if (polynomial-time) translations exist between the narrow and shallow representation systems, i.e., it zooms on the bottom-left edge of the cubes of Figure 2. An open problem is whether PrXML exp can be efficiently translated into PrXML mux,det (already stated as open in [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF]) or into TLMC. The top-right of Figure 3 of Figure 3 compares deep and wide models, the ones on the back top-right vertex of the cubes. For readability, translations across narrow and wide models are not shown, but they are straightforward: TLAMC, 1-AHMC, and AHMC can be translated in polynomial time to, respectively, TLMC, 1-HMC and HMC (and no translation exists in the other direction).

Apart from these and the open questions discussed above (shown with a "?"), the figure is complete in the following sense: there is a (solid) path between any two models if and only if there is a (polynomial-time) translation.

COMBINED COMPLEXITY

In Section 4 we have discussed data complexity of query evaluation for a very rich query language, MSO. We now comment on the combined complexity of query evaluation. We focus here only on the models that we have shown ratractable. For the most general model, RMC, the best we can say about the complexity of even simple queries (e.g., tree patterns) is that it is in PSPACE, via reduction to the existential theory of the reals (by iterating over an exponential number of automata whose union is equivalent to the query, and then applying the PSPACE algorithm of [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF] for computing reachability probabilities in RMCs).

Lowest combined complexity: tree-pattern queries. For tree patterns, the complexity of querying any of our tractable models is in FP #P (the class of computation problems that can be solved in polynomial time using a #P oracle). Tree patterns can be converted to a disjoint union of polynomialsize deterministic tree automata (by guessing an ordering of siblings), where each tree automaton is of linear size in the pattern. #P-hardness of tree-pattern evaluation holds even for PrXML mux,det [START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF].

Highest Combined Complexity: MSO. For full MSO the complexity of satisfiability over words is known to be nonelementary [START_REF] Stockmeyer | The Complexity of Decision Problems in Automata and Logic[END_REF]. Hence, determining whether an MSO query has positive probability is non-elementary, in any of our wide models (e.g., HMC, TLMC).

If we turn to shallow and narrow models, we note that the combined complexity of MSO query evaluation is PSPACEcomplete for on PrXML mux,det . Membership in PSPACE follows because each particular isomorphism type of a tree is of size linear in the representation, and we can evaluate an MSO query in PSPACE combined complexity over any fixed tree [START_REF] Libkin | Elements of Finite Model Theory[END_REF]. Thus we can determine the probability of a given query by simply generating every possible world d, recording the probability p of generation, evaluating the query in PSPACE on d, and then adding p to the running total if the query is satisfied. PSPACE-hardness is clear because the evaluation of MSO (indeed, even first-order logic) over a fixed tree is PSPACE-hard [START_REF] Libkin | Elements of Finite Model Theory[END_REF]. The same PSPACE-completeness result holds for any of our representation systems such that each representation S has a domain consisting only of documents of size polynomial in S. In particular, the same holds for PrXML exp and TLAMC.

For AHMC, representations S may generate documents at most exponential in the size of S. Thus, MSO probability evaluation is in EXPSPACE, again simply by iterating over documents and updating the probability. A lower bound can be obtained using techniques from [START_REF] Frick | Query evaluation on compressed trees[END_REF] where it is shown that the combined complexity of MSO evaluation over compressed trees is NEXPTIME-hard. The result holds even for the restricted fragment of existential MSO. By adapting the argument of [START_REF] Frick | Query evaluation on compressed trees[END_REF] and taking into account the fact that the probability evaluation problem is essentially a counting problem, we can show it is #EXP-hard: Proposition 17. Given an existential MSO formula q and S ∈ AHMC, computing Pr(q |= S) is #EXP-hard.

In between: Forward Navigational XPath. An intermediate language consists of forward navigational XPath (or FNXPath) filters, where navigational indicates that data joins are excluded [START_REF] Marx | Semantic characterizations of navigational XPath[END_REF], and forward that we only consider the child and descendant axes. We refer to [START_REF] Marx | Semantic characterizations of navigational XPath[END_REF] for detailed syntax and semantics.

We can consider each filter to define a Boolean query over documents; the query checks whether the root of the document satisfies the filter. It is known from [START_REF] Gottlob | Monadic Datalog and the expressive power of Web information extraction languages[END_REF] that FNXPath can be evaluated in polynomial time on XML documents. From this it follows that FNXPath can be evaluated in FP #P on PrXML mux,det models (the argument is similar to the one given in [START_REF] Grädel | The complexity of query reliability[END_REF] for computing the probability of a logical formula). Hence, it is FP #P -complete. The same argument shows that FNXPath is in FP #P for any formalism in which representations generate only trees of polynomial size.

Because satisfiability of FNXPath is PSPACE-hard [START_REF] Benedikt | XPath satisfiability in the presence of DTDs[END_REF] even on trees of fixed depth, the evaluation problem for FNXPath is PSPACE-hard for any of our unbounded models. In addition, [START_REF] Frick | Query evaluation on compressed trees[END_REF] shows that evaluation of FNXPath is PSPACE-hard on compressed documents, which are subsumed by AHMC and thus by HMC. Thus query evaluation for these formalisms is PSPACE-hard. We provide in the appendix an algorithm for FNXPath that is in PSPACE with respect to query complexity on AHMC.

Theorem 18. There is a query evaluation algorithm for FNXPath on AHMC that runs in PSPACE in the query and uses a number of arithmetic operations that is polynomial in the model size.

The key to the algorithm is that we do not calculate the probability of every tree, but only the probability of every "tree type", where a type abstracts trees according to which subexpressions of the the FNXPath expression it satisfies. The algorithm calculates the probability of the type by traversing the AHMC top-down, calculating probabilities for all compatible types of child subcomponents and combining them using the transition probabilities.

PSPACE combined complexity is arguably a sign that the tractability results in terms of data complexity of Section 4 apply in practice to non-trivial queries. The algorithm of Theorem 18 subsumes the well-studied case of tree-pattern queries, and applies to the most general narrow and shallow probabilistic XML representation system presented here.

DISCUSSION

Contribution. This work departs from the mainstream approach to probabilistic XML models, seen as XML documents with additional features. We propose new models based on variations of Markov chains, which go beyond the state-of-the-art in their ability to represent deep or wide documents, or worlds with probabilities double-exponentially small. This shift also gives new insights into tractability and expressiveness of the existing PrXML models.

The following models stand out in particular from the picture given in Figure 2: (i) TLMC because of its tractability in the usual bit cost arithmetic model together with its ability to represent wide trees; (ii) AHMC, a narrow and shallow model that is tractable in unit-cost arithmetic and that has PSPACE combined complexity; (iii) HMC, a wide model that is tractable in unit-cost arithmetic which is deep and also ra-tractable.

Applications. RMC can be seen as a probabilistic version of DTDs (or XML Schemas) and HMC as non-recursive DTDs. For example, consider the following DTD fragment describing an XML phone directory, with persons, each having a name and phone numbers:

<!ELEMENT directory (person*)> <!ELEMENT person (name,phone*)>
A probabilistic version of this DTD is Aex of Figure 1. An intriguing question is whether these probabilistic schemas can be applied to obtain more fine-grained models of collections of real-world documents which may not satisfy any nontrivial traditional (i.e., deterministic) schema. The learning algorithms available for SCFGs (e.g. [START_REF] Petrov | Learning accurate, compact, and interpretable tree annotation[END_REF]) can be applied here, although it remains to examine whether they can be tailored to produce output within particular subclasses that we have identified as interesting (e.g. tree-like).

One can also use our results to apply XML querying formalisms to the probabilistic trees given by SCFGs. The idea has been applied to querying the possible parses of a given string in [START_REF] Cohen | Querying parse trees of stochastic context-free grammars[END_REF]. Our results show that it is possible to query the (possibly infinite) collection of parse trees that can be produced by an SCFG language model using a powerful query language like MSO. One could, for instance, compute probabilities that a phrase having a specific structure appears in a corpus generated by the grammar.

APPENDIX A. RELATED WORK

A unified view of existing probabilistic XML models, in the form of p-documents, has been proposed in [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF]. Translations between families of p-documents, depending on the kind of distributional nodes allowed, are studied in detail in [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF]. Traditionally, probabilistic XML models have been unordered, shallow, and narrow. The first efficient algorithm for evaluating tree-pattern queries in PrXML mux,det has been proposed in [START_REF] Kimelfeld | Matching twigs in probabilistic XML[END_REF]; this has been extended to PrXML exp and Boolean combinations of tree-pattern queries in [START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF], and extended further to MSO queries in [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF] where Cohen et al. show how to run a deterministic bottom-up automaton on an ordered PrXML exp document. The same work introduces a limited form of sharing in p-documents (the possibility of re-using multiple times a given child), that is a restriction of the PrDAG exp model. Recent work [START_REF] Cohen | Querying parse trees of stochastic context-free grammars[END_REF] uses the techniques of probabilistic XML to compute the probability of a treepattern query over the set of parse trees of a given string in a stochastic context-free grammar. If the grammar has a specific property, a generalization of Chomsky normal form, it is possible to compute these probabilities in polynomial time. We stress, however, that the problem studied in [START_REF] Cohen | Querying parse trees of stochastic context-free grammars[END_REF] is fundamentally different from the work presented here: the probabilistic XML model is not the SCFG, but the SCFG together with an input string. And all possible worlds share the same set of leaf nodes, since possible worlds are all parse trees of this string.

Recursive Markov chains were introduced by Etessami and Yannakakis in [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF] as probabilistic versions of recursive state machines [START_REF] Alur | Analysis of recursive state machines[END_REF], used for the static analysis of programs and systems. An equivalent formalism, probabilistic pushdown systems, was introduced independently in [START_REF] Esparza | Model checking probabilistic pushdown automata[END_REF]. Some other stochastic formalisms from the literature (notably, treestructured quasi-birth-death processes) have been shown to be equivalent to RMCs [START_REF] Etessami | Quasi-birth-death processes, tree-like QBDs, probabilistic 1-counter automata, and pushdown systems[END_REF], while other still (quasi-birthdeath processes, probabilistic 1-counter automata) are a restricted class of RMCs [START_REF] Etessami | Quasi-birth-death processes, tree-like QBDs, probabilistic 1-counter automata, and pushdown systems[END_REF]. Stochastic (or probabilistic) context-free grammars are another example of widely used model (notably in natural language processing) that can be seen as a particular case of RMCs, specifically, 1-exit RMCs. While context-free grammars are as succinct as pushdown automata, probabilistic context-free grammars, though they generate the same probabilistic distributions as probabilistic pushdown automata, are exponentially less succinct [START_REF] Abney | Relating probabilistic grammars and automata[END_REF]. Algorithms for computing reachability probabilities in recursive Markov chains are presented in [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF]. This is extended in [START_REF] Etessami | Algorithmic verification of recursive probabilistic state machines[END_REF] to probabilities of verifying a given specification, through the construction of a product automaton, similarly to the construction we use to prove Theorem 8.

B. MATERIAL FOR SECTION 3

Proof of Proposition 6. Let P ∈ PrXML mux,det . We construct the corresponding RMC A as follows. The RMC contains one component Av for every node v of P. The component A0 corresponds to the root of P. Consider cases. (i) v is a regular (resp., det) node labeled a with m 0 children labeled a1, • • • , am. The corresponding component Av is given in Figure 4 (left), where µ(Av) = a (resp., µ(Av) = ε). (ii) v is a mux node with m children v1, • • • , vm and probabilities p1, • • • , pm. This corresponds to the component A ′ v in Figure 4, where µ(A ′ v ) = ε. This construction produces an RMC of a very restricted form, called 1-exit tree-like Markov chain (see Definition 9).

• • • • • • Av: a or ε Av 1 Av m → • • • → 1 1 • • • • • • A ′ v : ε Av 1 Av m • • • p1 pm

C. MATERIAL FOR SECTION 4

We show the ra-tractability of the class of piecewise-linear RMCs [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF], PLRMC. In order to introduce this class of models, we need the notion of call graph for RMCs, that is similar to call graphs in procedural programs. The call graph CGA of an RMC A has a node i for each component Ai of A and a directed edge from node i to node j if there are mappings from boxes of Ai to the component Aj. Definition 19. An RMC A is piecewise-linear if in every component Ai, for every path from an entry node to an exit node, there is at most one box which is mapped to a component in the same strongly connected subgraph of the call graph CGA as Ai.

PLRMC is deep, since it allows for recursion (for instance, the box within a component can be mapped to that same component), and also wide, since within a component there may be paths with several boxes from different strongly connected subgraphs of the call graph. The notion of piecewiselinearity is a generalization of the standard notion of linearity of context-free grammars, which allows at most one nonterminal on the right-hand side of each grammar rule; when adapted to RMCs, this constraint states that for every path from an entry node to an exit node, there is at most one box. It is easy to see that PLRMC also generalizes HMC.

Theorem 20 (Generalization of Theorem 8). PLRMC is ra-tractable for MSO.

To prove this result, we first introduce an alternate representation for RMCs in the form of probabilistic pushdown automata [START_REF] Abney | Relating probabilistic grammars and automata[END_REF]. We then show how to construct a product of this automaton with a tree automaton encoding the MSO formula, such that reachability of some state in the resulting automaton corresponds to the probability of the query. This is similar in spirit to what is done in [START_REF] Etessami | Algorithmic verification of recursive probabilistic state machines[END_REF] for model-checking RMCs with respect to a Büchi automaton. Definition 21. A probabilistic pushdown automaton (or pPDA) is a tuple P = (Q, Γ, q0, ∆, ν) that consists of a finite set of control states Q, a finite stack alphabet Γ, initial state q0 ∈ Q, a probabilistic transition relation ∆ with transitions of the form:

(q, γ) p,push(γ ′ ) ------→ q ′ , or (q, γ ′ ) p,pop ---→ q ′ , or (q, γ) p -→ q ′ ,
where q, q ′ ∈ Q, γ ∈ Γ ∪ {⊥}, γ ′ ∈ Γ, and p ∈ [0, 1] is the probability of the transition, and a functions ν mapping symbols of Γ to labels in L ∪ {ε}. For any state (q, γ) with outgoing transitions, transition probabilities sum up to 1.

Probabilistic pushdown automata are seen as a probabilistic XML model pPDA in the following way. Intuitively, a run of a pPDA generates a document d in a top-down fashion: if ν(γ) = a, ν(γ ′ ) = a ′ , and the top element of the stack is γ, then a push of γ ′ on top of γ, by means of the instruction push(γ ′ ), generates a node in d labeled a ′ as a child of the node labeled a. When the last child of a is generated, or when a is a leaf, the automaton pops γ from the stack and proceeds to generate siblings of a. If ν(γ) = ε, then neither pushing nor popping γ affects document generation. We consider the generation finished when a pop operation empties the stack. A pPDA assigns probabilities to runs, and thus to documents. We can also assign probabilities to runs that do not terminate on an empty stack. Thus for any state q ∈ Q, we can also talk about the probability of generating a partial document (d, n) in state q: by this, we mean the probability of generating a string ending in the closing tag of n in state q, such that the completion of this string with closing tags is the document d.

As shown in [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF], RMCs and pPDAs are essentially equivalent in the sense that there are linear translations from RMCs to pPDAs and the other way around such that there is some mapping from the states of the global Markov chain defined by each representation, with the same transition probabilities between states (see [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF] for a more formal statement). This equivalence very naturally extends to the probabilistic XML models defined by these representations.

Proposition 22. RMC ≡ poly pPDA.

It is well known that MSO queries can be converted to bottom-up deterministic tree automata [START_REF] Thomas | Languages, automata, and logic[END_REF]. In contrast, pPDAs work probabilistically, but generate input top-down. To prove Theorem 20, it will be more useful to convert the MSO query into an automaton of the same "form"-one that traverses the input in pre-order. A deterministic streaming tree automaton (DSTA) is an (accepting) pushdown automaton on strings (Q, Tag(Σ), Γ, q0, F, δ) where the input alphabet is the collection of begin and end tags over some alphabet Σ, Γ is the stack alphabet, q0 ∈ Q is the initial state, F ⊆ Q are the accepting states, δ is the transition function, and

• on input a there are only push transitions;

• on input /a there are only pop transitions. We run a DSTA on a document d by running it on its string representation in the usual sense. We can also run the DSTA on any prefix of this document string. By a run of a DSTA on d up until node n ∈ d, we mean on the substring up until the closing tag of n. We assume that our DSTAs have total transition functions, and hence for every DSTA A, document d and node n, there is a unique run of the automaton on d up until n, and we can talk about the state of A when run on (d, n). We use the following result from the literature on nested word automata and streaming tree automata. Fact 23. [START_REF] Gauwin | Streaming tree automata[END_REF] Every bottom-up tree automaton on ordered trees can be converted to an equivalent DSTA.

Given a pPDA A = (Q, Γ, q0, ∆, ν) and a DSTA A ′ = (Q ′ , tag(Γ), Γ ′ , q ′ 0 , δ ′ ) we can form the product A × A ′ , which is a pPDA with:

(i) states Q × Q ′ ; (ii) stack alphabet Γ × Γ ′ ; (iii) initial state (q0, q ′ 0 ); (iv) for every transition (q1, γ) p,push(γ ′ ) ------→ q2, and for every state q ′ 1 ∈ Q ′ with transition (q ′ 1 , γ ′ ) push(γ ′′ )

------→ q ′ 2 , a transition ((q1, q ′ 1 ), γ)

p,push(γ ′ ,γ ′′ )

---------→ (q2, q ′ 2 ); (v) for every transition (q1, γ) p,pop ---→ q2, and for every state q ′ 1 ∈ Q ′ with transition (q ′ 1 , /γ ) pop --→ q ′ 2 , a transition ((q1, q ′ 1 ), γ)

p,pop ---→ (q2, q ′ 2 ); (vi) for every transition (q1, γ) p -→ q2, and for every state q ′ ∈ Q ′ , a transition ((q1, q ′ 1 ), γ)

p,pop ---→ (q2, q ′ 2 ); (vii) labeling function ν ′′ with ν ′′ (q, q ′ ) = ν(q). This product has the following important property:

Lemma 24. Let A be a pPDA and A ′ a DSTA. The probability that A × A ′ generates a partial document (d, n) in state (q, q ′ ) is the probability that A generates a partial document (d, n) in state q and that the unique run of A ′ on d until n ends in state q ′ . In particular, determining the probability that A generates a document accepted by A ′ reduces to calculating reachability probability of states in A × A ′ .

Proof. This is proven by a direct transformation of runs in A × A ′ to pairs of runs of A and A ′ , where the transformation preserves probabilities.

We now give the intuition of our proof of Theorem 20. Given a piecewise-linear RMC M and an MSO formula F , we (i) construct (in linear time) a pPDA A equivalent to M (Proposition 22), (ii) translate F into a MSO formula F ′ over the stack alphabet of A, (iii) convert F ′ into a DSTA A ′ (Fact 23) and (iv) construct the product A × A ′ . It can be shown that the product is still a piecewise-linear RMC. We conclude by Lemma 24 and the ra-tractability of reachability probability computation in piecewise-linear RMCs [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF]. More formally:

Proof of Theorem 20. Let F be an MSO formula over documents labeled in L and M a piecewise-linear RMC. First construct from M (in linear time) an essentially equivalent pPDA (Q, Γ, q0, ∆, ν) as described in [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF]. We must now rewrite F so that the automaton constructed from it can directly be composed with this pPDA, even though some of the push transitions of the automaton do not produce any labels. To do this, we transform F into an MSO formula over documents labeled in Γ in the following way:

• Every subformula ∀xϕ is replaced with ∀x¬(γ1(x)∨• • •∨ γ k (x)) → ϕ, where γ1 . . . γ k ∈ Γ are all stack symbols such that ν(γ) = ε. • Every subformula ∃xϕ is replaced with ∃x¬(γ1(x) ∨ • • • ∨ γ k (x)) ∧ ϕ where γ1 . . . γ k ∈ Γ are all stack symbols such that ν(γ) = ε. • Every occurrence of a label predicate l(x) is replaced with the formula γ1(x) ∨ • • • ∨ γ k (x) where γ1 . . . γ k ∈ Γ are all stack symbols such that ν(γ) = l. Observe that the probability that F satisfies a document generated by M is equal to the probability that F ′ satisfies a document generated by A = (Q, Γ, q0, ∆, id) where id is the identity function. Then we convert F ′ into a DSTA A ′ . Lemma 24 shows that the probability that F satisfies a document generated by M is the probability of reaching the empty stack with a pop operation in A × A ′ (we can see this as the probability of reaching a state q f by adding a transition (⊥, q) p -→ q f for every state q = q0). Let M ′ be an RMC that is equivalent to A × A ′ .

Remark that if M is hierarchical, then M ′ is also hierarchical (if Q can be partitioned into i Qi such that a push transition always goes from a state of Q k to a state of Q k + 1, then Q × Q ′ can be stratified into i Qi × Q ′ , with the same property). Similarly, it can be checked that if M is piecewise-linear, then M ′ is also piecewise-linear. Informally, piecewise linearity means that when the RMC has recursion, then this recursion is linear. This property is preserved through the equivalence to pPDAs. Furthermore, the product construction neither add non-linearity nor recursion.

Since reachability probabilities are ra-tractable in piecewiselinear RMCs, the probability that F satisfies M is computable in PTIME assuming unit-cost rational arithmetic. We also need to normalize by the probability of termination of the RMC M , which is just another reachability probability.

We now prove the tractability of tree-like Markov chains.

Proof of Theorem 10. We apply the same construction as in the proof of Theorem 20. If M is tree-like then M ′ is also tree-like. The tree-like property can be seen in pPDAs as a condition that the push and pop transition graph is a forest of connected components of states, and this is preserved by the product construction. Reachability probabilities in tree-like Markov chains are just reachability probabilities in regular Markov chains, and they are computable in polynomial time.

Figure 1 :

 1 Figure 1: RMC Aex of Examples 2, 4, and 5

  call ports, Call(b) = {(b, en) | en ∈ N en Y i (b) } and return ports, Return(b) = {(b, ex) | ex ∈ N ex Y i (b) }, that indicate, respectively, the entries and the exits of the component corresponding to b; (iii) A transition relation δi, where transitions are of the form (u, pu,v, v) and (a) the source u is either a non-exit node u ∈ Ni \ N ex i , or a return port u = (b, ex) of a box b ∈ Bi, (b) the destination v is either a non-entry node v ∈ Ni \ N en i , or a call port u = (b, en) of a box b ∈ Bi, (c) pu,v is the probability of transiting from u to v.

  then for every sequence of boxes β and α ∈ Tag(L) ∪ {ε} there is a ∆-transition from (β, u, α) to (β, v, ε) with probability pu,v. (ii) If (b, en) ∈ Call(b) and µ(A Y (b) ) = l ∈ L, then for every β and α there is a ∆-transition from (β, (b, en), α) to (βb, en, l ) with probability 1. (iii) If (b, ex) ∈ Return(b), and µ(A Y (b) ) = l ∈ L, then for every β and α there is a ∆-transition from (βb, ex, α) to (β, (b, ex), /l ) with probability 1.

Figure 2 :

 2 Figure 2: Space of models considered in this paper. Considered dimensions (left), 1-exit models (middle), multi-exit models (right). Tractability of MSO queries: MODEL: tractable, MODEL: ra-tractable, MODEL: SQRT-SUM is reducible to query evaluation for some fixed MSO query.

Figure 3 :

 3 Figure 3: Translations between probabilistic XML representation systems. " ": polynomial translation, " ": existence of a translation, "?": no efficient translation known.

  where µ labels each Ai with an element from L ∪ {ε} and every component Ai is a graph Ai =

	(Ni, N en i , N ex i , Bi, Yi, δi) that consists of: (i) A set Ni of nodes, a subset of entry nodes N en i ⊆ Ni, and a subset of exit nodes N ex i ⊆ Ni; (ii) A set Bi of boxes, and a mapping Yi : Bi → {1, . . . , k} that assigns to every box (the index of) one of the com-
	ponents, A1, . . . , A k . To each box b ∈ Bi, we associate the sets of

  person name /name phone /phone phone /phone /person person name /name phone /phone phone /phone /person /directory

	This string can be generated by Aex with probability (0.8 × (0.5 × 0.5 × 0.5)) 2 × 0.2 = 0.2%. Note Aex generates skeletons of documents without any actual data. One can account
	for data by straightforwardly defining N and T with regular
	expressions specifying permissible names and phone numbers,

respectively. Since every document d in Aex has depth at most two, Aex is shallow. Moreover, since the number of persons rooted under the directory node and the number of telephones per person is arbitrary, Aex is wide.

* Supported by the EU projects Webdam (FP7-ICT-226513), FOX (FP7-ICT-233599), ONTORULE (FP7-ICT-231875), French ANR DataRing, and British EPSRC EP/G004021/1. † The author is co-affiliated with INRIA Saclay.

D. MATERIAL FOR SECTION 5

1-exit vs. Multi-exit Models. We prove Proposition 12 with the help of the two following lemmas: item 1 is a direct consequence of Lemma 25 and item 2 is obtained by combining Lemmas 25 and 26.

Lemma 25. Let S be one of TLAMC, AHMC, TLMC, HMC, PLRMC, RMC. Then S ≡ 1-S. Moreover, if reachability probabilities can be computed in polynomial time in S (with bit-cost arithmetic), then S ≡ poly 1-S.

Proof. For S = RMC, we use a result from [START_REF] Abney | Relating probabilistic grammars and automata[END_REF] that shows that every pPDA can be (inefficiently) translated into a SCFG that generates the same string language (recall that pPDA ≡ poly RMC).

The other cases are subclasses of PLRMC, for which reachability probabilities are rational [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF]. Let S ∈ S. Since any RMC can be transformed into a 1-entry equivalent RMC in polynomial time [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF], we assume that all components of S are 1-entry. Let Ai be a component of S with m exits. We substitute Ai with m components A 1 i , . . . , A m i , that are 1-exit copies of Ai where only the jth exit has been kept. We also remove from A j i all nodes from which the exit node is not reachable and renormalize the probabilities to obtain an Markov chain in which the probability of reaching the exit from the entry is 1, provided that all boxes terminate with probability 1. This can be done in polynomial time. Then one replaces every box b calling Ai with m boxes bj, one for each A j i . Finally one substitutes the transition (v, p, (b, en)) with m transitions (v, p • pj, (bj, en)), where pj is the probability of reaching the jth exit of Ai starting from its entrance (we assumed this is a rational probability). The resulting RMC generates the same px-space, and the construction preserves the hierarchical, tree-like, and acyclic properties.

Lemma 26. Consider the query q = ∃x c(x). For all n 0, there is an AHMC Hn of size O(n) such that Pr(q |= Hn) = 1 -2 -2 n . In contrast, there is no 1-RMC of size polynomial in n with the same query probability.

Proof. A hierarchical acyclic Markov chain that has the required property is given in Figure 5. The non-existence of a 1-exit RMC of size polynomial in n with a reachability probability doubly exponentially close to 1 (but not equal to 1) was proved in [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF], Lemma 29, and it directly yields the second part of the lemma.

Piecewise-linearity. We compare the piecewise linearity condition with the other classes. A direct consequence of Theorem 8.11 and Theorem 3.2, Case (1) of [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF] is that RMC is strictly more expressive than PLRMC. The former model can express irrational reachability probabilities, while the latter cannot. In turn, PLRMC is more expressive than HMC since HMC is not a deep model. Moreover it follows from [START_REF] Etessami | Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF] that PLSCFG ≡ poly 1-PLRMC.

E. MATERIAL FOR SECTION 6

We explain the algorithm behind Theorem 18 first in the one-exit case. In this case, we can assume without loss of generality that every component has at most two boxes in it, since every one-exit machine can be rewritten in this form.

The closure of an FNXPath filter F , denoted cl(F ), is the set of its subformulas. An F -type is a subset of cl(F ). A node in a tree satisfies an F -type if it satisfies exactly the formulas in the type. The idea of our algorithm will be to work top-down on the components, guessing types for every box.

We need the following properties of the closure of F : (i) it consists only of FNXPath filters; (ii) it consists of only a polynomial number of filters (in size of F ). Most importantly, it satisfies a "composition lemma", given below. A 2-pointed tree is a tree with two distinguished leaves. If p is a twopointed tree and t1, t2 are trees, p2[t1, t2] is the tree formed from plugging in t1 in to the first port of p (that is, identifying the root of t1 with the port) and t2 into the second port. The composition lemma states:

Lemma 27. Suppose p is a 2-pointed tree with neither of its ports equal to its root, and suppose t1 and t ′ 1 are two trees whose roots satisfy the same filters in cl(F ), and similarly for t2, t ′ 2 . Then for any filter in cl(F ),

Simultaneous induction on the height of p and F . For atomic expressions this is clear, while for Boolean operators it follows immediately by induction.

Suppose (p[t1, t2], root(p[t1, t2])) |= child[G].

There is a child c of the root that witnesses this. If this child is the root of t1, then we know (t1, root(t1)) |= G, and thus the same holds for (t ′ 1 , root(t ′ 1 )) by assumption. But then

with the root of t ′ 1 as the witness. We argue symmetrically if c is the root of t2.

If c is not in t1 or t2, then we let p ′ be the subtree of root rooted at c, and we conclude that p ′ [t ′ 1 , t ′ 2 ] satisfies G by induction on height, and thus that p

That is, for fixed p, the type of p[t1, t2] depends only on the types of t1 and t2. We also need the following:

Lemma 28. Given a filter F , three F -types tp 1 , tp 2 and tp 3 and a two-pointed tree p[x, y] one can check in PSPACE whether there are trees t2 and t3 with the root of p[t2, t3] satisfying tp 1 in p[t2, t3], the root of t2 satisfying tp 2 in t2, and the root of t3 satisfying tp 3 in t3.

Proof. We need to know if there is a tree q with distinguished nodes m2, m3 (given, e.g., as distinguished labels), such that the subtree of the root minus the subtrees of m2 and m3 is isomorphic to p, and the nodes m1, m2, root(q) satisfy the types tp 1 , tp 2 , tp 3 within the appropriate trees.

Any isomorphism type of an ordered tree can be described in FNXPath, hence this can be expressed as an FNXPath expression of polynomial size, using an enhanced label alphabet telling whether a particular node is m2 or m3. The result now follows, because satisfiability of FNXPath on trees of fixed depth d is in PSPACE in the size of the expression and the depth [START_REF] Benedikt | XPath satisfiability in the presence of DTDs[END_REF].

Call a 4-tuple (tp 1 , tp 2 , tp 3 , p) consistent if the above holds. Note that by Lemma 27, if (tp 1 , tp 2 , tp 3 , p) is consistent then for every t2, t3 whose roots satisfy tp 2 , tp 3 , respectively, the tree p[t2, t3] satisfies tp 1 at its root. We are now ready for the algorithm.

Proof of Theorem 18 (single-exit HAMCs). We fix a single-exit HAMC M . We know that in every component, there are only a polynomial number of paths from the entry node to the exit node. We also assume that every component has at most two boxes. An arbitrary AHMC can be normalized to achieve this. By acyclicity and the single-exit property each path hits each box at most once. Note that over a HMC, the axis descendant can be (efficiently) translated away, since the depth of the documents is bounded. Similarly, FNXPath expressions can be rewritten to explicitly skip over ε-nodes, using the bound on the depth of the tree. For example child

Our algorithm Gen(tp, b) takes as input F -type tp and box b of M , computing the probability that b generates a tree satisfying tp at the root. Applying this to the root of the top-level box, and iterating over every type tp that contains F , will give us the final probability that we want.

Gen(tp, b) works as follows. Let b point to component C that is associated with label l ∈ L, and b1, b2 be the boxes in C. Let p1 . . . pn be all paths from the entry node to the exit node in C, possibly going through both boxes. For each path pi, let l[pi] be the two-pointed tree that has a root labeled L and the path pi as a subforest, with ports corresponding to any occurrence of b1 and b2 in pi.

The algorithm guesses types tp 1 and tp 2 and then recursively calculates Gen(tp 1 , b1) and Gen(tp 2 , b2). It then iterates over each path pi, and checks whether the 4-tuple (tp 1 , tp 2 , tp 3 , l[pi]) is consistent; if they are multiples the probabilities returned by Gen(tp 1 , b1) and Gen(tp 2 , b2) with the product of probabilities of the edges in pi, adding this to the running probability. It returns the sum total of these probabilities over all pi.

The correctness of the algorithm follows directly from Lemma 27. The algorithm runs in PSPACE in the query, since we can implement it with a call stack that stores a sequence of pairs, box and type, of height at most the height of M . For any fixed query it will be ra-tractable, since the number of arithmetic operations used is a polynomial (depending on the query) in the AHMC.

Let us now extend this to multiple-exit HAMCs.

Proof of Theorem 18 (multiple-exit HAMCs).

We explain the extension to the general AHMC model of the proof given in the main text. In this case, there may be j per component, where is bounded by the size of the AHMC. We thus need to deal with j-pointed trees; the extension of Lemma 27 to j-pointed trees is straightforward. In a given component, there may be exponentially many p. However, each path is of size linear in the chain and we only need to deal with one at a time (we can record the last path we have visited using a polynomial amount of space). So the algorithm Gen(tp 1 , b) will guess a path in the component pointed to by b, in addition to choosing j types, where tpi is chosen for box bi in the component, and will then make a recursive call to Gen(tp i , bi) to compute the probability. Of course, we also need to verify type consistency, which requires a modification of Lemma 28 to the case where p is not of fixed sized but is part of the input. The extension follows because the FNXPath expression expressing the isomorphism type of the path is of size linear in the path.