SYNTHETIC DATA GENERATION

1 . A method for data generation, comprising:

identifying a generative probability distribution based on one or more cardinality constraints for populating a database table;

selecting one or more values for a corresponding one or more attributes in the database table based on the generative probability distribution and the cardinality constraints; and

generating a tuple for the database table, wherein the tuple comprises the one or more values.

2 . The method recited in claim 1 , wherein each of the cardinality constraint specifies:

the one or more attributes;

a query predicate; and

a cardinality of a result of running a database query comprising the query predicate against the database table.

3 . The method recited in claim 2 , wherein the generative probability distribution satisfies a property that for each constraint of the cardinality constraints, the probability that the query predicate is true for a tuple sampled from the generative probability distribution is k/N, where k comprises the cardinality, and N comprises a number of tuples in the database table.

4 . The method recited in claim 2 , wherein one of the cardinality constraints represents a preferred characteristic of a database comprising the database table.

5 . The method recited in claim 4 , wherein the preferred characteristic is naturalness, and wherein the cardinality is zero, and wherein the query predicate specifies a comparison between a source table comprising natural attribute values and the database table comprising the values.

6 . The method recited in claim 1 , wherein identifying the generative probability distribution comprises:

constructing a Markov network for a data generation problem (DGP) comprising the cardinality constraints and the database table, wherein the Markov network comprises a graph comprising one or more vertices and one or more edges between the vertices;

converting the Markov network to a chordal graph;

identifying one or more maximal cliques for the chordal graph;

solving for a plurality of marginal distributions of the maximal cliques; and

constructing the generative probability distribution using the marginal distributions.

7 . The method recited in claim 1 , wherein converting the Markov network to a chordal graph comprises adding one or more additional edges to the Markov network.

8 . The method recited in claim 1 , wherein identifying the generative probability distribution comprises:

constructing a Markov network for a data generation problem (DGP) comprising the cardinality constraints and the database table, wherein the Markov network comprises a graph comprising one or more vertices and one or more edges between the vertices;

identifying one or more maximal cliques for the Markov network;

solving for a plurality of marginal distributions of the maximal cliques; and

constructing the generative probability distribution using the marginal distributions.

9 . A system for data generation, comprising:

a processing unit; and

a system memory, wherein the system memory comprises code configured to direct the processing unit to:

construct a Markov network for a data generation problem (DGP) comprising one or more cardinality constraints for populating a database table, wherein the Markov network comprises a graph comprising one or more vertices and one or more edges between the vertices;

convert the Markov network to a chordal graph;

identify one or more maximal cliques for the chordal graph;

solve for a plurality of marginal distributions of the maximal cliques;

construct a generative probability distribution using the marginal distributions;

select one or more values for a corresponding one or more attributes in the database table based on the generative probability distribution and the cardinality constraints; and

generate a tuple for the database table, wherein the tuple comprises the one or more values.

10 . The system recited in claim 9 , wherein the code configured to direct the processing unit to convert the Markov network to a chordal graph comprises code configured to direct the processing unit to add one or more additional edges to the Markov network.

11 . The system recited in claim 9 , wherein each of the cardinality constraints specifies:

the one or more attributes;

a query predicate; and

a cardinality of a result of running a database query comprising the query predicate against the database table.

12 . The system recited in claim 11 , wherein the generative probability distribution satisfies a property that for each constraint of the cardinality constraints, the probability that the query predicate is true for a tuple sampled from the generative probability distribution is k/N, where k comprises the cardinality, and N comprises a number of tuples in the database table.

13 . The system recited in claim 11 , wherein one of the cardinality constraints represents a preferred characteristic of a database comprising the database table.

14 . The system recited in claim 13 , wherein the preferred characteristic is naturalness, and wherein the cardinality is zero, and wherein the query predicate specifies a comparison between a source table comprising natural attribute values and the database table comprising the values.

15 . One or more computer-readable storage media, comprising code configured to direct a processing unit to:

construct a Markov network for a data generation problem (DGP) comprising a plurality of cardinality constraints for populating one or more database tables, wherein the Markov network comprises a graph comprising one or more vertices and one or more edges between the vertices;

identify one or more maximal cliques for the Markov network;

solve for a plurality of marginal distributions of the maximal cliques;

construct the generative probability distribution using the marginal distributions;

select one or more values for a corresponding one or more attributes in the database tables based on the generative probability distribution and the cardinality constraints; and

generate a plurality of tuples for the plurality of database tables, wherein each of the tuples comprises the one or more values.

16 . The one or more computer-readable storage media recited in claim 15 , wherein each of the cardinality constraints specifies:

the one or more attributes;

a query predicate; and

a cardinality of a result of running a database query comprising the query predicate against the database table.

17 . The one or more computer-readable storage media recited in claim 16 , wherein the values are constrained by a plurality of intervals comprising constants specified by each query predicate.

18 . The one or more computer-readable storage media recited in claim 15 , wherein the generative probability distribution satisfies a property that for each constraint of the cardinality constraints, the probability that the query predicate is true for a tuple sampled from the generative probability distribution is k/N, where k comprises the cardinality, and N comprises a number of tuples in the database table.

19 . The one or more computer-readable storage media recited in claim 18 , wherein one of the cardinality constraints represents a preferred characteristic of a database comprising the database table.

20 . The one or more computer-readable storage media recited in claim 19 , wherein the preferred characteristic is naturalness, and wherein the cardinality is zero, and wherein the query predicate specifies a comparison between a source table comprising natural attribute values and the database table comprising the values.