Databases Reference
In-Depth Information
consists of one arbitrary constant
2
.The
Herbrand literal base
B
P
is the set of all ground
(classical) literals constructable from predicate symbols appearing in
P
and constants
in
U
P
(note that, for each atom
p
,
B
P
contains also the strongly negated literal
¬
p
).
Example 2. Consider the following program:
P
0
=
{
r
1
:a(X)
∨
b(X)
←
c(X,Y).
r
2
:e(X)
←
c(X,Y),
not
b(X).
r
4
: c(1,2).
}
then, the universe is
U
P
0
=
{
1
,
2
}
, and the base is
B
P
0
{
=
a(1), a(2), b(1), b(2), e(1),
¬
¬
¬
¬
¬
¬
¬
e(2), c(1,1), c(1,2), c(2,1), c(2,2),
a(1),
a(2),
b(1),
b(2),
e(1),
e(2),
c(1,1),
¬
c(1,2),
¬
c(2,1),
¬
c(2,2)
}
.
Ground Instantiation.
For any rule
r
,
Ground
(
r
) denotes the set of rules obtained by
replacing each variable in
r
by constants in
U
P
in all possible ways. For any program
P
)=
r∈P
, its ground instantiation is the set
Ground
(
P
Ground
(
r
). Note that for
propositional programs,
P
=
Ground
(
P
) holds.
Example 3. Consider again program
P
0
of Example 2. Its ground instantiation is:
Ground
(
P
0
)=
{
g
1
:a(1)
∨
b(1)
←
c(1,1).
g
2
:a(1)
∨
b(1)
←
c(1,2).
g
3
:a(2)
∨
b(2)
←
c(2,1).
g
4
:a(2)
∨
b(2)
←
c(2,2).
g
5
:e(1)
←
c(1,1),
not
b(1).
g
6
:e(1)
←
c(1,2),
not
b(1).
g
7
:e(2)
←
c(2,1),
not
b(2).
g
8
:e(2)
←
c(2,2),
not
b(2).
g
9
: c(1,2).
}
P
0
, while the rules
g
1
,...,g
4
(resp.
g
5
,...,g
8
) are obtained by replacing the variables in
r
1
(resp.
r
2
) with constants
in
U
P
0
.
Note that, the the atom
c
(1
,
2)
was already ground in
Answer Sets.
For every program
P
, its answer sets are defined using its ground instan-
tiation
Ground
(
) in two steps: First the answer sets of positive disjunctive programs
are defined, then the answer sets of general programs are defined by a reduction to
positive disjunctive programs and a stability condition.
An interpretation
I
is a consistent
3
P
set of ground classical literals
I
⊆
B
P
w.r.t. a
program
P
. A consistent interpretation
X
⊆
B
P
is called
closed under
P
(where
P
is
a positive disjunctive Datalog program), if, for every
r
∈
Ground
(
P
),
H
(
r
)
∩
X
=
∅
whenever
B
(
r
)
⊆
X
. An interpretation which is closed under
P
is also called
model
of
P
. An interpretation
X
⊆
B
P
is an
answer set
for a positive disjunctive program
P
,if
2
Actually, since the language does not contain function symbols and since rules are required to
be safe, this extra constant is not needed. However, we have kept the classic definition in order
to avoid confusion.
3
Aset
I ⊆ B
P
is
consistent
if for each positive classical literal such that
l ∈ I
it holds that
¬l∈ I
.