Query Optimization in Deductive and Relational Databases

摘要

Given a database query, the authors can often rewrite it as an equivalent querythat can be evaluated more efficiently than the original query. Such transformations are called query rewrite optimizations. A number of rewrite optimizations have been developed for recursive queries in deductive databases. The magic-sets trasnformation (MST) is perhaps the most important of the rewrite techniques. It works by restricting computation to the relevant portion of the database, and can be thought of as a recursive analog of the predicate pushdown optimization for nonrecursive queries. In the thesis, the authors develop the ground magic-sets transformation to push down arbitrary built-in predicates, called conditions. They use the idea of a condition adornment as an abstraction of a restriction imposed by an arbitrary built-in predicate. The authors consider other adornments, and provide a theoretical framework for comparing adornments.