Report Number: CS-TR-86-1132
Institution: Stanford University, Department of Computer Science
Title: Optimizing Datalog Programs
Author: Sagiv, Yehoshua
Date: March 1986
Abstract: Datalog programs, i.e., Prolog programs without function symbols, are considered. It is assumed that a variable appearing in the head of a rule must also appear in the body of the rule. The input of a program is a set of ground atoms (which are given in addition to the program's rules) and, therefore, can be viewed as an assignment of relations to some of the program's predicates. Two programs are equivalent if they produce the same result for all possible assignments of relations to the extensional predicates (i.e., the predicates that do not appear as heads of rules). Two programs are uniformly equivalent if they produce the same result for all possible assignments of initial relations to all the predicates (i.e. both extensional and intentional). The equivalence problem for Datalog programs is known to be undecidable. It is shown that uniform equivalence is decidable, and an algorithm is given for minimizing a Datalog program under equivalence. A technique for removing parts of a program that are redundant under equivalence (but not under uniform equivalence) is developed. A procedure for testing uniform equivalence is also developed for the case in which the database satisfies some constraints.
http://i.stanford.edu/pub/cstr/reports/cs/tr/86/1132/CS-TR-86-1132.pdf