In den oben beschrieben Sichtenwartungsregeln werden auch intensionale Prädikate benutzt. Bei der Auswertung der Sichtenwartungsregeln liegen die Extensionen dieser Prädikate nicht vor. Daher müssen die benötigten Teile der intensionalen Datenbank zur Auswertungszeit wieder hergeleitet werden. Während der Auswertung der Sichtenwartungsregeln mußalso eine Auswertung der normalen Anfrageregeln stattfinden.
Eine Möglichkeit zur Kombination dieser beiden Auswertungen wird in [SJ96] vorgestellt. Bei dem RoD-Algorithmus (Rederivation on Demand) werden die Sichtenwartungsregeln nach einem Magic-Set ähnlichen Verfahren transformiert. Magic-Set ist eine in [Ull89] vorgestellte Regelumschreibung, die eine effiziente Bottom-Up-Auswertung möglich macht. Bei der Bottom-Up-Auswertung werden ausgehend von den Basisrelationen die intensionalen Prädikate berechnet. Die Bottom-Up-Auswertung ist aber nicht zielgerichtet, und berechnet daher die ganze intensionale Datenbank. Durch die Magic-Set-Transformation werden die Regeln so umgeschrieben, daßsie nur dann ausgewertet werden, wenn sie auch für die gestellte Anfrage interessant sind. Das wird mit sogenannten magischen Prädikaten realisiert, die als Trigger in die Regeln eingefügt werden.
Die Anfrageregeln müssen für den RoD-Algorithmus ebenfalls in der Magic-Set-Form vorliegen. Ausgehend von den Änderungen der Basisrelationen werden die Anfrageregeln und die Sichtenwartungsregeln gemeinsam mit einer Bottom-Up-Prozedur ausgewertet. Die Auswertung einer Sichtenwartungsregeln beginnt bei den ins- und del-Literalen. Stößt man bei der Auswertung auf ein intensionales Prädikat, so wird mit Hilfe des entsprechenden magischen Prädikats die Anfrageregel mit den bis dahin bekannten Bindungen für die Variablen ausgewertet. Der RoD-Algorithmus ist in Anhang B aufgeführt.
Eine andere Möglichkeit zur Auswertung der Sichtenwartungsregeln und der Anfrageregeln ist, die Sichtenwartungsregeln mit einer Bottom-Up-Prozedur (auch Vorwärtsauswertung genannt) auszuwerten und die Anfrageregeln mit dem üblichen Auswerter zu berechnen. In ConceptBase werden die Regeln normalerweise durch SLDNF-Resolution (auch mit Rückwärtsauswertung bezeichnet) ausgewertet. Dafür ist keine weitere Transformation der Regeln notwendig, jedoch ist die Auswertung weniger effizient. Während bei einer reinen Bottom-Up-Auswertung nur auf die jeweils aktuelle Menge der bis dahin hergeleiteten Fakten zugegriffen werden muß, wird hier innerhalb der Bottom-Up-Auswertung eine Rückwärtsauswertung gestartet. Diese Rückwärtsauswertung der Anfrageregeln benutzt aber nicht die Ergebnisse der Vorwärtsauswertung und berechnet dadurch Teile der intensionalen Datenbank nochmal.
Damit beide Verfahren angewendet werden können, müssen die Regeln stratifizierbar sein. Stratifikation heißt, daßsich die Regeln in sogenannte Strata (Schichten) unterteilen lassen. In einem Stratum dürfen nur die Prädikate negiert vorkommen, die auf einem unteren Stratum definiert worden sind. Das heißt, daßes im Abhängigkeitsgraph der Regeln keine Zyklen mit einer negierten Kante geben darf.
Da die Sichtenwartungsregeln negierte Literale enthalten, müssen die Regeln zur Auswertung in Schichten unterteilt werden und dann Schicht für Schicht ausgewertet werden. Die Stratifikation der Ausgangsregeln bleibt aber durch die Transformation in Sichtenwartungsregeln oder eine weitere Umschreibung in Magic-Set erhalten.
Das Verfahren, das in ConceptBase zur Auswertung der Regeln benutzt wird, verzichtet auf die Unterteilung der Regelmenge in mehrere Schichten. Es basiert auf der bedingten Fixpunktprozedur von [Bry89]. Stattdessen wird in einer ersten Phase mit der Regelmenge der Fixpunkt auf bedingten Ausdrücken statt Fakten bzw. Tupelmengen berechnet. Diese bestehen aus einem normalen Kopftupel und der Bedingung. Die Bedingung setzt sich aus den Tupeln zusammen, die zu negativen Literalen in Regelrümpfen korrespondieren. Wird das Kopftupel bzw. die Relation, der es angehört, selbst mit anderen Tupeln per Join verbunden, geht die Bedingung in die Bedingung des Ergebnisses ein. Nach Erreichen des Fixpunktes erfolgt in einer zweiten Phase eine schrittweise Eliminierung aller Bedingungen bzw. sogar ganzer bedingter Ausdrücke. Falls eine Bedingung nicht als Kopf eines anderen bedingten Fakts auftritt, ist sie überflüssig. Findet sich dagegen für eine Bedingung ein unbedingtes Fakt, kann das gesamte bedingte Fakt entfernt werden.
Implizit führt man damit genau den Stratifizierbarkeitstest auf denjenigen Grundinstanzen der Regeln durch, die erreichbar sind. Lassen sich nämlich nicht alle bedingten Fakten auf diese Weise in einfache Fakten umschreiben, liegt eine Verletzung der Stratifizierbarkeitsbedingung durch die Anfrage bzw. betrachtete Regelmenge vor. Die verbleibenden bedingten Fakten beschreiben die alternativ möglichen, aber nicht eindeutigen Modelle der betrachteten Regelmenge. Der Algorithmus ist formal in Abbildung 5.3 beschrieben.
Abbildung 5.3: Algorithmus zur Auswertung der Sichtenwartungsregeln
Christoph Quix