Efficient hypothetical query evaluation in a database system

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.