Next: Modell_3: Getrennte Sorten-/Operatorbasis Up: Statische GLB-Berechnung Previous: Statische GLB-Berechnung

Horizontale Vorcompilation

Unabh"anig davon wie das Sortenwissen in der Sortbase notiert wurde, ob mit dem second-order Pr"adikat subsumes oder durch Hornregeln, wird dieses, in mehreren Schritten, in folgende interne Datenstruktur, eine Liste von Sortenlisten, "uberf"uhrt:


((sorte_1 (SUBSUMES ..) (INDIVIDUALS ..) 
                              (SUBSUMES* ..) (INDIVIDUALS* ..))
  .
  .
  .
 (sorte_n (SUBSUMES ..) (INDIVIDUALS ..) 
                             (SUBSUMES* ..) (INDIVIDUALS* ..)) )
Eine Sortenlisten beschreiben eine Sorte vollst"andig.

Die SUBSUMES-Liste enth"alt alle direkt definierten Untersorten der Sorte. F"ur alle Terminalsorten ist sie bis auf das Schl"usselwort SUBSUMES leer. In der n"achsten Liste (INDIVIDUALS-Liste) befinden sich alle f"ur diese Sorte direkt definierten Individuen. Auch diese Liste kann bis auf das Schl"usselwort INDIVIDUALS leer sein. In der Sortenhierarchie bestehen Abh"angigkeiten unter den Sorten bzgl. der Instanzierung, da"s soll hei"sen das z.B. $veb seine Individuen nur in Abh"angigkeit von den Individuen der Sorte $mammal bestimmen kann. Eine solche Abh"angigkeitschicht der Taxonomie kann man als ,,Stratum`` sehen. Unter der stratifizierten Liste der Taxonomie soll hier eine Liste der Sorten, deren Reihenfolge die Abh"angigkeiten der Sorte wiederspiegelt, verstanden werden.

Aus der SUBSUMES-/ INDIVIDUALS-Liste und der ,,stratifizierten`` Liste der Taxonomie wird die reflexive, transitive H"ulle bez"uglich der Untersorten und Individuen (SUBSUMES*-/INDIVIDUALS*-Liste) gebildet. Dabei wird die SUBSUMES*-Liste stratifiziert.

Der Algorithmus

1. Schritt

Zuerst wird aus der Partition mit Sortenwissen sortbase f"ur jede Sorte eine reduzierte Sortenliste erstellt.


((sorte_1 (SUBSUMES ..) (INDIVIDUALS ..))
  .
  .
  .
 (sorte_n (SUBSUMES ..) (INDIVIDUALS ..)) )

Dabei werden alle mehrfach aufgez"ahlten Individuen und Untersorten nur einmal in die entsprechende Liste aufgenommen.

2. Schritt Zun"achst werden die reduzierten Sortenlisten um die SUBSUMES* - und INDIVIDUALS*-Listen erweitert. Die Sternlisten werden mit den SUBSUMES- bzw. INDIVIDUALS-Listen initialisiert und dann schrittweise um die indirekt definierten Untersorten bzw. Individuen erg"anzt. Dabei ist die Reihenfolge, in der die Sortenlisten vervollst"andigt werden, von Bedeutung. Durch eine Abarbeitung der Sorten, schichtenweise der Taxonomie entsprechend, von unten nach oben, m"ussen die fehlenden Untersorten und Individuen nicht per Tiefensuche ermittelt werden, sondern k"onnen direkt aus den entsprechenden Stern-Listen "ubernommen werden. Zuletzt werden die SUBSUMES*-Listen aller Sorten noch entsprechend der stratifizierten Liste der Taxonomie sortiert.

Es wird also f"ur jede Sorte die stratifizierte, reflexive und transitive H"ulle bez"uglich der Subsorten (SUBSUMES*) und die reflexive, transitive H"ulle bez"uglich der Individuen (INDIVIDUALS*) gebildet (siehe Anhang ).

Beispiel:

Das Ergebnis der Vorcompilation ist die folgende Datenstruktur:


( (VEB (SUBSUMES MAMMAL FISH BIRD)
       (INDIVIDUALS)
       (SUBSUMES* VEB BIRD FISH MAMMAL CANARY GOLDFISH CAT HORSE DOG)
       (INDIVIDUALS* LASSY FIDO FURY TOM GARFIELD GOLDY TWEETY))
  (MAMMAL (SUBSUMES DOG HORSE CAT)
          (INDIVIDUALS) 
          (SUBSUMES* MAMMAL CAT HORSE DOG) 
          (INDIVIDUALS* LASSY FIDO FURY TOM GARFIELD))
  (DOG (SUBSUMES) (INDIVIDUALS LASSY FIDO)
       (SUBSUMES* DOG) (INDIVIDUALS* LASSY FIDO))
  (HORSE (SUBSUMES) (INDIVIDUALS FURY)
         (SUBSUMES* HORSE) (INDIVIDUALS* FURY))
  (CAT (SUBSUMES) (INDIVIDUALS TOM GARFIELD) 
       (SUBSUMES* CAT) (INDIVIDUALS* TOM GARFIELD))
  (FISH (SUBSUMES GOLDFISH) (INDIVIDUALS) 
        (SUBSUMES* FISH GOLDFISH) (INDIVIDUALS* GOLDY))
  (GOLDFISH (SUBSUMES) (INDIVIDUALS GOLDY)
            (SUBSUMES* GOLDFISH) (INDIVIDUALS* GOLDY))
  (BIRD (SUBSUMES CANARY) (INDIVIDUALS) 
        (SUBSUMES* BIRD CANARY) (INDIVIDUALS* TWEETY))
  (CANARY (SUBSUMES) (INDIVIDUALS TWEETY) 
          (SUBSUMES* CANARY) (INDIVIDUALS* TWEETY)))

Diese Vorcompilation scheitert mit einer Fehlermeldung, wenn die Taxonomie Zyklen enth"alt. Sind die restlichen Voraussetzungen nicht erf"ullt, terminiert die Vorcompilation ohne Fehlermeldung. Jedoch kann durch einfache Tests die G"ultigkeit der Restriktionen nachgewiesen werden. Man kann mit unvollst"andigen oder nicht eindeutigen Taxonomien weiterarbeiten. Allerdings werden dabei unvollst"andige Taxonomien nicht vervollst"andigt und die GLB-Berechnung w"ahlt den textuell zuerst gefundenen GLB, wenn die Taxonomie mehrdeutig ist.

Die GLB-Berechnung ist nun auf einen einfachen Links-Rechts-Vergleich der jeweiligen SUBSUMES*-Listen reduziert worden, da beim Vorcompilieren die SUBSUMES*-Listen stratifiziert bzw. entsprechend der stratifizierten Liste der Taxonomie geordnet wurden. Dadurch ist der GLB zweier Sorten in einer eindeutigen Taxonomie genau das erste gemeinsame Element der entsprechenden SUBSUMES*-Listen. Liegt eine nicht eindeutige Taxonomie vor, wird die Sorte als GLB zur"uckgeliefert, die textuell zuerst in der SUBSUMES*-Liste vorkommt. Wenn eine der Eingabesorten unter der anderen liegt, ist sie selbst der GLB; daher ist es in den SUBSUMES*-Listen notwendig, Sorten reflexiv als ihre eigenen Untersorten aufzuf"uhren.
Beispiel, da"s der GLB das erste gemeinsame Element der SUBSUMES*-Listen ist:

Genauso ist der Test, ob ein Individuum bzw. eine endliche Dom"ane zu einer Sorte geh"ort, auf einen bzw. mehrere Tests, die pr"ufen, ob das Individuum in der INDIVIDUALS*-Liste enthalten ist, vereinfacht worden.
Beispiel:



Next: Modell_3: Getrennte Sorten-/Operatorbasis Up: Statische GLB-Berechnung Previous: Statische GLB-Berechnung


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