Databases Reference
In-Depth Information
The following notation will be useful for further discussion. If
r
is a rule of form (1),
then
H
(
r
)=
{
a
1
,...
,
a
n
}
is the set of literals in the head and
B
(
r
)=
B
+
(
r
)
∪
B
−
(
r
)
is the set of the body literals, where
B
+
(
r
) (the
positive body
)is
{
b
1
,
...,
b
k
}
and
B
−
(
r
)
(
the negative body
)is
{
b
k
+1
,
...,
b
m
}
.
An
ASP program
P
is a finite set of rules. A not-free program
P
(i.e., such that
:
B
−
(
r
)=
) is called
positive
or
Horn
,
1
∀
r
∈P
∅
and a
∨
-free program
P
(i.e., such
that
1) is called
normal logic program
.
In ASP, rules in programs are usually required to be safe. The motivation of safety
comes from the field of databases, where safety has been introduced as a means to
guarantee that queries (programs in the case of ASP) do not depend on the universe (the
set of constants) considered. As an example, a fact
p
(
X
)
.
gives rise to the truth of
p
(
a
)
when the universe
∀
r
∈P
:
|
H
(
r
)
|≤
{
a
}
is considered, while it gives rise to the truth of
p
(
a
) and
p
(
b
)
when the universe
is considered. Safe programs do not suffer from this problem
when at least the constants occurring in the program are considered. For a detailed
discussion, we refer to [2].
Aruleis
safe
if each variable in that rule also appears in at least one positive literal
in the body of that rule. An ASP program is safe, if each of its rules is safe, and in the
following we will only consider safe programs.
A term (an atom, a rule, a program, etc.) is called
ground
, if no variable appears in
it. Sometimes a ground program is also called
propositional
program.
{
a, b
}
Example 1. Consider the following program:
r
1
:a(X)
∨
b(X)
←
c(X,Y), d(Y),
not
e(X).
r
2
:
←
c(X,Y), k(Y), e(X),
not
b(X)
n, o, a(1).
r
4
: c(1,2).
r
1
is a disjunctive rule with
H
(
r
1
)=
r
3
:m
←
,
B
+
(
r
1
)=
{
a
(
X
)
,b
(
X
)
}
{
c
(
X,Y
)
,d
(
Y
)
}
,
and
B
−
(
r
1
)=
.
r
2
is an integrity constraint with
B
+
(
r
2
)=
{
e
(
X
)
}
{
c
(
X,Y
)
,k
(
Y
)
,
e
(
X
)
}
, and
B
−
(
r
2
)=
{
b
(
X
)
}
.
r
3
is a ground, positive, and non-disjunctive rule with
H
(
r
3
)=
{
m
}
,
B
+
(
r
3
)=
{
n, o, a
(1)
}
, and
B
−
(
r
3
)=
∅
.
r
4
, finally, is a fact (note that
←
is omitted). Moreover, all of the rules are safe.
Semantics.
We next describe the semantics of ASP programs, which is based on the
answer set semantics originally defined in [7]. However, different to [7] only consistent
answer sets are considered, as it is now standard practice.
We note that in ASP the availability of some pre-interpreted predicates is assumed,
such as =,
<
,
>
. However, it would also be possible to define them explicitly as facts,
so they are not treated in a special way here.
Herbrand Universe and Literal Base
For any program
P
,the
Herbrand universe
,de-
noted by
U
P
, is the set of all constants occurring in
P
. If no constant occurs in
P
,
U
P
1
In positive programs negation as failure (
not
) does not occur, while strong negation (
¬
)may
be present.
