An extension of Van Gelder's alternating fixpoint to magic programs

We study the application of the magic-sets transformation technique to Datalog¬ (function-free programs with negation) that may not have two-valued well-founded models. In this general setting, the well-founded model of the original program does not always agree with the well-founded model of the magic program derived by commonly used left-to-right sideways information-passing strategies on the query. In order to correct this disagreement we present a novel method that is obtained by slightly and naturally tailoring Van Gelder's alternating fixpoint technique to any magic program. © 1996 Academic Press, Inc.