Database Reference
In-Depth Information
kann damit unter dem Gesichtspunkt der Vollstandigkeit fest vorgegeben werden
durch eine so genannte
Selektionsfunktion
; in allen Prolog-Implementierungen wird
als Selektionsfunktion das erste Atom A
1
ausgewahlt. Die Selektionsfunktion hat
also keinen Einfluss auf die Vollstandigkeit des Suchverfahrens, wohl aber auf die
Große des Suchraums und damit auf die E
zienz.
Problematischer ist die zweite Form von Indeterminismus: Die Auswahl der
Programmklausel, mit der resolviert wird. Hier gilt, dass man im Allgemeinen jede
Klausel berucksichtigen muss (
don't know nondeterminism
). Der dadurch aufge-
spannte Suchraum ist baumartig strukturiert: An jedem Knoten gibt es so viele
Nachfolgeknoten, wie es Programmklauseln gibt, deren Kopf mit dem ausgewahl-
ten Atom unifizierbar ist. Fur die Definition dieses so genannten SLD-Baumes wird
daher eine vorgegebene Selektionsfunktion benotigt.
Die Vollstandigkeit der SLD-Resolution bezuglich der Selektionsfunktion be-
sagt dann, dass es fur alle Anfragen, fur die es uberhaupt eine Ableitung gibt, in
jedem
SLD-Baum dazu eine Ableitung gibt. Die Antwortvollstandigkeit bezuglich
der Selektionsfunktion besagt daruber hinaus, dass es fur jede korrekte Antwort-
substitution σ fur
und G einen Pfad zu einer
leeren Klausel gibt, so dass die in diesem Pfad berechnete Antwortsubstitution σ
b
allgemeiner als σ ist (d.h., es gibt eine Substitution σ
mit σ = σ
◦
P
und G in
jedem
SLD-Baum fur
P
σ
b
)[6].
Ein SLD-Baum spannt also den gesamten Suchraum bezuglich eines Programms
und einer Anfrage bei gegebener Selektionsfunktion auf. Die Suchstrategie, die fest-
legt, welche Programmklausel als nachstes ausgewahlt werden soll, bestimmt, wie
der SLD-Baum durchsucht wird. Daher hangt auch die Reihenfolge, in der die ein-
zelnen Blatter erreicht, also die verschiedenen Losungen ausgegeben werden, von
der verwendeten Suchstrategie ab. Die in Prolog ubliche Tiefensuche versucht die
alternativen Programmklauseln in der Reihenfolge, wie sie im Programm aufge-
schrieben sind (eben “von oben nach unten”). Sobald eine Sackgasse erreicht ist
(das erste Atom der abgeleiteten Zielklausel kann mit keinem Kopfliteral des Pro-
gramms unifiziert werden - dieser Fall entspricht einem erfolglosen, endlichen Pfad
in dem SLD-Baum) wird zur zuletzt ausgewahlten Alternative zuruckgesetzt. Dieser
Vorgang wird
Backtracking
genannt.
Falls der SLD-Baum unendliche Pfade enthalt, konnte eine Tiefensuche in dem
Baum erfolglos bleiben, obwohl es (endliche) erfolgreiche Pfade in dem Baum gibt.
Eine Breitensuche dagegen wurde einen vorhandenen erfolgreichen Pfad auch immer
finden. Da in Prolog-Systemen aus E
zienzgrunden die Tiefensuche als Suchstra-
tegie verwendet wird, spielt daher die Anordnung der Klauseln, die von oben nach
unten durchsucht werden, eine entscheidende Rolle. Da auch die Selektionsfunktion
in Prolog fest vorgegeben ist (immer das am weitesten links stehende Literal der
Zielkausel), ist auch die Reihenfolge der Literale in einem Klauselrumpf wesentlich.
Als generelle Richtschnur kann man z.B. sagen, dass bei rekursiv definierten Pradi-
katen die Basisfalle vor den rekursiv definierten Fallen aufgefuhrt werden sollen.
Noch ein weiterer Hinweis zu Prolog: Die hier vorgestellten Hornklauseln und
die SLD-Resolution bilden den so genannten “logischen Kern” von Prolog. Prolog
selbst enthalt daruber hinaus eine Vielzahl von weiteren Elementen, wie z.B. die
bereits erwahnte Form der Negation als Fehlschlag, eingebaute Arithmetik, Seiten-
effekte, etc. [42, 225].
