Magic Sets for Data Integration

Wolfgang Faber, Gianluigi Greco, Nicola LeoneAAAI 2008

Abstract

Data integration systems frequently encounter inconsistencies when merging information from disparate sources. To resolve these conflicts, researchers employ $\text{Datalog}^\neg$ (Datalog with negation) under stable model semantics. However, query answering in this framework is co-NP-complete, and traditional optimization techniques like Magic Sets are often incompatible with unstratified negation. This paper presents a generalized Magic Sets transformation that enables efficient query answering by identifying "dangerous rules" and utilizing a novel modularity framework. Experimental results from the INFOMIX project demonstrate that this approach reduces search space and improves performance by several orders of magnitude.

Introduction

In the realm of data integration, the primary goal is to provide a unified view of data residing in autonomous and heterogeneous sources. A significant challenge in this process is the presence of inconsistencies—instances where different databases provide conflicting information regarding the same entity or relationship. To reason through these inconsistencies, the logic programming community utilizes $\text{Datalog}^\neg$ under stable model semantics.

While powerful, this approach is computationally expensive. Standard top-down optimization techniques, most notably the "Magic Sets" method, are designed to propagate constraints from a query down to the underlying data, thereby avoiding the processing of irrelevant facts. However, the original Magic Sets algorithm is limited to stratified programs. In data integration, where rules may negatively depend on each other in cycles (unstratified negation), the standard method fails to capture the complex dependencies required for sound query answering.

The Challenge of Unstratified Negation

The core difficulty with unstratified negation is that the truth of a fact may depend on the absence of another fact in a recursive cycle. In such scenarios, simple top-down propagation of bindings is insufficient because the truth value of a predicate cannot be determined solely by its sub-goals. To address this, the authors propose a more sophisticated rewriting strategy that accounts for the bidirectional flow of information necessitated by stable model semantics.

Methodology

The proposed optimization hinges on three primary innovations: the identification of dangerous rules, a new modularity framework, and a specialized rewriting algorithm.

1. Dangerous Rules and Bidirectional Propagation

The authors identify a category of "dangerous rules" where standard head-to-body binding propagation is inadequate. A rule is classified as dangerous if it involves predicates within an odd negation cycle or if it depends on a predicate already identified as dangerous. For these specific rules, the algorithm employs body-to-head propagation. By effectively "inverting" the rule, the system ensures that all necessary binding information is captured, even when the truth of a head predicate is influenced by the negation of its body literals.

2. A Query-Oriented Modularity Framework

To provide a theoretical foundation for their method, the authors developed a new definition of a "module" for logic programs. Traditional modularity concepts, such as splitting sets, were designed for generating entire models. In contrast, this new framework is specifically tailored for query answering. It allows the system to isolate and process only the segments of the program that are strictly relevant to a specific query, significantly pruning the computational search space.

3. The Rewriting Algorithm

The transformation is implemented via a stack-based algorithm. Given a $\text{Datalog}^\neg$ program and a query, the algorithm outputs an optimized version of the program. This version introduces "magic predicates" that act as filters. These filters ensure that the reasoning engine only considers ground rules that contribute to the final query result, preventing the exponential blowup often associated with grounding large-scale databases.

Experimental Evaluation

The effectiveness of the generalized Magic Sets method was evaluated using the INFOMIX project framework. The testing focused on a real-world data integration scenario involving the information system of the University “La Sapienza” in Rome.

The evaluation involved executing practical queries over a large-scale integrated database characterized by numerous mapping conflicts and inconsistencies. The results were definitive: the Magic Set optimization improved query performance by orders of magnitude. By ignoring mapping conflicts irrelevant to the specific query, the system maintained a manageable search space even as the underlying data complexity increased.

Theoretical Insights and Limitations

A critical finding of this research is the "Consistency Proviso." The authors prove that if the original program is consistent (i.e., it possesses at least one stable model), the Magic Set transformation is perfectly equivalent to the original program. In cases where the program is inconsistent, the transformation remains "cautious-sound" and "brave-complete," offering a reliable approximation of the query results.

Furthermore, the authors demonstrate that the overhead of the optimization is minimal. Identifying "dangerous" predicates is NL-complete, meaning the preprocessing step is computationally efficient and does not detract from the overall performance gains.

Conclusion

This work extends the reach of Magic Set optimizations to the complex domain of unstratified $\text{Datalog}^\neg$. By combining bidirectional information propagation with a novel modularity framework, the authors provide a robust solution for efficient reasoning in inconsistent data integration environments. Future research may explore extending these techniques to programs with infinite stable models or refining the handling of complex negation to achieve further speedups.

Summary updated

BibTeX
@inproceedings{faber2008magic,
  author = {Wolfgang Faber and Gianluigi Greco and Nicola Leone},
  title = {{Magic Sets for Data Integration}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure