Serge Abiteboul
email: serge.abiteboul@inria.fr

T.-H Hubert Chan

Evgeny Kharlamov
email: kharlamov@inf.unibz.it

Werner Nutt
email: nutt@inf.unibz.it

Pierre Senellart
email: pierre@senellart.com

Aggregate Queries for Discrete and Continuous Probabilistic XML *

Keywords: H.2.3 [Database Management]: Logical Design, Languages-data models, query languages; F.2.0 [Analysis of Algorithms, Theory XML, probabilistic databases, aggregation, complexity, algorithms

Sources of data uncertainty and imprecision are numerous.

A way to handle this uncertainty is to associate probabilistic annotations to data. Many such probabilistic database models have been proposed, both in the relational and in the semi-structured setting. The latter is particularly well adapted to the management of uncertain data coming from a variety of automatic processes. An important problem, in the context of probabilistic XML databases, is that of answering aggregate queries (count, sum, avg, etc.), which has received limited attention so far. In a model unifying the various (discrete) semi-structured probabilistic models studied up to now, we present algorithms to compute the distribution of the aggregation values (exploiting some regularity properties of the aggregate functions) and probabilistic moments (especially, expectation and variance) of this distribution. We also prove the intractability of some of these problems and investigate approximation techniques. We finally extend the discrete model to a continuous one, in order to take into account continuous data values, such as measurements from sensor networks, and present algorithms to compute distribution functions and moments for various classes of continuous distributions of data values.

INTRODUCTION

The (HTML or XML) Web is an important source of uncertain data, for instance generated by imprecise automatic tasks such as information extraction. A natural way to model this uncertainty is to annotate semistructured data with probabilities. This is the basis of recent works that consider queries over such imprecise hierarchical information [START_REF] Abiteboul | Querying and updating probabilistic information 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] Kimelfeld | Query efficiency in probabilistic XML models[END_REF][START_REF] Kimelfeld | Matching twigs in probabilistic XML[END_REF][START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF][START_REF] Senellart | On the complexity of managing probabilistic XML data[END_REF][START_REF] Van Keulen | A probabilistic XML approach to data integration[END_REF]]. An essential aspect of query processing has been ignored in all these works, namely, aggregate queries. This is the problem we consider here. We provide a comprehensive study of query processing for a very general model of imprecise data and a very large class of aggregate queries.

We consider probabilistic XML documents and the unifying representation model of p-documents [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF][START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF]. A pdocument can be viewed as a probabilistic process that randomly generates XML documents. Some nodes, namely distributional nodes, specify how to perform this random generation. We consider three kinds of distributional operators: cie, mux, det, respectively for conjunction of independent events (a node is selected if a conjunction of some probabilistic conditional events holds), mutually exclusive (at most one node selected from a set of a nodes), and deterministic (all nodes selected). This model, introduced in [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF][START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF], captures a very large class of models for probabilistic trees that had been previously studied. For queries, we consider tree-pattern queries possibly with value joins and the restricted case of single-path queries. For aggregate functions, we consider the standard ones, namely, sum, count, min, max, countd (count distinct) and avg (average).

A p-document is a (possibly very compact) representation of a probabilistic space of (ordinary) documents, i.e., a finite set of possible documents, each with a particular probability. In the absence of a grouping operation à la SQL (GROUP BY), the result of an aggregate query is a single value for each possible document. Therefore, an aggregate query over a p-document is a random variable and the result is a distribution, that is, the set of possible values, each with its probability. It is also interesting to consider summaries of the distribution of the result random variable (that is possibly very large), and in particular, its expected value and other probabilistic moments. When grouping is considered, a single value (again a random variable) is obtained for each match of the grouping part of the query. We investigate the computation of the distributions of random variables (in presence of grouping or not) and of their moments.

Our results highlight an (expectable) aspect of the different operators in p-documents: the use of cie (a much richer means of capturing complex situations) leads to an increase in complexity. For documents with cie nodes, we show the problems are hard (typically NP-or FP #P -complete). For count and sum, in the restricted setting of single-path queries, we show how to obtain moments in P. We also present Monte-Carlo methods that allow tractable approximations of probabilities and moments. On the other hand, with the milder forms of imprecision, namely mux and det, the complexity is lower. Computing the distribution for treepattern queries involving count, min and max is in P. The result distribution of sum may be exponentially large, but the computation is still in P in both input and output. On the other hand, computing avg or countd is FP #P -complete. On the positive side, we can compute expected values (and moments) for most aggregate tree-pattern queries in P. When we move to queries involving joins, the complexity of moment and distribution computation becomes FP #P -complete.

A main novelty of this work is that we also consider probabilistic XML documents involving continuous probability distributions, which captures a very frequent situation occurring in practice. We formally extend the probabilistic XML model by introducing leaves representing continuous value distributions. We explain how the techniques for the discrete case can be adapted to the continuous case and illustrate the approach by results that can be obtained.

The paper is organized as follows. After presenting preliminaries and introducing the problems in Sections 2 and 3, we consider cie nodes in Section 4. In Section 5, we consider monoid aggregate functions in the context of mux and det nodes. Continuing with this model, we study complexity of distributions and moments in Section 6. We briefly discuss approximation algorithms in Section 7. Continuous probability distributions are considered in Section 8. Finally, we present related work and conclude in Section 9.

A preliminary version of some of this work appeared in [START_REF] Abiteboul | Agrégation de documents XML probabilistes[END_REF] (a national conference without proceedings).

DETERMINISTIC DATA AND QUERIES

We recall the data model and query languages we use. We assume a countable set of identifiers I and one of labels L, such that I ∩ L = ∅. The set of labels includes a set of data values (e.g., the integers, on which the aggregate functions will be defined). A document is a pair d = (t, θ), consisting of a finite, unordered 1 tree t, where each node has 1 Ignoring the ordering of the children of nodes is a common simplification over the XML model that does not sig- [32] 50 [START_REF] Ash | Probability & Measure Theory[END_REF] bonus [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF] person [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF] person Mary [31] pda [START_REF] Cheng | Evaluating probabilistic queries over imprecise data[END_REF] bonus John 50 [START_REF] Calvanese | Aggregate queries over ontologies[END_REF] name 37 [START_REF] Abiteboul | Agrégation de documents XML probabilistes[END_REF] IT-personnel [START_REF] Papadimitriou | Computational Complexity[END_REF] laptop 44 [START_REF] Afrati | Answering aggregate queries in data exchange[END_REF] name

15

[51] pda d: An aggregate function maps a finite bag of values (e.g., rationals) into some domain (possibly the same or different).

In particular, we assume that any aggregate function is defined on the empty bag. In the paper we study the common functions: sum, count, min, countd (count distinct), and avg (average) under the usual semantics. Our results easily extend to max and topK .

Aggregate functions can be naturally extended to work on documents d: the result α(d) is α(B) where B is the bag of the labels of all leaves in d. This makes the assumption that all leaves are of the type required by the aggregate function, e.g., rational numbers for sum. Again to simplify, we ignore this issue here and assume they all have the proper type. It is straightforward to extend our models and results with a more refined treatment of typing.

As we will see some particular aggregate functions, the so-called monoid ones [START_REF] Cohen | Rewriting queries with arbitrary aggregation functions using views[END_REF], play a particular role in our investigation, because they can be handled by a divide-andconquer strategy. Formally, a structure (M, ⊕, ⊥) is called an abelian monoid if ⊕ is an associative and commutative binary operation with ⊥ as identity element. If no confusion arises, we speak of the monoid M . An aggregate function is a monoid one if for some monoid M and any a1, . . . , an ∈ M :

α({|a1, . . . , an| }) = α({|a1| }) ⊕ • • • ⊕ α({|an| }).
It turns out that sum, count, min, max and topK are monoid aggregate functions. For sum, min, max: α({|a| }) = a and ⊕ is the corresponding obvious operation. For count: α({|a| }) = 1 and ⊕ is +. On the other hand, it is easy to check that neither avg nor countd are monoid aggregate functions. nificantly change the results of this paper.

Finally, we introduce tree pattern queries with joins, with join-free queries and single-path queries as special cases. We then extend them to aggregate queries.

We assume a countable set of variables Var. A tree pattern (with joins), denoted Q, is a tree with two types of edges: child-edges, denoted E / , and descendent edges, denoted E // . The nodes of the tree are labeled by a labeling function2 λ with either labels from L or with variables from Var. Variables that occur more than once are called join variables. We refer to nodes of Q as n, m in order to distinguish them from the nodes of documents.

A tree pattern query with joins has the form

Q[n],
where Q is a tree pattern with joins and n is a tuple of nodes of Q (defining its output). We sometimes identify the query with the pattern and write Q instead of Q[n] if n is not important or clear from the context. If n is the empty tuple, we say that the query is Boolean. A query is join-free if every variable in its pattern occurs only once. If the set of edges E / ∪E // of a query is a linear order, the query is a single-path query. We denote the set of all tree pattern queries, which may have joins, as TPJ. The subclasses of join-free and single path queries are denoted as TP and SP, respectively.

A valuation ν maps query nodes to document nodes. A document satisfies a query if there exists a satisfying valuation, which maps query nodes to the document nodes in a way that is consistent with the edge types, the labeling, and the variable occurrences. That is, (1) nodes connected by child/descendant edges are mapped to nodes that are children/descendants of each other; (2) query nodes with label a are mapped to document nodes with label a; and (3) two query nodes with the same variable are mapped to document nodes with the same label.

Slightly differently from other work, we define that applying a query Q[n] to a document d returns a set of tuples of nodes: Q(d) := {ν(n) | ν satisfies Q}. One obtains the more common semantics, according to which a query returns a set of tuples of labels, by applying the labeling function of d to the tuples in Q(d).

An aggregate TPJ-query has the form

Q[α(n)],
where Q is a tree pattern, n is a node of Q and α is an aggregate function. We evaluate such a Q[α(n)] in three steps: First, the non-aggregate query

Q ′ := Q[n] over d, obtaining a set of nodes Q ′ (d). We then compute the bag B of labels of Q ′ (d), that is B := {|θ(n) | n ∈ Q ′ (d)| }.
Finally we apply α to B. Identifying the aggregate query with its pattern, we denote the value resulting from evaluating Q over d as Q(d).

If Q[n] is a non-aggregate query and α an aggregate function, we use the shorthand Q α to denote the aggregate query Q[α(n)]. More generally, we denote the set of aggregate queries obtained from queries in TPJ, SP, TP and some function α, as TPJ α , SP α , TP α , respectively.

The syntax and semantics above can be generalized in a straightforward fashion to aggregate queries with SQL-like GROUP BY. Such queries are written Q[n, α(n)] and return an aggregate value for every binding of n to a tuple of document nodes. Since we can reduce the evaluation of such queries to the evaluation of several simpler queries of the kind defined before, while increasing the data complexity by no more than a polynomial factor, we restrict ourselves to that simpler case.

DISCRETE PROBABILISTIC DATA

We next present discrete probability spaces over data trees (see [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF] for a more detailed presentation) and formalize the problems we will study in the following sections.

px-Spaces and p-Documents

A finite probability space over documents, px-space for short, is a pair S = (D, Pr), where D is a finite set of documents and Pr maps each document to a probability Pr(d)

such that {Pr(d) | d ∈ D} = 1.
p-Documents: Syntax. Following [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF], we now introduce a very general syntax for representing compactly px-spaces, called p-documents. A p-document is similar to a document, with the difference that it has two types of nodes: ordinary and distributional. Distributional nodes are used for defining the probabilistic process that generates random documents but they do not actually occur in these. Ordinary nodes have labels and they may appear in random documents. We require the leaves to be ordinary nodes 3 . More precisely, we assume given a set X of independent Boolean random variables with some specified probability distribution ∆ over them. A p-document, denoted by P, is an unranked, unordered, labeled tree. Each node has a unique identifier v and a label µ(v) in L ∪ {cie(E)}E ∪ {mux(Pr)} Pr ∪ {det} where L are labels of ordinary nodes, and the others are labels of distributional nodes. We consider three kinds of the latter labels: cie(E) (for conjunction of independent events), mux(Pr) (for mutually exclusive), and det (for deterministic). We will refer to distributional nodes labeled with these labels, respectively, as cie, mux and det nodes. If a node v is labeled with cie(E), then E is a function that assigns to each child of v a conjunction e1 ∧ • • • ∧ e k of literals (x or ¬x, for x ∈ X ). If v is labeled with mux(Pr), then Pr assigns to each child of v a probability with the sum equal to 1.

Example 3. Two p-documents are shown in Figures 3 and4. The first one has only cie distributional nodes. For example, node n21 has label cie(E) and two children n22 and n24, such that E(n22) = ¬x and E(n24) = x. The second pdocument has only mux and det distributional nodes. Node n52 has label mux(Pr) and two children n53 and n56, such that Pr(n53) = 0.7 and Pr(n56) = 0.3.

x, z [START_REF] Provan | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF] [56] [START_REF] Cohen | Incorporating constraints in probabilistic XML[END_REF] x [START_REF] Dalvi | Probabilistic databases: Diamonds in the dirt[END_REF] z ¬z, x [START_REF] Grädel | The complexity of query reliability[END_REF] [52]

[41]

x [55] ¬x ¬x [START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF] [32]

[54] [START_REF] Ré | Efficient evaluation of HAVING queries on a probabilistic database[END_REF] [21] cie

[31] pda [START_REF] Ash | Probability & Measure Theory[END_REF] We denote classes of p-documents by PrXML with a superscript denoting the types of distributional nodes that are allowed for the documents in the class. For instance, PrXML mux,det is the class of p-documents with only mux and det distributional nodes, like P on Figure 4.

p-Documents: Semantics. The semantics of a p-document P, denoted by P , is a px-space over random documents, where the documents are denoted by P and are obtainable from P by a randomized three-step process.

1. We choose a valuation ν of the variables in X . The probability of the choice, according to the distribution ∆, is pν = x in P,ν(x)=true ∆(x) • x in P,ν(x)=false (1 -∆(x)).

2. For each cie node labeled cie(E), we delete its children v where ν(E(v)) is false, and their descendants. Then, independently for each mux node v labeled mux(Pr), we select one of its children v ′ according to the corresponding probability distribution Pr and delete the other children and their descendants, the probability of the choice is Pr(v ′ ). We do not delete any of the children of det nodes. 43. We then remove in turn each distributional node, connecting each ordinary child v of a deleted distributional node with its lowest ordinary ancestor v ′ , or, if no such v ′ exists, we turn this child into a root.

The result of this third step is a random document P. The probability Pr(P) is defined as the product of pν, the probability of the variable assignment we chose in the first step, with all Pr(v ′ ), the probabilities of the choices that we made in the second step for the mux nodes. Remark. In our analysis, we only consider distributional nodes of the types cie, mux, and det. In [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF] two more types of distributional nodes (ind and exp) are considered. As shown there, the first kind can be captured by mux and [START_REF] Cohen | Incorporating constraints in probabilistic XML[END_REF] [55] [START_REF] Kimelfeld | Matching twigs in probabilistic XML[END_REF] [54] [START_REF] Grädel | The complexity of query reliability[END_REF] [11]

[41] 0.7 0.3 0.75

[52]

[53] [START_REF] Provan | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF] 0.25 0.1 0.9 [START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF] [32] [START_REF] Ré | Efficient evaluation of HAVING queries on a probabilistic database[END_REF] [56]15

[31] pda mux det, while the second is a generalization of mux and det and most results of PrXML mux,det can be extended to PrXML exp . As proved in [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF], PrXML cie is strictly more expressive than PrXML mux,det . It was shown in [START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF][START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF] that data complexity of answering TP-queries is intractable for PrXML cie (FP #Pcomplete) whereas it is polynomial for PrXML mux,det .

Aggregating Discrete Probabilistic Data

Let Q α be an aggregate query and S = (D, Pr) be a pxspace of documents. Since Q α maps elements of the probability space S to values in the range of α, we can see Q α as a random variable.

We therefore define the result of applying Q α to S as the distribution of this random variable, that is

(Q α (S))(c) = Pr(d) d ∈ D, Q α (d) = c ,
for c in the range of α.

Since in applications px-spaces are given under the form of p-documents, we further extend the definition to p-documents by defining Q α ( P) := Q α ( P ). We denote the random variable over the p-document P corresponding to Q as Q(P). 3 gives the distribution {(0, 0.14175), (15, 0.80325), (44, 0.00825) (59, 0.04675)}, while evaluation over the mux-det-document in Figure 4 gives the distribution {(15, 0.3), (59, 0.7)}.

Example 5. Evaluation of the query Q[sum(n)] from Example 2 over the cie-document in Figure

Computational Problems. For an aggregate query Q, we are interested in the following three problems, where the input parameters are a p-document P with corresponding random document P and possibly a number c:

Membership: Given a number c, is c in the carrier of Q(P), i.e., is Pr(Q(P) = c) > 0? Probability computation: Given a number c, compute Pr(Q(P) = c). Moment computation: Compute the moment E(Q(P) k ),
where E is the expected value.

Membership and probability computation can be used to return to a user the distribution Q( P) of an aggregate query. Computing the entire distributions may be too costly or the user may prefer a summary of the distributions. For example, a user may want to know its expected value E(Q(P)) and the variance Var(Q(P)). In general the summary can be an arbitrary k-th moment E(Q(P) k ) and the moment computation problem addresses this issue. 5In the following, we investigate these problems for the classes of cie documents and mux-det documents. For each class, we further distinguish between aggregate queries of the types SP, TP, and TPJ with the functions min, count, sum, countd and avg. We do not discuss max and topK since they behave similarly as min. In the paper we mainly speak about data-complexity, when the input is a p-document and the query is fixed. Occasionally we also consider combined complexity, when both the p-document and the query are inputs of the problem.

AGGREGATING PrXML cie

We now study the problems introduced in Section 3 for the most general class of p-documents, PrXML cie . By definition, one approach is to first construct the entire px-space of a p-document P, then to apply the aggregate query Q to each document in P separately, and finally combine the results to obtain the distribution Q( P). This approach is expensive, since the number of possible documents is exponential in the number of variables occurring in P.

Our complexity results show that for practically all functions and all problems nothing can be done that would be significantly more efficient. All the decision problems are NP-complete while computational problems are NP-hard or FP #P -complete. The only exception is the computation of moments for aggregate single-path queries with sum and count. The intractability is due to dependencies between nodes of p-documents expressed using variables.

Principles

We now show several general principles for p-documents that are used later on to support the results.

Functions in #P and FP #P . We recall here the definitions of some classical complexity classes (see, e.g., [START_REF] Papadimitriou | Computational Complexity[END_REF]) that characterize the complexity of aggregate functions on PrXML cie . An N-valued function f is in #P if there is a non-deterministic polynomial-time Turing machine T such that for every input w, the number of accepting runs of T is the same as f (w). A function is in FP #P if it is computable in polynomial time using an oracle for some function in #P. Following [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF], we say that a function is FP #P -hard if there is a polynomial-time Turing reduction (that is, a reduction with access to an oracle to the problem reduced to) from every function in FP #P to it. Hardness for #P is defined in a standard way using Karp (many-one) reductions. For example, the function that counts for every propositional 2-DNF formula the number of satisfying assignments is in #P and #P-hard [START_REF] Provan | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF], hence #P-complete. We notice that the usage of Turing reductions in the definition of FP #Phardness implies that any #P-hard problem is also FP #Phard. Therefore, to prove FP #P -completeness it is enough to show FP #P -membership and #P-hardness. Note also that #P-hardness clearly implies NP-hardness.

We now consider membership in FP #P . We say that an aggregate function α is scalable if for every p-document P ∈ PrXML cie , one can compute in polynomial time a natural number M such that for every d ∈ P the product M • α(d) is a natural number. The following result is obtained by adapting proof techniques of [START_REF] Grädel | The complexity of query reliability[END_REF]. Proposition 6. Let α be an aggregate function that is computable in polynomial time and Q be an aggregate TPJquery using α. If α is scalable, then the following functions mapping p-documents to rational numbers are in FP #P :

1. for every c ∈ Q the function P → Pr(Q(P) = c); 2. for every k 1, the function P → E(Q(P) k ).

The proposition above shows membership in FP #P of both probability and moment computation for aggregate queries in TPJ with all aggregate functions mentioned in the paper.

Reducing Query Evaluation to Aggregation. Now we show that for answering aggregate SP-queries it is possible to isolate aggregation from query processing.

Let P be in PrXML cie . If Q is an SP-query, we can apply it naively to P, ignoring the distributional nodes. The result PQ is the subtree of P containing the original root and as leaves the nodes satisfying Q (i.e., the nodes matched by the free variable of Q). Interestingly, it turns out that for all aggregate functions α, evaluating Q α over P is the same as applying α to PQ. If P is in PrXML mux,det , then PQ can be obtained analogously and, again, evaluating Q α over PQ can be reduced to evaluating α over PQ. Therefore, answering an aggregate SP-query Q α over P in PrXML cie,mux,det can be done in two steps, first one queries P with the non-aggregate part Q, which results in a p-document PQ, and then one aggregates all the leaves of PQ. The previous discussion leads to the following result.

Proposition 7. Let Q[n] be a non-aggregate SP-query.
Then for every p-document P ∈ PrXML cie,mux,det we can compute in time quadratic in |Q| + | P| a p-subdocument PQ of P such that for every aggregate function α we have:

Q α ( P) = α( PQ).
Hardness Results for Branching Queries. With the next lemma, we can translate data complexity results for nonaggregate queries to lower bounds of the complexity of computing probabilities of aggregate values and moments of distributions. An aggregate function α is faithful if α({|1| }) = 1. Lemma 8. Let Q be TPJ-query, P a p-document and α a faithful aggregate function. Then one can construct in linear time an aggregate TPJ-query Q ′ α with the function α and a p-document P ′ such that for any k 1,

Pr(P |= Q) = Pr(Q ′ α (P ′ ) = 1) = E(Q ′ α (P ′ ) k ). Moreover, 1. if Q ∈ TP, then Q ′ α ∈ TP α ; 2. if P ∈ PrXML cie , then P ′ ∈ PrXML cie ; 3. if P ∈ PrXML mux,det , then P ′ ∈ PrXML mux,det .
In [START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF] it has been proved that for every non-trivial Boolean tree pattern query, computing the probability to match ciedocuments is #P-hard. By reducing #2DNF, we can show that for the more restricted case of mux-det documents, evaluation of tree pattern queries with joins can be #P-hard. Lemma 9. There is a Boolean TPJ-query with #P-hard data complexity over PrXML mux,det .

The result in [START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF] and the previous lemma yield immediately the following complexity lower bounds for probability and moment computation for TP and TPJ.

Corollary 10. For any faithful aggregate function α, there exist an aggregate TP-query Q1 and an aggregate TPJ-query Q2, both with function α, such that each of the following computation problems is #P-hard:

1. probability computation for Q1 over PrXML cie ; 2. k-th moments of Q1 over PrXML cie , for any k 1; 3. probability computation for Q2 over PrXML mux,det ; 4. k-th moments of Q2 over PrXML mux,det , for any k 1.

We are ready to present aggregation of PrXML cie .

Computational Problems

We first show how to check for membership over PrXML cie .

Theorem 11 (Membership). Let α be one of sum, min, count, avg, and countd. Then membership over PrXML cie is in NP for the class TPJ α . Moreover, the problem is NP-hard for any aggregate query in SP α .

The upper bound holds because, given a query, guessing a world and evaluating the query takes no more than polynomial time. The lower bound follows from the next lemma.

Lemma 12. Let Q be an SP-query with one free variable and let AGG = {sum, count, min, countd, avg}. For every propositional DNF formula ϕ, one can compute in polynomial time a p-document Pϕ ∈ PrXML cie such that the following are equivalent: [START_REF] Abiteboul | Agrégation de documents XML probabilistes[END_REF] ϕ is falsifiable, ( 2) Pr(Q α (P) = 1) > 0 over Pϕ for some α ∈ AGG, [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF]

Pr(Q α (P) = 1) > 0 over Pϕ for all α ∈ AGG.
next show how to compute probability over PrXML cie .

Theorem 13 (Probability). Let α be one of sum, count, min, avg, and countd. Then probability computation over PrXML cie is in FP #P for the class TPJ α . Moreover, the problem is #P-hard for every query in SP α .

Proof. (Sketch) The FP #P upper bound follows from Proposition 6 and #P-hardness can be shown by a reduction of probability computation for DNF propositional formulas (that is known to be #P-hard), see the following lemma.

The following lemma supports Theorems 13 and 15.

Lemma 14. Let α be one of sum, count, min, avg, countd, and β be one of min, avg, countd. Let Q α and Q β be SPqueries. Then for every propositional DNF formula ϕ, one can compute in polynomial time a p-document Pϕ ∈ PrXML cie such that the following are equivalent:

1. Pr(Q α (Pϕ) = 0) = 1 -Pr(ϕ); 2. E(Q β (Pϕ) k ) = 1 -Pr(ϕ) for any k 1.
We finally show how to compute moments over PrXML cie .

Theorem 15 (Moments). Let α be one of sum, count, min, avg, and countd. Then computation of moments of any degree over PrXML cie is in FP #P for the class TPJ α . Moreover, the problem is 1. of polynomial combined complexity for the classes SP sum and SP count ; 2. #P-hard for any query in the classes SP min , SP avg and SP countd ; 3. #P-hard for some query in TP sum and TP count .

Proof. Again, as for Theorem 13, the FP #P upper bound follows from Proposition 6. Claim 2 follows from Lemma 14 and its analogues for min, countd, and avg. Claim 3 follows from Corollary 10.

To prove Claim 1, we rely on Proposition 7, which reduces answering aggregate SP-queries to evaluating aggregate functions, and the following lemmas.

The next lemma shows that the computation of the expected value for sum over a px-space, regardless whether it can be represented by a p-document, can be polynomially reduced to computation of an auxiliary probability.

Lemma 16. Let S be a px-space and V be the set of all leaves occurring in the documents of S. Suppose that the function θ labels all leaves in V with rational numbers and let sum(S) be the random variable defined by sum on S. Then

E(sum(S) k ) = (v 1 ,...,v k )∈V k k i=1 θ(vi) × Pr ({d ∈ S | v1, . . . , v k occur in d}) ,
where the last term denotes the probability that a random document d ∈ S contains all the nodes v1, . . . , v k .

Intuitively, the proof exploits the fact that E(sum(S)) is a sum over documents of sums over nodes, which can be rearranged as a sum over nodes of sums over documents.

The auxiliary probability introduced in the previous lemma can be in fact computed in polynomial time for px-spaces represented by P ∈ PrXML cie . Lemma 17. There is a polynomial time algorithm that computes, given a p-document P ∈ PrXML cie and leaves v1, . . . , v k occurring in P, the probability Pr {d ∈ P | v1, . . . , v k occur in d} . Now we are ready to conclude the proof of the theorem.

Proof. of Theorem 15.1

By Lemma 16, the k-th moment of sum over P is the sum of |V | k products, where V is the set of leaves of P. The first term of each product, k i=1 θ(vi), can be computed in time at most | P| k . By Lemma 17, the second term can be computed in polynomial time. This shows that for every k 1, the k-th moment of sum can be computed in polynomial time. The claim for count follows as a special case, where all leaves carry the label 1.

Table 1 gives an overview of the data complexity results of this section.

MONOID AGGREGATES

The previous section highlighted the inherent difficulty of computing aggregate queries over cie-documents. The intuitive reason for this difficulty is that the event variables used in a p-document can impose constraints between the structure of subdocuments in very different locations. In contrast, mux,det-documents only express "local" dependencies. As a consequence, for the special case of single path queries and monoid aggregate functions, mux-det documents allow for a conceptually simpler computation of distributions, which in a number of cases is also computationally efficient.

The key to developing methods in this setting is Proposition 7, which reduces the evaluation of a single path aggregate query Q α over P to the evaluation of the function α over the document PQ. Note that PQ is again a mux-det document if P is one. Therefore, we can concentrate on the question of evaluating α over mux,det-documents.

We are going to show how a mux,det-document P can be seen as a recipe for constructing the px-space P in a bottom-up fashion, starting from elementary spaces represented by the leaves and using essentially two kinds of operations, convex union and product. Convex union corresponds to mux-nodes and product corresponds to det-nodes and regular nodes. (To be formally correct, we would need to distinguish between two slightly different versions of product for det and regular nodes. However, to simplify our exposition, we only discuss the case of regular nodes and briefly indicate below the changes necessary to deal with det-nodes.)

For any α, the distribution over the space described by a leaf of P is a Dirac distribution, that is, a distribution of the form δa, where δa(b) = 1 if and only if a = b. For monoid functions α, the two operations on spaces, convex union and product, have as counterparts two operations on distributions, convex sum and convolution, by which one can construct the distribution α( P) from the Dirac distributions of the leaves of P. We sketch in the following both the operations on spaces and on distributions, and the way in which they are related.

As the base case, consider a leaf node v with label l. This is the simplest p-document possible, which constitutes an elementary px-space that contains one document, namely node v with label l, and assigns the probability 1 to that document. Over this space, α evaluates with probability 1 to α({|l| }), hence, the probability distribution is δ α({ |l| }) . As a special case, if α is a monoid aggregation function over M the distribution of α over the space containing only the empty document ε is δ ⊥ , where ⊥ is the identity of M .

Inductively, suppose that v is a mux-node in P, the subtrees below v are P1, . . . , Pn, and the probability of the i-th subtree Pi is pi (see Figure 5, left). Without loss of generality we can assume that the pi are convex coefficients, that is, p1 + • • • + pn = 1, since we admit the empty tree as a special p-document. As a consequence, α( Pv)(c), the probability that α has the value c over Pv, equals the weighted sum p1α( P1)(c) + • • • + pnα( Pn)(c) of the probabilities that α has the value c over P1, . . . , Pn. In a more compact notation we can write this as α( Pv) = p1α( P1) + • • • + pnα( Pn), which means that the distribution α( Pv) is a convex sum of the α( Pi).

mux v: Pv v1 p1 • • • vn pn P1 Pn α( Pv) = p1α( P1) + • • • + pnα( Pn) v Pv v1 • • • vn P1 Pn α( Pv) = α( P1) * M • • • * M α( Pn)
For the second induction step, suppose that v is a regular non-leaf node in P, with the label l. (see Figure 5, right). Similar to the previous case, suppose that the subtrees below v are P1, . . . , Pn, that Pv = (Dv, Prv) and that Pi = (Di, Pri) for 1 i n. Moreover, the Di are mutually disjoint.

Every document d ∈ Dv has as root the node v, which carries the label l, and subtrees d1, . . . , dn, where di ∈ Di. We denote such a document as d = v l ({d1, . . . , dn}). Conversely, according to the semantics of regular nodes in mux-det documents, every combination {d1, . . . , dn} of documents di ∈ Di gives rise to an element v l ({d1, . . . , dn}) ∈ Dv. (Note that, due to the mutual disjointness of the Di, the elements of Dv are in bijection with the tuples in the Cartesian product

D1 × • • • × Dn.)
Consider a collection of documents di ∈ Di, 1 i n, with probabilities qi := Pri(di). Each di is the result of dropping some children of mux-nodes in Pi and qi is the product of the probabilities of the surviving children. Then d := v l (d1, . . . , dn) is the result of dropping simultaneously the same children of those mux-nodes, this time within Pv. The set of surviving children in Pv is exactly the union of the sets of children having survived in each Pi and, consequently, for the probability q := Prv(d) we have that q = q1 • • • qn. In summary, this shows that the probability space (Dv, Prv) is structurally the same as the product of the spaces (Di, Pri).

Suppose now that, in addition, α is a monoid aggregate function taking values in (M, ⊕, ⊥). Then for any document d = v l (d1, . . . , dn) ∈ Pv we have that α

(d) = α(d1) ⊕ • • • ⊕ α(dn). Hence, the probability that α(Pv) = c is the sum of all products Pr(α(P1) = c1) • • • Pr(α(Pn) = cn) such that c = c1 ⊕ • • • ⊕ cn.
Motivated by this observation, we define the following operation. For any functions f , g : M → R, the convolution of f and g with respect to M is the function

f * M g : M → R such that (f * M g)(m) = m 1 ,m 2 ∈M : m 1 ⊕m 2 =M f (m1)g(m2).
(1)

From our observation above it follows that the distribution α( Pv) is the convolution of the distributions α( Pi) with respect to M , that is,

α( Pv) = α( P1) * M • • • * M α( Pn).
(

) 2
For det-nodes v, the same equation applies, although the supporting arguments are a bit more complicated. The crucial difference is that for det-nodes, Pv is a space of forests, not trees, since the trees (or forests) in the Pi are combined without attaching them to a new root.

We summarize how one can use the operations introduced to obtain the distribution of a monoid aggregate function over a mux-det document.

Theorem 18. Let α be a monoid aggregation function taking values in M and P ∈ PrXML mux,det . Then α( P) can be obtained in a bottom-up fashion by 1. attaching a Dirac distribution to every leaf and for every occurrence of the empty document; 2. taking convex sums at every mux-node; and 3. taking convolutions with respect to R at each det and each regular non-leaf node.

Essentially the same relationship between distributions as spelled out in Theorem 18 exists also if we allow continuous distributions at the leaves of documents. An evaluation algorithm then has to compute convex sums and convolutions, starting from continuous instead of Dirac distributions (we will discuss this in detail in Section 8).

The carrier of a function f : M → R is the set of elements m ∈ M such that f (m) = 0. Since for any P the carrier of min( P) and of count( P) has at most as many elements as there are leaves in P, we can draw some immediate conclusions from Theorem 18.

Corollary 19. For any mux,det-document P, 1. the distributions count( P) and min( P) can be computed in time polynomial in | P|; 2. the distribution sum( P) can be computed in time polynomial in | P| + |sum( P)|.

Proof. (Sketch) Claim 1 holds because computing a convex sum and convolutions with respect to "+" and min of two distributions is polynomial and all distributions involved in computing count( P) and min( P) have size O(| P|). Claim 2 holds because, in addition, a convex sum and the convolution with respect to "+" of two distributions have at least the size of the largest of the two arguments.

Remark. For the monoid of integers with addition, (1) is the same as the well-known discrete convolution. ( 2) is in fact a special case of a general principle: If X and Y are two M -valued random variables on the probability spaces X , Y, with distributions f , g, respectively, then the distribution of X ⊕ Y : X × Y → M is the convolution f * M g of f and g. This principle has also been applied in [START_REF] Ré | Efficient evaluation of HAVING queries on a probabilistic database[END_REF] in the context of queries with aggregation constraints over probabilistic relational databases.

AGGREGATING PrXML mux,det

We investigate the three computational problems for aggregate queries for the restricted class of PrXML mux,det , drawing upon the principles developed in the preceding section.

Theorem 20 (Membership). Let α be one of sum, count, min, avg, and countd. Then membership over PrXML mux,det is in NP for the class TPJ α . Moreover, the problem is 1. NP-hard for every query in SP sum , SP avg and SP countd ; 2. of polynomial combined complexity for the classes SP min and SP count ; 3. of polynomial data complexity for any query in TP min and TP count .

Proof. (Sketch) The NP upper bound is inherited from the cie-case (Theorem 11). Claim 1 can be shown by a reduction of subset-sum and exact cover by 3-sets. Claims 2 and 3 follow from their counterparts (Claims 1 and 2, respectively) in Theorem 21.

We next consider probability computation.

Theorem 21 (Probability). Let α be one of sum, count, min, avg, and countd. Then probability computation over PrXML mux,det is in FP #P for the class TPJ α . Moreover, the problem is 1. of polynomial combined complexity for the classes SP min and SP count ; 2. of polynomial data complexity for any query in TP min and TP count ; 3. #P-hard for any query in SP avg and SP countd ; 4. #P-hard for some query in TPJ sum , TPJ count and TPJ min .

Proof. (Sketch) The FP #P upper bound is inherited from the cie-case (Theorem 13). Claim 1 follows from Corollary 19, since, due to Proposition 7, for an aggregate SPquery Q α we have that Q α ( P) = α( PQ).

Regarding Claim 2, algorithms for count and min can be developed in a straightforward way, applying the techniques in [START_REF] Cohen | Incorporating constraints in probabilistic XML[END_REF] to evaluate TP-queries with aggregate constraints. For a given p-document, there are only linearly many possible values for min and count, the probability of which can be computed in polynomial time by incorporating them in constraints. Consequently, the entire distribution of min or count can be computed in polynomial time.

Claim 3 can be shown by a reduction of the #K-cover problem for countd and the #Non-Negative-Subset-Average problem for avg. 6 Claim 5 follows from Corollary 10.

Finally, we consider moments over PrXML mux,det .

Theorem 22 (Moments). Let α be one of sum, count, min, avg, and countd. Then computation of moments of any degree over PrXML mux,det is in FP #P for the class TPJ α . Moreover, the problem is 1. of polynomial combined complexity for the class SP α ; 2. of polynomial data complexity for the class TP α , if α = avg; 3. #P-hard for some query in TPJ α .

Proof. The FP #P upper bound is inherited from the ciecase (Theorem 15). Claim 3 follows from Corollary 10.

Regarding Claim 1, all our algorithms first reduce aggregate query answering to function evaluation (see Proposition 7). The algorithm for count and sum is a refinement for the one for the cie-case (Theorem 15). The algorithm for min works on the entire distribution, which can be computed in polynomial time ( Corollary 19).

For countd we apply similar techniques of regrouping sums to those that we used for sum in Lemma 16. In doing so, we exploit the fact that the probability for a value (or sets of values of fixed cardinality) to occur in a query result over a mux,det-document can be computed in polynomial time, which follows from work in [START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF].

The algorithm for avg traverses p-documents in a bottomup fashion. It maintains conditional moments of sum for each possible value of count and combines them in two posways, according to the node types. 7 Regarding Claim 2, moments for count and min can be computed directly from the distributions, which can be constructed in polynomial time as sketched in the proof of Theorem 21.2.

Algorithms for sum and countd can be based on a generalisation of the principle of regrouping sums (see Lemma 16) for tree pattern queries. Analogously as for the case of singlepath queries, the crucial element for the complexity of the sum-algorithm is the difficulty of computing the probability that a node (or sets of nodes of fixed cardinality) occur in a query result. For tree pattern queries without joins, these probabilities can be computed in polynomial time adapting the techniques in [START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF]. A variation of this principle, where the probabilities of a given set of values to occur in a query result is computed, gives an algorithm for countd.

Table 2 gives an overview of data complexity results of this section. 6 The same problems has been used earlier in [START_REF] Ré | Efficient evaluation of HAVING queries on a probabilistic database[END_REF] to show #P-hardness of evaluating relational queries with countd and avg-constraints. 7 A technique that is similar in spirit has been presented in [START_REF] Jayram | Efficient aggregation algorithms for probabilistic data[END_REF] for probabilistic streams.

APPROXIMATIONS AND SAMPLING

Without loss of generality, we only discuss how to estimate cumulative distributions Pr(Q α (P) c) and moments E(Q α (P) k ) for aggregate TPJ-queries. Notice that by using cumulative distributions one can also approximate the probability of individual values: to estimate Pr(Q α (P) = c), we estimate Pr(Q α (P) c + γ) and Pr(Q α (P) cγ) for a small γ (that depends on α and P) and subtract the second from the first.

For instance, in order to approximate the cumulative probability Pr(Q countd (P) 100), one evaluates the query on independent random samples of worlds of P, and then use the ratio of resulting samples where countd is at most 100 as an estimator. Similarly, for approximating E(Q countd (P)), one returns the average of countd over the results. Using Hoeffding's Bound [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] we obtain the following two propositions for approximating a point for the cumulative distribution of an aggregate query and moments of any degree, respectively. Proposition 23. Let Q be an aggregate TPJ-query, P ∈ PrXML cie,mux,det a p-document and x ∈ Q. Then for any rationals ε, δ > 0, it is sufficient to have O( 1 ε 2 log 1 δ ) samples so that with probability at least 1-δ, the quantity Pr(Q(P) x) can be estimated with an additive error of ε.

Observe that the number of samples in Proposition 23 is independent of the size of P. A problem may arise if Pr(Q(P) x) ε, since then an additive error of ε makes the estimate useless. However, for probabilities above a threshold p0, it is enough to have the number of samples proportional to 1/p 2 0 (with additive error, say p0/10).

Proposition 24. Let Q be an aggregate TPJ-query, f a function mapping Q to Q, such that f (Q(P)) ranges over an interval of width R and P ∈ PrXML cie a p-document. Then, for any rationals ε, δ > 0, it is sufficient to have O( R 2 ε 2 log 1 δ ) samples so that, with probability at least 1δ, the quantity E(f (Q(P))) can be estimated with additive error of ε.

As a consequence, if Q takes values in [0, R], choosing f (x) := x k yields that the k-th moment of Q(P) around zero can be estimated with O( R 2k ε 2 log 1 δ ) samples. Observe that if the range R has magnitude polynomial in size of P, then we have a polynomial-time estimation algorithm. For example, to approximate E(Q countd ( P)) it is enough to draw a quadratic number of samples, since the range R is at most the number of the leaves in P.

CONTINUOUS PROBABILISTIC DATA

We generalize p-documents to documents whose leaves are labeled with (representations of) probability distributions over the reals, instead of single values. We give semantics to such documents in terms of continuous distributions over documents with real numbers on their leaves.

Continuous px-Spaces. In the discrete case, a p-document defines a finite set of trees and probabilities assigned to them. In the continuous case, a p-document defines an uncountably infinite set of trees with a continuous distribution, which assigns probabilities to (typically infinite) sets of trees, the possible events, which form a σ-algebra. We refer to a textbook on measure and probability theory such as [START_REF] Ash | Probability & Measure Theory[END_REF] for the definitions of the concepts used in this section.

From now on, we consider only documents whose leaves are labeled with real numbers. We say that two documents d = (t, θ) and d ′ = (t ′ , θ ′ ) are structurally equivalent, denoted d ∼st d ′ , if t = t ′ and θ(v) = θ(v ′ ) for every v that is not a leaf of t. That is, d and d ′ differ only in the labels of the leaves. Obviously, ∼st is an equivalence relation on the set of all documents. Intuitively, the structure and the labels of inner nodes fix the structure of a document while the leaves contain values.

A set of documents D is structurally finite (or sf for short) if [START_REF] Abiteboul | Agrégation de documents XML probabilistes[END_REF] for any document d ∈ D and any d ′ that is structurally equivalent to d, we have d ′ ∈ D; (2) D consists only of finitely many ∼st-equivalence classes. That is, intuitively, if it contains a document d, then it contains also all documents that have the same structure, but different values, and it contains only finitely many structurally distinct documents.

Let D be an sf set of documents. We define a σ-algebra AD on D and then probabilities on AD by doing so first for each ∼st-class and then for D as a whole.

Let d0 = (t0, θ0) be a document, l := (l1, . . . , l k ) a tuple consisting of the leaf nodes of d0, and [d0]∼ st the equivalence class of d0 under ∼st. For every document d = (t, θ) with d ∈ [d0]∼ st we define θ( l) := (θ(l1), . . . , θ(l k )) a k-tuple of real numbers. In fact, this mapping of tuples of leaf values to tuples of numbers is a bijection between [d0]∼ st and R k , which we denote as β. The standard σ-algebra on R k is the algebra of Borel sets. We use β to introduce a σ-algebra A0 on [d0]∼ st . We say that D0 ∈ A0 for a set D0 ⊆ [d0]∼ st if and only if β maps D0 to a Borel set of R k . In the same vein, we can identify probability distributions over R k with distributions over [d0]∼ st . Note that, due to symmetry, the definition of A0 does not depend on the specific order of the leaves that is used by β. Now, suppose that D = n i=1 [di]∼ st and that Ai is the σ-algebra on [di]∼ st defined above. Then we define

AD := {D1 ∪ • • • ∪ Dn | Di ∈ Ai}.
Clearly, since all the Ai are σ-algebras, AD is a σ-algebra. Moreover, suppose that for each equivalence class [di]∼ st we have a probability distribution Pri and that p1, . . . , pn are convex coefficients (that is, pi 0 and p1 + • • • + pn = 1). Then we define for every D ′ ∈ AD

Pr(D ′ ) := n i=1 pi • Pri(D ′ ∩ [di]∼ st ).
Clearly, Pr is a probability on AD. Conversely, every probability Pr over (D, AD) can be uniquely decomposed into probabilities Pri over the ∼st-classes of D such that Pr can be obtained from the Pri as described above. Moreover, each Pri is essentially a probability over some R k . p-documents. To support (possibly continuous) distributions on leaves, we extend the syntax of p-documents by an additional type of distributional nodes, the cont nodes. A cont node has the form cont(D), where D is a representation of a probability distribution over the real numbers. In contrast to the distribution nodes introduced earlier, a cont node can only appear as a leaf.

Example 25. Consider the PrXML cont,mux,det p-document 0.6 [START_REF] Dalvi | Probabilistic databases: Diamonds in the dirt[END_REF] 0 Any finitely representable distribution can appear in a cont node. As an example, we consider in the following piecewise polynomial distributions. A function ∞ -∞ f = 1 is the density function of a probability. Clearly, in this case f |I 1 and f |Im are identical to 0. Note that distributions defined by piecewise polynomial densities are a generalization of uniform distributions. Piecewise polynomials are an example of a class of functions stable under convex sum, (classical) convolution, product, and integration. We shall use this stability property to compute the distribution of aggregate query answers.

f : R → R is piecewise polynomial if there are points -∞ = x0 < x1 < . . . < xm = ∞ such that for each interval Ii := ]xi-1, xi[, 1 i m, the restriction f |I i of f to Ii
When the symbol cont appears as a superscript of PrXML, possibly in combination with other symbols, it indicates a class of p-documents that have distributions on their leaves. The symbol cont can be used with class symbols like the three above as arguments to specify the kind of distributions that can appear.

We define the semantics P of continuous p-documents of PrXML cont,cie,mux,det as a continuous px-space as defined earlier. More precisely, let P ∈ PrXML cont,cie,mux,det and P ′ ∈ PrXML cie,mux,det be the p-document obtained from P by replacing every continuous node with an arbitrary value, say, 0. P ′ is a (discrete) px-space ({d1 . . . dn}, {p1 . . . pn}) with pi = 1. For a given 1 i n, we consider the document Pi of PrXML cont obtained by putting back in di the continuous nodes of P, where the corresponding leaves still exist. Let Di1 . . . D ik be the k probability distributions over the real numbers represented in the cont nodes of Pi. We define then a continuous probability distribution Pri over R k as the product distribution [START_REF] Ash | Probability & Measure Theory[END_REF] of the Dij 's, i.e., the unique distribution such that Pri(X1 ×

• • • ×X k ) = Di1(X1)ו • • ×D ik (X k ).
Using the inverse of the bijection β discussed earlier, Pri can be translated into a probability distribution over [di]∼ st , the equivalence class of di under ∼st. Let D = ∪ n i=1 [di]∼ st . We then define as already discussed the probability distribution Pr of P on the σ-algebra AD as:

Pr(D ′ ) := n i=1 pi • Pri(D ′ ∩ [di]∼ st ).
Aggregating Continuous Probabilistic Data . Having defined the semantics of continuous p-documents, we now show how the results for aggregate queries obtained in the discrete case can be lifted to the continuous case. Our purpose here is not to give a comprehensive picture of the complexity, as in the discrete case, but to see what kind of tractability results can be obtained. Let us restrict ourself to monoid aggregate functions, and p-documents of PrXML cont,mux,det , which is our main case of tractability in the discrete case. For simplicity, we only deal with single-path queries.

The following result is at the basis of the tractability of monoid aggregate query evaluation in PrXML cont,mux,det . Proposition 26. Let X, Y be independent real-valued random variables with probability density functions f , g and cumulative distribution functions F , G (i.e., F = f , G = g). We have:

1. The density function of X + Y is f * g, the convolution of f and g.

The cumulative distribution function of

max(X, Y ) is F × G. 3. The cumulative distribution function of min(X, Y ) is F + G -F × G.
there is no hope of computing probabilities of aggregate query answers if it is not possible to somehow combine (either symbolically or numerically) the probability distributions of the leaves. The preceding result hints that if we are able to efficiently apply a number of basic operations on our probability distribution functions, we are able to compute the distribution of the min, max or sum. The following operations are required: convex sums (for mux nodes); convolution (for sum, in conjunction with det nodes); integration and multiplication (for min and max, in conjunction with det nodes). One simple case where we can perform these operations efficiently is when cont leaves are piece-wise polynomials of a bounded degree. For a fixed K > 0 let PP(K) be the set of all piecewise polynomial probability distributions whose polynomials have degree K. It is reasonable to assume that such a bound K exists for every application. This bound ensures that the piecewise polynomial representing the distribution of the query answer has degree polynomial in the size of the document. Hence: Theorem 27. For p-documents in PrXML cont,mux,det that are labeled with distributions in PP(K) we have:

1. The distribution of results of queries in SP sum can be computed in polynomial time in the combined size of the input and the output. 2. The distribution of results of queries in SP max and SP min can be computed in polynomial time.

3. All moments of results of queries in SP sum , SP max , and SP min can be computed in polynomial time.

Other results from the discrete case can be generalized to the continuous case. For example, it can be shown that moments of queries in TP sum can be computed in polynomial time over PrXML cont,mux,det (and similarly for SP sum and PrXML cont,cie ), by replacing the cont nodes by the expected value of the represented distribution.

RELATED WORK AND CONCLUSION

Related Work. The probabilistic XML models that have been proposed in the literature can be grouped in two main categories, depending on the kind of supported probabilistic dependencies: PrXML mux,det -like local dependencies [START_REF] Hung | PXML: A probabilistic semistructured data model and algebra[END_REF][START_REF] Hung | Probabilistic interval XML[END_REF][START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF][START_REF] Van Keulen | A probabilistic XML approach to data integration[END_REF], or PrXML cie -like global dependencies [START_REF] Abiteboul | Querying and updating probabilistic information in XML[END_REF][START_REF] Senellart | On the complexity of managing probabilistic XML data[END_REF], in the spirit of c-tables [START_REF] Imieliński | Incomplete information in relational databases[END_REF]. We used here the unifying framework of [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF][START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF].

The complexity of non-aggregate query answering over PrXML mux,det and PrXML cie has been investigated in [START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF][START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF][START_REF] Kimelfeld | Matching twigs in probabilistic XML[END_REF][START_REF] Senellart | On the complexity of managing probabilistic XML data[END_REF]. Several results presented here either extend or use these works. The dynamic-programming algorithm for computing the probability of a Boolean tree-pattern query from [START_REF] Kimelfeld | Query efficiency in probabilistic XML models[END_REF][START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF][START_REF] Kimelfeld | Matching twigs in probabilistic XML[END_REF] is in particular used for Claim 2 of Theorem 22. The same authors have also studied in [START_REF] Cohen | Incorporating constraints in probabilistic XML[END_REF] the problem of treepattern query answering over PrXML mux,det documents with constraints expressed using aggregate functions, i.e., something similar to the HAVING queries of SQL. We use their results for proving Claim 2 of Theorem 21.

Only a few works have considered aggregate queries in a setting of incomplete data. In non-probabilistic settings aggregate queries were studied for conditional tables [START_REF] Lechtenbörger | Aggregate queries over conditional tables[END_REF], for data exchange [START_REF] Afrati | Answering aggregate queries in data exchange[END_REF] and for ontologies [START_REF] Calvanese | Aggregate queries over ontologies[END_REF]. In probabilistic settings, to the best of our knowledge, in addition to the aforementioned [START_REF] Cohen | Incorporating constraints in probabilistic XML[END_REF], only [START_REF] Ré | Efficient evaluation of HAVING queries on a probabilistic database[END_REF] studies aggregate queries. Ré and Suciu consider the problem of evaluating HAVING queries (using aggregate functions) in "block-independent databases", which are roughly PrXML mux,det restricted to relations (limited-depth trees). The complexity bounds of Claim 3 of Theorem 21 use similar arguments than the corresponding results for block-independent databases presented in [START_REF] Ré | Efficient evaluation of HAVING queries on a probabilistic database[END_REF]. In both [START_REF] Cohen | Incorporating constraints in probabilistic XML[END_REF] and [START_REF] Ré | Efficient evaluation of HAVING queries on a probabilistic database[END_REF], the authors discuss the filtering of possible words that do not satisfy a condition expressed using aggregate functions, and do not consider the problem of computing the distribution of the aggregation, or moments thereof. Computation of the expected value of aggregate functions over a data stream of probabilistically independent data items is considered in [START_REF] Jayram | Efficient aggregation algorithms for probabilistic data[END_REF]. This is a simpler setting than ours, but we use similar techniques in the proof of Theorem 22.

There is very little earlier work on querying continuous probability distributions. The authors of [START_REF] Deshpande | Model-driven data acquisition in sensor networks[END_REF] build a (continuous) probabilistic model of a sensor network to run subsequent queries on the model instead of the original data. In [START_REF] Cheng | Evaluating probabilistic queries over imprecise data[END_REF], algorithms are proposed for answering simple classes of queries over uncertain information, typically given by a sensor network. As noted in a recent survey on probabilistic relational databases [START_REF] Dalvi | Probabilistic databases: Diamonds in the dirt[END_REF], "although probabilistic databases with continuous attributes are needed in some applications, no formal semantics in terms of possible worlds has been proposed so far". We proposed in Section 8 such a formal semantics.

Conclusion.

We provided algorithms for, and a characterization of the complexity of, computing aggregate queries for both PrXML mux,det and PrXML cie models, i.e., very general and most interesting probabilistic XML models. We also considered the expected value and other moments, i.e., summaries of the probability distribution of the results of aggregate functions. In the case of PrXML mux,det , we have identified a fundamental property of aggregate functions, that of being monoid, that entails tractability. The complexity of aggregate computations in many cases has led us to introduce polynomial-time randomized approximation schemes. Finally, a last original contribution has been the definition of a formal continuous extension of probabilistic XML models. We have shown how some of the results of the discrete case can be adapted.

Because our work has many facets, it may be extended in a number of directions. First, we intend implement a system that manages imprecise data with aggregate functions. In particular, we want the system to handle continuous probabilities, which are quite useful in practice. A main novelty of the present work is the use of continuous probabilities for data values. We are currently developing the theory in this direction. Finally, observe that although a p-document (with continuous probabilities) represents uncountably infinite possible worlds, they only have finitely many possible structural equivalence classes, and in particular, they all are of bounded height and width. It would be interesting to investigate extensions of the model without this restriction.

Figure 1 :

 1 Figure 1: Document d: personnel in IT department.

Figure 2 :Example 2 .

 22 Figure 2: Query: sum of bonuses for Mary.

Figure 3 :

 3 Figure 3: PrXML cie p-document: IT department.

Example 4 .

 4 One can obtain the document d in Figure 1 by applying the randomized process to the p-document in Figure 4. Then the probability of d is Pr(d) = .75 × .9 × .7 = .4725. One can also obtain d from the p-document in Figure 3, assuming that Pr(x) = .85 and Pr(z) = .055, by assigning {x/1, z/1}. In this case the probability of d is Pr(d) = .85 × .055 = .04675.

15 [

 15

Figure 4 :

 4 Figure 4: PrXML mux,det p-document: IT department.

Table 1 :

 1 ProbabilityFP #P -c FP #P -c FP #P -c Moments count, sum P others FP #P -c FP #P -c FP #P -c Data complexity of query evaluation over PrXML cie . NP-c means NP-complete.

Figure 5 :

 5 Figure 5: Distribution of monoid functions over composed PrXML mux,det documents.

  is a polynomial. (The points x1, . . . , xn-1 are the partition points and the intervals I1, . . . , Im are the partition intervals of f .) Every piecewise polynomial function f 1 with

Table 2 : Data complexity of query evaluation over PrXML mux,det

 2

	PrXML mux,det		Aggregate query language
			SP, TP	TPJ
	Membership		sum, avg, countd NP-c
			count, min P	count, min NP
	Probability	avg, countd FP #P -c count, min P	FP #P -c
	Probability (for sum)	SP P *	TP FP #P	FP #P -c
		SP	TP
	Moments	P	avg FP #P others P	FP #P -c

. NP-c means NP-complete, NP means membership in NP and * means in the size of |in-put|+|distribution|.

  The data in the document are measurements at time 3 by sb and at time 5 by either sa or sc. At time 3 the measurement is either 17, or a value in the interval from 15 to 19. The fact the latter value is unknown and can be anywhere between 15 and 19 is represented by a continuous node cont(U ([15; 19]), where U stands for the uniform distribution. We know that both sensors sa and sc have an inherent imprecision and the real measurement is normally distributed around the one they sent. We model it by a continuous node with a normal distribution cont(N (25; 1)) with mean 25 and variance 1.

	cont, mux, det:		[1] monitoring
					[2] sensor				[3] sensor
			[4] id	[5] measurement	[6] id	[7] measurement
		0.75	mux	.25	[22] time	[31] value	[41]	sb	[55] time	[50] value
	[8]	sa	[13]	sc	[23]	5	[32]	N(25,1)			[56]	3	[51] 0.4	mux
												[52]	17	[53]	U[15,19]
	Figure 6: PrXML cont,mux,det p-document: monitoring.
	in Figure 6. The document collects results of (e.g., tempera-
	ture) monitoring by sensors sa, sb and sc.

We denote the labeling function for queries as λ in order to distinguish it from the labeling function θ for documents.

In[START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF], the root is also required to be ordinary. For technical reasons, we do not use that restriction here.

It may seem that using det nodes is redundant, but actually they increase the expressive power when used together with mux and other types of distributional nodes[START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF]: mux alone can express that subtrees are mutually exclusive, but in combination with det it can also express this on subforests.

The variance is the central moment of order 2; it is known that the central moment of order k can be tractably computed from the regular moments of order k.

* This research was funded by the European Research Council grant Webdam (under FP7), grant agreement 226513, and by the Dataring project of the French ANR. † The author is co-affiliated with INRIA Saclay.


Philippe De Reffye

Sébastien Lemaire

Nitish Srivastava

Fabienne Maupas

Paul-Henry Cournède
email: paul-henry.cournede@ecp.fr

Modeling Inter-Individual Variability in Sugar Beet Populations

Modeling heterogeneity in field crops is a key issue for a better characterization of field production. This paper presents some experimental data on sugar beet illustrating this heterogeneity. Several sources of individual variability within plant populations are identified: namely, initial condition (seed biomass, emergence delay), genetic variability (including phyllochron) and environment (including spacing and competition). A mathematical framework is introduced to integrate the different sources of variability in plant growth models. It is based on the classical method of Taylor Series Expansion, which allows the propagation of uncertainty in the dynamic system of growth and the computation of the approximate means and standard deviations of the model outputs. The method is applied to the GreenLab model of plant growth and more specifically to sugar beet. It opens perspectives in order to assess the different sources of variability in plant populations and estimate their parameters from experimental data. However important issues like optimization of data collection and system identifiability have to be resolved first, since the uncertainty effects may be mixed in an inextricable way or may necessitate a too huge amount of experimental data for their estimation.

Introduction

Modeling crops as communities of individual plants has brought new insights to understand and describe crop production [START_REF] Fournier | A 3d architectural and processbased model of maize development[END_REF], and can be seen as a complementary approach to the more classical crop / process-based models describing ecophysiological processes per field unit surface area [START_REF] De Reffye | Plant growth models[END_REF]. The literature on individual-based plant growth models is now abundant (we refer to [START_REF] Vos | Functional-structural plant modelling in crop production[END_REF] introducing some of the most recent advances). Such models are usually seen as integrative systems, allowing a very detailed description of ecophysiological processes, at different biological scales [START_REF] Buck-Sorlin | A rule-based model of barley morphogenesis, with special respect to shading and gibberellic acid signal transduction[END_REF].

So far, few of them aim at a real predictive capacity and are calibrated from experimental data [START_REF] Guo | Parameter optimization and field validation of the functional-structural model greenlab for maize[END_REF], [START_REF] Luquet | Ecomeristem, a model of morphogenesis and competition among sinks in rice. 1. concept, validation and sensitivity analysis[END_REF], [START_REF] Wernecke | The virtual crop-modelling system 'vica' specified for barley[END_REF]. Likewise, the extrapolation of individual-based models to the field scale is still at its early stages. It mostly concerns competition for light, by considering radiosity models to compute light interception [START_REF] Fournier | ADEL-maize: An L-system based model for the integration of growth process from the organ to the canopy. application to regulation of morphogenesis by light availability[END_REF] or empirical functions to describe interactions between neighbours [START_REF] Cournède | Computing competition for light in the Green-Lab model of plant growth: a contribution to the study of the effects of density on resource acquisition and architectural development[END_REF]. The latter approach based on the GreenLab model of plant growth has led to model calibration at the population level in different density conditions for maize [START_REF] Ma | Parameter optimization and field validation of the functional-structural model greenlab for maize at different population densities[END_REF], tomato [START_REF] Dong | Does the structure-fonction model greenlab deal with crop phenotypic plasticity induced by plant spacing? a case study on tomato[END_REF] or sugar beet [START_REF] Lemaire | Analysis of the density effects on the source-sink dynamics in sugar-beet growth[END_REF]. The calibration process is based on an average individual plant. Such result is an improvement compared to classical crop models giving the compartment biomasses per unit surface area, since beside the compartments which are also simulated, the average plant is described at the organ level. However, owing to the strong variability among individuals, only predicting the average plant growth is also restrictive, it only gives a partial characterization of field production. The objective of this paper is to identify the different sources of variability in sugar beet growth and propose a mathematical framework based on the theory of uncertainty propagation ( [START_REF] Julier | A new method for the nonlinear transformation of means and covariances in filters and estimators[END_REF], [START_REF] Beveridge | Axillary meristem development. budding relationships between networks controlling flowering, branching, and photoperiod responsiveness[END_REF]) to integrate this variability in individual plant growth models. This way, we are able to describe the statistical distribution of individual productions and architectures in a population of plants. Such method can be seen as a first step towards the design of population models. Section 2 introduces some experimental results for sugar beet underlining the strong heterogeneity within a population. The different sources of variability are also identified. In Section 3, we recall some basic concepts of the Taylor Series Expansion (TSE) method to propagate uncertainty in dynamic system and show how to apply it to the GreenLab model of plant growth. Some computations are performed to compare the approximations of means and standard deviations of model outputs to Monte Carlo simulations. Finally, the perspectives of such method for parametric estimation or for applications to other crops are discussed.

Inter-individual variability in sugar beet populations

Field experiments were conducted in 2006 by the ITB (Instut Technique de la Betterave sucrière) to investigate the source-sink dynamics of sugar beet growth with the GreenLab model (see [START_REF] Lemaire | A morphogenetic crop model for sugar-beet (beta vulgaris l.)[END_REF] for more details on the experimental work). The final population was estimated to be 9.6 plants per m 2 . The thermal time, corresponding to the accumulation of daily temperature above a base temperature (0 • C) was calculated from emergence. Destructive biomass measurements were carried out at eighteen different stages during the growing period. At each date, 15 individual plants were selected and the dry masses were measured at the level of organ compartments: total dry mass of blades, that of petioles and that of root. The final stage of measurements corresponds to harvest. The results are shown in Figure 1 and reveal a very strong variability among individuals. For mono-specific crops, 3 sources of individual variability are identified [START_REF] Liu | Response of corn grain yield to spatial and temporal variability in emergence[END_REF]: first, growth initial conditions, which are given by the seed biomass and emergence delay; second the environmental conditions, which may strongly vary in a field, from one plant to another, (including spacing with neighbours); finally genetic variability: some species, like sugar beet, are not pure-bred [START_REF] Bosemark | Genetics and breeding[END_REF] and it may result in variable responses to growth environmental conditions among individuals. A good illustration of this genetic variability in sugar beet is given by the phyllochron (that is to say the thermal time elapsing between the appearance of two successive leaves). For most crops, the phyllochron usually shows a good range of stability, even though it may be strongly affected by environmental factors, see [START_REF] Clerget | Variability of phyllochron, plastochron and rate of increase in height in photoperiod-sensitive sorghum varieties[END_REF] for a short review on the main results for different plants. In sugar beet populations, [START_REF] Lemaire | Analysis of the density effects on the source-sink dynamics in sugar-beet growth[END_REF] found that the mean phyllochron is extremely stable (during the first stage of growth) among seasons and for different density, hydric and nitrogen conditions. However, if the mean is stable, the differences among individuals are very important as shown by Figure 2. Such strong variability between individuals within a cultivar was reported by other authors (see for exemple [START_REF] Frank | Phyllochron differences in wheat, barley, and forage grasses[END_REF]). The key issue is thus to set a proper framework to integrate the different sources of variability in individual plant growth models. It is examined in the next section.

Propagation of uncertainty in plant growth models

In forest ecosystem modeling, some results were obtained to assess the effects of individual variability for static allometry models ( [START_REF] Dietze | Capturing diversity and interspecific variability in allometries: A hierarchical approach[END_REF], [START_REF] Vieilledent | Structurer l'incertitude et la variabilité dans les modèles de dynamique forestière[END_REF]) in the statistical frame of hierarchical models. The problem is more complex for dynamic system of plant growth: the different sources of variability given above may be seen as uncertain inputs of the dynamic system, and the variability in system outputs results from the propagation of probabilistic uncertainty. This issue has already been studied in the context of crop models [START_REF] Monod | Uncertainty and sensitivity analysis for crop models[END_REF]. The proposed method to study the output distribution is based on Monte Carlo sampling, which might be restrictive regarding the computing cost when model inversion is involved (for parameter estimation at population level for example) or to solve optimization problems. There exist several other methods widely used in physics [START_REF] Julier | A new method for the nonlinear transformation of means and covariances in filters and estimators[END_REF], [START_REF] Bevington | Data reduction and error analysis for the physical sciences[END_REF] that overcome this difficulty. Here, we recall a method to compute uncertainty propagation based on Taylor series expansion, and we apply it in the context of the GreenLab model of plant growth.

A general method based on Taylor series expansion

We recall here the basic concepts of the classical Taylor Series Expansion (TSE) method (see for exemple [START_REF] Morgan | Uncertainty[END_REF] for more details). Let x be a random vector in R d with mean x and covariance matrix P . Let g : R d → R a transformation of x, y = g(x). Statistics on y can be obtained by Monte Carlo simulations [START_REF] Monod | Uncertainty and sensitivity analysis for crop models[END_REF]. However, the evaluation cost of g can be prohibitive for such simulations. A classical approximation of the moments of g(x) can be obtained by considering the multivariate Taylor series expansion of g(x) about x [START_REF] Julier | A new method for the nonlinear transformation of means and covariances in filters and estimators[END_REF]. If we consider x as the sum of x and a zero-mean disturbance ∆x, we have for all n > 0:

g(x) = g (x)+D∆xg (x)+ D 2 ∆x g (x) 2! +• • •+ D n ∆x g (x) n! +o ( ∆x n ) (1)
where D ∆x is the differential operator corresponding to the perturbation ∆x

D ∆x = d i=1 ∆x i ∂ ∂x i such that D ∆x g (x) = d i=1 ∆x i ∂g ∂x i (x)
and

D i ∆x g (x) =   d i=1 ∆x i ∂ ∂x i i g   (x) .
We can approximate the expectation and variance of g(x), respectively E [g(x)] and V [g(x)] thanks to the Taylor series (1). Since ∆x is zero-mean variable, its first moment is zero, and we have:

E [g(x)] = g (x) + 1 2 i,j ∂ 2 g ∂xi∂xj (x) E [∆x i ∆x j ] +E 1 3! D 3 ∆x g (x) + • • •
, and we finally have the approximation, with an error at the third order:

E [g(x)] ≈ g (x) + 1 2 i,j ∂ 2 g ∂x i ∂x j (x) P ij . (2)
For the variance, we have:

V ar [g(x)] = E (g(x) -E [g(x)]) 2 , with g(x) -E [g(x)] = D∆xg (x) + D 2 ∆x g (x) 2! + D 3 ∆x g (x) 3! + • • • - 1 2 i,j ∂g ∂xi (x) ∂g ∂xi (x) Pij -E D 3 ∆x g (x) 3! + • • •
and we have the approximation with an error at the third order given by:

V ar [g(x)] ≈ E (D ∆x g (x))
2 and thus

V ar [g(x)] ≈ i,j ∂g ∂x i (x) ∂g ∂x j (x) P ij . (3)
Remark 1: Since the standard deviation is the square root of the variance and is comparable to x (same unit), the order of the approximation for the variance in 3 may prove unsufficient. We shall consider increasing the order of the approximation, but it requires the knowledge of the moments of higer orders for the distribution of x.

Remark 2: If g is not scalar and takes its value in R m , the same principle applies for each component function g k , 1 ≤ k ≤ m. The only difference is that we also need to determine an approximation of all Cov (g k (x), g l (x)) given by:

Cov (g k (x), g l (x)) ≈ i,j ∂g k ∂x i (x) ∂g l ∂x j (x) P ij .

Application to the GreenLab equation of plant growth

In this section, we first show how to characterize the production distribution in a plant population on a simple example. We suppose that the main source of variability in the population is the seed mass, which is given by a Gaussian law N (u 0 , σ 0 ), and we want to deduce the distribution of the total biomass produced by each individual in the population at a given time T . In GreenLab, the time step is chosen to coincide with the growth cycle, based on phytomer appearance. T growth cycles thus correspond to T phyllochrons. We recall the classical GreenLab equation giving Q t , plant biomass production at growth cycle t related to Beer's law [START_REF] Cournède | Computing competition for light in the Green-Lab model of plant growth: a contribution to the study of the effects of density on resource acquisition and architectural development[END_REF]:

Q t = E t µS p 1 -exp -k S t S p (4)
where E t is the environmental input at growth cycle t, µ is plant efficiency, S p is a characteristic surface related to plant competition, k is Beer's coefficient of light interception and S t is the photosynthetic leaf surface area at growth cycle t. Since S t is the result of successive biomass allocation to leaves, S t is a function of biomass production at the previous cycles Q t-1 , Q t-2 , . . . We get (see [START_REF] Cournède | Dynamic system of plant growth[END_REF]):

S t = - 1 e t-1 k=t-T b Q k D k   k+T b -t j=0 N k b (j)p k b (j)   (5)
with N k b (j), the number of leaves of chronological age j at growth cycle k, p k b (j) their corresponding sinks, T b leaf life span, e specific blade mass (supposed constant) and D k plant demand at growth cycle k computed as the sum of all living sinks at growth cycle k. If there is no retroaction of growth on plant organogenesis, the functions giving the numbers of organs as well as the demand are given. The environmental function E t is also supposed given. Therefore, substituting Eq. ( 5) into Eq. ( 4) yields a recurrent equation of order T b for the sequence

(Q t ) t .
For a direct application of the method presented in Section 3.1, we first rewrite the dynamic system of growth. Let us define the state vector X t ∈ R T +1 as :

X t =               Q 0 Q 1 . . . Q t 0 0 . . . 0               (6)
The system evolution equation is thus written for all n ≤ T -1:

X t+1 = F t (X t ) (7)
with (F t ) i , 1 ≤ i ≤ T + 1, the components of F t given by:

F t i (X) = (X) i for 1 ≤ i ≤ t + 1 , (8)
F t t+2 (X) = E t+1 µS p 1 -exp kS t+1 S p (9)
with

S t+1 = 1 e t k=t-T b +1 X k+1 N k • p k   k+T b -t-1 j=0 N k b (j)p k b (j)   .
(10) and

F t i (X) = 0 for t + 2 < i ≤ T + 1 . (11)
We can apply the methodology introduced in Section 3.1 to propagate the uncertainty in the dynamic system in the form of Equation [START_REF] Wernecke | The virtual crop-modelling system 'vica' specified for barley[END_REF]. In this way, we can determine recursively an approximation of the distribution moments of X T . Note that partial derivatives can be computed analytically. The initial condition is given by:

X 0 =      u 0 0 . . . 0      and Cov X 0 =      σ 2 0 0 • • • 0 0 0 • • • 0 . . . . . . . . . . . . 0 • • • 0 0     
and if we suppose known X t and Cov (X t ), we deduce X t+1 and Cov X t+1 as follows.

• For the mean:

-if 1 ≤ i ≤ T + 1, i = t + 2: X t+1 i = X t i , - and
X t+1 t+2 = F t t+2 X t + 1 2 i,j ∂ 2 F t t+2 ∂X i ∂X j X t Cov X t ij .
• For the covariance:

-for

1 ≤ i ≤ t + 1, 1 ≤ j ≤ t + 1: Cov X t+1 ij = Cov X t+1 i , X t+1 j ij = Cov X t ij -for i > t + 2 ou j > t + 2: Cov X t+1 ij = 0 -finally, for j < t + 2: Cov X t+1 t+2 , X t+1 j = k,l ∂F t t+2 ∂X k X t ∂F t j ∂X l X t Cov X t kl ,
and

Cov X t+1 j , X t+1 t+2 = Cov X t+1 t+2 , X t+1 j .
It is also possible to choose an approximation of higer order. Finally, we obtain the approximations of the mean and variance of plant biomass production at any growth cycle t, since:

Q t = X t t+1 and V ar Q t = Cov X t t+1 , X t t+1 .
A numerical application of these results is given in Figure 3, in which are shown the evolutions of the mean and standard deviation of biomass production with the growth cycle. For the gaussian distribution of seed biomass, we have chosen standard deviations corresponding to 10% and 20% of the mean seed mass. There is a very good agreement between the Monte Carlo simulations and the approximations given by the theoretical formula ( 12) and [START_REF] Julier | A new method for the nonlinear transformation of means and covariances in filters and estimators[END_REF], which seems to indicate a good range of validity for the TSE method. It is interesting to note that the standard deviation of the biomass production reaches a peak and then decreases to zero. The reason is the saturation of biomass production due to Beer's law: after some time, even the plants with the smallest seeds will reach the limit production in our example.

All the variables of interest (organ masses, compartment masses. . . ) can be obtained as linear combinations of (Q t ) t , therefore it is straightforward to get their approximate means and variances. For example, for the total plant biomass M (T ), we have:

M (T ) = T +1 i=0 X T i , (12)
with variance

V ar (M (T )) = k,l Cov X T kl . (13)
We now turn to a more complex computation, which we perform for conditions close to those of sugar beet population. We use the parameters estimated from 2006 experimental data and given in [START_REF] Lemaire | A morphogenetic crop model for sugar-beet (beta vulgaris l.)[END_REF] and we choose to consider 4 soures of variability, all gaussian: seed biomass, local environment E t , competition effects due to uneven spacing, which is characterized in the GreenLab model by the parameter S p , and phyllochron. The emergence delay is not taken into account since the experimental observations showed a delay inferior to the phyllochron. The formula giving the approximation formula for the mean and variance of biomass production are not presented in details but derive from the multivariate versions of Equations ( 2) and (3). The computations are heavy but quite straightforward. The results are shown in Figure 4: the standard deviation of seed biomass Q 0 corresponds to 20% of the mean mass; the environment E t is chosen constant for an individual plant, but with a standard deviation of 10% of its mean value in the population; S p has a standard deviation of 10% of its mean value in the population; and the standard deviation of the phyllochron is also 10% of its mean value. The approximation formula are compared to Monte Carlo simulation results. Small differences appear, but remain acceptable. We also compute the correlation coefficients between the growth rate Q t and the variation factors u 0 , E, S p and P (Phyllochron) during plant growth. The results are given in Figure 5. It is interesting to see that, in keeping with our remark on the previous exemple, the effect of seed variation decreases to zero, while the variation of S p has no effect at the beginning and increases when the leaf area index begins to saturate. The effect of the environment variation is important during the whole growth as expected. The evolution of the correlation between Q t and the phyllochron (r QP ) is interesting: the plant takes advantage of a longer phyllochron in the early and late stages of growth, while the influence is less (or even negative) in the mid-stage. It can be explained by the evolution of the ratio of the competing sinks at the beginning of growth: blade sink variation function increases quicker than that of petiole. Thus, having older organs (which is a consequence of a longer phyllochron) favour the development of leaf surface area and consequently Q t . The influence decreases when biomass production saturates, but when senescence starts, the effects of the early differences are visible again.

Discussion

Experimental observations of sugar beet populations have revealed a very strong inter-individual variability. In order to take into account this variability and to improve the statistical description of the population, we have proposed a framework to integrate different sources of variability in an individual-based crop model, GreenLab. The classical Taylor series expansion method is used to propagate uncertainty in the dynamic system of plant growth. Good approximations of the mean and standard deviations of the variables of interest (organ or compartment masses, biomass production. . . ) can be computed. When the sources of variability are well characterized, the method is simply a way to bypass Monte Carlo simulations.

A more interesting application is when the sources of variability are identified but not fully characterized: the method is well-adapted to model inversion (contrary to Monte Carlo simulations) and to the estimation of uncertainty distribution parameters (mean, standard deviation). If the experimental sampling is important enough, the experimental target to fit is composed of both mean values and standard deviations and such outputs are provided by the model. Some preliminary fitting experiments, not presented in this paper, were performed and gave some indications. They seem to work well when one or two sources of variability are considered, but when too many sources are considered together, some identifiability problems seem to occur: it is difficult to distinguish between all the variance effects. Some complementary studies are needed to fully assess the identification method. It is interesting to note that the computation have been done without using the Gaussian hypothesis. Only the means and standard deviations of the sources of variability are considered. However, for strongly non-linear systems, we may need to increase the approximation order, which would require the knowledge of higher order moments (which are easily obtained, for example, under the Gaussian hypothesis). Likewise, when the levels of variations become important, we have to study in more details the quality of the approximation. We have seen in Figure 4 that approximations given by Equations ( 2) and (3) begin to show some defaults when several sources of variability are considered together at reasonable levels corresponding to variation coefficients of 10%. It is always possible to increase the approximation order (see [START_REF] Morgan | Uncertainty[END_REF]), but the formulas become tedious. Resorting to symbolic computation software may prove of great help to perform differentiation. Finally, if this method was illustrated on sugar beet, it seems potentially applicable to a wide variety of crops and its interest is crucial for heterogeneous crops, e.g. rapeseed. From a purely theoretical point of view, there is no limit to the method, as long as the underlying model is properly defined. However, the computation might prove very complex, as well as the data collection, since an important amount of individuals have to be measured to get proper information on variances within population. Moreover, the confrontation to experimental data might raise the issue of system identifiability since the variability effects might be too strongly inter-connected. The next step is thus to study in details the parametric estimation from experimental data derived from this modeling approach taking into account inter-individual variability within plant populations.

Figure 1 .

 1 Figure 1. Individual variability in sugar beet fields: shoot and root dry masses versus thermal time for all measured individuals.

Figure 2 .

 2 Figure 2. Inter-individual variability of sugar beet phyllochron: number of phytomers versus thermal time for all measured individuals.

Figure 3 .

 3 Figure 3. Effects of the variance in seed biomass: (a) the red line gives the evolution of the approximation of mean biomass production for σ0 = 0.1 and the blue line for σ0 = 0.2 (both lines are superposed); the dots are the corresponding Monte Carlo results for 10 4 simulations. (b) The red line gives the evolution of the standard deviation of biomass production for σ0 = 0.1 and the blue line for σ0 = 0.2; the dots are the corresponding Monte Carlo results for 10 4 simulations.

Figure 4 .

 4 Figure 4. Effects of the variances in seed biomass u 0 , environment E, S p and phyllochron P : (a) the red line gives the evolution of the mean biomass production computed with the approximation formula, the dots are the corresponding Monte Carlo results for 10 4 simulations; (b) the blue line gives the evolution of standard deviation in biomass production computed with the approximation formula, the dots are the corresponding Monte Carlo results for 10 4 simulations.

Figure 5 .

 5 Figure 5. Evolution of the correlations between Q t and the different sources of variability: seed biomass u 0 (r Qu0 ), environment E t (r QE ), local competition S p (r QSp ) and phyllochron P (r QP ).

Acknowledgment

The authors would like to thank the two anonymous reviewers for helping improving the clarity of the manuscript. N. Srivastava is supported by the Summer Undergraduate Research Grant for Excellence (SURGE) between IIT Kanpur and Centrale Paris.