Wolfgang Faber, Gianluigi Greco, Nicola Leone
We present a generalization of the Magic Sets technique to Datalog^not programs with (possibly unstratified) negation under the stable model semantics. The technique optimizes Datalog^not 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^not 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^not 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.
Subjects: 3.3 Nonmonotonic Reasoning; 11. Knowledge Representation
Submitted: Apr 11, 2008