
Chapter 17: Optimizing Datalog Programs 669
Optimizing
Recursive
Programs
In this paper we consider a particular type of optimization, namely, removing
redundant atoms from the body of a rule and removing redundant rules from a
program. This optimization is useful since it reduces the number of joins
needed to compute the output. The problem of optimizing nonrecursive
programs has been solved, both for the case of single-rule programs (Aho,
Sagiv, and Ullman [1979], and Chandra and Merlin [1976]) and for the case
of programs with many rules (Sagiv and Yannakakis [1980]). Essentially, it
has been shown that a program consisting of nonrecursiv ...