
Chapter 17: Optimizing Datalog Programs 663
the presence of constraints, but they assumed that both rules and constraints
are nonrecursive. An interesting open question is whether our proof procedure
can be used in order to extend the results of Chakravarthy et al. [1986,1988]
to recursive rules and constraints. Other works on semantic query optimization
are those of Finger [1986] and of King [1981].
Naughton [1986] has developed a method for optimizing Datalog programs
by moving atoms from a recursive rule to nonrecursive rules (the method may
create new nonrecursive rules). The atoms that are moved to nonrecursive
rules may not be redundan ...