Patent ID: 8234295

Claim:
A method comprising: specifying data uncertainty using at least one variable generation (VG) function, wherein said VG function generates pseudorandom samples of uncertain data values; specifying a random database based on said VG function; generating a number N Monte Carlo instantiations of said random database, wherein N is a number greater than 1; identifying a database tuple bundle t, wherein the database tuple bundle t is a data structure representing N instantiations of a tuple in the N Monte Carlo instantiations; using a processor, executing a query Q over the N Monte Carlo instantiations, wherein said query Q is an aggregation query, wherein said executing comprises: executing a query plan for the query Q once over the set of all database tuple bundles; and outputting zero or more numerical values that are used to estimate statistical properties of the probability distribution of the result of the query Q, wherein said outputting comprises outputting a set of pairs (v,f), where each v is a distinct tuple and f is a fraction of said Monte Carlo instantiations in which said tuple v appears at least once in a query result; computing a table having entries of the form (v,n), wherein v is a query-result and n is a number of N Monte Carlo instantiations in which the query result is equal to v; and executing a second query over the table to obtain an estimate of a statistical property of the probability distribution of the result of the query Q.