Databases Reference
In-Depth Information
Fig. 1.
General architecture of an ASP system
5
Implementations and Applications
In this section we consider some additional topics that allow the reader to have a broader
picture of ASP. In particular, we introduce the general architecture of ASP systems, and
we briefly describe several applications of ASP.
5.1
System Algorithms
Initially somewhat impeded by complexity considerations, reasonable algorithms and
systems supporting ASP became available in the second half of the 1990s. The first
widely used ones were Smodels [102,43], supporting non-disjunctive ASP, and DLV
[42], supporting ASP (with disjunction) as defined in [7]. These two systems have been
improved over the years and are still in widespread use. Later-on, more systems for
non-disjunctive ASP, like ASSAT [103,104], Cmodels [105], and Clasp [106] became
available, and also more disjunctive ASP systems became available with the advent of
GnT [107], cmodels-3 [108], and ClaspD [109].
While, as discussed below, the systems do not use the same techniques, they basically
agree on the general architecture depicted in Figure 1.
The evaluation flow of the computation is outlined in detail. Upon startup, the input
specified by the user is parsed and transformed into the internal data structures of the
system.
6
In general, an input program
contains variables, and the first step of a computa-
tion of an ASP system is to eliminate these variables, generating a ground instantiation
ground
(
P
. This variable-elimination process is called
instantiation
of the pro-
gram (or
grounding
), and is performed by the
Instantiator
module (see Figure 1).
Anaıve Instantiator would produce the full ground instantiation
Ground
(
P
) of
P
) of the
input, which is, however, undesirable from a computational point of view, as in general
many useless ground rules would be generated. All of the systems therefore employ
different procedures, which are geared towards keeping the instantiated program as
small as possible. A necessary condition is, of course, that the instantiated program
must have the same answer sets as the original program. However, it should be noted
that the Instantiator solves a problem, which is in general EXPTIME-hard, the produced
P
6
The input is usually read from text files, but some systems also interface to relational databases
for retrieving facts stored in relational tables.
