Efficient hypothetical query evaluation in a database system
First Claim
1. A method of evaluating a hypothetical query in a database system, the method comprising the steps of:
- applying to the hypothetical query one or more algebraic equivalences involving explicit substitutions in order to generate at least one query which is equivalent to the hypothetical query, wherein each of at least a subset of the explicit substitutions represents a hypothetical database state change; and
directly evaluating the equivalent query.
2 Assignments
0 Petitions
Accused Products
Abstract
A hypothetical query in a database system is transformed using algebraic equivalences involving explicit substitutions so as to produce one or more equivalent queries which can be evaluated more efficiently than the original hypothetical query. The hypothetical query may be of the form Q when {U} where Q is a relational algebra query and U is an update expression. The value assigned to the hypothetical query in a database state DB is the value that Q would return in the database state reached from DB by executing update U. One or more explicit substitutions are used to represent hypothetical database state changes, and algebraic equivalences involving the explicit substitutions are applied to the hypothetical query in order to generate at least one additional query which is equivalent to the hypothetical query. Several equivalent queries may be generated, and their estimated computation times compared, in order to select a particular equivalent query for direct evaluation. The use of explicit substitutions to represent hypothetical database state changes allows when constructs or other similar hypothetical programming constructs to be eliminated from the equivalent query. The evaluation process may be facilitated by configuring the original hypothetical query into an evaluable normal form, such that one or more hypothetical state expressions of the query correspond to explicit substitutions, and the hypothetical query does not utilize a composition operator. The selected equivalent query can be evaluated using a purely lazy evaluation strategy, or a hybrid lazy-eager evaluation strategy.
52 Citations
50 Claims
-
1. A method of evaluating a hypothetical query in a database system, the method comprising the steps of:
-
applying to the hypothetical query one or more algebraic equivalences involving explicit substitutions in order to generate at least one query which is equivalent to the hypothetical query, wherein each of at least a subset of the explicit substitutions represents a hypothetical database state change; and directly evaluating the equivalent query. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. An apparatus for use in evaluating a hypothetical query in a database system, the apparatus comprising:
-
a memory for storing at least one data item referenced by the hypothetical query; and a processor coupled to the memory and operative to (i) apply to the hypothetical query one or more algebraic equivalences involving explicit substitutions in order to generate at least one query which is equivalent to the hypothetical query, wherein each of at least a subset of the explicit substitutions represents a hypothetical database state change, and (ii) directly evaluate the equivalent query. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42)
-
-
43. An apparatus for evaluating a hypothetical query in a database system, the apparatus comprising:
-
means for applying to the hypothetical query one or more algebraic equivalences involving explicit substitutions in order to generate at least one query which is equivalent to the hypothetical query, wherein each of at least a subset of the explicit substitutions represents a hypothetical database state change; and means for directly evaluating the equivalent query. - View Dependent Claims (44, 45, 46, 47, 48, 49, 50)
-
Specification