APPROXIMATING QUERY RESULTS BY RELATIONS OVER TYPES FOR ERROR DETECTION AND OPTIMIZATION

• US 20090234801A1
• Filed: 03/11/2009
• Published: 09/17/2009
• Est. Priority Date: 03/11/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Semmle Limited (Microsoft Corporation)
• Inventors: Schaefer, Max, Avgustinov, Pavel, Verbaere, Mathieu, Sereni, Damien, Moor, Oege De
• Granted Patent: US 8,332,385 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 8/437 Type checking

Abstract

A method and system is provided for computing an approximation of the results of a query. The approximation represents a superset of all possible results, by computing a set of records of types (as opposed to a set of records of values, which is the normal result of a query). This is different from conventional systems, which typically infer types for each field individually. For each record of types, one may also keep track of equalities of fields to improve the precision of the approximation. The approximation can be used to detect erroneous parts of queries that always return an empty result, regardless of the contents of the data source. Furthermore, the same approximation is also useful in performing optimizations: first, by eliminating parts of procedure calls that are guaranteed to be irrelevant to the calling context, and second, by eliminating unnecessary type tests in the query.

Claims

1. A computer-implemented method for approximating any results returned by a query over a relational data source, the method comprising:

receiving, at a computer system, a set of types, wherein a type in the set of types represents a superset of a set of values that is storable in that field;

receiving, at the computer system, a type for each field in a schema, wherein the schema describes a relational data source to be searched;

producing, at the computer system, at least one approximation of at least one result returned by a query, wherein the query includes calls to other query procedures, and wherein the approximation includes at least one of a set of records of types and a set of records of Boolean formulas over types, wherein each field in the result occurs as a field in a record of types, and each type assigned to a field represents a superset of the set of values that are storable in that field; and

optimizing, at the computer system, by transforming the other query procedures using the approximation by eliminating query parts that return an empty set of results regardless of the contents of the relational data source in a context where the query parts are called.

2. The computer-implemented method of claim 1, further comprising:

translating the query to relational algebra comprising a set of relational algebra operators, and wherein the approximation is produced by interpreting each relational algebra operator as a corresponding operator on sets of records of types.

3. The computer-implemented method of claim 1, wherein the approximation is produced by evaluating the query on an especially constructed database comprising a set of relations, wherein each relation in the especially constructed database is constructed in terms of types.

4. The computer-implemented method of claim 1, further comprising:

adding equality constraints to each record of types, wherein the equality constraints that have been added list which fields have equal values in each of the records of types, whereby a more precise approximation of sets of records of values is computed based on the equality constraints that have been added.

5. The computer-implemented method of claim 1, wherein the type for each field in a schema is an entity type, and wherein an entity type is a set comprising:

partial order;

a meet operator giving for any two types t and s a t and s; and

a bottom type that is a subtype of all types;

wherein a set of values in the meet of two types is an intersection of the values in those types, and a set of values in the bottom type is empty.

6. The computer-implemented method of claim 5, where the entity type is represented using at least one of:

a set of classes in an object-oriented class hierarchy, which is downward-closed;

an expression in a system for knowledge representation, such as a description logic;

an automaton describing a set of values the type represents.

7. The computer-implemented method of claim 1, wherein the approximation is a set of records of Boolean formulas over types, and

a set of type facts is given, wherein each type fact is a Boolean formula over types;

and

a subtype order on types is determined by the set of type facts.

8. The computer-implemented method of claim 7, wherein the Boolean formulas over types are represented using at least one of;

Binary Decision Diagrams (BDDs), and

a form suitable for processing by at least one of SAT solvers and theorem provers.

9. The computer-implemented method of claim 8, wherein a set of dependencies is deduced from the set of type facts, wherein the set of dependencies is used to determine an order of BDD variables for efficient evaluation.

10. The computer-implemented method of claim 9, wherein the order of BDD variables is determined by placing variables that are mentioned together in a single type fact close together in a variable order.

11. The computer-implemented method of claim 9, further comprising:

deducing a graph of dependencies between variables from the set of type facts;

identifying strongly connected components in the graph;

placing variables in a same strongly connected component close together in variable order; and

placing at least a first strongly connected component that includes a smaller number of variables before at least a second strongly connected component that includes a larger number of variables in the variable order.

12. The computer-implemented method of claim 9, further comprising:

deducing a cost metric from the set of type facts; and

selecting a variable order of minimum cost among multiple alternative variable orders based on the cost metric.

13. The computer-implemented method of claim 7, further comprising:

representing the approximation as a Boolean formula, wherein each field in a record corresponds to a designated propositional variable, and an assertion that a field has a particular type is represented as an implication that the designated propositional variable implies the Boolean formula that represents the type.

14. The computer-implemented method of claim 13, further comprising:

adding equality constraints to a representation of records of types, and these equality constraints are themselves represented as logical equivalences between the designated propositional variables.

15. The computer-implemented method of claim 13, wherein the approximation is represented as a Boolean formula;

and

wherein the Boolean formula for the approximation is represented using at least one of Binary Decision Diagrams (BDDs) and a form suitable for processing by at least one of SAT solvers and theorem provers.

16. The computer-implemented method of claim 15, wherein BDDs are used for representing the approximation as a Boolean formula, and wherein a set of dependencies is deduced from the set of type facts, and wherein the set of dependencies is used to determine an order of BDD variables for efficient evaluation.

17. The computer-implemented method of claim 1, wherein the approximation of the result is produced by at least one of:

recording that one field'"'"'s values are smaller than another field'"'"'s values;

modeling constants in the query as new types; and

using formal grammars to model data values and their dependencies.

18. The computer-implemented method of claim 1, wherein data is stored in a plurality of relational data sources including at least one of:

a relational database;

a web service;

a web page; and

a file on a hard disk.

19. The computer-implemented method of claim 1, further comprising:

identifying, based on the approximation, erroneous parts of the query that return an empty set of results regardless of contents stored in the relational data source.

20. The computer-implemented method of claim 19, further comprising:

determining that an empty part of the query includes a conjunction of other parts; and

determining at least one cause of the query being empty based on identifying a smallest set of query parts that have a conjunction that is itself empty.

21. The computer-implemented method of claim 20, further comprising:

searching all parts of the query to identify an empty part of the query;

keeping a stack of approximations of a context where a currently searched part of the query is being used;

pushing, when entering a query part, a conjunction of the approximation of that query part and a context on top of the stack; and

in response to the top of the stack being empty, reporting an error.

22. The computer-implemented method of claim 19, further comprising:

warning a user of the query, based on the identifying, that the query is associated with an empty query part, wherein the warning identifies at least one cause of the empty query part.

23. The computer-implemented of claim 19, further comprising:

visually identifying to a user of the query how a set of queries can be combined by conjunction without creating empty parts in a combined query.

24. The computer-implemented of claim 23, wherein the visually identifying comprises depicting compatible types with similar pictures in a user interface.

25. The computer-implemented method of claim 1, wherein the context of the query procedure in the query is computed by:

traversing a call graph of that query;

keeping a stack of approximations of a context where the query procedure is being used; and

in response to entering a procedure in the call graph, pushing a conjunction of an approximation of a body of that procedure and a top of the stack onto the stack as a new context.

26. The computer-implemented method of claim 1, wherein the query parts that return an empty set are eliminated to achieve virtual method resolution in an object-oriented query language.

27. The computer-implemented of claim 1, further comprising:

optimizing, based on the approximation, queries by eliminating type tests, wherein a type test is a query part that tests whether a value has a given type, and wherein the approximation shows one of

the value having the type regardless of contents stored in the relational data source, and

the value failing to have the type.

28. The computer-implemented method of claim 27, further comprising:

determining that a part of the query is a type test by checking that the query'"'"'s approximation is exact.

29. The computer-implemented of claim 28, wherein checking that the approximation of the result returned by the query is exact further comprises:

checking that the query includes only projections to fields that have been marked in a schema of the relational data source as coinciding with the fields'"'"' declared type, and does not include any selections and negations.

30. A system for approximating the result returned by a query over a relational data source, the system comprising:

a memory;

a processor communicatively coupled to the memory; and

a compiler communicatively coupled to the memory and the processor, wherein the compiler is adapted to;

receive a set of types, wherein a type in the set of types represents a superset of a set of values that is storable in that field;

receive a type for each field in a schema, wherein the schema describes a relational data source to be searched;

produce at least one approximation of at least one result returned by a query, wherein the query includes calls to other query procedures, and wherein the approximation includes at least one of a set of records of types and a set of records of Boolean formulas over types, wherein each field in the result occurs as a field in a record of types, and each type assigned to a field represents a superset of the set of values that are storable in that field; and

optimize by transforming the other query procedures using the approximation by eliminating query parts that return an empty set of results regardless of the contents of the relational data source in a context where the query parts are called.

31. A computer program product for approximating the result returned by a query over a relational data source, the computer program product comprising instructions for:

receiving a set of types, wherein a type in the set of types represents a superset of a set of values that is storable in that field;

receiving a type for each field in a schema, wherein the schema describes a relational data source to be searched;

producing at least one approximation of at least one result returned by a query, wherein the query includes calls to other query procedures, and wherein the approximation includes at least one of a set of records of types and a set of records of Boolean formulas over types, wherein each field in the result occurs as a field in a record of types, and each type assigned to a field represents a superset of the set of values that are storable in that field; and

optimizing by transforming the other query procedures using the approximation by eliminating query parts that return an empty set of results regardless of the contents of the relational data source in a context where the query parts are called.