Generating Queries Using Cardinality Constraints

• US 20070185851A1
• Filed: 01/27/2006
• Published: 08/09/2007
• Est. Priority Date: 01/27/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Thomas, Dilys, Chaudhuri, Surajit, Bruno, Nicolas
• Granted Patent: US 7,882,121 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

A query generation using cardinality constraints process including choosing a first set of parameters for a query, calculating an additional set of parameters based on the first set of parameters, executing the query using additional set of parameters, evaluating the cardinality error the additional set of parameters, and refining the additional set of parameters to meet the desired cardinality constraint. Creating a query and selecting parameters for the query to meet a desired cardinality constraint or set of cardinality constraints when the query is executed against a database may be difficult. A query generation using cardinality constraints process may create a set of parameters for a query which satisfies a desired cardinality constraint or set of cardinality constraints. An application of such a query generation using cardinality constraints process may be database component and code testing.

Claims

1. A method, comprising:

choosing a first set of parameters for a query;

calculating at least one additional set of parameters based on the chosen first set of parameters;

executing the query using the calculated at least one additional set of parameters;

evaluating a cardinality value of the calculated at least one additional set of parameters; and

refining the at least one additional set of parameters when a result of the evaluating is outside a predetermined range of values.

2. The method of claim 1, wherein the query is a SQL query.

3. The method of claim 1, wherein the query is a SQL query including at least one SELECT statement.

4. The method of claim 1, wherein the query is a SQL query which joins at least two database tables.

5. The method of claim 1, wherein the query includes more than one sub-expression.

6. The method of claim 1, wherein the evaluating the cardinality error includes relatively comparing at least one actual cardinality value and at least one estimated cardinality value.

7. The method of claim 1, wherein the evaluating the cardinality error includes absolutely comparing at least one actual cardinality value and at least one estimated cardinality value.

8. The method of claim 1, wherein the executing using a maximum value of each parameter in the at least one additional set of parameters returns all entries in the database.

9. The method of claim 1, wherein the chosen first set of parameters and the calculated at least one additional set of parameters are single-sided predicates.

10. The method of claim 1, wherein the chosen first set of parameters and the calculated at least one additional set of parameters are double-sided predicates.

11. At least one computer-readable medium having one or more executable instructions that, when read, cause one or more processors to:

(a) create a set of initial parameters based on a structure of a pattern query;

(b) derive at least one set of candidate parameters for the pattern query based on at least a step size;

(c) evaluate, against a database, the pattern query using each sub-set of candidate parameters respectively corresponding to each of the at least one set of candidate parameters;

(d) select the sub-set of candidate parameters that produce the smallest deviation from a predetermined cardinality relative to the remainder of the sub-sets of candidate parameters;

(e) divide the step size by a predetermined value; and

(f) repeat (b)-(e) a predetermined number of times for a particular refinement model.

12. The at least one computer-readable medium of claim 11, wherein the one or more instructions to create the initial set of parameters cause the one or more processors to create the set of parameters that are estimated to produce a smallest cardinality error for the pattern query.

13. The at least one computer-readable medium of claim 11, wherein the one or more instructions to derive cause the one or more processors to select parameters symmetrically offset by a factor of the step size.

14. The at least one computer-readable medium of claim 11, wherein the one or more instructions to evaluate cause the one or more processors to decompose the pattern query into at least one sub-pattern query.

15. The at least one computer-readable medium of claim 11, wherein the predetermined value is two.

16. The at least one computer-readable medium of claim 11, wherein the one or more instructions to repeat cause the one or more processors to repeat based on at least one size of one data field in the database.

17. A system, comprising:

a database to store data;

a query generator to generate at least one set of parameters for a pattern query returning a predetermined number of results from the database based on a particular refinement model; and

a query evaluation layer to perform the pattern query using the at least one set of parameters.

18. The system of claim 17, wherein the database is a SQL database.

19. The system of claim 17, wherein the refinement model is a hill-climbing algorithm.

20. The system of claim 17, wherein the refinement model is a hill-climbing algorithm with halving search.