Dynamic Magic Sets and Super-coherent Answer Set Programs

Mario Alviano, Wolfgang Faber

Research output: Contribution to journalArticle

16 Citations (Scopus)

Abstract

For many practical applications of ASP, for instance data integration or planning, query answering is important, and therefore query optimization techniques for ASP are of great interest. Magic Sets are one of these techniques, originally defined for Datalog queries (ASP without disjunction and negation). Dynamic Magic Sets (DMS) are an extension of this technique, which has been proved to be sound and complete for query answering over ASP programs with stratified negation. A distinguishing feature of DMS is that the optimization can be exploited also during the non-deterministic phase of ASP engines. 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, which may result in exponential performance gains. In this paper, the correctness of DMS is formally established and proved for brave and cautious reasoning over the class of super-coherent ASP programs (ASPsc programs). ASPsc programs guarantee consistency (i.e., have answer sets) when an arbitrary set of facts is added to them. This result generalizes the applicability of DMS, since the class of ASPsc programs is richer than ASP programs with stratified negation, and in particular includes all odd-cycle-free programs. DMS has been implemented as an extension of DLV, and the effectiveness of DMS for ASPsc programs is empirically confirmed by experimental results with this system.
Original languageEnglish
Pages (from-to)125-145
Number of pages21
JournalAI Communications
Volume24
Issue number2
DOIs
Publication statusPublished - 2011
Externally publishedYes

Fingerprint

Data integration
Acoustic waves
Engines
Planning

Cite this

Alviano, Mario ; Faber, Wolfgang. / Dynamic Magic Sets and Super-coherent Answer Set Programs. In: AI Communications. 2011 ; Vol. 24, No. 2. pp. 125-145.
@article{9b842110c69b4b74a22965b3ddaceeec,
title = "Dynamic Magic Sets and Super-coherent Answer Set Programs",
abstract = "For many practical applications of ASP, for instance data integration or planning, query answering is important, and therefore query optimization techniques for ASP are of great interest. Magic Sets are one of these techniques, originally defined for Datalog queries (ASP without disjunction and negation). Dynamic Magic Sets (DMS) are an extension of this technique, which has been proved to be sound and complete for query answering over ASP programs with stratified negation. A distinguishing feature of DMS is that the optimization can be exploited also during the non-deterministic phase of ASP engines. 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, which may result in exponential performance gains. In this paper, the correctness of DMS is formally established and proved for brave and cautious reasoning over the class of super-coherent ASP programs (ASPsc programs). ASPsc programs guarantee consistency (i.e., have answer sets) when an arbitrary set of facts is added to them. This result generalizes the applicability of DMS, since the class of ASPsc programs is richer than ASP programs with stratified negation, and in particular includes all odd-cycle-free programs. DMS has been implemented as an extension of DLV, and the effectiveness of DMS for ASPsc programs is empirically confirmed by experimental results with this system.",
keywords = "Magic sets, Query answering optimization, General answer set programming",
author = "Mario Alviano and Wolfgang Faber",
year = "2011",
doi = "10.3233/AIC-2011-0492",
language = "English",
volume = "24",
pages = "125--145",
journal = "AI Communications",
issn = "0921-7126",
publisher = "IOS Press",
number = "2",

}

Dynamic Magic Sets and Super-coherent Answer Set Programs. / Alviano, Mario; Faber, Wolfgang.

In: AI Communications, Vol. 24, No. 2, 2011, p. 125-145.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Dynamic Magic Sets and Super-coherent Answer Set Programs

AU - Alviano, Mario

AU - Faber, Wolfgang

PY - 2011

Y1 - 2011

N2 - For many practical applications of ASP, for instance data integration or planning, query answering is important, and therefore query optimization techniques for ASP are of great interest. Magic Sets are one of these techniques, originally defined for Datalog queries (ASP without disjunction and negation). Dynamic Magic Sets (DMS) are an extension of this technique, which has been proved to be sound and complete for query answering over ASP programs with stratified negation. A distinguishing feature of DMS is that the optimization can be exploited also during the non-deterministic phase of ASP engines. 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, which may result in exponential performance gains. In this paper, the correctness of DMS is formally established and proved for brave and cautious reasoning over the class of super-coherent ASP programs (ASPsc programs). ASPsc programs guarantee consistency (i.e., have answer sets) when an arbitrary set of facts is added to them. This result generalizes the applicability of DMS, since the class of ASPsc programs is richer than ASP programs with stratified negation, and in particular includes all odd-cycle-free programs. DMS has been implemented as an extension of DLV, and the effectiveness of DMS for ASPsc programs is empirically confirmed by experimental results with this system.

AB - For many practical applications of ASP, for instance data integration or planning, query answering is important, and therefore query optimization techniques for ASP are of great interest. Magic Sets are one of these techniques, originally defined for Datalog queries (ASP without disjunction and negation). Dynamic Magic Sets (DMS) are an extension of this technique, which has been proved to be sound and complete for query answering over ASP programs with stratified negation. A distinguishing feature of DMS is that the optimization can be exploited also during the non-deterministic phase of ASP engines. 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, which may result in exponential performance gains. In this paper, the correctness of DMS is formally established and proved for brave and cautious reasoning over the class of super-coherent ASP programs (ASPsc programs). ASPsc programs guarantee consistency (i.e., have answer sets) when an arbitrary set of facts is added to them. This result generalizes the applicability of DMS, since the class of ASPsc programs is richer than ASP programs with stratified negation, and in particular includes all odd-cycle-free programs. DMS has been implemented as an extension of DLV, and the effectiveness of DMS for ASPsc programs is empirically confirmed by experimental results with this system.

KW - Magic sets

KW - Query answering optimization

KW - General answer set programming

U2 - 10.3233/AIC-2011-0492

DO - 10.3233/AIC-2011-0492

M3 - Article

VL - 24

SP - 125

EP - 145

JO - AI Communications

JF - AI Communications

SN - 0921-7126

IS - 2

ER -