
Chapter
17
Optimizing Datalog Programs
Yehoshua Sagiv
Department of Computer Science
The Hebrew University of Jerusalem,
Jerusalem, Israel
Abstract
Datalog programs, i.e, Prolog programs without function symbols, are con-
sidered. It is assumed that a variable appearing in the head of a rule must also
appear in the body of the rule. The input to a program is a set of ground atoms
(which are given in addition to the rules of the program) and, therefore, can be
viewed as an assignment of relations to some predicates of the program. Two
programs are equivalent if they produce the same result for all possible assign-
ments of relations to the extensiona ...