Magic sets and other strange ways to implement logic programs (extended abstract)

Several methods for implementing database queries expressed as logical rules are given and they are compared for efficiency. One method, called “magic sets,” is a general algorithm for rewriting logical rules so that they may be implemented bottomUP (= forward chaining) in a way that cuts down on the irrelevant facts that are generated. The advantage of this scheme is that by working bottom-up, we can take advantage of efficient methods for doing massive joins. Two other methods are ad hoc ways of implementing “linear” rules, i.e., rules where at most one predicate in any body is recursive. These methods are