Magic Conditions

Much recent work has focused on the bottom-up evaluation of Datalog programs [Bancilhon and Ramakrishnan 1988]. One approach, called magic-sets, is based on rewriting a logic program so that bottom-up fixpoint evaluation of the program avoids generation of irrelevant facts [Bancilhon et al. 1986; Beeri and Ramakrishnan 1987; Ramakrishnan 1991]. It was widely believed for some time that the principal application of the magic-sets technique is to restrict computation in recursive queries using equijoin predicates. We extend the magic-sets transformation to use predicates other than equality (X > 10, for example) in restricting computation. The resulting ground magic-sets transformation is an important step in developing an extended magic-sets transformation that has practical utility in "real" relational databases, not only for recursive queries, but for nonrecursive queries as well [Mumick et al. 1990b; Mumick 1991].