Magic Sets for Disjunctive Datalog Programs

Mario Alviano, Wolfgang Faber, Gianluigi Greco, Nicola Leone

Research output: Contribution to journalArticle

39 Citations (Scopus)

Abstract

In this paper, a new technique for the optimization of (partially) bound queries over disjunctive Datalog programs with stratified negation is presented. The technique exploits the propagation of query bindings and extends the Magic Set optimization technique (originally defined for non-disjunctive programs).

An important feature of disjunctive Datalog programs is non-monotonicity, which calls for non-deterministic implementations, such as backtracking search. A distinguishing characteristic of the new method is that the optimization can be exploited also during the non-deterministic phase. In particular, after some assumptions have been made during the computation, parts of the program may become irrelevant to a query under these assumptions. This allows for dynamic pruning of the search space. In contrast, the effect of the previously defined Magic Set methods for disjunctive Datalog is limited to the deterministic portion of the process. In this way, the potential performance gain by using the proposed method can be exponential, as could be observed empirically.

The correctness of the method is established and proved in a formal way thanks to a strong relationship between Magic Sets and unfounded sets that has not been studied in the literature before. This knowledge allows for extending the method and the correctness proof also to programs with stratified negation in a natural way.

The proposed method has been implemented in the DLV system and various experiments on synthetic as well as on real-world data have been conducted. The experimental results on synthetic data confirm the utility of Magic Sets for disjunctive Datalog, and they highlight the computational gain that may be obtained by the new method with respect to the previously proposed Magic Set method for disjunctive Datalog programs. Further experiments on data taken from a real-life application show the benefits of the Magic Set method within an application scenario that has received considerable attention in recent years, the problem of answering user queries over possibly inconsistent databases originating from integration of autonomous sources of information.
Original languageEnglish
Pages (from-to)156-192
Number of pages37
JournalArtificial Intelligence
Volume187-188
Early online date26 Apr 2012
DOIs
Publication statusPublished - Aug 2012
Externally publishedYes

Fingerprint

Experiments
Magic
experiment
source of information
scenario
performance
Experiment
Negation
Correctness
literature
Real World
Data Base
Computational
Scenarios
Real Life

Cite this

Alviano, M., Faber, W., Greco, G., & Leone, N. (2012). Magic Sets for Disjunctive Datalog Programs. Artificial Intelligence, 187-188, 156-192. https://doi.org/10.1016/j.artint.2012.04.008
Alviano, Mario ; Faber, Wolfgang ; Greco, Gianluigi ; Leone, Nicola. / Magic Sets for Disjunctive Datalog Programs. In: Artificial Intelligence. 2012 ; Vol. 187-188. pp. 156-192.
@article{5eb09e2077734f82be706e2ff5bbc24a,
title = "Magic Sets for Disjunctive Datalog Programs",
abstract = "In this paper, a new technique for the optimization of (partially) bound queries over disjunctive Datalog programs with stratified negation is presented. The technique exploits the propagation of query bindings and extends the Magic Set optimization technique (originally defined for non-disjunctive programs).An important feature of disjunctive Datalog programs is non-monotonicity, which calls for non-deterministic implementations, such as backtracking search. A distinguishing characteristic of the new method is that the optimization can be exploited also during the non-deterministic phase. In particular, after some assumptions have been made during the computation, parts of the program may become irrelevant to a query under these assumptions. This allows for dynamic pruning of the search space. In contrast, the effect of the previously defined Magic Set methods for disjunctive Datalog is limited to the deterministic portion of the process. In this way, the potential performance gain by using the proposed method can be exponential, as could be observed empirically.The correctness of the method is established and proved in a formal way thanks to a strong relationship between Magic Sets and unfounded sets that has not been studied in the literature before. This knowledge allows for extending the method and the correctness proof also to programs with stratified negation in a natural way.The proposed method has been implemented in the DLV system and various experiments on synthetic as well as on real-world data have been conducted. The experimental results on synthetic data confirm the utility of Magic Sets for disjunctive Datalog, and they highlight the computational gain that may be obtained by the new method with respect to the previously proposed Magic Set method for disjunctive Datalog programs. Further experiments on data taken from a real-life application show the benefits of the Magic Set method within an application scenario that has received considerable attention in recent years, the problem of answering user queries over possibly inconsistent databases originating from integration of autonomous sources of information.",
author = "Mario Alviano and Wolfgang Faber and Gianluigi Greco and Nicola Leone",
year = "2012",
month = "8",
doi = "10.1016/j.artint.2012.04.008",
language = "English",
volume = "187-188",
pages = "156--192",
journal = "Artificial Intelligence",
issn = "0004-3702",
publisher = "Elsevier",

}

Alviano, M, Faber, W, Greco, G & Leone, N 2012, 'Magic Sets for Disjunctive Datalog Programs', Artificial Intelligence, vol. 187-188, pp. 156-192. https://doi.org/10.1016/j.artint.2012.04.008

Magic Sets for Disjunctive Datalog Programs. / Alviano, Mario; Faber, Wolfgang; Greco, Gianluigi; Leone, Nicola.

In: Artificial Intelligence, Vol. 187-188, 08.2012, p. 156-192.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Magic Sets for Disjunctive Datalog Programs

AU - Alviano, Mario

AU - Faber, Wolfgang

AU - Greco, Gianluigi

AU - Leone, Nicola

PY - 2012/8

Y1 - 2012/8

N2 - In this paper, a new technique for the optimization of (partially) bound queries over disjunctive Datalog programs with stratified negation is presented. The technique exploits the propagation of query bindings and extends the Magic Set optimization technique (originally defined for non-disjunctive programs).An important feature of disjunctive Datalog programs is non-monotonicity, which calls for non-deterministic implementations, such as backtracking search. A distinguishing characteristic of the new method is that the optimization can be exploited also during the non-deterministic phase. In particular, after some assumptions have been made during the computation, parts of the program may become irrelevant to a query under these assumptions. This allows for dynamic pruning of the search space. In contrast, the effect of the previously defined Magic Set methods for disjunctive Datalog is limited to the deterministic portion of the process. In this way, the potential performance gain by using the proposed method can be exponential, as could be observed empirically.The correctness of the method is established and proved in a formal way thanks to a strong relationship between Magic Sets and unfounded sets that has not been studied in the literature before. This knowledge allows for extending the method and the correctness proof also to programs with stratified negation in a natural way.The proposed method has been implemented in the DLV system and various experiments on synthetic as well as on real-world data have been conducted. The experimental results on synthetic data confirm the utility of Magic Sets for disjunctive Datalog, and they highlight the computational gain that may be obtained by the new method with respect to the previously proposed Magic Set method for disjunctive Datalog programs. Further experiments on data taken from a real-life application show the benefits of the Magic Set method within an application scenario that has received considerable attention in recent years, the problem of answering user queries over possibly inconsistent databases originating from integration of autonomous sources of information.

AB - In this paper, a new technique for the optimization of (partially) bound queries over disjunctive Datalog programs with stratified negation is presented. The technique exploits the propagation of query bindings and extends the Magic Set optimization technique (originally defined for non-disjunctive programs).An important feature of disjunctive Datalog programs is non-monotonicity, which calls for non-deterministic implementations, such as backtracking search. A distinguishing characteristic of the new method is that the optimization can be exploited also during the non-deterministic phase. In particular, after some assumptions have been made during the computation, parts of the program may become irrelevant to a query under these assumptions. This allows for dynamic pruning of the search space. In contrast, the effect of the previously defined Magic Set methods for disjunctive Datalog is limited to the deterministic portion of the process. In this way, the potential performance gain by using the proposed method can be exponential, as could be observed empirically.The correctness of the method is established and proved in a formal way thanks to a strong relationship between Magic Sets and unfounded sets that has not been studied in the literature before. This knowledge allows for extending the method and the correctness proof also to programs with stratified negation in a natural way.The proposed method has been implemented in the DLV system and various experiments on synthetic as well as on real-world data have been conducted. The experimental results on synthetic data confirm the utility of Magic Sets for disjunctive Datalog, and they highlight the computational gain that may be obtained by the new method with respect to the previously proposed Magic Set method for disjunctive Datalog programs. Further experiments on data taken from a real-life application show the benefits of the Magic Set method within an application scenario that has received considerable attention in recent years, the problem of answering user queries over possibly inconsistent databases originating from integration of autonomous sources of information.

U2 - 10.1016/j.artint.2012.04.008

DO - 10.1016/j.artint.2012.04.008

M3 - Article

VL - 187-188

SP - 156

EP - 192

JO - Artificial Intelligence

JF - Artificial Intelligence

SN - 0004-3702

ER -