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.