Databases Reference
In-Depth Information
ground program being potentially of exponential size with respect to the input program.
Optimizations in the Instantiator therefore often have a big impact, as its output is the
input for the following modules, which implement computationally hard algorithms.
Moreover, if the input program is normal and stratified, the Instantiator module is, in
some cases, able to directly compute its stable model (if it exists).
The subsequent computations, which constitute the non-deterministic part of an ASP
system, are then performed on
ground
(
) by both the
Ground Reasoner
and the
Model
Checker
. Roughly, the former produces some “candidate” answer set, whose stability is
subsequently verified by the latter.
The existing ASP systems mainly differ in the technique employed for implement-
ing the
Ground Reasoner
. There are basically two approaches, that we will refer to
as
search-based
and
rewriting-based
. In the search-based approach, the
Ground Rea-
soner
implements a backtracking search algorithm, which works directly on the ground
instantiation of the input program. Search-based systems, like e.g. DLV and Smodels,
are often referred to as “native” ASP systems, because the employed algorithms di-
rectly manipulate logic programs and are optimized for those. In the rewriting-based
approach, the
Ground Reasoner
transforms the ground program into a propositional
formula and then invokes a Boolean satisfiability solver for finding answer set candi-
dates.
As previously pointed out, the
Model Checker
verifies whether an answer set candi-
date at hand is an answer set for the input program. This task is as hard as the problem
solved by the Ground Reasoner for disjunctive programs, while it is trivial for non-
disjunctive programs. However, there is also a class of disjunctive programs, called
Head-Cycle-Free programs [32], for which the task solved by the Model Checker is
provably simpler, which is exploited in the system algorithms.
Finally, once an answer set has been found, ASP systems typically print it in text
format, and possibly the
Ground Reasoner
resumes in order to look for further answer
sets.
In order to implement query answering, an important technique is a generaliza-
tion of the Magic Set algorithm, originally proposed for Datalog programs. It has
been extended to ASP without negation and integrity constraints in [110] and [111],
and extended to certain classes of programs containing negation but no disjunction in
[112,113]. In [114] the technique is described for programs with both disjunction and
negation (but in a limited form, also integrity constraints are not permitted), and in [115]
a large fragment of programs has been identified, for which this technique is correct.
It has been implemented in the ASP system DLV, and also inside the system KAON2
[116,117].
P
5.2
Applications
Answer Set Programming has been successfully applied to many areas including:
-
Information integration
. ASP has been exploited for supporting consistent query
answering, in information integration systems under the so-called Global-as-View
approach [118,119,120], also in presence of data inconsistencies and data incom-
pleteness.
