Optimizing Bottom-Up Query Evaluation for Deductive Databases

Abstract

Abstract: "Deductive databases extend the power of traditional database query languages such as SQL by allowing recursive definitions of predicates. Bottom-up query evaluation is an important query evaluation mechanism for deductive databases and logic programs. In recent years, deductive databases have been extended by allowing facts to contain complex terms that can possibly include variables, and by allowing the use of aggregate operations on sets of answers. This thesis addresses optimization issues related to these extensions. In the first part of the thesis we compare bottom-up and Prolog query evaluation. We show that using existing techniques, bottom-up evaluation performs no more 'actions' than (a model of) Prolog for a restricted class of programs, but this does not hold for all programs. We develop rewrite-based optimization techniques that help us extend the above results to all logic programs. We then develop novel techniques for evaluating these rewritten programs. We compare bottom-up query evaluation (using our rewrite optimizations along with our evaluation optimization) with Prolog query evaluation, and show the following. Suppose we are given a program; if (our model of) Prolog evaluation of a query takes time t on a database, bottom-up query evaluation on the database, without subsumption checking, takes time O(t * log log t). For a restricted class of programs, bottom-up query evaluation on the database, with subsumption checking, takes time at worst O(t). (In both cases, the time taken by bottom-up evaluation also depends on the size of the program, which we assume to be small). On the other hand, for many programs, Prolog is arbitrarily slower than bottom-up evaluation. Our optimization techniques are of importance in evaluating programs that generate facts concerning variables. In the second part of the thesis, we develop optimizations related to the use of aggregate operations such as min or max. We show how to view several such operations as 'selections', and how to propagate these selections into programs. We demonstrate the power and utility of the optimization techniques, using programs for problems such as computing shortest paths and critical paths." Cover title. "November 1992." Thesis (Ph. D.)--University of Wisconsin, Madison, 1992. Includes bibliographical references.