Generating queries using cardinality constraints

• US 7,882,121 B2
• Filed: 01/27/2006
• Issued: 02/01/2011
• Est. Priority Date: 01/27/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Thomas, Dilys, Chaudhuri, Surajit, Bruno, Nicolas
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): MUELLER, KURT A
• Application Number:
  US11/275,782
• Publication Number:
  US 20070185851A1
• Time in Patent Office: 1,831 Days
• Field of Search: 707/4, 707/2, 707/690, 707/700, 707/759, 707/766, 707/779, 707/780
• US Class Current: 707/759
• 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 for testing a component of a database application, the method comprising:

populating, as specified by a user, a column in a database with test data that falls within a certain range specified by the user;

specifying, by the user, a desired cardinality constraint suitable for testing the component, the component operating on a computing device, wherein the component is a software component;

specifying, by the user, a parametric pattern query that includes a parameter, wherein the parametric pattern query is compatible with the database, and wherein the parametric pattern query is configured to restrict cardinality when evaluated against the database;

selecting a candidate value;

evaluating, by the computing device via the component, the parametric pattern query against the database with the parameter set to the candidate value;

calculating, by the computing device, a cardinality error as a difference between a returned cardinality and the desired cardinality constraint, wherein the returned cardinality results from the evaluating; and

adjusting the candidate value based on the calculated cardinality error and then repeating the evaluating the parametric pattern query against the database with the parameter set to the adjusted candidate value and the calculating the cardinality error until the calculated cardinality error is within an allowable limit.

2. The method of claim 1, further comprising:

selecting a second candidate value;

evaluating, by the computing device via the component, the parametric pattern query against the database with a second parameter set to the second candidate value, wherein the parametric pattern query further includes the second parameter;

adjusting, by the computing device, the second candidate value; and

the repeating the evaluating the parametric pattern query against the database with the parameter set to the adjusted candidate value further comprising the second parameter set to the adjusted second candidate value.

3. The method of claim 2, wherein the parametric pattern query is a SQL query of the form:

SELECT * from T WHERE p # T.c OPERATOR p2 #₂ T.c

where T represents a table of the database that includes the column, and where p is the parameter, and where # represents an arithmetic expression, and where T.c represents the column, and where OPERATOR represents a logical operator, and where p2 is the second parameter, and where #₂ represents a second arithmetic expression.

4. The method of claim 1, wherein the parametric pattern query joins at least two tables of the database.

5. The method of claim 1, wherein the parametric pattern query is a SQL query of the form:

SELECT * from T WHERE p # T.c

where T represents a table of the database that includes the column, and where p is the parameter, and where # represents an arithmetic expression, and where T.c represents the column.

6. The method of claim 1, wherein the test data comprises numerical values and wherein the certain range is zero to one inclusive.

7. The method of claim 1, wherein the parametric pattern query comprises a plurality of subqueries and wherein a distinct cardinality constraint is specified for each subquery.

8. The method of claim 1, wherein, in response to the cardinality error being within the allowable limit, the parametric pattern query with the parameter set to the candidate value or the adjusted candidate value is utilized to test the component.

9. A system for testing a component of a database application, the system comprising:

a server configured to populate a column in a database with test data that falls within a certain range specified by a user;

a query generator configured to specify, as indicated by the user, a desired cardinality constraint suitable for testing the component, the component operating on the system, wherein the component is a software component, wherein the system is a computing device;

the query generator further configured to specify, as indicated by the user, a parametric pattern query that includes a parameter, wherein the parametric pattern query is compatible with the database, and wherein the parametric pattern query is configured to restrict cardinality when evaluated against the database;

the query generator further configured to select a candidate value;

a query evaluation layer configured for evaluating, via the component, the parametric pattern query against the database with the parameter set to the candidate value;

the query generator further configured for calculating a cardinality error as a difference between a returned cardinality and the desired cardinality constraint wherein the returned cardinality results from the evaluating;

the query generator further configured to adjust the candidate value based on the calculated cardinality error and further configured to then repeat the evaluating the parametric pattern query against the database with the parameter set to the adjusted candidate value and the calculating the cardinality error until the calculated cardinality error is within an allowable limit.

10. The system of claim 9, wherein the parametric pattern query is a SQL query of the form:

SELECT * from T WHERE p # T.c

where T represents a table of the database that includes the column, and where p is the parameter, and where # represents an arithmetic expression, and where T.c represents the column.

11. The system of claim 9, further comprising:

the query generator further configured to select a second candidate value;

the query evaluation layer further configured to evaluate, via the component, the parametric pattern query against the database with a second parameter set to the second candidate value, wherein the parametric pattern query further includes the second parameter;

the query generator further configured to adjust the second candidate value in response to the cardinality error not being within the allowable limit; and

the query evaluation layer further configured to evaluate, via the component and in response to the cardinality error not being within the allowable limit, the parametric pattern query against the database with the second parameter set to the adjusted second candidate value.

12. The system of claim 11, wherein the parametric pattern query is a SQL query of the form:

SELECT * from T WHERE p # T.c OPERATOR p2 #₂ T.c

where T represents a table of the database that includes the column, and where p is the parameter, and where # represents an arithmetic expression, and where T.c represents the column, and where OPERATOR represents a logical operator, and where p2 is the second parameter, and where #₂ represents a second arithmetic expression.

13. The system of claim 9, wherein the test data comprises numerical values and wherein the certain range is zero to one inclusive.

14. The system of claim 9, wherein the parametric pattern query comprises a plurality of subqueries and wherein a distinct cardinality constraint is specified for each subquery.

15. The system of claim 9, wherein, in response to the cardinality error being within the allowable limit, the parametric pattern query with the parameter set to the candidate value or the adjusted candidate value is utilized to test the component.

16. A computer-readable medium storage device comprising computer-executable instructions that, when executed by a processor, cause a computing device to perform a method for testing a component of a database application, the method comprising:

populating, as specified by a user, a column in a database with test data that falls within a certain range specified by the user;

specifying, by the user, a desired cardinality constraint suitable for testing the component, the component operating on a computing device, wherein the component is a software component;

specifying, by the user, a parametric pattern query that includes a parameter, wherein the parametric pattern query is compatible with the database, and wherein the parametric pattern query is configured to restrict cardinality when evaluated against the database;

selecting a candidate value;

evaluating, by the computing device via the component, the parametric pattern query against the database with the parameter set to the candidate value;

calculating, by the computing device, a cardinality error as a difference between a returned cardinality and the desired cardinality constraint wherein the returned cardinality results from the evaluating; and

adjusting the candidate value based on the calculated cardinality error and then repeating the evaluating the parametric pattern query against the database with the parameter set to the adjusted candidate value and the calculating the cardinality error until the calculated cardinality error is within an allowable limit.

17. The computer-readable medium of claim 16, wherein the parametric pattern query is a SQL query of the form:

SELECT * from T WHERE p # T.c

where T represents a table of the database that includes the column, and where p is the parameter, and where # represents an arithmetic expression, and where T.c represents the column.

18. The computer-readable medium of claim 16, the method further comprising:

selecting a second candidate value;

evaluating, by the computing device via the component, the parametric pattern query against the database with a second parameter set to the second candidate value, wherein the parametric pattern query further includes the second parameter;

adjusting, by the computing device, the second candidate value; and

the repeating the evaluating the parametric pattern query against the database with the parameter set to the adjusted candidate value further comprising the second parameter set to the adjusted second candidate value.

19. The computer-readable medium of claim 18, wherein the parametric pattern query is a SQL query of the form:

SELECT * from T WHERE p # T.c OPERATOR p2 #₂ T.c

where T represents a table of the database that includes the column, and where p is the parameter, and where # represents an arithmetic expression, and where T.c represents the column, and where OPERATOR represents a logical operator, and where p2 is the second parameter, and where #₂ represents a second arithmetic expression.

20. The computer-readable medium of claim 16, wherein, in response to the cardinality error being within the allowable limit, the parametric pattern query with the parameter set to the candidate value or the adjusted candidate value is utilized to test the component.