Magic sets for data integration

We present a generalization of the Magic Sets technique to Datalog programs with (possibly unstratified) negation under the stable model semantics, originally defined in (Faber, Greco, & Leone 2005; 2007). The technique optimizes Datalog¬ programs by means of a rewriting algorithm that preserves query equivalence, under the proviso that the original program is consistent. The approach is motivated by recently proposed methods for query answering in data integration and inconsistent databases, which use cautious reasoning over consistent Datalog¬ programs under the stable model semantics. In order to prove the correctness of our Magic Sets transformation, we have introduced a novel notion of modularity for Datalog¬ under the stable model semantics, which is more suitable for query answering than previous module definitions, and which is also relevant per se. A module under this definition guarantees independent evaluation of queries if the full program is consistent. Otherwise, it guarantees soundness under cautious and completeness under brave reasoning.