zbMATH — the first resource for mathematics

Magic sets and their application to data integration. (English) Zbl 1112.68365
Eiter, Thomas (ed.) et al., Database theory – ICDT 2005. 10th international conference, Edinburgh, UK, January 5–7, 2005. Proceedings. Berlin: Springer (ISBN 3-540-24288-0/pbk). Lecture Notes in Computer Science 3363, 306-320 (2005).
Summary: We propose a generalization of the well-known Magic Sets technique to Datalog\(^\neg\) programs with (possibly unstratified) negation under stable model semantics. Our technique produces a new program whose evaluation is generally more efficient (due to a smaller instantiation), while preserving soundness under cautious reasoning. Importantly, if the original program is consistent, then full query-equivalence is guaranteed for both brave and cautious reasoning, which turn out to be sound and complete.
In order to formally prove the correctness of our Magic Sets transformation, we introduce a novel notion of modularity for Datalog\(^\neg\) under the stable model semantics, which is relevant per se. We prove that a module can be evaluated independently from the rest of the program, while preserving soundness under cautious reasoning. For consistent programs, both soundness and completeness are guaranteed for brave reasoning and cautious reasoning as well.
Our Magic Sets optimization constitutes an effective method for enhancing the performance of data-integration systems in which query-answering is carried out by means of cautious reasoning over Datalog\(^\neg\) programs. In fact, preliminary results of experiments in the EU project INFOMIX, show that Magic Sets are fundamental for the scalability of the system.
For the entire collection see [Zbl 1067.68004].
68P15 Database theory
68N17 Logic programming
68Q55 Semantics in the theory of computing
NP Datalog
Full Text: DOI