Database Reference
In-Depth Information
•
Bestimme alle Kontexte!
Aus E
zienzgrunden wird dieser Auftrag jedoch nicht wortlich erfullt. Ein ATMS
konzentriert sich vielmehr auf relevante Teilaufgaben:
•
Aufdeckung von Inkonsistenzen in Kontexten;
Entscheidung, ob ein Knoten in einem bestimmten Kontext enthalten ist.
Zu diesen Zwecken benutzt das ATMS fur Knoten eine spezielle Datenstruktur, die
eine e
ziente Beschreibung der Kontexte liefert, in denen ein Knoten gultig ist.
Intern wird ein Knoten n in der folgenden Form dargestellt:
•
n =
Aussage
,
Label
,
Begrundungen
Dabei ist
Begrundungen
die Menge aller Begrundungen, die n als Konsequenz ent-
halten.
Label
ist eine Menge von Umgebungen und beschreibt, von welchen (Mengen
von) Annahmen die
Aussage
letztendlich abhangt. Das Label wird vom ATMS be-
rechnet und verwaltet und besitzt die folgenden Eigenschaften:
•
es ist
konsistent
, d.h., alle seine Umgebungen sind konsistent;
•
es ist
korrekt (sound)
fur den Knoten n, d.h., n ist aus jeder der Umgebungen
des Labels (zusammen mit allen Begrundungen) ableitbar;
•
es ist
vollstandig
, d.h., jede konsistente Umgebung, in der n gultig ist, ist eine
Obermenge einer der Labelmengen;
es ist
minimal
, d.h., keine der Labelmengen ist in einer anderen enthalten.
Ein Knoten ist in einem Kontext enthalten, wenn er in der entsprechenden cha-
rakterisierenden Umgebung gultig ist. Wegen der Vollstandigkeit des Labels ist das
genau dann der Fall, wenn die charakterisierende Umgebung eine Obermenge ei-
ner der Labelmengen ist. Umgekehrt definiert jede konsistente Umgebung, die eine
Obermenge einer der Labelmengen ist, einen Kontext, in dem n enthalten ist. Mit
Hilfe des Labels lasst sich also die Frage, in welchen Kontexten ein Knoten enthal-
ten ist, auf die einfache Uberprufung einer Teilmengenbeziehung reduzieren. Zur
Bestimmung von Labels und zur Illustration von Umgebungen und den zugehori-
gen Kontexten nutzt man aus, dass Umgebungen einen Mengenverband bilden, der
durch die Teilmengenbeziehung (partiell) geordnet ist.
Abbildung 7.9 zeigt einen solchen Verband aller Teilmengen der Menge
•
{
,wobeiwirzunachst sowohl die eckigen und ovalen Markierungen als
auch die Durchstreichungen ignorieren wollen. Dabei symbolisieren aufwarts gerich-
tete Kanten eine Teilmengenbeziehung. Alle Obermengen einer Menge lassen sich
also bestimmen, indem man den Kanten nach oben folgt. In umgekehrter Richtung
findet man alle Teilmengen einer Menge. Die Labelmengen eines Knotens lassen sich
dann als die großten unteren Schranken derjenigen Umgebungen charakterisieren,
in denen der Knoten gultig ist.
Ein weiterer Vorteil der Verbandsdarstellung ist die ubersichtliche Verfolgung
inkonsistenter Umgebungen, also von nogoods: Ist eine Umgebung inkonsistent, so
offensichtlich auch jede ihrer Obermengen. Alle diese Mengen sind zur Bestimmung
von Kontexten irrelevant. Wir wollen diese Ideen an einem Beispiel illustrieren.
A, B, C, D
}
