Database Reference
In-Depth Information
Dieser Unterschied fuhrt zu einem dreiwertigen Antwortverhalten, das normale
logische Programme bei Anfragen zeigen konnen. Fur eine Grundanfrage Q an ein
normales logisches Programm
P
lautet die Antwort (auf der Basis der stabilen
Semantik)
•
yes
,wenn
P|
=
stab
Q gilt;
=
stab
•
no
,wenn
P|
¬
Q gilt;
•
unknown
in allen anderen Fallen.
Beispiel 9.24
Wir erweitern das logische Programm
P
2
aus Selbsttestaufgabe 9.23:
P
3
: P (a) ←
not
Q(a). (a) ←
not
P (a).
P (c). P (a) ← R(a).
Aus den Ergebnissen der Selbsttestaufgabe 9.23 folgt sofort, dass
P
3
zwei stabile
Modelle hat, namlich S
1
=
und S
2
=
{
P (a),P(c)
}
{
Q(a),P(c)
}
. Es gilt also
=
stab
Q(a). Die
Antworten zu den Anfragen P (c)bzw.R(a)lautenalso
yes
bzw.
no
,wahrend die
Anfragen P (a) und Q(a)beidemit
unknown
beantwortet werden.
=
stab
=
stab
=
stab
P
3
|
P (c) und
P
3
|
¬
R(a), aber
P
3
|
P (a) und
P
3
|
Die stabile Semantik verwendet implizit die
closed world assumption (CWA)
- wenn es keinen Grund gibt, eine Aussage zu glauben, so wird angenommen, dass
sie definitiv falsch ist.
Die Bestimmung der Semantik und des Antwortverhaltens eines normalen lo-
gischen Programms vereinfachen sich entscheidend, wenn man weiß, dass das Pro-
gramm genau ein stabiles Modell hat. Letzteres muss nicht notwendig so sein, wie
die obigen Beispiele zeigen. Wir werden nun eine Eigenschaft vorstellen, die dies
erzwingt. Wichtig hierfur ist der Begriff der Niveau-Abbildungen.
Definition 9.25 (Niveau-Abbildung)
Sei
P
ein normales logisches Programm.
Abbildungen
|| · ||
:
H
(
P
)
→ N
von der Menge der Grundatome
H
(
P
)indienaturlichen Zahlen heißen
Niveau-
Abbildungen
(
level mappings
)von
P
.
Niveau-Abbildungen ordnen also die Grundatome in Schichten an, wobei je-
de Schicht aus denjenigen Grundatomen besteht, die der gleichen Zahl zugeordnet
sind, und auch mehrere Grundatome enthalten kann. Ist diese Schichtung mit den
Regeln in einem logischen Programm vertraglich, so liegt ein (lokal) stratifiziertes
Programm vor:
Definition 9.26 ((lokal) stratifiziert)
Ein normales logisches Programm
P
heißt
(lokal) stratifiziert ((locally) stratified)
, wenn es eine Niveau-Abbildung
||·||
von P gibt, so dass fur jede Regel r von P gilt:
1. fur jedes A
∈
pos
(r), und fur H
∈
head
(r) gilt
||
A
|| ≤ ||
H
||
;
2. fur jedes B ∈
neg
(r), und fur H ∈
head
(r) gilt ||B|| < ||H||.
