Next: Modell_2: Getrennte Sorten-/Operatorbasis Up: Dynamische GLB-Berechnung Previous: Dynamische GLB-Berechnung

Modell_1: Gemeinsame Sorten-/Operatorbasis mit subsumes-Pr"adikat

In diesem ersten Modell existiert nur eine Partition, in der das gesamte Wissen gesammelt ist. Wie bereits erw"ahnt, ist es sinnvoll, das Sortenwissen vom Behauptungswissen abzugrenzen[BBDV91].
Beispiel:

Zeichnet man die taxonomiebeschreibenden Regeln nicht aus, sondern betrachtet alle einpr"amissigen DATALOG-Regeln "uber un"are Pr"adikate als solche, wird das Pr"adikat furry als Untersorte der Sorte $mammal verstanden. Die Berechnung der Anfrage $mammalis $fish (entsprechend glb(mammal,fish)) w"achst dann kombinatorisch. Es wird nicht nur versucht, glb(dog,fish) zu berechnen, sondern zus"atzlich noch die Anfragen glb(furry,fish), glb(hair_all_over,fish), ..., bevor schlie"slich ein FAIL ausgel"ost wird. Diese Trennung des Sortenwissens vom Behauptungswissen soll hier durch das spezielle second-order Pr"adikat subsumes erreicht werden.


Durch eine Abgrenzung des Sortenwissens vom Behauptungswissen wird die Komplexit"at der Anfragebearbeitung verringert. Jetzt scheitert die gleiche Anfrage bereits nach wenigen Rechenschritten.

Die GLB-Berechnung

Der GLB wird in diesem Modell zur Laufzeit berechnet. Die GLB-Berechnung greatest-lower-bound( Sort, Sort) wird auf eine CLB-Berechnung (Berechnung aller gemeinsamer Untersorten von sort und sort - Common Lower-Bounds) abgest"utzt [AKBLN89].


greatest-lower-bound(X, Y) :- & remove-subsumed-lbs(all-lbs(X,Y)).

lb(X, X) :- & X.
lb(X, Y) :- subsumes(X, Z) & lb(Z, Y).
lb(X, Y) :- subsumes(Y, Z) & lb(X, Z).

all-lbs(X, Y) :- & remove-duplicates(tupof(lb(X,Y))).

remove-subsumed-lbs(Lbs) :- & rsl(Lbs, []).

rsl([], Rlbs) :- & Rlbs.
rsl([Lb | Lb-rest], Rlbs) :-
  & rsl(rsl1(Lb, Lb-rest), tup(Lb | rsl1(Lb, Rlbs))).

rsl1(Lb, []) :- & [].
rsl1(Lb, [Lb1 | Rest]) :- subsumes+(Lb, Lb1) ! & rsl1(Lb, Rest).
rsl1(Lb, [Lb1 | Rest]) :- & tup(Lb1 | rsl1(Lb, Rest)).

subsumes+(X,Y) :- subsumes(X,Y).
subsumes+(X,Y) :- subsumes(X,Z), subsumes+(Z,Y).
Bei der CLB-Berechnung lb(Sort, Sort) wird mittels der subsumes-Fakten ein Weg zwischen sort und sort gesucht. Da die subsumes-Relation nicht kommutativ, sondern gerichtet ist (siehe Seite ), existieren zwei Regeln lb(X, Y), um diesen Weg zu finden. Die erste Regel scheitert, wenn das erste Argument an eine Sorte ohne Untersorten gebunden ist; erst dann wird die zweite Regel benutzt. Findet auch die zweite Regel keine gemeinsame Sorte, wird per Backtracking weiter nach einem Weg gesucht. Die meistens CLB's sind mehrfach herleitbar, deshalb werden die mehrfach auftauchenden CLB's in all-lbs mit remove-duplicates aus der Liste (tupof) der lb-Werte entfernt.

Nachdem so alle CLB's berechnet wurden, wird aus diesen der gr"o"ste/ allgemeinste ausgew"ahlt. Die Funktion remove-subsumed-lbs entfernt aus der Liste aller CLB's diejenigen CLB's, die von einem anderen CLB subsumiert werden. Dazu l"oscht rsl mit rsl1 einen CLB aus der Liste aller CLB's (Rest des 1. Arguments), wenn er von dem aktuell betrachteten CLB (Kopf vom 1. Arguments) subsumiert (transitiv: subsumes+) wird. Im 2. Argument von rsl befinden sich die ,,Subsumierer``. Es bleibt noch zu pr"ufen ob der aktuell betrachtete CLB einen dieser Subsumierer subsumiert (wiederum mit rsl1), gegebenfalls wird ein solch subsumierter CLB gel"oscht.

Wenn die Taxonomie eindeutig und vollst"andig ist, werden so alle CLB's, die ungleich dem GLB sind, entfernt.


constant-in-sort(Const, Sort):- Sort(Const) &Const.
constant-in-sort(Const, Sort):- subsumes(Sort, Subsort),
                                &constant-in-sort(Const, Subsort).
Mit der Funktion constant-in-sort wird gepr"uft, ob eine Konstante direkt oder indirekt in einer Sorte enthalten ist. Dazu mu"s gegebenenfalls die Untersorte gefunden werden, f"ur die das Individuum definiert wurde. Analog wird der Test, ob eine Dom"ane in einer Sorte liegt, durch mehrere constant-in-sort-Anfragen realisiert.

Bei der Unifikation mit mindestens einer Sorte wird dann vom RELFUN-Interpreter aus die entsprechende Anfrage in RELFUN selbst gestellt (siehe Anhang ).



Next: Modell_2: Getrennte Sorten-/Operatorbasis Up: Dynamische GLB-Berechnung Previous: Dynamische GLB-Berechnung


Harold Boley & Victoria Hall (hall@dfki.uni-kl.de)