Databases Reference
In-Depth Information
can be summarized as follows: a database of facts is used to specify an instance of the
problem, while a set of (usually disjunctive
5
) rules, called “guessing part”, is used to
define the search space; solutions are then identified in the search space by another (op-
tional) set of rules, called “checking part”, which impose some admissibility constraint.
Basically, the answer sets of the program, which combines the input database with the
guessing part, represent “solution candidates”; those candidates are then filtered, by
adding the checking part, which guarantee that the answer sets of the resulting program
represent precisely the admissible solutions for the input instance. To grasp the intu-
ition behind the role of both the guessing and checking parts, consider the following
example.
Example 8. Suppose that we want to partition a set of persons in two groups, while
avoiding that father and children belong to the same group. Following the guess&check
methodology, we use a disjunctive rule to “guess” all the possible assignments of per-
sons to groups as follows:
group
(
P,
1)
∨ group
(
P,
2)
← person
(
P
)
.
To understand what this rule does, consider a simple instance of the problem, in which
there are two persons:
joe
and his father
john
. This instance is represented by four facts
person
(
john
)
.person
(
joe
)
.father
(
john,joe
)
.
We can verify that the answer sets of the resulting program (facts plus disjunctive rule)
correspond to all possible assignments of the three persons to two groups:
{
person(john), person(joe), father(john,joe), group(john,1), group(joe,1)
}
{
person(john), person(joe), father(john,joe), group(john,1), group(joe,2)
}
{
person(john), person(joe), father(john,joe), group(john,2), group(joe,1)
}
{
person(john), person(joe), father(john,joe), group(john,2), group(joe,2)
}
However, we want to discard assignments in which father and children belong to the
same group. To this end, we add the checking part by writing the following constraint:
←
group
(
P
1
,G
)
,group
(
P
2
,G
)
,father
(
P
1
,P
2)
.
The answer sets of the augmented program are then the intending ones, where the check-
ing part has acted as a sort of filter:
{
person(john), person(joe), father(john,joe), group(john,1), group(joe,2)
}
{
person(john), person(joe), father(john,joe), group(john,2), group(joe,1)
}
5
Some ASP variants use
choice rules
as guessing part (see [97,98,43]), Moreover, in some
cases, it is possible to emulate disjunction by unstratified normal rules by “shifting” the dis-
junction to the body [32,33,34], but this is not possible in general.
