Managing uncertain data using Monte Carlo techniques

• US 9,063,987 B2
• Filed: 06/13/2012
• Issued: 06/23/2015
• Est. Priority Date: 06/03/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Haas, Peter J, Jampani, Ravindranath, Wu, Mingxi, Xu, Fei, Jermaine, Christopher M, Perez, Luis L
• Primary Examiner(s): SYED, FARHAN M
• Application Number:
  US13/495,610
• Publication Number:
  US 20120254238A1
• Time in Patent Office: 1,105 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

According to one embodiment of the present invention, a method for managing uncertain data is provided. The method includes specifying data uncertainty using at least one variable generation (VG) function. The VG function generates pseudorandom samples of uncertain data values. A random database based on the VG function is specified and multiple Monte Carlo instantiations of the random database are generated. Using a Monte Carlo method, a query is repeatedly executed over the multiple Monte Carlo instantiations to output a Monte Carlo method result and associated query-results. The Monte Carlo method result may then be used to estimate statistical properties of a probability distribution of the query-result.

Claims

1. A computer implemented 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, by a processor coupled to memory, a number of N Monte Carlo instantiations of said random database, wherein N is a number greater than 1;

identifying a plurality of database tuple bundles t, wherein each of the plurality of database tuple bundles t is a data structure comprising a correlated tuple from each of the N Monte Carlo instantiations;

representing the plurality of database tuple bundles t in a compressed form in which only pseudorandom numbers used to generate the uncertain data values are represented;

expanding the plurality of database tuple bundles t represented in the compressed form to an expanded form, wherein the plurality of database tuple bundles t is represented in the expanded form when all instantiated attribute values are explicitly represented;

executing, by a processor coupled to memory, a query Q over the N Monte Carlo instantiations, wherein said executing comprises;

executing a query plan for the query Q once over each of the plurality of database tuple bundles; and

outputting query-results, where zero or more numerical values that are used to estimate statistical properties of the probability distribution of the result of the query Q;

maintaining a running statistical property of query-results as each query-result is determined, wherein each query-result corresponds to one or more of the N Monte Carlo instantiations; and

after N query-results are determined, outputting the final value of the running statistical property to be the estimated statistical property of the probability distribution of the result of the query Q.

2. The method according to claim 1, where executing the query plan further comprises filtering out tuples based on the compressed form of the plurality of database tuple bundles.

3. The method according to claim 1 wherein said outputting comprises outputting a set of pairs (v,f), where each v is a distinct tuple and f is the fraction of said Monte Carlo instantiations in which said tuple v appears at least once in a query result.

4. The method according to claim 1, wherein the second query computes an average of query-results in the table.

5. The method of claim 1, further comprising:

outputting N query-results, wherein each query-result corresponds to one of the N Monte Carlo instantiations; and

using the N query-results, computing an estimate of a statistical property of the probability distribution of the result of the query Q.

6. The method according to claim 1, wherein specifying said random database based on the VG function comprises specifying random tables based on the VG function.

7. A computer-implemented 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, by a processor coupled to memory, a number N Monte Carlo instantiations of said random database, wherein N is a number greater than 1;

representing the plurality of database tuple bundles t in a compressed form in which only pseudorandom numbers used to generate the uncertain data values are represented;

expanding the plurality of database tuple bundles t represented in the compressed form to an expanded form, wherein the plurality of database tuple bundles t is represented in the expanded form when all instantiated attribute values are explicitly represented;

repeatedly executing a query, by the processor coupled to memory, over said multiple Monte Carlo instantiations to output a Monte Carlo result and associated query-results by identifying a plurality of database tuple bundles comprising correlated tuples from each of the Monte Carlo instantiations and executing the query on each of the plurality of database tuple bundles; and

estimating statistical properties of the probability distribution of said query-result;

maintaining a running statistical property of query-results as each query-result is determined, wherein each query-result corresponds to one or more of the N Monte Carlo instantiations; and

after N query-results are determined, outputting the final value of the running statistical property to be the estimated statistical property of the probability distribution of the result of the query Q.

8. The method according to claim 7, wherein specifying said random database based on said VG function comprises specifying random tables based on said VG function.

9. The method according to claim 8, wherein specifying random tables based on said VG function comprises specifying random tables of a relational database based on said VG function.

10. The method according to claim 7, wherein said VG function is user-defined.

11. The method according to claim 10, wherein the VG function is parameterized and is based on results of SQL queries executed over parameter tables stored in a relational database.

12. A system comprising:

a database containing data values and zero or more parameters tables;

a variable generation (VG) function component that receives the results of SQL queries over said parameters as input and that output pseudorandom samples of said uncertain data values;

a random database comprising said pseudorandom samples;

specifying a random database based on said VG function;

a processor generating multiple Monte Carlo instantiations of said random database;

a query execution component receiving a query and executing a query over said multiple Monte Carlo instantiations to output a Monte Carlo result and associated query-results by identifying a plurality of database tuple bundles comprising correlated tuples from each of the Monte Carlo instantiations and executing the query on each of the plurality of database tuple bundles, wherein the plurality of database tuple bundles are in a compressed form in which only pseudorandom numbers used to generate the uncertain data values are represented and expand the plurality of database tuple bundles t represented in the compressed form to an expanded form, wherein the plurality of database tuple bundles t is represented in the expanded form when all instantiated attribute values are explicitly represented; and

a statistical property estimator receiving said Monte Carlo result, estimating statistical properties of the probability distribution of said query result, maintaining a running statistical property of query results as each query result is determined, wherein each query result corresponds to one or more of the N Monte Carlo instantiations; and

outputting the final value of the running statistical property, after N query results are determined, wherein the running statistical property to be the estimated statistical property of the probability distribution of the result of the query Q.

13. A computer program product for managing uncertain data, said computer program product comprising a non-transitory computer readable medium having computer usable program code embodied therewith, said computer usable program code configured to:

specify data uncertainty using at least one variable generation (VG) function, wherein said VG function generates pseudorandom samples of uncertain data values;

specify a random database based on said VG function;

generate a number N Monte Carlo instantiations of said random database, wherein N is a number greater than 1;

represent the plurality of database tuple bundles t in a compressed form in which only pseudorandom numbers used to generate the uncertain data values are represented;

expand the plurality of database tuple bundles t represented in the compressed form to an expanded form, wherein the plurality of database tuple bundles t is represented in the expanded form when all instantiated attribute values are explicitly represented;

repeatedly execute a query over said multiple Monte Carlo instantiations to output a Monte Carlo result and associated query-results by identifying a plurality of database tuple bundles comprising correlated tuples from each of the Monte Carlo instantiations and executing the query on each of the plurality of database tuple bundles; and

estimate statistical properties of the probability distribution of said query-result;

maintain a running statistical property of query-results as each query-result is determined, wherein each query-result corresponds to one or more of the N Monte Carlo instantiations; and

after N query-results are determined, output the final value of the running statistical property to be the estimated statistical property of the probability distribution of the result of the query Q.