Query optimization by semantic reasoning

The problem of database query optimization is to select an efficient way to process a query expressed in logical terms from among the alternative ways it can be carried out in the physical database. This thesis presents a new approach to this problem, called semantic query optimization. The goal of semantic query optimization is to produce a semantically equivalent query that is less expensive to process than the original query. Semantic query optimization actually transforms the original query into a new one by means of a process of inference. The transformations are limited to those that yield a semantically equivalent query, one that is guaranteed to produce the same answer as the original query in any permitted state of the database. This guarantee is achieved because the knowledge used to transform a query is the same knowledge used to insure the semantic integrity of the data stored in the database. Thus, semantic query optimization brings together the apparently separate research areas of query processing and database integrity. The thesis formally defines transformations that preserve semantic equivalence for queries in the relational calculus. In addition, it identifies several classes of cost-reducing query transformations for relational database queries, and provides quantitative estimates of the improvements they can produce, based upon widely accepted models of query processing. The thesis also discusses the design and implementation of a system that carries out semantic query optimization for an important class of relational database queries.