Rheinisc - idb.uni-bonn.de · Resume Zusammenfassung und Ausblic k. Einleitung Die Seman tik deduktiv er Daten bank en wird gew ohnlic h mittels Fixpunktop eratoren de niert w elc

Rheinische Friedrich�Wilhelms�Universit�at Bonn

Institut f�ur Informatik

Abteilung III

Diplomarbeit

E�ziente Implementierung des alternierendenFixpunktoperators unter Verwendung von

�Anderungspropagierung

Ralf Martini

�� September ��

Erstgutachter� Prof� Dr� R� Manthey

�

Erkl�arung gem�a x� �� der Pr�ufungsordnung

Hiermit erkl�are ich� diese Diplomarbeit selbst�andig durchgef�uhrt und keine anderen als

die angegebenen Quellen und Hilfsmittel benutzt zu haben�

Bonn� den �� September ��

Ralf Martini

Inhaltsverzeichnis

� Deduktive Datenbanken �

�� Syntax � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

�� Fixpunktsemantik deduktiver Datenbanken � � � � � � � � � � � � � � � � � � ��

�� Der naive Fixpunktoperator � � � � � � � � � � � � � � � � � � � � � � ��

�� Das iterierte Fixpunktverfahren �IFPI � � � � � � � � � � � � � � � � ��

�� Das di�erenzielle Fixpunktverfahren �DFPI � � � � � � � � � � � � � ��

�� Unstrati�zierbare Regelmengen � � � � � � � � � � � � � � � � � � � � �

� Nicht strati�zierbare Datenbanken ��

�� Semantik nicht strati�zierbarer Datenbanken � � � � � � � � � � � � � � � � � ��

�� Der Conditional Fixpoint Operator �CFP � � � � � � � � � � � � � � � � � � ��

�� Das alternierende Fixpunktverfahren �AFPI � � � � � � � � � � � � � � � � � ��

�� Der Doubled Program Ansatz� Eine Implementierung des AFPI � � � � � � �

�� CFP versus AFPI � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

� �Anderungspropagierung ��

�� Grundlagen � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

�� Syntax � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

�� Semantik � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

�� Propagierungsregeln � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

�� Naive Propagierungsregeln f�ur echte �Anderungen � � � � � � � � � � ��

�� Propagierungsregeln f�ur echte �Anderungen � � � � � � � � � � � � � � ��

�� Transitionsregeln � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

�� Naive Transitionsregeln � � � � � � � � � � � � � � � � � � � � � � � � � ��

�� Inkrementelle Transitionsregeln f�ur echt �Anderungen � � � � � � � � ��

�� Strukturierte �Anderungspropagierung � � � � � � � � � � � � � � � � � � � � � ��

�� Die Magic�Set Methode � � � � � � � � � � � � � � � � � � � � � � � � ��

�

INHALTSVERZEICHNIS �

�� Magic Updates � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

� Implementierung des AFPI mittels Updates

�� Grundlegende Idee � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

�� Propagierungsregeln f�ur NDF�Regeln � � � � � � � � � � � � � � � � � � � � � ��

�� Propagierungsregeln f�ur DT�Regeln � � � � � � � � � � � � � � � � � � � � � � ��

�� Transitionsregeln � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

�� Der DPA�Algorithmus mittels �Anderungspropagierung � � � � � � � � � � � ��

�� Fazit � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

AFPI mittels Magic Updates ��

�� Regelmengen ohne positiven Zyklus � � � � � � � � � � � � � � � � � � � � � � ��

�� Regelmengen mit positiven Zyklen � � � � � � � � � � � � � � � � � � � � � � � ��

�� L�osungsvorschlag �� Verwendung von T�D � � � � � � � � � � � � � � � � � � � ��

�� L�osungsvorschlag �� Ubersch�atzung der negativen Delta�Fakten � � � � � � �

�� L�osungsvorschlag �� Sequenzieller Fixpunktoperator � � � � � � � � � � � � � ��

�� T�D versus sequenzieller Fixpunktoperator � � � � � � � � � � � � � � � � � � � ��

�� L�osungsvorschlag �� Angepasster schwacher Fixpunkt � � � � � � � � � � � � ��

�� Resume � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� Zusammenfassung und Ausblick �

Einleitung

Die Semantik deduktiver Datenbanken wird gew�ohnlich mittels Fixpunktoperatoren de�

�niert� welche zugleich ein konstruktives Verfahren zur Bedeutungsbestimmung induzie�

ren� Hierbei werden regelde�nierte Daten materialisiert� indem Fixpunktoperatoren so

lange auf regelde�nierte Daten angewandt werden� bis keine neuen Daten mehr ableitbar

sind� Fixpunktverfahren k�onnen unter anderem f�ur die Auswertung von Anfragen und zur

Propagierung von �Anderungen eingesetzt werden� Die gew�ohnlichen Fixpunktverfahren�

wie z�B� der naive Fixpunktoperator� bestimmen die Semantik bestimmter Datenbank�

klassen� Die Datenbankklassen h�angen im wesentlichen von der Verwendung der Negati�

on in den regelde�nierten Daten ab� Die Semantik allgemeiner deduktiver Datenbanken

kann durch ��alternierende Fixpunktverfahren� bestimmt werden� Ziel dieser Diplomar�

beit ist� die Berechnung des alternierenden Fixpunkts unter Einsatz von Techniken der�Anderungspropagierung und der Anfrageauswertung e�zient zu realisieren�

Die Entstehungsgeschichte deduktiver Datenbanken reicht bis in die ��er Jahre zur�uck�

In den ��er Jahren entsteht eine eigene Forschungsrichtung f�ur deduktive Datenbanken�

Gleichzeitig wird in dieser Zeit die theoretische und praktische Grundlage relationaler Da�

tenbanken �Codd gelegt� Die logische Programmiersprache Prolog ensteht� Theoretische

Grundlagen f�ur logische Programmierung und deduktive Datenbanken werden gemeinsam

entwickelt� Anzuf�uhren sei hier der Artikel ��Logic and Databases �� von Gallaire und

Minker� Es ensteht der Wunsch� System der k�unstlichen Intelligenz und Datenbankmana�

gementsysteme zu integreieren� Erste Forschungsprojekte zur Implementation von dedukti�

ven Komponenten in realtionalen Datenbanksystemen entstehen� �� ver�o�entlicht LLoyd

das erste Lehrbuch �uber logische Programmierung ��Foundations of Logic Programming��

Die ��er und �er Jahre sind gekennzeichnet durch die Enstehung gr�osserer Forschungs�

und Entwicklungsprojekte�

Datenbanksysteme mit Deduktionskomponente bieten die M�oglichkeit aus Daten� die in

�


der Datenbank explizit gespeichert sind� neue �intensionale Daten abzuleiten� Deklarative

Regeln dr�ucken hierbei den Zusammenhang zwischen intensionalen Daten und Basisdaten

aus� Deduktive Datenbanksysteme bestehen aus einem Datenbankmanagementsystem mit

einer zus�atzlichen Inferenzkomponente� welche mittels Regeln� die in der Meta�Datenbasis

stehen� neue Fakten herleitet� die in der Datenbasis zusammen mit den Basisfakten ab�

gespeichert werden� Jedes Datenmodell und jede deklarative Anfragesprache kann als

Grundlage f�ur die Beschreibung deduktiver Regeln verwendet werden� Gew�ohnlich wird

das auf dem relationalen Datenmodell basierende Datalog als Regel� und Anfragesprache

verwendet� Die Semantikde�nition f�ur Datalog� welche in dieser Arbeit betrachtet wird� ist

die Fixpunktsemantik� Diese induziert ein intuitiv verst�andliches konstruktives iteriertes

Verfahren zur Herleitung neuer Fakten�

Je nach Verwendung der Negation unterscheidet man drei Klassen deduktiver Datenbanken�

semi�positive� strati�zierbare und allgemeine� Semi�positive Datenbanken referenzieren le�

diglich Basisfakten negativ� Zur Materialisierung dient hier der naive Fixpunktoperator�

Wird hingegen negativ Bezug auf abgeleitete Relationen genommen� so muss anhand ei�

ner Strati�kation �Schichteneinteilung der Regeln sichergestellt werden� dass Fakten nicht

��zu fr�uh� hergeleitet werden� Der iterierte Fixpunktoperator materialisiert dann entlang

dieser Strati�kation f�ur jede Schicht den Fixpunkt� Bedeutungen unstrati�zierbare Regel�

mengen lassen sich beispielsweise mittels der Doubled Program� Implementierung �KSS��

des AFPI ermitteln� Unstrati�zierbare Regelmengen k�onnen das Ergebnis von Magic�

Set Transformationen sein� welche auf eine strati�zierbare Regelmenge angewandt wurde�

Die Magic�Set Transformation �BMSU�� ist eine Technik� die eine Top�Down Anfrage�

auswertung per Bottom�Up�Inferenzverfahren simuliert� Die Anfrageauswertung wird mit

deduktiven Regeln kodiert� Nicht strati�zierbare Regeln k�onnen aber auch direkt aus ei�

ner Modellierung entstehen� wie am Beispiel der Qualit�atskontrolle komplexer Bauteile zu

sehen ist�

ok�X � gestestet�X �

ok�X � komplexes teil�X ��hat defektes teil�X �

hat defektes teil�X � teil�X� Y ��ok�Y �komplexes teil�X � teil�X� Y �

Hier besteht eine wechselseitige negative Referenz zwsichen ok und hat defektes teil� die

unstrati�zierbar ist�

Die AFPI wertet solche unstrati�zierbaren Regelmengen in zwei ineinander verschr�ankten

Fixpunktprozessen aus� Die inneren Fixpunktprozesse berechnen anhand einer festen nega�


tiven Referenzmenge inner Fixpunkte� Der �ausserer Fixpunktprozess ermittelt anhand des

vorigen inneren Fixpunkte alternierend eine �Uber� und Untersch�atzung der negativen Re�

fernzmenge f�ur den folgenden inneren Fixpunkt� Das Verfahren terminiert dann� wenn sich

keine �Anderungen mehr in den �Ubersch�atzungen ergeben� Die inneren Fixpunkte enthal�

ten im Vergleich durch die wiederholte Berechnung redundante Fakten� Die grundlegende

Idee ist es� nur noch die Di�erenzen zwischen den inneren Fixpunkten abzuleiten� Dazu

untersucht diese Arbeit� wie sich die verschr�ankten Fixpunktprozesse unter Verwendung

von �Anderungspropagierung und Magic�Set Transformation e�zient berechnen lassen�

Die Arbeit ist wie folgt aufgebaut� In Kapitel � werden die Grundlagen von deduktiven

Datenbanken behandelt� Es wird die Syntax von Datalog� sowie die Fixpunktverfahren f�ur

semi�positive und strati�zierbare deduktive Datenbanken beschrieben� Kapitel � betrach�

tet unstrati�zierbare Regelmengen und stellt die Fixpunktverfahren conditional Fixpunk�

toperator �CFP � alternierender Fixpunktoperator �AFP und dessen Doubled�Program

Implementierung vor� Kapitel � f�uhrt in die Techniken der �Anderungspropagierung und

Magic�Set Transformation� sowie dessen Kombination ��Magic Updates� ein� Kapitel �

stellt die grundlegende Idee des Einsatzes von �Anderungspropagierung f�ur die Ermittlung

der Faktendi�erenz als Mittel f�ur die Berechnung des AFPI vor� Kapitel � untersucht den

Einsatz von Magic Updates f�ur die AFPI Materialisierung� Ferner werden Problematiken

aufgezeigt die sich durch Magic�Updates ergeben� sowie deren spezielle L�osung im AFPI

Kontext� Kapitel � fasst die ehaltenen Ergbnisse zusammen und bietet einen weiteren

Ausblick�

Kapitel �

Deduktive Datenbanken

Das Kapitel f�uhrt in deduktive Datenbanken ein� Im ersten Abschnitt wird die Syntax

vorgestellt� wie deduktive Datenbanken in dieser Arbeit beschrieben werden� Insbesondere

werden die Begri�e der deduktiven Regel� Fakt� Abh�angigkeitsgraph und das Konzept

der Strati�kation de�niert� Der zweite Abschnitt beschreibt die Bedeutungsbestimmung

strati�zierbarer deduktiver Datenbanken mittels Fixpunktverfahren�

�� Syntax

Im Rahmen dieser Diplomarbeit werden deduktive Datenbanken betrachtet� die aus Fakten

und Regeln bestehen� Syntaktische Grundlage f�ur die Darstellung von Fakten und Regeln

ist die Sprache Datalog�� Datalog� ist im Bereich der deduktiven Datenbankforschung

allgemein akzeptiert� Diese Sprache wird im folgenden eingef�uhrt�

Gegeben sei ein festes Alphabet zur Darstellung von Pr�adikaten und Regeln� Insbesondere

ist Darstellungsform zwischen Variablen� Konstansten und Pr�adikatssymbolen zu unter�

scheiden� Jedes Pr�adikat besitzt eine Stelligkeit n � � und de�niert eine n�stellige Relation�

Des weiteren werden folgende Schreibweisen festgelegt�

In theoretischen Ausf�uhrungen wird X� Y und Z als Symbole f�ur Variablen verwendet�

a� b und c sind Darstellungen f�ur Konstanten� p� q und r werden zur Bezeichnung von

Relationen verwendet� Variablen beginnen mit einem Grobuchstaben� hingegen beginnen

alle anderen Symbole mit Kleinbuchstaben�

Deduktive Regeln setzen sich aus Literalen als Hauptbestandteil zusammen�

�

KAPITEL �� DEDUKTIVE DATENBANKEN �

De�nition �� Literal�� Sei p ein n�stelliges Pr�adikat und ti �i � �� n und n � � Terme� dann bezeichnet

p�t�� tn

ein Literal oder Atom� p wird anstelle von p�� geschrieben� wenn n� ist� Wenn A ein

Atom ist� wird mit pred�A� das Pr�adikatsymbol von A bezeichnet�

Ein wichtiger Teil einer deduktiven Regel ist die Aufz�ahlung von Literalen L�� Ln�

De�nition �� Variablenvorkommen�� F�ur eine Aufz�ahlung W � L�� Ln von Li�

teralen bezeichnet vars�W� die Menge der in W vorkommenden Variablen� Ist vars�W� �

� so wird W auch als ground oder instanziiert bezeichnet�

Desweiteren unterscheidet man bei Variablenvorkommen zwischen Input� und Output�

Variablen� Input�Variablen kommen nur in negativen Literalen vor und m�ussen deshalb

gebunden sein� um diese korrekt auswerten zu k�onnen� Alle anderen Variablen werden als

Output�Variablen bezeichnet�

De�nition �� Input� und Output�Variablen�� F�ur eine Formel W wird die Menge

der Input�Variablen vars��W und der Output�Variablen vars��W de�niert als

�� Wenn W � A ein positives Literal ist� dann sind alle Variablen von A Output�

Variablen�

� Wenn W � �A ein negatives Literal ist� dann sind alle Variablen von A Input�

Variablen�

�� Wenn W � L� � � � � � Ln�n � � eine Konjunktion von Literal ist� dann sind alle

Variablenvokommen auf Input Positionen Input�Variablen� alle �ubrigen sind Output�

Variablen�

vars��W ��S

i�� n

vars��Li nS

i�� n

vars��Li

vars��W ��S

i�� n

vars��Li

Deduktive Regeln gliedern sich in zwei Teile auf�

KAPITEL �� DEDUKTIVE DATENBANKEN

De�nition �� Deduktive Regel�� Eine deduktive Regel ist ein Ausdruck der Form

A�W �

wobei A ein Atom ist� W ist eine Menge von Literalen ist und ist entweder�

�� positives Literal A�

� negatives Literal �A� oder

�� eine Aufz�ahlung L�� Ln von Literalen Li �i � �� n �

Das Literal A wird als Kopf �head� und die W als Rumpf �body� der deduktiven Regel

bezeichnet� A ist ein Fakt� falls f�ur die deduktive Regel kein Regelrumpf W existiert�

Beispiel f�ur eine Regel� p�X� Y � q�X� Y ��r�Y

Beispiel f�ur Fakten� q�� q�� q�a� b � q�c� c

Jede deduktive Regel R soll sicher sein� dass heisst alle im Kopf vorkommenden Variablen

oder alle in negativ Literalen erscheinenden Variablen� m�ussen positiv in einem Rumplite�

ral enthalten sein�

vars�A � vars��W und vars��W � �

Desweiteren erh�alt man� wenn pred�A � p ist� eine De�nition von p� Die gesamte De��

nition von p ergibt sich �uber die Menge aller deduktiver Regeln� die p de�nieren �Vereini�

gungssemantik � def�C beschreibt die Menge der Pr�adikatensymbole� die von der Menge

der deduktiven Regeln C de�niert werden�

Mit diesen De�nitionen wurde beschrieben wie deduktive Regeln und wie Fakten in der

Syntax von Datalog� dargestellt werden� Deduktive Regeln R und Fakten F zusammenge�

nommen de�nieren eine deduktive Datenbank D�

De�nition �� Deduktive Datenbank�� Eine deduktive Datenbank D ist de�niert als

das Paar hF �Ri� wobei F die Menge der Basisfakten und R die Menge der deduktiven

Regeln ist� so dass def�F � def�R � �

KAPITEL �� DEDUKTIVE DATENBANKEN ��

In einer deduktiven Datenbank D � hF �Ri wird das Pr�adikat p pred�D als abgeleitet

bezeichnet� wenn p def�R � also p nur durch Regeln in R de�niert wird� anderfalls nennt

man p extensional� wenn es nur durch Fakten in f beschrieben wird�

Die Abh�angigkeiten zwischen extensionalen und abgeleiteten Pr�adikaten einer gegebenen

deduktiven Datenbank lassen sich als Graph beschreiben� Die Begri� des Abh�angigkeitsgraphen

ist ein wichtiger Bestandteil der Diskussion der nachfolgenden Kapitel�

De�nition �� Abh�angigkeitsgraph von Pr�adikaten�� Sei D � hF �Ri eine deduk�

tive Datenbank� Der Abh�angigkeitsgraph von D ist ein markierter� gerichteter Graph

GD � hV�Ei� wobei V � pred�D� die Menge der Pr�adikatensymbole von D ist und E

die Menge der markierten Kanten wie folgt ist� Sei A � W D eine deduktive Regel�

L W ein Literal� pred�A� � p� und pred�L� � q�

�� Ist L ein positives Literal� dann enth�alt GD eine Kante von q nach p�

�positive Kante genannt�

� Ist L ein negatives Literal� dann enth�alt GD eine Kante von q nach p mit �� als

Markierung�

�negative Kante genannt�

De�nition �� Pr�adikatabh�angigkeiten�� Sei D � hF �Ri eine deduktive Datenbank

und p und q Pr�adikate in pred�D�� dann gilt�

�� H�angt p von q ab �p � q�� dann enth�alt der Abn�angigkeitsgraph GD von D einen Pfad

von q nach p der L�ange n � ��

� H�angt p von q positiv ab �p �� q� und ist p � q� dann enth�alt der Pfad keine negative

Kante�

�� H�angt p von q negativ ab �p �� q� und ist p � q� dann enth�alt der Pfad mindestens

eine negative Kante�

�� H�angen p und q gegenseitig voneinander ab �p q�� dann ist p � q und q � p�

Die im Folgenden vorgestellten unterschiedlichen Datenbankklassen unterscheiden sich in

der Charakteristik ihrer Regelmengen� Positive Datenbanken verbieten Negationen in Re�

geln� wohingegen semi�positive Datenbanken zumindest negative Abh�angikeiten zu exten�

sionalen Relationen zulassen� Im Falle von strati�zierbaren Datenbanken d�urfen abgeleite�

te Relationen negativ abh�angig sein� jedoch darf der Abh�angigkeitsgraph keinen negativen

Zyklus enthalten�


De�nition �� Datenbankklassen�� Eine deduktive Regelmenge R heisst

�� positiv� genau dann wenn es keine Pr�adikate p� q pred�R gibt� so dass p �� q�

� semi�positiv� genau dann wenn es keine Pr�adikate p� q pred�R gibt� so dass p �� q

und q def�R �

�� hierarchisch� genau dann wenn es kein Pr�adikat p pred�R gibt� so dass p p�

�� hierarchisch� genau dann wenn es kein Pr�adikat p pred�R gibt� so dass p �� p�

Eine deduktive Datenbank D � hF �Ri wird positiv� semi�positiv� hierarchisch� oder stra�ti�zierbar genannt� wenn die Regelmenge R positiv� semi�positiv� hierarchisch� oder stra�

ti�zierbar ist�

p

q

s r

¬

1

2

3

Abbildung �� Beispiel� Abh�angigkeitsgraph mit Strati�kation

De�nition �� Strati�kation�� Sei R eine deduktive Regelmenge� Ein Strati�kation �

von R ist eine Abbildung der Menge aller Pr�adikatensymbole pred von R auf die Menge

der positiven nat�urlichen Zahlen N�� so dass f�ur alle Pr�adikate p� q pred�R gilt�

p � def�R �� p � �

p def�R �� p � �

p � q �� p � ��q


p �� q �� p � ��q �

Desweiteren de�niert � eine Partition R� � � � � � Rm von R� so dass f�ur jedes Pr�adikatp def�R alle Fakten und Regeln� die p beschreiben� in der Regelmenge R��p� der jewei�

ligen Schichten liegen�

Intuitiv beschrieben� Eine deduktive Regelmenge ist genau dann strati�zierbar� wenn der

zugeh�orige Abh�angigkeitsgraph keinen negativen Zyklus enth�alt�

�� Fixpunktsemantik deduktiver Datenbanken

Dieser Abschnitt besch�aftigt sich mit der Fixpunktsemantik strati�zierbar deduktiver Da�

tanbanken� Das n�achste Kapitel stellt Fixpunktoperatoren f�ur nicht�strati�zierbare Re�

gelmengen vor� Zun�achst wird der ��naive Fixpunktoperator� vorgestellt� danach die

��iterierte Fixpunktberechnung�� welche eine konkrete Regelabarbeitungsreihenfolge f�ur

Abh�angigkeiten mit Negationen voraussetzt� im Anschlu an diese wird das ��semi�naive�

Fixpunktverfahren n�aher beschrieben� welches versucht� redundante Herleitungen zu ver�

meiden� Abschliessend wird als Vorbereitung f�ur das n�achste Kapitel auf die Problematik

der Auswertung nicht�strati�zierbarer Regelmengen eingegangen�

�� Der naive Fixpunktoperator

Das grundlegende Element f�ur den naiven Fixpunktoperator ist der Ableitungsoperator T

f�ur strati�zierte Regelmengen�

De�nition �� Ableitungsoperator T�� Sei D � hF �Ri eine deduktive Datenbank

und Ri eine Regel aus R der Form A� B�� Bn��C�� Cm� Dann ist T de�niert

als�

T �Ri��F �� f A�j � konsistente Substitution

� � i � n � Bi� F�

� � j � n � Cj� � Fg

Intuitiv betrachtet� wird eine beliebige Regel aus R bez�uglich einer Inputfaktenmenge Fausgewertet� Suche die Substitution f�ur alle Literale der Regel heraus� also binde die


Variablen der Literale an die Fakten der entsprechenden Literale� so dass f�ur die Varia�

blenbindungen �uber die gesamte Regel die Ersetzung konsistent ist�

Negative Literale �Cj werden jedoch anders ausgewertet� F�ur diese wird vorausgesetzt�

dass die Regel sicher ist� das heisst� dass Variablen eines Literals positiv �uber ein Literal

im Regelrumpf gebunden sind� Dadurch wird erreicht� dass jede Variable eines negativen

Literals eine Ersetzung erh�alt� Diese Substitution darf jedoch nicht in der Inputfaktenbasis

enthalten sein� damit die Ableitung erf�ullt wird�

Deduktive Datenbanken werden auf die Speicherung positiver Fakten beschr�ankt� Dieses

bedingt eine andere Auswertung negativer Literale� deren Wahrheitswert falsch oder wahr

nicht in der Datenbank abgespeichert wird�

Vielmehr wendet man hier das Prinzip der ��closed world assumption� �CWA an� Es wird

dabei angenommen� dass die Negierung eines Faktes wahr ist� wenn es weder in F enthal�

ten ist� noch durch Auswertung der Regeln aus F abgeleitet werden kann� Wenn f�ur ein

negatives Literal einer Regel das entsprechende positive Fakt nicht in der Inputfaktenmen�

ge F enthalten ist� kann man mit der CWA schlieen� dass das negative Literal wahr ist�

Dieses Prinzip wird als ��negation as failure� �NAF bezeichnet�

Bisher wurde erl�autert� wie eine einzelne Regel ausgewertet wird� Eine deduktive Daten�

bank kann jedoch durchaus aus mehreren Regeln bestehen� Die Regeln sollten �uber den

gleichen Status der Dantenbank� also �uber derselben Datenbasis ausgewertet werden� um

von einer gleichen Ausgangsbasis auszugehen� Der kollektive TR� Operator wendet deshalb

die gegebene Inputregelmenge auf die Inputfaktenmenge simultan an�

TR�F ��S

Ri�R

T �Ri��F �kollektiv

Die gleichzeitige Anwendung der Regeln bewirkt� dass Zwischenergebnisse� die aus einer

fr�uhzeitig vollendeten Ableitung stammen� nicht f�ur andere im Ableitungsproze be�ndli�

che Regeln sichtbar sind�

Mit diesem Schritt wird die vollst�andige Materialisierung von Relationen erreicht� die vom

Anh�angigkeitsgraphen her betrachtet� nur von Basisrelationen abh�angen� Wie verh�alt es

sich jedoch mit Relationen� die h�oher im Abh�angikeitsgraphen angesiedelt sind� die also

zum Beispiel sowohl von abgeleiteten� als auch von Basisgelationen anh�angen�

Diese ben�otigen eine Mehrfachanwendung von TR unter Beibehaltung der Ergebnisse vor�

heriger Anwendungsschritte als Input f�ur die neue Anwendung inklusive der initialen Ba�

sisfakten als Input� Die Anzahl der Anwendungen von TR h�angt in diesem Fall von der

H�ohe des Abh�angigkeitsgraphen der deduktiven Datenbank ab�


Ein weiteres Problem sind rekursive Regeln� Hier stellt sich die Frage� wie oft TR ange�

wendet werden muss� Diese Frage l�asst sich nicht �uber die H�ohe des Abh�angigkeitsgraphen

beantworten� Vielmehr ist die Art und Anzahl der Basisfakten� sowie der bereits hergeleitet

Fakten magebend� Es ist zu beachten� dass Ableitungen vorhergehender Anwendungen

von TR als neue Inputfakten f�ur neue Herleitungsrunden gebraucht werden� Dies erzwingt

eine Anh�aufung der bisherigen Ergebnisse und wird von dem im Folgenden erl�auterten

Fixpuntoperator geleistet�

Die gesamte Bedeutung einer gegebenen strati�zierbaren deduktiven Datenbank wird �uber

die Mehrfachanwendung des kumulativen Fixpunktoperators T �R bestimmt�

T �R�F �� TR�F � F �kumulativ

Dieser Operator erh�alt die Inputfaktenmenge und vereinigt diese mit den jeweiligen Er�

gebnissen der akktuellen Ableitungsrunde des TR� Diese Vereinigung stellt wiederum die

Inputfaktenmenge f�ur die n�achte Ableitungsrunde dar� Die Inputerhaltung hat jedoch zur

Folge� dass Ableitungen aus vorhergehenden Runden sich wiederholen� Fakten werden

mehrfach hergeleitet� Dieses Prozedere wiederholt sich so lange� bis keine neuen Fakten

mehr abgeleitet werden k�onnen� Der Zustand der Datenbank �andert sich somit nicht mehr�

Dann ist der Fixpunkt F � bez�uglich F und R erreicht�

F � wird die Bedeutung von D � hF �Ri genannt�

F � � T �R�F

�

F � enth�alt alle Basisfakten F� sowie alle durch R ableitbaren Fakten� Man schreibt auch�

De�nition �� Bedeutung einer deduktiven Datenbank�� Die Bedeutung einer semi�

positiven deduktiven Datenbank D � hF �Ri ist der kleinste Fixpunkt F � von T �R der F ganz

enth�alt�

F � ��lfp�T �R� F

Tarski zeigte in �Tar�� dass T �R monoton ist und dass der daraus abgeleitete Fixpunkt F

�

existiert� eindeutig und der kleinste ist�


�� Das iterierte Fixpunktverfahren �IFPI�

In den Betrachtungen f�ur den naiven Fixpunktoperator wurde angenommen� dass die Nega�

tion nur in Abh�angigkeit zu Basisrelationen verwendet wird� T �R wertet dann die gegebene

deduktive Datenbank korrekt aus�

Die zugelassene Verwendung von Negationen wird so erweitert� so dass auch negative

Abh�angigkeiten zwischen abgeleiteten Relation existieren d�urfen� Wendet man nun den

eben de�nierten T �R Fixpunktoperator auf eine solche Regelmenge an� so erh�alt man in

jedem Fall einen Fixpunkt� Dieser Fixpunkt hat jedoch das Manko� dass dieser Fixpunkt

nicht unbedingt einer g�ultigen Interpretation des zugeh�origen Modells entspricht� Dies

liegt daran� dass die vorkommenden Negationen in den Regeln nicht korrekt durch T �R

ausgewertet worden sind�

Was ist also geschehen� T �R wendet alle gegebenen Regeln simultan an� Es werden dadurch

Negationen unter Umst�anden zu fr�uh ausgewertet� es muss also daf�ur Sorge getragen werde�

dass Relationen vollst�andig materialisiert werden� bevor diese durch andere Regeln negativ

refenziert werden�

Ein negatives Literal wird nur dann korrekt durch das NAF�Prinzip evaluiert� wenn die

im Abh�angigkeitsgraphen darunterliegende Relation vollst�andig materialisiert worden ist�

Ein Fakt was noch nicht abgeleitet worden ist� aber im Laufe der Ableitungsrunden positiv

erscheinen wird� wird zuvor �uber das NAF�Prinzip bei einer Negation als falsch hergeleitet�

weil diese Fakt noch nicht in der Datenbank enthalten ist� Im weiteren Verlauf wird

das Fakt in diesem Szenario jedoch wahr �uber NAF ausgewertet� �Uber die kumulative

Eigenschaft von T �R w�urden dann folglich auch inkorrekte Ableitungen gesammelt werden�

Die Regeln m�ussen von T �R in einer kontrollierten Reihenfolge angewendet werden� um eine

zu f�uhe Auswertung von Regeln zu vermeiden� die negative Literale enthalten�

Die Unterteilung der gegebenen Datenbank in eine korrekte Regelabarbeitungsreihenfolge

wird durch das Konzept der Strati�kation geleistet� Die formale De�nition der Strati�ka�

tion wurde bereits in Abschnitt � gegeben�

Das Verfahren der Strati�kation versucht eine Datenbank so in Schichten einzuteilen� dass

negative Abh�angigkeiten nur zwischen jeweils verschiedenen Schichten bestehen d�urfen und

nicht innerhalb einer selbigen Schicht� anders betrachtet ist eine deduktive Datenbank stra�

ti�zerbar� wenn im Abh�angigkeitsgraph kein Zyklus mit einer Negation enthalten ist�

Iterierter Fixpunktoperator bei gegebener Strati�kation � auf D mit maximaler Schicht l�

F� � F


Fi � lfp�T�Ri� Fi�� f�ur � � i � l

F � � Fl �Iterierter Fixpunkt von D

Das iterierte Fixpunktverfahren �IFPI bildet den kleinsten Fixpunkt F � von D� indem

dieser von der untersten Schicht angefangen jeweils den kleinsten Fixpunkt Fi �der Fi��

als Inputfaktenmenge gesamt enth�alt der vorliegenden Schicht bildet und diesen Fixpunkt

als Inputfaktenmenge f�ur den Fixpunktproze der n�achst h�oheren Schicht nimmt� Dieses

Verfahren wir so lange angewandt� bis der kleinste Fixpunkt Fl der h�ochsten Schicht erreicht

ist� Fl ist dann F � von D� Die kumulative Eigenschaft von T �R gew�ahrleistet� dass die

kleinsten Fixpunkte der jeweiligen Schichten in Fl enthalten sind�

Aus einem anderen Blickwinkel betrachtet wird mit diesem Verfahren die gegebene deduk�

tive Datenbank D � hF �Ri in kleinerer Teilprobleme respektive Teildatenbanken der FormDi � hFi��Rii zerlegt� In diesen Teildatenbanken gibt es negative Abh�angigkeiten nur inBezug auf Basisrelationen der jeweiligen betrachteten Schicht� Somit sind die Bedeutungen

der Di mittels T�R herleitbar�

Dieses Verfahren garantiert f�ur strati�zierbare Regelmengen� dass Relationen vollst�andig

materialisiert werden� bevor auf diese negativen Bezug genommen wird�

�� Das di�erenzielle Fixpunktverfahren �DFPI�

Der generelle Nachteil des naiven Fixpunktverfahrens �und des iterierten Fixpunktverfah�

rens ist die wiederholte Ableitung von Fakten in jeder Iterationsrunde� die aus vorherigen

Ableitungsrunden bereits als wahr bewiesen worden sind�

Diese redundanten Berechnungen versucht das di�erenzielle Fixpunktverfahren �DFPI zu

eliminieren� Das Verfahren erscheint in der Literatur auch oftmals unter dem Begri� semi�

naives Fixpunktverfahren� Die grundlegende Idee dieses Verfahrens ist� dass neue Fakten

in der aktuellen Runde nur durch Fakten� die in der vorhergehenden Iterationsrunde er�

zeugt wurden� hergeleitet werden k�onnen�

Das di�erenziellen Fixpunktverfahren kann wie folgt allgemein beschrieben werden�

In der Initialisierungsphase werden alle Fakten� die direkt aus den Basisfakten mit den

Regeln ableitbar sind� hergeleitet�


In der anschliessenden Iterationsphase werden alle impliziten Fakten mit den Fakten aus

dem ersten Schritt abgeleitet� In jeder Iterationsrunde wird dabei jede Regel entsprechend

der Anzahl der abgeleiteten Relationen im Regelrumpf wiederholt angewendet� Bei jeder

Anwendung wird die Auswertung eines der abgeleiteten Rump�iterale auf die Fakten der

vorigen Iterationsrunde beschr�ankt� Somit erh�alt man alle ableitbaren Fakten dieser Ite�

rationsrunde� durch die Beschr�ankung der Auswertung auf Fakten der vorigen Runde ist

jede Ableitung f�ur diese Regel neu�

Zur Speicherung der abgeleiteten Fakten einer Iterationsrunde wird f�ur jede abgeleitete

Relation p eine sogenannte Delta�Relation �p erzeugt� Diese enth�alt alle p�Fakten� die in

einer Iterationsrunde der Relation p hinzugef�ugt wurden� Die zugeh�origen Delta�Regeln

dr�ucken im Wesentlichen aus� wie und aus welchen abgeleiteten Relationen neue Fakten�

also Delta�Fakten� hergeleitet werden k�onnen�

In der Literatur wird zwischen zwei Verfahren unterschieden� deren unterschiedliche Be�

handlung der Delta�Relationen und der Delta�Regelerstellung zu grunde liegt� Die zwei

unterschiedlichen Verfahren werden anhand eines Beispiels im Folgenden diskutiert�

Pfadbeispiel� p�X� Y � e�X� Y

p�X� Y � p�X�Z � p�Z� Y

�� p ��p � �� also p und �p sind disjunkt�

Die Delta�Regeln haben f�ur diesen Fall die Form�

�� p�X� Y � e�X� Y �Nur in Initialisierungsphase

�� p�X� Y � �p�X�Z � p�Z� Y

�� p�X� Y � p�X�Z ��p�Z� Y

�� p�X� Y � �p�X�Z ��p�Z� Y

In der Initialisierungsphase wird die Regel � ausgewertet� Diese ermittelt die ersten neuen

Fakten� welche f�ur die Auswertung der n�achsten Regeln ben�otigt werden� In den n�achsten

Iterationsphasen werden dann nur die Regeln �� wie folgt ausgewertet�

Die aus der vorherigen Runde gewonnenen Delta�Fakten plus die ��alten� p�Fakten wer�

den zur Auswertung der Regeln �� herangezogen� Aus dieser Ableitungsrunde entstehen


��neue� Delta�Fakten� Nach jeder Runde werden die ��alten� Delta�Fakten aus der vorigen

Runde in die p�Relation eingetragen� Die ��neuen� Delta�Fakten werden dann zur Berech�

nung der Regelr�umpfe in der n�achsten Ableitungsrunde herangezogen� Bevor jedoch eine

neue Runde beginnt� wird zun�achst eine Duplikateneliminierung auf den ��neuen� p�Delta�

Fakten bez�uglich der alten p�Fakten durchgef�uhrt� Dieser Schritt ist notwendig� denn es

besteht die M�oglichkeit� dass ein p�Fakt bereits durch eine alternative Regel abgeleitet wur�

de� In diesem Fall bringt dieses Delta�Fakt dann keine neuen Erkenntnisse und w�urde nur

dazu f�uhren bereits als wahr bewiesene Fakten abzuleiten� Das Verfahren wird dann be�

endet� wenn nach der Duplikateliminierung in den Delta�Relationen keine �neuen Fakten

enthalten sind� somit ist dann auch der Fixpunkt zu gegebenem D erreicht�

Der Vorteil dieser Variante ist� dass die redundante Speicherung der Fakten der letzten

Iterationsrunde in p und in �p vermieden wird� Es ist jedoch nachteilig zu bemerken� dass

bei dieser Realisierung f�ur die Delta�Regeln alle Kombinationen von Delta�Relationen in

einem Regelrumpf betrachtet werden m�ussen� um alle m�oglichen Ableitungen einer Itera�

tionsrunde zu erhalten� F�ur eine Regel mit n abgeleiteten Rump�iteralen erh�alt man dann

�n � � Delta�Regeln�

�� p ��p � �p� also in p sind die �p enthalten�

Die Delta�Regeln haben f�ur diesen Fall die Form�

�� p�X� Y � e�X� Y �Nur in Initialisierungsphase

�� p�X� Y � �p�X�Z � p�Z� Y

�� p�X� Y � p�X�Z ��p�Z� Y

Die erste Regel wird in der Initialisierungsphase genauso ausgewertet� wie dies f�ur das erste

Verfahren beschrieben wurde� Als Unterschied werden jedoch die neu gewonnen p�Delta�

Fakten bereits sofort in die p�Relation eingetragen� Die Eintragung der p�Delta�Fakten in

die p�Relation geschieht unter Ber�ucksichtigung der Duplikateliminierung f�ur die p�Delta�

Relation bez�uglich der p�Relation�

In den weiteren Iterationsphasen wird die Rumpfauswertung auf den p�Relationen und

den p�Delta�Relationen durchgef�uhrt� welche beide jeweils die neuen Fakten aus der vorigen

Runde enthalten� Als Konsequenz der Rumpfauswertung erh�alt man ��neue� Delta�Fakten�

Das Verfahren dieser zweiten Variante wird dann beendet� wenn nach der Duplikatelimi�

KAPITEL �� DEDUKTIVE DATENBANKEN �

nierung in den Delta�Relationen keine �neuen Fakten enthalten sind� somit ist dann auch

der Fixpunkt zu gegebenem D erreicht�

Der Vorteil dieser zweiten Variante ist� dass linear viele Delta�Regeln erzeugt werden� Dies

geschieht in Abh�angigkeit zu den in den Regelr�umpfen erscheinenden abgeleiteten Litera�

len� Ein durchaus nachteiliger Aspekt dieser Realisierung ist die redundante Speicherung

der neuen Fakten sowohl in �p� als auch in p�

Welche dieser zwei Varianten schliesslich angewandt wird� h�angt von der zugrunde lie�

genden Regelmenge� sowie von der gegebenen Faktenmenge ab� Wiegt man die Vor� und

Nachteile ab� so kann man durchaus die zweite Variante empfehlen� in der Ho�nung� dass

im Vergleich zu den Basisrelationen� die Menge der neu erzeugten Fakten in den einzelnen

Iterationsrunden klein ist�

Eine weitere M�oglichkeit redundante Ableitungen zu vermeiden ist die Verwendung von�Anderungspropagierung� die jedoch erst in sp�ateren Kapiteln wesentlicher Gegenstand der

Untersuchungen sein wird�

�� Unstratizierbare Regelmengen

Die bisher vorgestellten Fixpunktoperatoren und Fixpunktverfahren hatten als Vorausset�

zung f�ur die korrekte Semantikbestimmung die Strati�zierbarkeit der gegebenen deduktiven

Datenbank� Liegt diese vor� so werden negative Literale �uber das NAF�Prinzip ausgewer�

tet�

Nicht strati�zierbare Datenbanken bestehen bildlich gesprochen aus einer Regelmenge

die mindestens einen Zyklus mit Negation in ihrem Angh�angigkeitsgraphen enth�alt� Die

vollst�andige Materialisierung von Relationen� auf welche per Negation zugegri�en wird�

ist somit nicht mehr gew�ahleistet� Die Anwendung des NAF�Prinzips kann zu falschen

Konsequenzen f�uhren�

Dass unstrati�zierbare Regelmengen sinnvoll eingesetzt werden k�onnen� soll das folgende

klassische Beispiel zeigen�

Regel� even�X � succ�X� Y ��even�Y Fakten� succ��

succ��

succ��

succ�i� �� i


Eine Zahl X ist genau dann gerade� wenn X als Nachfolger Y hat und Y nicht gerade �unge�

rade ist� L�asst man die Semantik dieses Beispiels mit dem kumulativen Fixpunktoperator

T �R�F bestimmen� so erh�alt man als Ergebnis

F � � feven�� even�� even�� even�i� � g�

erwartet wird jedoch

F � � feven�� even�� even�� g�

eine Menge von de�nitiv wahren Fakten� die man ��argumentativ� ermitteln kann� Wird

zu den Basisfakten zum Beispiel succ�� hinzugef�ugt� so versagt auch hier das ��argu�

mentative� Verfahren der Regelanwendung� Das Ergebnis wechselt mit der Annahme� ob

even�� wahr oder falsch ist� even�� ist somit unde�niert�

Als Resume l�asst sich anf�uhren� dass die vorgestellten Fixpunktverfahren f�ur nicht strati��

zierbare Datenbanken versagen� obwohl das Ergebnis aus de�nitiv wahren Fakten besteht�

��andere� Fixpunktverfahren werden also ben�otigt� Desweiteren wurde festgestellt� dass

sich die Annahme �uber implizit falsche und explizit wahre gegebene Fakten nicht mehr

halten l�asst� sondern der Semantikbegri� um unde�nierte Fakten erweitert werden muss�

Kapitel �

Fixpunktverfahren f�ur nicht

strati�zierbare Datenbanken

Im vorletzten Kapitel � wurde zum Abschlu motivierend auf die Problematik der nicht

strati�zierbaren Datenbanken eingegangen� Kapitel � wird auf diese Problematik n�aher

eingehen� Zun�achst wird ein neuer Sematikbegri� eingef�uhrt� der den unde�nierten Fak�

ten gerecht wird� Danach werden zwei Verfahren vorgestellt� welche konstruktiv zwei

Teilsemantiken berechnen� das Conditional�Fixpoint� �CFP und das alternierende Fix�

punktverfahren �AFPI � Das Kapitel � schliesst mit einem Vergleich der beiden Verfahren

ab�

�� Semantik nicht strati�zierbarer Datenbanken

Zun�achst wird der erweiterte Semantikbegri� formal de�niert�

De�nition �� Herbrand�Basis und Modell�� Sei D eine deduktive Datenbank� Die

Herbrand�Basis HD von D ist die Menge aller instanziierten Atome� die aus der Menge

der Konstanten� welche in hF �Ri vorkommen� konstruieren kann� Jede Teilmenge I von

HD ist eine Herbrand�Interpretation von D� I ist ein Herbrand�Modell von D� wenn es ein

Modell von D ist� also zum Beispiel alle Fakten und Regeln wahr in I sind� Ein Herbrand�

Modell von D ist das kleinste Herbrand�Modell von D� wenn es in jedem Herbrand�Modell

von D enthalten ist und heisst minimal wenn keine seiner Teilmengen Herbrand�Modell

von D ist�

Der explizite Status einer Datenbank ist gegeben durch deren Regeln und Fakten�

��

KAPITEL �� NICHT STRATIFIZIERBARE DATENBANKEN ��

Der implizite Status einer deduktiven Datenbank ist de�niert als die Menge der aus dem

explititem Status herleitbaren Fakten�

De�nition �� Implizierter Datenbankstatus�� Sei D eine deduktive Datenbank� Der

implizite Datenbankstatus SD von D ist defniert als das ��well�founded� Modell �VGRS��

f�ur D�

SD �� F �� F �

��

wobei F �� F

�� HD Mengen von instanziierten Atomen sind und ��F �

� alle Negationen der

Atome aus F �� enth�alt� Die Menge F �

� repr�asentiert den wahren Anteil des well�founded

Modells� w�ahrend ��F �� alle wahren negativ Schl�usse inne hat� also F �

� schliesst alle falschen

Atome ein�

Die Menge der unde�nierten Atome ist implizit gegeben durch F �� HD n �F �

��F �� Diese

Menge besteht aus den Atomen der Herbrand�Basis� die weder wahr� noch falsch sind�

undefined

*

?F

*

�F

*

�F

true false HD

Abbildung �� Herbrandbasis

Es ist also das Ziel geeigneter Fixpunktverfahren� die Herbrand�Basis HD zu einer gegebe�

nen deduktiven Datenbank D� in mindestens zwei Teilsemantiken konstruktiv zu untertei�

len� so dass die dritte Teilsemantik implizit ermittelbar ist�

�� Der Conditional Fixpoint Operator �CFP�

Das erste hier vorzustellende Verfahren ist der Conditional Fixpoint Operator �CFP � F�

Bry postulierte diesen Fixpunktoperator erstmals in seiner Ver�o�enltichung �Bry�� aus

dem Jahr �� Nachfolgende De�nitionen sind aus �ZF�� entnommen�


Der wesentliche Unterschied im Vergleich zu den bisher vorgestellten Fixpunktverfahren ist

die Darstellung von Fakten� Bisher wurden de�nitiv wahre Fakten explizit gespeichert� Der

CFP erweitert die Darstellung der Fakten um das Konzept der ��Conditional Facts� �CF �

��Bedingte Fakten� �CF enthalten instanziierte negative Literale� deren Wahrheitswert

noch nicht bewiesen wurde� z�B� even�� even��

De�nition �� Conditional Facts�� Ein Conditional Fact ist eine Grundinstanz der

Form A��B�� Bn oder der Form A��C� wobei C eine Menge von Atomen mit C �

fB�� Bng ist� Eine Menge von Conditional Facts wird als ��quasi�Interpretation� be�

zeichnet� F�ur eine Quasi�Interpretation I werden folgende Mengen de�niert�

facts�I �� fA j A� Igheads�I �� fA j �C � A��C Igconds�I �� fB j �A��C I � B Cg

Die grundlegende Idee ist� dass wenn immer eine Grundinstanz einer Regel angewandt

wird� negative Literale ignoriert werden und als Bedingungen an das abgeleitete conditio�

nal fact angeh�angt werden inklusive all derer Bedingungen der CF die zur Instanziierung

der Regel notwendig sind�

Das CFP�Verfahren gliedert sich in zwei Hauptphasen auf�

�� In der Fixpunktphase werden alle m�oglichen condiational facts abgeleitet�

�� In der Reduktionsphase werden die abgeleiteten CF systematisch reduziert�

also wenn m�oglich als wahr oder falsch bewiesen �

F�ur die erste Phase� die Fixpunktphase wird der Fixpunktoperator de�niert als�

De�nition �� Conditional Fixpunkt Operator�� Sei P ein allgemeines logisches Pro�

gramm und sei I eine Quasi�Interpretation� Dann wird die Menge der direkten bedingten

Ableitungen von I bez�uglich P de�niert als�

TCP �I �� fA��C j es gibt eine Grundinstanz A� A�� Am��B�� Bn

einer Regel aus P� so dass

�A��C� � � � � � Am��Cm I und C � fB�� Bng �Sm

i�� Cig


Die erste initiale Quasi�Interpretation I besteht aus CF� die aus den Basisfakten erzeugt

wurden� Basisfakten werden in der Form succ�� oder succ�� true dargestellt�

Der Fixpunktoperator TCP wird so lange angewandt� bis keine neuen bedingten Fakten

mehr abgeleitet werden k�onnen�

Anschliessend �ndet in der zweiten Phase� der Reduktionsphase� die Reduktion der aus

der Fixpunktphase gewonnenen bedingten Fakten statt� Dazu wird de�niert�

De�nition �� Reduktion von Quasi�Interpretationen�� Sei I eine Quasi�Interpretation�

Dann ist die Reduktion von I de�niert als�

R�I �� fA��C j �A��C� I � C � � facts�I � � und C � C � � heads�I g

Dieser Reduktionsoperator f�uhrt zwei Schritte aus�

�� Wenn eine Bedingung �B eines conditional facts falsch in I ist� z�B� B facts�I � dann

wird das conditional fact gel�oscht �negative Reduktion �

�� Wenn eine Bedingung �B eines conditional facts wahr in I ist� z�B� B � heads�I �

dann wird diese Bedingung aus dem conditional fact gel�oscht �positive Reduktion � Die

Anwendung des Reduktionsoperators endet dann� wenn keine weiteren Reduktionen mehr

m�oglich sind�

Diese beiden Phasen zusammen genommen werden auch als ��Residualprogramm� bezeich�

net� welches wie folgt de�niert wird�

De�nition �� Residualprogramm�� Sei P ein allgemeines logisches Prorgramm� Das

Residualprogramm res�P� von P wird de�niert als�

res�P �� R��TC��P ��

res�P beinhaltet dann die Teilbedeutungen F �� und F �

� � wobei die unde�nierten Fakten

conditional facts mit Bedingungen sind� deren Wahrheitswert nicht bewiesen werden konn�

te�

Als motivierendes Beispiel sei hier wieder das Beispiel aus Kapitel � angef�uhrt�

P � f even�X � succ�X� Y ��even�Y


succ�� succ�� succ�� succ�� succ�� succ��

Die Fixpunktphase berechnet�

even�� even�� even�� even�� even�� even�� even�� even�� even�� even�� even�� even��

Die Reduktionsphase zum Fixpunkt aus der ersten Phase�

even�� even��

��

even�� even�� even��

��even��

��

even�� even�� even��

��even��

even�� even��

F �� feven�� even�� even�� g� F �

� � feven�� g

�� Das alternierende Fixpunktverfahren �AFPI�

Das zweite vorzustellende Verfahren zur Bestimmung einer m�oglichen drei�wertigen Se�

mantik einer deduktiven Datenbank �wahr� falsch� unde�niert ist das ��alternierende Fix�

punktverfahren� �AFPI nach A� van Gelder �VG�� VG��


Das AFPI basiert auf zwei grundlegenden Ideen�

�� Wie bereits mehrfach erw�ahnt wird das NAF�Prinzip zur Auswertung negativer Literale

den m�oglicherweise vorkommenden unde�nierten Fakten nicht gerecht� Das AFPI spei�

chert deshalb falsche Fakten explizit ab�

�� Es werden zwei Mengen falscher Fakten hinterlegt� Eine �Ubersch�atzung und eine Un�

tersch�atzung von falschen Fakten� Diese zwei Mengen dienen jeweils als negative Referenz�

menge eines noch zu de�nierenden Fixpunktoperators T �D�Neg� T

�D�Neg leitet eine Menge von

wahren Fakten her� Das Komplement dieser Menge bez�uglich HD bildet dann abwechselnd

eine neue �Uber� oder Untersch�atung von falschen Fakten� Aus der Mengendi�erenz der�Uber� und Untersch�atzung wird die Menge der unde�nierten Fakten gebildet�

Das AFPI setzt zur Bestimmung der endg�ultigen �Uber� und Untersch�atzung von falschen

Fakten zwei ineinander verschr�ankte Fixpunktprozesse ein� einen inneren und einen �ausseren

Fixpunktprozess�

Der innere Fixpunktprozess ist durch den Fixpunktoperator T �D�Neg mit D � hF �Ri cha�

rakterisiert�

De�nition �� Ableitungsoperator mit fester negativer Referenzmenge�� Sei R

eine Regel der Form A � B�� Bn� Pos eine Menge von wahren Fakten und Neg ei�

ne Menge von falschen Fakten� Dann wird der Ableitungsoperator TNeg�R��Pos wie folgt

de�niert�

TNeg�R��Pos �� fA� j erf�ullt��B�� Pos�Neg � � i � n g

mit erf�ullt��L�X�� X� ��

�L� X�� wennL � L�

L� X�� wennL � �L�

De�nition �� Fixpunktoperator mit fester negativer Referenzmenge�� Sei D ei�

ne deduktive Datenbank mit D � hF �Ri� Sei Pos eine Menge von wahren Fakten und Neg

die negative Referenzmenge von falschen Fakten� Dann ist der Fixpunktoperator T �D�Neg

de�niert als�

T �D�Neg�Pos ��

SRi�R

TNeg�Ri��Pos � F


Der Fixpunktoperator T �D�Neg berechnet die Semantik einer deduktiven Datenbank D bez�uglich

einer festen negativen Referenzmenge Neg�

Der �ausserer Fixpunktprozess ist gekennzeichnet durch die jeweils abwechselnde Berech�

nung der �Uber� und Untersch�atzung von falschen Fakten� Diese �Uber� und Untersch�atzungen

dienen alternierend dem inneren Fixpunktprozessen T �D�Neg als feste negative Referenzmen�

ge�

Die �Uberg�ange zwischen den �Uber� und Untersch�atzungen von falschen Fakten werden

beschrieben durch�

SD�Neg �� lfp�T �D�Neg �Menge wahrer Fakten

eSD�Neg �� HD � SD�Neg � �Menge falscher Fakten

Der Ableitungsoperator zu zwei gleichartigen �Uber� oder Untersch�atzungen hin� ist be�

schrieben durch�

AD�Neg �� eSD�eSD�Neg

Mit diesen Mengenbeschreibungen wird der kleinste Fixpunkt des �ausseren Ableitungsope�

rators de�niert�

F �� lfp�AD

Der kleinste �aussere Fixpunkt ist genau dann erreicht� wenn sich die Mengen zweier auf�

einander folgender� z�B� Untersch�atzungen nicht mehr �andert�

Die beiden weiteren Teilsemantiken werden ermittelt per�

F �� SD�F

�� und F �

� �� H D � �F �� F �

��

Anhand von Abbildung �� wird nun das alternierende Fixpunktverfahren intuitiv n�aher

beschrieben� ohne jedoch eine konkrete Regel� und Faktenmenge als Beispiel zu betrachten�

Das Verfahren des alternierenden Fixpunktoperators beginnt mit der Annahme� dass kein

Fakt de�nitiv falsch ist �DF� � � � respektive wird angenommen� dass die Herbrandbasis


NDF NDF NDF

NDT NDT NDTDF

DT DT DT

DF DF

Abbildung �� AFPI nach van Gelder

HD der zugeh�origen Datenbank D m�oglicherweise vollst�andig wahr ist �NDF� � HD �

Bemerkung� W�urde imGegensatz dazu im ersten Schritt angenommen� dass die vollst�andige

HD de�nitiv falsch w�are �inklusive der Basisfakten � so wird T�D�HD

�� nichts herleiten� vor�

ausgesetzt� dass die Regelmenge R sicher ist� Diese Annahme wird jedoch den gegebenen

Basisfakten nicht gerecht� denn diese werden immer als de�nitiv wahr vorausgesetzt� Dieses

bedeutet� dass zumindest die Basisfakten immer in den Mengen NDFi und DTi enthalten

sein sollten� �Der im n�achsten Abschnitt beschriebene doubled program Ansatz beginnt

jedoch anders�

Mit diesen Annahmen berechnet T �D�DF�

�� die erste Untersch�atzung der de�nitv wahren

Fakten �DT� � wobei DF� � � die erste negative Referenzmenge ist� Dieses bedeutet

insbesondere� dass nur positive Regeln �Regeln ohne negative Literale ausgewertet werden�

Die erste angenommene �Ubersch�atzung von m�oglicherweise falschen Fakten �NDT� � wird

�uber das Komplement bez�uglich der Herbrandbasis HD der eben berechneten DT� Fakten�

menge gebildet�

Mit der ersten �Ubersch�atzung von m�oglicherweise falschen Fakten �NDT� als negative

Referenzmenge berechnet T �D�NDT�

�� die zweite �Ubersch�atzung von m�oglicherweise wah�

ren Fakten �NDF� � davon das Komplement stellt die zweite Untersch�atzung von falschen

Fakten �DF� bereit�

KAPITEL �� NICHT STRATIFIZIERBARE DATENBANKEN �

Mit der zweiten Untersch�atzung DF� als negative Referenzmenge leitet T�D�DF�

�� die zwei�

te Untesch�atzung DT� her�

Diese Schritte werden so lange wiederholt bis das folgende Abbruchkriterium erf�ullt wird�

Das alternierende Berechnen der �Uber� und Untersch�atzungen von falschen Fakten endet

dann� wenn sich an zwei Bl�ocken �DFn�� NDTn�� und �DFn� NDTn nichts mehr �andert�

Damit ist dann der �aussere Fixpunkt erricht� Die gesamte Bedeutung der deduktiven

Datenbank kann� wie oben formal beschrieben� nun ermittelt werden�

Beobachtungen� �� Die Mengen der DFi und DTi sind monoton anwachsend�

�� Die Mengen der NDFi und NDTi sind monoton abnehmend�

Die Beobachtung� dass NDF monoton abnehmend ist� und dass DT monoton anwachsend

ist� wird eine entscheidende Rolle bei der E�zienzsteigerungsbetrachtungen in den n�achsten

Kapiteln sein�

�� Der Doubled Program Ansatz Eine Implemen

tierung des AFPI

Einer der ersten Ans�atze das alternierende Fixpunktverfahren e�zient praktisch zu imple�

mentieren� ist der Ansatz des ��Doubled Program� �DPA von Kemp� Stuckey und Sriva�

stava �KSS�� KSS��

Das Verfahren des ��verdoppelten Programms� wird in dieser Diplomarbeit eines der grund�

legenden Konzepte zur E�zienzsteigerung der Berechnung des AFPI sein� Vorweg genom�

men wird im weiteren Verlauf dieser Arbeit das DPA um die Techniken der �Anderungspropagierung

und deren e�ziente Auswertung� erweitert werden�

Das grundlegende Wesen dieses Ansatzes ist die Vermeidung mit der Herbrandbasis HD

einer gegebenen deduktiven Datenbank zu arbeiten� In diesem Zusammenhang wird die ex�

plizite Spreicherung von falschen Fakten vermieden� Die Herbrandbasis kann in Abh�angigkeit

der verwendeten Fakten und Relationen gross werden� Diese kann jedoch an dem Punkt

Verwendung �nden� an dem es zum Schlu� nach der Fixpunktberechnug� um die Berech�

nung der de�nitv falschen Fakten geht� Ein weiterer Grund das AFPI nicht direkt zu


implementieren� ist der Wunsch nur mit positiven Fakten zu arbeiten� Im Zusammenhang

mit Datenbanksystem ist dies ein Vorteil� weil es wesentlich einfacher ist in Anbetracht der

Speicherung und des Abfragens von Relationen mit positiven Fakten unzugehen�

Der au��alligste Unterschied im Vergleich des DPA mit der direkten Implementierung des

AFPI� ist die Handhabung der Auswertung der negativen Literale� Dieser Unterschied ist

bedingt durch die Tatsache� dass der DPA explizit falsche Fakten nicht speichert� sondern

�uber eine ��Trick� negative Literale per NAF auswertet� Der ��Trick� besteht im wesentli�

chen aus der ��Verdopplung� der gegebenen Regelmenge� Die Verdopplung der Regelmenge

geht mit einer Transformation der Literale einher� Das eine erzeugte Programm berechnet

die NDF Mengen� das andere leitet die DT Menge her� Auch das AFPI berechnet diese

beiden Mengen abwechselnd� Die Transformation der Regelmenge wird in zwei Teilen in�

formal dargestellt�

�� F�ur die Berechnung desNDF �Programms wird den positiven Literalen der urpr�unglichen

Regelmenge das Pr�a�x ��ndf� vorangestellt� z�B aus p�X� Y wird ndf p�X� Y � Negative

Literale erhalten der Pr�a�x ��dt�� z�B� aus �q�X wird �dt q�X �

�� F�ur die Berechnung des DT �Programms wird den positiven Literalen der urpr�unglichen

Regelmenge das Pr�a�x ��dt� vorangestellt� z�B aus p�X� Y wird dt p�X� Y � Negative Li�

terale erhalten der Pr�a�x ��ndf�� z�B� aus �q�X wird �ndf q�X �

Basisfaktenliterale werden nicht transformiert� Diese werden so wie sie sind in die NDF �

und DT �Regelmenge �ubernommen� weil die Basisfakten a priori de�nitiv wahr sind und

somit in beiden Mengen enthalten sein sollten�

Die innere Fixpunktbildung wird auf die zwei verschiedenen Regelmengen� NDF und DT �

abwechselnd getrennt durchgef�uhrt�

Das AFPI werwendete hierzu den T �D�Neg Fixpunktoperator an� Dieser arbeitet auf ein

und der selben Regelmenge� Es wird jedoch zwischen den �Uber� und Untersch�atzungen

der negativen Referenzmenge di�erenziert� die aus dem Komplement der vorigen inneren

Fixpunktberechnungen resultierten�

Das DPA leitet die zwei verschiedenen inneren Fixpunkt mit dem herk�ommlichen T �R�F

Fixpunktoperator her� Dieses ist m�oglich� weil die zwei Regelmengen in ihrer getrennten

Betrachtung immer strati�zierbar sind� Vielmehr h�angen vorkommende negative Litera�

le nur von ��virtuellen� Basisfakten ab� ��Virtuell� bedeutet in diesem Zusammenhang�


dass diese angesprochenen Basisfakten in der vorhergehenden Fixpunktberechnung abge�

leitet wurden und nicht mit den eigentlichen Basisfakten der gegebenen Datenbank D zu

verwechseln sind�

Die Auswertung von negativen Literalen im Vergleich zum AFPI erfolgt wie folgt�

Der AFPI wertet negative Literale aus� indem nachgeschaut wird� ob das zu testende Fakt

mit seinen Variablenbindungen in der nagtiven Referenzmenge ist� Wenn das der Fall ist�

wird das negative Literal als wahr ausgewertet�

Der DPA besitzt keine negative Referenzmenge� sondern wertet instanziierte negative Li�

terale in der Art aus� als das nachgefragt wird� ob das Fakt im postiven Anteil vorigen

inneren Fixpunktbildung zu �nden ist� also in NDF f�ur die DT�Berechnung� bzw� in DT

f�ur die NDF�Berechnung� Ist dies nicht der Fall� so wird �uber das NAF�Prinzip geschlossen�

dass es im Komplement sein muss und dann die Negation als wahr ausgewertet wird�

Beispiel� Angenommen die DT�Regeln werden angewendet� so werden negative Literale

im AFPI explizit in der DF�Referenzmenge des vorigen Fixpunktes ausgewertet� Im DPA

werden negative Literale ausgewertet� in dem gefragt wird ob diese nicht im NDF sind�

also folglich per NAF�Prinzip in DF sind�

Abbildung �� S�aulendiagramm des Doubled Program Ansatzes

Die innere und �aussere Fixpunktberechnungen des ��doubled Program� Ansatzes bildlich

erl�autert �siehe dazu auch Abbildung ��

Der DPA beginnt mit der Annahme� dass die positive Menge DT� leer ist �die Basisfakten

ausgenommen � Mit dieser Annahme berechnet T �RNDF

�F �DT� den ersten kleinsten Fix�punkt NDF� von NDF�Fakten mittels der NDF�Regeln� �Negative Literale beginnen mit

dem Pr�a�x ��dt� � DT� ist die erste implizite negative Referenzmenge�


In der zweiten inneren Fixpunktberechnung leitet T �RDT

�F �NDF� die erste Menge DT�

von DT�Fakten mittels der DT�Regeln her� �Negative Literale beginnen mit dem Pr�a�x

��ndf� � NDF�� der Fixpunkt aus der ersten Berechnung� ist jetzt die implizite negative

Referenzmenge�

In der dritten Fixpunktberechnung leitet T �RNDF

�F �DT� die zweite Menge NDF� mittels

der NDF�Regeln her� DT�� der Fixpunkt aus der zweiten Berechnung� ist nun die implizite

negative Referenzmenge�

In der vierten Fixpunktberechnung leitet T �RDT

�F �NDF� die zweite Menge DT� mittels

der DT�Regeln her� NDF� ist die implizite negative Referenzmenge�

Diese Schritte werden so lange angewandt� bis der �aussere Fixpunkt erreicht ist�

Der �aussere Fixpunkt ist genau dann erreicht� wenn sich die DT�Fakten nicht mehr �andern�

also wenn DTi � DTi�� ist�

Im weiteren Vergleich zwischen der direkten Implementierung des alternierenden Fixpunkt�

verfahrens und dem Doubled Program Ansatz f�allt auf� dass die beiden Verfahren mit zwei

di�erierenden Annahmen beginnen� Das AFPI beginnt mit der Annahme� dass DF� � �

ist� Der DPA beginnt mit der Annahme DT� � �� Beide Verfahren liefern jedoch das

gleiche Endergebnis� wie die Autorin in �Gri�� beweist�

Intuitiv ist dieser Versatz der Starts�aulen um einen inneren Fixpunkt mit der Tatsache

begr�undet� dass der DPA mit positiven Fakten arbeitet und das Betrachten und Herleiten

von HD vermieden werden soll� Wie bereits beschrieben betrachtet das AFPI im ersten

Fixpunkt aufgrund der Anfangsannahme nur positive Regeln� Dieses ��Vers�aumnis� wird

jedoch in den ersten beiden innerern Fixpunkten des DPA nachgeholt und beeintr�achtigt

nicht die impliziten negativen Referenzmengen�

In Vorbereitung auf den DPA�Algorithmus wird die nachfolgende Notation de�niert� die

es erm�oglicht getrennt die DT � und NDF �Fakten anzusprechen und somit berechnete

Fixpunkte auf den DT � bzw� NDF �Bereich einzuschr�anken�

De�nition �� ndf� und dt�Einschr�ankung�� Sei D � hF �Ri eine deduktive Daten�

bank� Ddpa � hF �RNDF �RDT i die entsprechend DPA transformierte deduktive Datenbank


mit ihrer Herbrandbasis HDDPA� F�ur eine Faktenmenge I HDDPA sei folgendes de�niert�

Ijdt �� f dt A j A HD n F und dt A I gIjndf �� f ndf A j A HD n F und ndf A I g

i ��

DT� ��

repeat

i �� i ��

NDFi �� lfp�T �RNDF

�F �DTi�� jndf �DTi �� lfp�T �

RDT�F �NDFi jdt�

until DTi � DTi��

DT �� DTi�

NDF �� NDFi�

Abbildung �� Der DPA Algorithmus

Motivierendes Beispiel �aus dem CFP Abschnitt �

R �� feven�X � succ�X� Y ��even�Y g�F �� fsucc�� succ�� succ�� succ�� succ�� succ�� g

RNDF �� fndf even�X � succ�X� Y ��dt even�Y gRDT �� fdt even�X � succ�X� Y ��ndf even�Y g

Mit DT� � ��

NDF� � f ndf even�� ndf even�� ndf even�� ndf even�� ndf even�� ndf even�� gDT� � f dt even�� g

NDF� � f ndf even�� ndf even�� ndf even�� ndf even�� ndf even�� gDT� � f dt even�� dt even�� g

NDF � f ndf even�� ndf even�� ndf even�� ndf even�� gDT � f dt even�� dt even�� dt even�� g

NDF � f ndf even�� ndf even�� ndf even�� ndf even�� gDT � f dt even�� dt even�� dt even�� g


DT � DT Der �aussere Fixpunkt ist erreicht�

F �� f even�� even�� even�� g und F �

� � f even�� g

Das Conditional Fixpunktverfahren �CFP � sowie das alternierende Fixpunktverfahren

�AFPI in der Doubled Program �DPA Verwirklichung� berechnen f�ur die obige Beispiel�

datenbank die gleiche resultierende Bedeutung�

�� CFP versus AFPI

Mit den Beispieldatenbanken wurde bereits intuitiv festgestellt� dass das Conditional Fix�

punkt Verfahren die gleichen Ergebniss liefert� wie das alternierende Fixpunktverfahren�

Bry stellte dazu fest� das beide Verfahren �aquivalente Ergebnisse berechnen� Beide Ver�

fahren berechnen das well�founded Modell einer gegebenen deduktiven Datenbank�

Die gravierenden Unterschiede liegen in der Art und Weise� wie die beiden Verfahren das

Resultat berechnen� Dem CFP kann man durchaus als Vorteil vermerken� dass dieser

��nur� eine Fixpunktphase ben�otigt� Der AFPI ben�otigt im Vergleich mehrere innere Fix�

punktphasen� deren Anzahl von der Art der Fakten und Regeln abh�angt� Ein Nachteil

des CFP ist die M�oglichkeit des exponenziellen Wachstums von bedingten Fakten in der

Fixpunktphase� z�B� durch folgende Regeln und Fakten�

Regeln�

q�X � s�X� ��q�X �r�X � s�X� ��r�X �p�X � p�Y � s�Y�X ��q�Y �p�X � p�Y � s�X� Y ��r�Y �

Fakten� p�� succ�i� �� i f�ur �� i � n

Die Fixpunktphase des CFP berechnet�

q�� q�� r�� r�� q�� q�� r�� r��

��


q�n� � � �q�n� � r�n� � � �r�n� �

p�� q�� p�� r��

p�� q�� q�� p�� r�� q�� p�� q�� r�� p�� r�� r��

p�� q�� q�� q�� p�� r�� q�� q�� p�� q�� r�� q�� p�� r�� r�� q�� p�� q�� q�� r�� p�� r�� q�� r�� p�� q�� r�� r�� p�� r�� r�� r��

��

Es werden insgesamt �n nPi��

�i � �n �n�� bedingte Fakten materialisiert�

Ein weiterer negativer Aspekt des CFP� ist die praktische Implementierung in einem kon�

kretem Datenbanksystem� Diese Problematik ergibt sich aus der Fragestellung� wie die

bedingten Fakten in der Datenbank darzustellen sind� und wie einfach deren Handha�

bung im Zusammenhang mit anderen Konzepten� wie der Anfragebearbeitung oder der�Anderungspropagierung ist�

Der Nachteil des AFPI� der mehrfachen inneren Fixpunktiterationen� wird in dieser Arbeit�

durch die Diskussion �uber die Kombination bekannter Verfahren mit dem DPA� versucht

zu relativieren�

Kapitel �

�Anderungspropagierung

Das Kapitel �uber �Anderungspropagierung stellt die Komponente vor� um welche der Doub�

led Progam Ansatz erweitert werden soll� In Abschnitt eins werden die Grundlagen der�Anderungssprache und deren Auswertung vorgestellt� Im darauf folgenden Abschnitt wird

die Erstellung von Propagierungsregeln n�aher erl�autert� In Kombination mit dem Ab�

schnitt �uber Transitionsregeln erh�alt man einen grundlegenden Mechanismus f�ur die Aus�

wertung von echten �Anderungen�

�� Grundlagen

Dieser Abschnitt behandelt kurz die Grundlagen der �Anderungsanweisungen� In Unter�

abschnitt eins wird die fomale Sprache f�ur �Anderungsanweisungen vorgestellt� Der zwei�

te Unterabschnitt behandelt dann die Auswertung der �Anderungsanweisungen im Hin�

blick auf Basisfakten�anderungen� Wie bereits eben erw�ahnt liegt der Focus auf Basisfak�

ten�anderungen� wie das Einf�ugen und L�oschen von Fakten aus Basisrelationen�

�� Syntax

Der wesentliche Bestandteil der �Anderungssprache sind die sogenannten ��dynamischen Li�

terale�� welche die L�oschung oder Einf�ugung individueller Fakten ausdr�ucken�

De�nition �� Dynamisches Literal�� Sei D eine deduktive Datenbank und A ein Ba�

sisatom mit pred�A pred�D � Dann ist A mit f ��g ein dynamisches Literal�

�A heisst positives dynamisches Literal� �A heisst negatives dynamisches Literal�

��

KAPITEL �� ANDERUNGSPROPAGIERUNG ��

Dynamische Literale k�onnen durchaus als Behauptungen �uber den neuen Zustand einer

Datenbank betrachtet werden� Intuitiv besagt das positive Literal A� dass A im neuen

Datenbankzustand wahr werden soll� hingegen besagt �A� dass A im neuen Zustand falsch

sein soll�

De�nition �� Anderungsanweisung�� Sei D eine deduktive Datenbank� �Anderungsanweisungen

bez�uglich D werden induktiv wie folgt de�niert�

�� Ein dynamisches Literal A bzgl� D ist eine �einfache� �Anderungsanweisung�

� Wenn P�� Pn �Anderungsanweisungen sind� dann ist fP�� Png eine Menge

von �Anderungsanweisungen�

�� Wenn P eine �Anderungsanweisung und W eine Formel ist� dann ist P � W eine

bedingte �Anderungsanweisung�

Genau wie im Falle von Datenbankregeln werden in dieser Arbeit nur sichere �bedingte

Anweisungen behandelt�

De�nition �� Sichere �Anderungsanweisungen�� Eine �Anderungsanweisung P wird

als sicher bezeichnet� genau dann wenn diese sicher bez�uglich der Leeren Menge von Va�

riablen ist� Sicher bez�uglich einer Variablenmenge X wird wie folgt induktiv de�niert�

�� Ein dynamisches Literal A heisst sicher bez�uglich X� genau dann wenn vars�A � X�

� Eine Menge fP�� Png von �Anderungsanweisungen heisst sicher bez�uglich X� ge�

nau dann wenn jedes Pi �i � �� n sicher bez�uglich X ist�

�� Eine bedingte �Anderungsanweisung P � W heisst sicher bez�uglich X� genau dann

wenn vars��W � X und P sicher bez�uglich X � vars��W ist�

�� Semantik

Eine �Anderungsanweisung wird in zwei Phasen ausgef�uhrt� Die erste Phase berechnet die�Anderungen unter Beachtung der Bedingungen bei bedingten �Anderungsanweisungen� also

Fakten die in Basisrelationen eingef�ugt� oder gel�oscht werden� Die zweite Phase f�ugt oder

entfernt die berechneten �Anderungen in die Datenbank ein�


De�nition �� Auswertung einer �Anderungsanweisung�� Sei D eine deduktive Da�

tenbank und P ein sichere �Anderungsanweisung� Dann ist das Ergebnis der Auswertung

von P bez�uglich D das Paar h�D �P � �D �P i� wobei �D �P und �D �P Mengen von instan�

ziierten Atomen sind und wie folg de�niert werden�

�� Ist P ein dynamisches Literal �A oder �A� dann ist

�D � A �� fAg �D � A ��

�D ��A �� D ��A �� fAg

� Ist P eine Menge von �Anderungsanweisungen fP�� Png� dann ist

�D �fP�� Png ��S

i�� n �D �Pi

�D �fP�� Png ��S

i�� n �D �Pi

�� Ist P eine bedingte �Anderungsanweisung P � �W � dann ist

�D �P� �W �� fA j SD j�W� und A �D �P

�� g�D �P

� �W �� fA j SD j�W� und A �D �P�� g

Die aus der Auswertung der �Anderungsanweisungen gewonnenen Faktenmengen sind nicht

unbedingt disjunkt� �D kann Fakten zur Einf�ugung enthalten� die jedoch bereits in der

Datenbank D enthalten sind� Es kann auch vorkommen� dass �D zu l�oschende Fakten

beinhaltet� die gar nicht gel�oscht werden k�onnen� weil diese Fakten nicht in der Datenbank

D enthalten sind� Bevor nun also die �Anderungen in die Datenbank eingetragen werden�

werden Transitionen ausgef�uhrt� welche obige inkonsistente Zust�ande heraus�ltern� Da�

nach ist die Menge der Einf�ugungen und L�oschungen disjunkt� so dass die Reihenfolge der

Eintragungen in die Datenbank keine Rolle spielt�

De�nition �� Transitionen�� Sei D ein expliziter Datenbankstatus� P eine sichere�Anderungsanweisung� und h�D �P � �D�P i das Ergebnis der Auswertung von P bzgl� Dann

ist die Transition von P auf D �D�P � h��D�P � ��D�P i mit

��D�P �� D �P n �D �P nD��D�P �� D �P n �D �P �D

Schliesslich ist noch die zweite Phase� also die Eintragungen der berechneten L�oschungen

und Einf�ugungen in die Datenbank� zu de�nieren�

KAPITEL �� ANDERUNGSPROPAGIERUNG �

De�nition �� Das Resultat einer �Anderungsanweisung�� Sei D � hF �Ri ein ex�

pliziter Datenbankstatus� P eine sichere �Anderungsanweisung� und �D�P � h��D�P � ��D�P ieine Transition von P auf D� Dann ist das Ergebniss der Anwendung von P auf D der neue

explizite Datenbankstatus D� � hF ��Ri mit

F � �� F n ��D�P � ��D�P �

Gerade im Hinblick auf deduktive Regeln werden �Anderungen in den Basisfakten auch

zu �Anderungen in abgeleiteten Relationen f�uhren� Die �Anderungen der intensionalen und

extensionalen Relationen werden als ��induzierte �Anderungen� bezeichnet�

De�nition �� Induzierte �Anderungen�� Sei D eine strati�zierbare deduktive Daten�

bank� und � eine Transition von D nach D�� Dann induziert � eine Transition �SD�SD�

von SD nach SD�� welches ein Paar h��SD�SD�

��SD�SD�

i einer Mennge von Fakten �Delta�

Mengen� ist� so dass

��SD�SD�

� SD� n SD��SD�SD�

� SD n SD�

Die Fakten in ��SD�SD�

stellen die induzierten Einf�ugungen dar� in ��SD�SD�

sind die indu�

zierten L�oschungen enthalten� Im weiteren Verlauf wird zur Abk�urzung � statt �SD�SD�

verwendet werden�

�� Propagierungsregeln

Die wesentlichen Teile dieses Abschnitts sind aus �Gri�� entnommen� Dieser Abschnitt be�

handelt jedoch nur die Regelerzeugung f�ur ��true updates� �wahre oder echte �Anderungen �

Es werden nur echte �Anderungen in den Basisfakten betrachtet� sowie die daraus resultie�

renden echten induzierten Folge�anderungen abgeleiteter Relationen� Die �Anderungsklassen

wie ��safe� und ��potential updates� sind in �Gri�� nachzulesen�

Unabh�angig von den gegebenen Basisfakten und deren �Anderungen werden die Propagie�

rungsregeln aus den gegebenen deduktiven Regeln erstellt� Die erstellten Propagierungs�

regeln de�nieren die sogenannten ��Delta�Relationen�� Delta�Relationen beschreiben die�Anderungen der Fakten in abgeleiteten Relationen� Die Delta�Mengen beschreiben hinge�

gen die echten �Anderungen in den Basisrelationen�


Die Delta�Relationen stellen die induzierten Unterschiede zwischen dem alten und neuen

Datenbankstatus nach Einbringung der Basisdaten�anderungen dar�

Delta�Relationen�� Angenommen p sei eine abgeleitete Relation mit der Stelligkeit

n� dann bilden die beiden Relationen p� und p� mit jeweils der Stelligkeit n die Delta�

Relationen von p� p�� positives Delta�Literal genannt� stellt die echten Einf�ugungen und

p�� negatives Delta�Literal genannt� die echten L�oschungen von Fakten aus p dar� Aus

den �Anderungen in den Basisrelationen werden Delta�Fakten erzeugt� Diese Delta�Fakten

stossen wiederum induzierte �Anderungen in den abgeleiteten Relationen an�

�� Naive Propagierungsregeln fur echte Anderungen

Die naive Erstellung von Propagierungsregeln f�ur echte �Anderungen kann intuitiv �uber die

Transition vom alten Datenbankstatus in den neuen Datenbankstatus erk�art werden�

Ein Fakt wird als echte Einf�ugung betrachtet� wenn es im neuen� aber nicht im alten Daten�

bankstatus ableitbar ist� Analog wird ein Fakt echt aus der aktuellen Datenbank gel�oscht

werden� wenn es im alten Status ableitbar war� jedoch im jetzigen� neuen Zustand nicht

mehr ableitbar ist� Aus dieser intuitiven Beschreibung k�onnen zwei Propagierungsregeln

f�ur jede abgeleitete Relation erstellt werden�

A� � new A � old �AA� � old A � new �A

old und new sind Meta�Predikate� die auf den alten und neuen Datenbankstatus verweisen�

In Beispielen werden zur besseren Lesbarkeit die Kennzeichnungen f�ur den alten und neuen

Zustand einer Relation als Exponent des Pr�adikatensymbols geschrieben� z�B� pnew�X� Y

Die obigen naiven Propagierungsregeln werden gerade deshalb als ��naiv� bezeichnet� weil

diese die Basisdaten�anderungen nicht n�aher in Betrachtung ziehen� sondern einen Ver�

gleich bzw� Di�erenz zwischen dem vollst�anigen alten und neuen Datenbankstatus ziehen�

Diese zwei naiven Regeln zeigen jedoch die grundlegende Struktur auf� aus welcher jede

Propagierungsregel besteht� die echte �Anderungen beschreibt�

�� Der Ableitungstest auf �� new A bzw� �� old A wird durchgef�uhrt um zu ermitteln�

ob A im neuen� bzw� im alten Datenbankstatus ableitbar ist�

�� Der E�ektivit�atstest auf �� old A bzw� �� new A pr�uft nach� ob das durch den

Ableitungstest gewonnene Fakt nicht im gegens�atzlichen Datenbankstatus alternativ

herleitbar ist�


�� Propagierungsregeln fur echte Anderungen

Wie bereits im vorigen Abschnitt angesprochen� haben die naiven Propagierungsregeln den

gravierenden Nachteil� dass die Delta�Fakten der Basisdaten�anderungen nicht individuell

f�ur die Berechnung der induzierten Folge�anderungen in Betracht gezogen werden� Die im

Folgenden vorgestellten Propagierungsregeln werden jedoch dem Anspruch gerecht� indi�

viduelle �Anderungen in den Basisfakten� sowie in den abgeleiteten Relationen� durch die

deduktiven Regeln zu propagieren�

In dem Kapitel �uber die semi�naive Fixpunktmaterialisierung wurde bereits beschrieben�

dass nur dann neue Fakten f�ur eine Relation hergeleitet werden k�onnen� wenn ein neues

Fakt aus der vorhergehenden Iterationsrunde noch nicht in einem Rump�iteral in Betracht

gezogen worden ist� Diese Idee ist von Nutzen f�ur die di�erenziertere Erstellung von Propa�

gierungsregeln� die individuelle �Anderungen in den Rump�iteralen zu beachten leisten� Die

Betrachtungen f�ur den semi�naiven Fall m�ussen jedoch um die Frage nach L�oschungen in

den Rump�iteralen erweitert werden� F�ur inkrementelle �Anderungspropagierung m�ussen

vier F�alle unterschieden werden� wie �Anderungen in den Rump�iteralen zu �Anderungen in

den Kop�iteralen f�uhren� also wie die Folge�anderungen aussehen�

�� F�ur positive Rump�iterale�

�a Eine Einf�ugung kann eine Einf�ugung induzieren�

�b Eine L�oschung kann eine L�oschung induzieren�

�� F�ur negative Rump�iterale�

�a Eine Einf�ugung kann eine L�oschung induzieren�

�b Eine L�oschung kann eine Einf�ugung induzieren�

Hinsichtlich dieser vier F�alle� wird f�ur jedes Rump�iteral und dessen m�oglichen �Anderungen

� �� eine Propagierungsregel aufgestellt� Dieses bedeutet� dass f�ur jede Regel aus der

urspr�unglichen Regelmenge �n Propagierungsregeln generiert werden� wobei n die Anzahl

der Rump�iterale ist�

De�nition �� Propagierungsregeln f�ur echte �Anderungen�� Sei R eine strati��

zierbare deduktive Regelmenge� Dann bezeichnet �t�R die Menge der Propagierungsregeln

f�ur echte �Anderungen und ist de�niert als�

�� F�ur jede Regel A � L�� Ln R und f�ur jedes Rump�iteral Li�i � �� n

erzeuge die positiven und negativen Propagierungsregeln der Form�


A� � L�i � new�L�� Li�� Li�� Ln � old �A mit Li � L

A� � L�i � new�L�� Li�� Li�� Ln � old �A mit Li � �L

A� � L�i � old�L�� Li�� Li�� Ln � new �A mit Li � L

A� � L�i � old�L�� Li�� Li�� Ln � new �A mit Li � �L

� Keine anderen Regeln sind in �t�R Im Gegensatz zu den naiven Propagierungsregeln besteht der Ableitungstest jetzt nicht

mehr aus der abzuleitenden Relation selber� sondern aus jedem Rump�iteral� welches diese

Relation de�niert plus ein Delta�Literal� dessen abgeleitete Delta�Relation einen m�oglichen

Ableitungspfad f�ur �Anderungen enth�alt� Der E�ektivit�atstest bleibt jedoch so bestehen�

Dieser verweist auf den gegenteiligen Datenbankzustand der betrachteten Relation�

Beispiel� Gegeben sei folgende strati�zierbare deduktive Regelmenge RBsp� wobei p� e Ba�

sisrelationen sind�

p�X� Y � s�X� Y

p�X� Y � p�X�Z � p�Z� Y ��e�Y

Aus den obigen� urspr�unglichen Regeln� werden nun die Propagierungsregeln erstellt�

p��X� Y � s��X� Y ��pold�X� Y p��X� Y � s��X� Y ��pnew�X� Y

p��X� Y � p��X�Z � pnew�Z� Y ��enew�Y ��pold�X� Y p��X� Y � p��Z� Y � pnew�X�Z ��enew�Y ��pold�X� Y p��X� Y � e��Y � pnew�X�Z � pnew�Z� Y ��pold�X� Y

p��X� Y � p��X�Z � pold�Z� Y ��eold�Y ��pnew�X� Y p��X� Y � p��Z� Y � pold�X�Z ��eold�Y ��pnew�X� Y p��X� Y � e��Y � pold�X�Z � pold�Z� Y ��pnew�X� Y

Dieses Beispiel zeigt� dass jede Propagierungsregel ein Delta�Literal enth�alt� welches die

Auswertung auf die �Anderungen dieses Rump�iterales beschr�ankt� Der Vorlteil dieser

Beschr�ankung auf die Auswertung relevanter �Anderungen wird jedoch im Fall der Bottom�

Up Materializierung relativiert werden� denn f�ur die korrekte Materialisierung z�B� der

p�Relation� muss sowohl der old� als auch der new�Status der Relation hergeleitet werden�


Im Abschnitt �uber Magic�Updates wird eine Technik vorgestellt werden� die dieses Manko

zu umgehen versucht� indem die Propagierungsregeln mit Techniken der Top�Down Aus�

wertung kombiniert werden�

�� Transitionsregeln

Die im vorigen Abschnitt behandelten Propagierungsregeln f�ur echt �Anderungen weisen

den Nachteil auf� dass f�ur die Herleitung der Folge�anderungen sowohl der alte als auch der

neue Datenbankstatus der abgeleiteten Relationen notwendig ist� Dies hat den praktischen

Nachteil� dass mindestans zwei Datenbankzust�ande in der Datenbank vorgehalten werden�

f�ur die jeweils Deduktionsmechanismen bereit gestellt werden m�ussen�

Die Fragestellung� die dieser Abschnitt zu untersuchen versucht� ist die Frage nach der

M�oglichkeit� ob die Datenbankzust�ande� bzw� die Zust�ande von Relationen voneinander

abgeleitet werden k�onnen� also ��Kann der old�Status aus dem new�Status heraus abgeleitet

werden�� Oder vice versa�

Der Vorteil einer solchen ��Statussimulation� ist� dass das Datenbanksystem keine zwei

Mechanismen f�ur das Arbeiten auf zwei verschiedenen Datenbankzust�anden bereitstellen

muss� Der aktuelle Status reicht dann vollkommen aus� Die deduktiven Regeln� welche

diese Simulation von Zust�anden leisten� werden Transitionsregeln genannt�

Die Entscheidung welcher Zustand simuliert wird� ist eine Designfrage und h�angt von den

gegebenen deduktiven Regeln und Fakten ab�

Die Simulation des old�Status wird als ��optimistischer� Ansatz bezeichnet� Der optimi�

stische Ansatz tr�agt die gew�unschten Basisdaten�anderungen direkt in die Datenbank ein

und geht davon aus� dass die danach berechneten Folg�anderungen keine Restriktionen des

Datenbanksystems� wie z�B� Integrit�atsbedingungen verletzen� Im Falle von Verletzungen

m�ussen diese eingetragenen �Anderungen wieder �kostenintensiv ��zur�uckgerechnet� wer�

den�

Die Simulation des new�Status wird als ��pessimistischer� Ansatz bezeichnet� Der pessimi�

stische Ansatz tr�agt die gew�unschten Basisdaten�adnerungen nicht direkt in die Datenbank

ein� sondern geht davon aus� dass die danach berechneten Folg�anderungen Restriktionen in

Form von Integrit�atsbedingungen verletzen werden� Die �Anderungen der Basisdaten und

abgeleiteten Relationen werden erst nach erfolgreicher �Uberpr�ufung von Verletzungen in

die Datenbank eingetragen� Im Falle von Verletzungen werden die berechneten �Anderungen

�kosteng�unstig verworfen�

Die Transitionsregeln werden zun�achst in ihrer ��naiven� Form vorgestellt�


�� Naive Transitionsregeln

Zu Beginn wird als Motivation der new�Status simuliert werden� Der neue Zustand wird

aus dem alten Status inklusive der �Anderungen in den Basisfakten berechnet� Aus dem

Abschnitt �uber Datenbanktransitionen ist bekannt� dass der neue Datenbankstatus aus

dem alten Zustand unter Ber�ucksichtigung der �Anderungen �t hergeleitet werden kann�

SD� � �SD n��t ��

t �

Diese Gleichung als �Aquivalenz auf Faktenebene ausgedr�uckt�

new A�� old A � ��A� � A�

Die Transitionsregeln f�ur die new�Simulation der Basisrelationen aus dem eben gestellten

Beispiel sehen dann wie folgt aus�

s�X� Y new � s�X� Y old��s�X� Y �s�X� Y new � s�X� Y �

Diese beiden Transitionsregeln bez�uglich einer urpr�unglichen Basisrelation nennt man auch

inkrementelle Transitionsregeln� Der neue Zustand s�X� Y new wird aus dem alten Zustand

s�X� Y old gebildet� indem die zu l�oschenden Fakten s�X� Y � vom alten Status abgezogen

werden� Zus�atzlich sind �uber die Vereinigung im neuen Zustand die einzuf�ugenden Fakten

aus s�X� Y � enthalten�

Durch die Annahmen� dass der neue Zustand der Datenbank simuliert werden soll� und dass

der aktuelle materialisierte Zustand der Datenbank der alte Zustand ist� wird im Folgenden

die Kennzeichnungen der alten Zust�ande in den Pr�adikatensymbolen weggelassen�

s�X� Y new � s�X� Y ��s�X� Y �s�X� Y new � s�X� Y �

e�X new � e�X ��e�X �e�X new � e�X �

Die neuen Zust�ande der abgeleiteten Relationen werden im naiven Ansatz �uber die naiven

Transitionsregeln der Basisrelationen abgeleitet� Die Beispielregeln nehmen nach dieser

Erweiterung folgende Form an�


p��X� Y � s��X� Y ��p�X� Y p��X� Y � s��X� Y ��pnew�X� Y

p��X� Y � p��X�Z � pnew�Z� Y ��enew�Y ��p�X� Y p��X� Y � p��Z� Y � pnew�X�Z ��enew�Y ��p�X� Y p��X� Y � e��Y � pnew�X�Z � pnew�Z� Y ��p�X� Y

p��X� Y � p��X�Z � p�Z� Y ��e�Y ��pnew�X� Y p��X� Y � p��Z� Y � p�X�Z ��e�Y ��pnew�X� Y p��X� Y � e��Y � p�X�Z � p�Z� Y ��pnew�X� Y

pnew�X� Y � snew�X� Y

pnew�X� Y � pnew�X�Z � pnew�Z� Y ��enew�Y

Diese transformierten Propagierungsregelmenge ist nun in der Lage bei gegebenen Basis�

daten�anderungen in s und e� die Folge�anderungen der abeleiteten Relationen mittels eines

inkrementellen Fixpunktverfahrens� z�B� T �R�F zu berechnen� Zu jeder gegebenen strati��

zierbaren Regelmenge ist die darauss resultiernde Menge der Propagierngsregeln f�ur echte�Anderungen inklusive der erstellten naiven Transitionsregeln immer strati�zierbar� Die

Erstellung der naiven Transitionsregeln ist formal de�niert per�

De�nition �� Naive Transitionsregeln�� Sei R eine strati�zierbare deduktive Regel�

menge� Die Menge der naiven Transitionsregeln f�ur die Simulation des neuen Zustandes

bez�uglich der Regelmenge R ist bezeichnet mit newn �R und wird wie folgt de�niert�

�� F�ur jede n�stellige Basisrelation p pred�R sind in newn �R zwei Transitionsregelnder Form�

Anew � A��A� �inkrementelle Transitionsregeln�

Anew � A�

enthalten� mit A � p�x�� xn �

� F�ur jede abgeleitete Regel A � L�� Ln ist in newn �R eine Transitionsregel der

Form�

Anew � Lnew� � � � � � Lnew

n �naive Transitionsregel�


enthalten�

�� Keine anderen Regeln sind newn �R �Der Vorteil dieser naiven Transitionsregeln ist� dass die resultiernde Regelmenge immer

strati�zierbar ist� Ein Nachteil ist jedoch die Tatsache� dass f�ur jede abgeleitete Relation

eine entsprechende Regel erstellt werden muss� die den neuen Status vollst�andig materia�

lisiert� Diese entsprechende Transitionsregel wird aus der urspr�unglichen Regel erscha�en�

in dem die alte Regel �ubernommen wird und die vorkommenden Kopf� und Rump�iterale

mit ��new� als Exponenten markiert bzw� umbenannt werden�

�� Inkrementelle Transitionsregeln fur echt Anderungen

Unter der Betrachtung des E�ektivit�atstests in Propagierungsregeln� die echte L�oschungen

berechnen� stellt man fest� dass unter Umst�anden eine hohe Anzahl von Transitionsregeln

f�ur die Herleitung des neuen Zustandes kreiert werden m�ussen� denn eine abgeleitete Rela�

tion kann durch mehrere Regeln de�niert werden� deren Ableitungsm�oglichkeiten f�ur den

neuen Status in Betracht gezogen werden m�ussen� Im Raum steht folglich die Frage� ob

insbesondere f�ur den E�ektivit�atstest inkrementelle Transitionsregeln verwendet werden

d�urfen� welche den Vorteil haben direkt auf die �Anderungen der Reltationen zugreifen zu

k�onnen ohne den neuen Status �uber Ableitungen zu den Basisdaten�anderungen herleiten

zu m�ussen� Dazu die transformierten Beispielregeln�

p��X� Y � s��X� Y ��p�X� Y p��X� Y � s��X� Y ��pnew�X� Y

p��X� Y � p��X�Z � pnew�Z� Y ��enew�Y ��p�X� Y p��X� Y � p��Z� Y � pnew�X�Z ��enew�Y ��p�X� Y p��X� Y � e��Y � pnew�X�Z � pnew�Z� Y ��p�X� Y


pnew�X� Y � p�X� Y ��p��X� Y pnew�X� Y � p��Y� Y

In diesem Beispiel ist zu erkennen� dass die alleinige Verwendung von inkrementellen Tran�

sitionsregeln zu resultierenden nicht strati�zierbaren Regeln f�uhrt�


p��X� Y �� pnew�X� Y pnew�X� Y �� p��X� Y

Die Relation p��X� Y ist �uber den negativ referenzierten E�ektivit�atstest �pnew�X� Y und der inkrementellen Transitionsregel� von sich selbst negativ abh�angig�

Die Verwendung von naiven Transitionsregeln f�ur den E�ektivit�atstest bringt nur f�ur den

Fall einer hierarchischen Datenbank Abhilfe� Liegt zum Beispiel eine selbst rekursive Regel�

wie im Beispiel die p�Relation vor� so w�urden die new�Literale in der naiven Transitionsre�

gel per inkrementeller Transition simuliert werden� und das Strati�kationsproblem kommt

dann eine Stufe tiefer wieder hervor� Auszug aus dem Beisiel�

p��X� Y � p��X�Z � p�Z� Y ��e�Y ��pneweff�X� Y p��X� Y � p��Z� Y � p�X�Z ��e�Y ��pneweff�X� Y p��X� Y � e��Y � p�X�Z � p�Z� Y ��pneweff�X� Y

pneweff�X� Y � snew�X� Y

pneweff�X� Y � pnew�X�Z � pnew�Z� Y ��enew�Y

pnew�X� Y � p�X� Y ��p��X� Y pnew�X� Y � p��Y� Y

Diese Erkenntnis bedeutet� dass Relationen� die im Abh�angigkeitsgraphen der original Re�

gelmenge einen Zyklus ohne Negation bilden� via naiver Transitionsregeln simuliert werden�

alle anderen Relationen werden inkrementell simuliert�

Ein hilfreiches Instrument f�ur diese di�erenzierte Erstellung von Transitionsregeln ist die

maximale Strati�kation� bzw� die der starken Zusammenhangskomponenten� Dies f�uhrt

zu einer weiteren De�nition�

De�nition �� Inkrementelle Transitionsregeln f�ur echte �Anderungen�� Sei Reine strati�zierbare deduktive Regelmenge und � die maximale Strati�kation auf R� Dann

bezeichnet newl �Ri die Menge der Transitionsregeln f�ur echte �Anderungen bzgl� der Si�

mulation des neuen Zustandes von Ri und ist de�niert als�

�� F�ur jede n�stellige Basisrelation p pred�Ri sind in newl �Ri zwei Transitionsregeln

der Form�

Anew � A��A� �inkrementelle Transitionsregeln�

Anew � A�


enthalten� mit A � p�x�� xn �

� F�ur jede abgeleitete Regel A� L�� Ln Ri ist in newl �Ri eine Transitionsregel

der Form�

Anew � Lnew� � � � � � Lnew

n �naive Transitionsregel�

enthalten�

�� Keine anderen Regeln sind newl �Ri �

Diese De�nition leistet intuitiv geschildert nichts anderes als die Erzeugung von naiven

Transitionsregeln pro Stratum nach der De�nition �� Die abgeleiteten Relationen in

einem Stratum werden naiv betrachtet� wohin gegen die Relationen der unteren Schichten

als Basisrelationen angesehen werden und per inkrementellen Transitionsregeln simuliert

werden�

Die Autorin in �Gri�� zeigt an dieser Stelle eine andere De�nition der ��inkrementellen

Transitionsregeln f�ur echte �Anderungen auf�� Sie untersucht den Abh�angigkeitsgraphen

einer gegebenen Regelmenge auf wechselseitige Abh�angigkeiten von Relationen� F�ur die�

se Abh�angigkeiten erstellt sie ��indirekte� Transitionsregeln und markiert diese mit newi

�naive Transitionsregeln � Diese indirekten Transitionsregeln werden den E�ektivit�atstests

der negativen Propagierungsregeln zugewiesen� Des weiteren erstellt die Autorin f�ur je�

de Relation der Regelmenge ��direkte� Transitionsregeln �inkrementelle Transitionsregeln

und bezeichnet diese mit newd�

Die beiden Verfahren leisten das selbe� Sie verhindern das Strati�kationsproblem der di�

rekten Anwendung von inkrementellen Transitionsregeln� Die hier angegebene De�nition

vermeidet die explizite Unterscheidung zwischen direkten �inkrementellen und indirekten

�naiven Transitionsregeln indem diese die Strata der Ursprungsregelmenge naiv transfor�

miert�

�� Strukturierte �Anderungspropagierung

Der vorige Abschnitt �uber Transitionsregeln hat gezeigt� dass die alleinige Verwendung von

inkrementellen Transitionsregeln zu Strati�zierungsproblemen f�uhrt� Insbesondere wurden

deshalb f�ur die E�ektivit�atstests von negativen Propagierungsregeln� dessen Test auf dem

KAPITEL �� ANDERUNGSPROPAGIERUNG �

neuen Zustand durchgef�uhrt wird� naive Transitionsregeln eingef�uhrt� Diese Transitions�

regeln leiten den vollst�andigen Zustand der zu betrachtenden und weiterer abgeleiteter

Relationen vollst�andig her� Ziel von �Anderungspropagierung ist jedoch die beschr�ankte

Materialisierung von Fakten� welche gerade notwendig sind� die berechneten �Anderungen

durch die Regelmenge zu verbreiten�

Ziel der ��strukturierten �Anderungspropagierung� ist es zum einen die new�Simulation des

E�ektivit�atstest bei negativen Propagierungsregeln so zu beschr�anken� dass gerade nur die

relevanten Fakten bzgl� der �Anderung abgeleitet werden� Zum Anderen wird dieses Ziel

auch f�ur die Auswertung der new�Literale im Ableitbarkeitstest von positiven Propagie�

rungsregeln beansprucht�

Die Idee intuitiv erkl�art�

Im Falle von negativen Propagierungsregeln soll die Auswertung des E�ektivit�atstests

auf ein Minimum beschr�ankt werden� Die Literale im Residuum inklusive des Delta�

Literals mit den �Anderungen ergeben zusammen den Ableitungstest des m�oglicherweise

zu l�oschenden Fakts� Der E�ektivit�atstest ��entscheidet� dann� ob die Folge�anderung eine

echte �Anderung darstellt� Die Entscheidung wird gefallen� indem der neue Zustand der

Relation hergeleitet wird und dann getestet wird� ob die zu l�oschenden Fakten im neuen

Status der Relation vorkommen� oder nicht� Kommen diese dort nicht vor� so ist die Fol�

ge�anderung eine wahre �Anderung�

p��X� Y � �z �Folge�anderung

�Ableitungstestz ��

p��X�Z � �z �Delta�Literal

� p�Z� Y ��e�Y � �z �Residuum

�

Effektivit�atstestz �� pnew�X� Y

Die Idee besteht im wesentlichen darin� dass die aus dem Ableitungstest gewonnenen Delta�

Fakten f�ur eine ��Anfrage� an den E�ektivit�atstest genutzt werden� Als Ergebnis dieser

Anfrage ergibt sich� ob die anzufragenden Fakten im neuen Zustand der Relation enthalten

sind� Dieses Verfahren gewinnt dann einen Vorteil� wenn Techniken der Anfrageauswer�

tung angewandt werden� Der Vorteil von Anfrageauswertungstechniken besteht darin� dass

nur relevante Relationen mit relevanten Fakten abgeleitet werden� Im Falle des E�ekti�

vit�atstests sollte dieser nicht vollst�andig hergeleitet werden� sondern nur bez�uglich der

gestellten Anfrage�

p��X� Y � �z �Folge�anderung

�Anfragez ��

p��X�Z � p�Z� Y ��e�Y �Effektivit�atstestz �� pnew�X� Y


�� Die Magic�Set Methode

Die einfachste Methode zu einer gegebenen Anfrage die entsprechende Antwort zu �nden�

ist zun�achst die vollst�andige Datenbank zu materialisieren� um dann nachzuschauen wie

die Bindungen der Anfrage mit denen aus der Faktenbasis �ubereinstimmen�

Eine andere geschicktere M�oglichligkeit ist die Top�Down Anfrageexpandierung mittels Re�

solution� An einem Beispiel wird diese im Allgemeinen wie folgt beschrieben�

Sei p�� Y � die Anfrage� wobei Y eine Variable ist� Sei p�X� Y � s�X� Y � q�Y eine gege�

bene Regel� Bilde aus der Anfrage p�� Y � die Substitution � � fX � �g� Uni�ziere � mitden Regelk�opfen� F�ur jeden passenden Kopf gehe in die Literale des Rumpfes herein� uni��

zier diese und bilde f�ur abgeleitete Rump�iterale eine entsprechende Unteranfrage an deren

Regeln mit der bisher gewonnenen Substitution �� Dieses wird bis zu den Basisrelationen

durchgef�uhrt� Die Ergebnissubstitutionen werde den �ubergeordneten Stufen tur�uckgegeben

und weiter expandiert� bis die Top�Anfrage wieder erricht ist� Die Antworten bilden sich

aus den zur�uckgegebenen Ergebnissubstitutionen� z�B� �n � fX � �� Y � �g� Die Ant�wort lautet dann p�� Zur Vermeidung von Problemen der Terminierung bei rekursiven

Regeln werden interne Anfrage� und Antwortprotokollierungsrelationen verwendet� Dieses

kurz beschriebene Verfahren ist unter dem K�urzel ��QSQ� �Quer� SubQuery� bekannt ge�

worden�

Eine der m�oglichen Methoden dieses Verfahren in Form von Regeln auszudr�ucken ist

die sogenannte ��Magic�Set� Methode �BMSU�� Die Magic�Set Methode simuliert eine

Top�Down Anfrageexpandierung durch eine Bottom�Up Auswertung der Magic�Set�Regeln

per geeignetem Fixpunktverfahren� Der Vorteil dieses Vorgehens ist� dass keine eigene

Top�Down Inferenztechnik implementiert werden muss� sondern auf Bottom�Up Techniken

zur�uckgegri�en werden kann�

Die grundlegende Idee dieser Methode ist es die Anfrage� und Ergebnissubstitutionen zu

simulieren� Die Magic�Set Methode arbeitet in zwei Schritten� Die erste Phase geht von

der urspr�unglichen Regelmenge aus� Die Literale der Regeln werden entsprechend der

Top�Down Expandierung einer konkreten Anfrage mit den Bindungen ihrer Variablen im

Exponenten markiert� ��b� steht f�ur gebunden �bound und ��f� steht f�ur frei �free � Die�

se Markierung ��adornment� entspricht der Anfragesubstitutionsbelegung zu Beginn der

Auswertung dieses Literals unter Ber�ucksichtigung der gew�ahlten SIP�Strategie �Sideway

Information Passing � Die SIPS legt die Auswertungsreihenfolge der Rump�iterale fest�


Gew�ohnlich werden Rump�iterale von ��links nach rechts� ausgewertet�

Beispiel� Seien e� s Basisrelationen� p ist abgeleitet� p��Y � ist die Anfrage�

p�X� Y � s�X� Y

p�X� Y � p�X�Z � p�Z� Y ��e�Y

Mit der Anfrage und der ��links�rechts� Auswertung wird daraus die Adornment�Regelmenge

Rad�

pbf �X� Y � s�X� Y

pbf �X� Y � pbf�X�Z � pbb�Z� Y ��e�Y pbb�X� Y � pbf�X�Z � pbb�Z� Y ��e�Y

Die zweite Phase transformiert die Adornment�RegelmengeRad in die Magic�Set Regelmen�

ge Rms� In diesem Schritt werden die Adornment�Regeln um ein Anfrage�Literal mit dem

Pr�a�x ��m � erweitert� Die Bindungen des Anfrage�Literals entsprechen den Bindungen

aus dem Kopf�Literal� Das Anfrage�Literal simuliert die Variblenbelegungen der Anfrage�

substitution� Des weiteren werden Regeln f�ur die Anfrage�Relationen aus den Adornment�

Regeln produziert� Der letzte Schritt besteht aus der Einf�ugung des ��Magic�Fakts� in die

zugeh�orige Anfragerelation� Das Magic�Fakt ist die als Fakt kodierte Top�Anfrage� z�B�

m pbf ��

De�nition �� Magic�Set Transformation�� Sei D � hF �Ri eine positive deduk�

tive Datenbank� Q eine Anfrage an D� Rad die Adornment�Regelmenge von R bzgl� der

Anfrage Q� Dann erzeugt die Magic�Set Transformation die neue Datenbank Dms � hF �fm Qg�Rms und ist de�niert als�

�� F�ur jede deduktive Regel A� L�� Ln Rad� ist eine Regel der Form�

A� m A�L�� Ln

in Rms enthalten�

� F�ur jede deduktive Regel A� L�� Ln Rad und jedem abgeleitetem Rump�iteral

Li �� i � n � ist eine Regel der Form�


m Li � m A�L�� Li��

in Rms enthalten�

�� Keine weiteren Regeln sind in Rms�

Beispiel� Aus der Adornment�Regelmenge Rad�

pbf �X� Y � s�X� Y

pbf �X� Y � pbf�X�Z � pbb�Z� Y ��e�Y pbb�X� Y � pbf�X�Z � pbb�Z� Y ��e�Y

wird nach der Magic�Set Transformation die Regelmenge Rms�

pbf �X� Y � m pbf �X � s�X� Y

pbf �X� Y � m pbf �X � pbf�X�Z � pbb�Z� Y ��e�Y pbb�X� Y � m pbb�X� Y � pbf�X�Z � pbb�Z� Y ��e�Y

m pbf�X � m pbf �X

m pbf�X � m pbb�X� Y

m pbb�X� Y � m pbf�X � pbf�X�Z

m pbb�X� Y � m pbb�X� Y � pbf �X�Z

Ist die urspr�ungliche Regelmenge strati�zierbar� was a priori angenommen wird� so kann

es durchaus vorkommen� dass die Magic�Set transformierte Regelmenge nicht mehr strati�

�zierbar ist� Dies ist zum Beispiel der Fall� wenn die e Relation aus dem Beispiel abgeleitet

ist� Eine der Anfragen an e�Y wird gebildet durch

m eb�X � m pbb�X� Y � pbf�X�Z � pbb�Z� Y

Die Auswertung von pbb�X� Y nimmt dann negativen Bezug �uber �e�Y auf sich selbst��KP�� haben in ihrem Aufsatz bewiesen� dass wenn aus einer strati�zierbaren Regelmenge

nach der Magic�Set Transformation ein nicht strati�zierbare Regelmenge resultiert� die

Bedeutung zwei�wertig ist� Um die Auswertung mittels CFP oder AFPI zu vermeiden�

wurde f�ur diesen speziellen Fall der Magic�Set Transformierten� der sogenannte ��schwache

Fixpunktoperator� �Tweak von den beiden Autoren entwickelt� Auf Tweak wird an dieser

Stelle nicht genauer eingegangen�


�� Magic Updates

Die Grundlagen und haupts�achlichen Konzepte der ��Magic Updates� sind aus �Gri��

entnommen�

Die wesentliche Idee von Magic Updates ist es� nicht den simulierten Zustand einer Da�

tenbank �new vollst�andig zu materialisieren� sondern nur die relevanten Fakten des neuen

Zustandes herzuleiten� die zur Herleitung der Folge�anderung notwendig sind� Zu diesem

Zwecke werden die Propagierungsregeln um die Technik der Anfrageauswertung erweitert�

Um verschiedene Inferenzmethoden zu vermeiden� Top�Down f�ur die Anfrageauswertung

und Bottom�Up f�ur die Propagierungsregeln� wird der Top�Down Teil mittels der Magic�Set

Methode per Bottom�Up simuliert�

Das folgende Beispiel� von den naiven Transitionsregeln her bekannt� beschr�ankt sich we�

gen des Umfangs auf die Betrachtung von negativen Propagierungsregeln� Im Bereich der

negativen Propagierungsregeln werden Anfragen an den E�ektivit�atstest gestellt� welcher

im neuen Zustand berechnet wird� Die initiale Anfrage m pnew bb�X� Y an den E�ekti�

vit�atstest wird aus den Ableitungstests der entsprechenden Propagierungsregeln gebildet�

Die Bedeutung der Anfrage an den E�ektivit�atstest ist im wesentlichem herauszu�nden� ob

die zu ermittelnde Folge�anderung im neuen Zustand eine alternative Ableitungsm�oglichkeit

besitzt� Die Magic�Set Anfrageauswertung zieht sich durch die Transitionsregeln des new�

Status� die f�ur abgeleitete Relationen naiv sind� insbesondere f�ur den E�ektivit�atstest�

bishin zu den Basisrelationen� dessen Zustand inkrementell simuliert wird�

Negative Propagierungsregeln als Beispiel�

p��X� Y � s��X� Y ��pnew�X� Y


pnew�X� Y � m pnew bb�X� Y � snew�X� Y

pnew�X� Y � m pnew bb�X� Y � pnew�X�Z � pnew�Z� Y ��enew�Y

m pnew bb�X� Y � s��X� Y

m pnew bb�X� Y � p��X�Z � p�Z� Y ��e�Y m pnew bb�X� Y � p��Z� Y � p�X�Z ��e�Y


m pnew bb�X� Y � e��Y � p�X�Z � p�Z� Y

s�X� Y new � m snew bb�X� Y � s�X� Y ��s�X� Y �s�X� Y new � m snew bb�X� Y � s�X� Y �

m snew bb�X� Y � m pnew bb�X� Y

e�X new � m enew b�X � e�X ��e�X �e�X new � m enew b�X � e�X �

m enew b�X � m pnew bb�X� Y � pnew�X�Z � pnew�Z� Y

In diesem Beispiel ist ein generelles Problem von Magic Updates deutlich zu erkennen�

F�ur die urspr�ungliche Regelmenge wurde die Strati�zierbarkeit vorausgesetzt� Die resul�

tierenden Propagierungsregeln wurden durch den Einsatz von naiven und inkrementellen

Transitionsregeln zur Simulation des neuen Zustandes� strati�zierbar gehalten� Mit der

Kombination der Magic�Set Methode tritt jedoch wieder ein Strati�kationsproblem auf�

Dieses Problem taucht genau dann auf� wenn in der Ursprungsregelmenge Regeln enthal�

ten sind� welche direkt oder indirekt von sich selbst �mehrfach abh�angig sind�

Im aufgef�uhrten Beispiel ist es die p�Relation� Aufgrund der Eigenschaften zur Erzeugung

von Propagierungsregeln werden diese Propagierungsregeln auch direkt von sich selbst �uber

die Delta�Literale �p��X�Z und p��Z� Y abh�angig� Die initiale Anfragen an den nega�

tiv referenzierten E�ektivit�atstest werden aus den Ableitunstests der Propagierngsregeln

erstellt z�B� m pnew bb�X� Y � p��X�Z � p�Z� Y ��e�Y � In dieser Regel ist das Delta�Literal p��X�Z enthalten� Diese Anfrageliterale werden in den naiven Transitionsregeln

pnew�X� Y referenziert� Betrachtet man sich den Abh�angigkeitsgraphen dieser Propagie�

rungsregelmenge� so stellt man fest� dass die Folge�anderung p��X� Y �uber den negativ

referenzierten E�ektivit�atstest �pnew�X� Y und der darin vorkommenden initialen Anfra�gerelation m pnew bb�X� Y � negativ von sich selbst abh�angig ist�

Als m�ogliche L�osung dieses Problems stellt die Autorin in �Gri�� die Verwendung des

alternierenden Fixpunktverfahrens dar und diskutiert zum einen die ausschliessliche Ver�

wendung von inkremtellen Transitionsregeln und zum anderen die Verwendung der naiven

Transitionsregeln�

Im Kontext dieser Diplomarbeit werden Techniken vorgestellt und diskutiert� welche die

Benutzung des AFPI in dieser Problemstellung vermeiden�

Kapitel �

Implementierung des AFPI mittels

Updates

In diesem Kapitel wird untersucht in wie weit die Erweiterung des Doubled Program Ansat�

zes um die eben vorgestellte �Anderungspropagierung Vorteile bringt� Im ersten Abschnitt

wird die Idee aufgzeigt� welche �Anderungsszenarien im DPA enthalten sind� In den weite�

ren Abschnitten werden die besonderen Eigenheiten der Propagierungsregeln und Transi�

tionsregeln aufgezeigt� die der DPA mit sich bringt� In den letzten Abschnitten wird ein

Algorithmus sowie ein konkretes Beispiel gezeigt� welche die Eigenarten und potenziellen

Vorteile dieses Verfahrens aufzeigt�

�� Grundlegende Idee

In Kapitel � wurde die Implementierung des alternierenden Fixpunktverfahrens mittels

des Doubled Program Ansatzes n�aher erkl�art� Die jeweiligen Regelmengen der beiden un�

terschiedlichen Regelmengen sind immer strati�zierbar� Der DPA berechnet abwechselnd

den kleinsten Fixpunkte der nicht de�nitiv falschen Fakten �DF und den kleinsten Fix�

punkt der de�nitiv wahren Fakten �DT � Als implizite virtuelle negative Referenzmenge

zur Auswertung von negativen Literalen wird jeweils das Ergenbnis der vorhergehenden

S�aulenberechnung genommen� Diese negative Referenzmenge wird als Basisrelation ange�

sehen� Es wurde festgestellt� dass die Menge der NDF Fakten monoton abnimmt und die

Menge der DT Fakten monoton anw�achst�

Indem die NDF Menge kleiner wird� wird die implizite Referenzmenge DF gr�osser� Somit

k�onnen mehr negative Literale f�ur die DT Menge als wahr hergeleitet werden� die Menge

��

KAPITEL �� IMPLEMENTIERUNG DES AFPI MITTELS UPDATES ��

der DT Fakten steigt�

Indem die DT Menge gr�osser wird� wird die implizite Referenzmenge NDT kleiner� Folg�

lich k�onnen weniger negative Literale f�ur die NDF Menge als wahr hergeleitet werden� die

Menge der NDF Fakten verringert sich�

Abbildung �� S�aulendiagramm des Doubled Program Ansatzes

Intuitiv� Die Di�erenz zwischen zwei DT S�aulen �DTi�DTi�� also der Hinzugewinn von

Fakten �Abnahme von negativen Referenzfakten � bewirkt� dass NDFi�� im Vergleich zu

NDFi kleiner wird�

Im Gegensatz dazu bewirkt die Di�erenz zwischen zwei NDF S�aulen �NDFi �NDFi��

also die Abnahme von Fakten �Hinzugewinn von negativen Referenzfakten � dass die DTi��

S�aule im Vergleich zur DTi S�aule zunimmt�

Ziel der DPA Implementierung mit Verwendung von �Anderungspropagierung ist es� die

Di�erenzen zwischen zwei gleichartigen S�aulen f�ur die �anderungsgetriebene Inferenz der

andersartigen n�achsten S�aule zu nutzen� Redundante Faktenherleitungen sollen in den

Fixpunktprozessen damit vermieden werden�

Die Di�erenz DTi�DTi�� wird als Basisdaten�anderung der impliziten negativen Referenz�

menge f�ur die NDFi�� S�aule herangezogen� respektive wird die Di�erenz NDFi�NDFi��

als Basisdaten�anderung f�ur die Inferenz der DTi�� S�aule benutzt�

Die anf�anglichen Basisdaten�anderungen� respektive Di�erenzen� werden wie folgt motiviert�

Der DPA beginnt mit der Annahme� dass die erste DT Menge leer ist �DT� � � und be�

rechnet damit NDF�� Mit NDF�� als eine Menge der Basisfaktenrelationen� wird DT�

berechnet� was bisher keine Neuerung darstellt� Die Di�erenz zwichen DT� und DT� ist

aufgrund der Anfangsannahme DT�� somit ist DT� die erste Delta�Menge ��DT��

�DT�


wird als Basisdaten�anderung angesehen und wird f�ur die Berechnung der Folge�anderungen

��NDF� genommen� Im n�achsten Schritt wird ��NDF� als Basisdaten�anderung ange�

sehen� usw�

Die Ermittlung der initialen Delta�Fakten �uber die Di�erenz zwischen den ersten beiden

NDF S�aulen ist im Rahemen einer Implementierung nicht praktikabel und w�urde dem

DPA widersprechen� denn f�ur die erste NDF S�aule wird die Herbrandbasis HD angenom�

men�

Die eben dargelegten Gedanken stellen noch nicht den vollst�andigen Algorithmus dar� son�

dern sollten die Betrachtungen der Di�erenzen als Basisdaten�anderungen n�aherbringen� In

den Folgenden Betrachtungen wird ein zugeh�origer Algorithmus kontinuierlich entwickelt�

Insbesondere fehlen noch die Betrachtungen zu den Propagierungsregeln� Transitionsregeln�

sowie zu der Frage nach den Einbringungen der ��virutellen� Basisdaten�anderungen�

�� Propagierungsregeln f�ur NDFRegeln

Bereits mehrfach wurde erw�ahnt� dass die Menge der positiven NDF Fakten monoton

abnimmt� Dies bedeutet� dass in Bezug auf NDFi�� Fakten gel�oscht werden� L�oschung

bedeutet in diesem Fall� dass die Fakten in die implizite DF Menge wandern und somit

de�nitiv falsch werden�

Die Idee besteht darin� dass zun�achst eine gr�osst m�ogliche NDF Faktenmenge unter

DT� � � berechnet wird� Diese NDF Menge wird dann nach ensprechenden Fixpunkt�

berechnungen um die ��NDFi abgebaut� Die Tatsache� dass im Falle der NDF�Menge

nur ��L�oschungen� vorkommen� bringt den Vorteil� dass f�ur die NDF�Regeln RNDF nur

negative Propagierungsregeln aufgestellt werden m�ussen� Die Klasse der Propagierungsre�

geln� die hier betrachtet wird� sind die bereits aus dem vorigen Kapitel eingef�uhrten echten�Anderungen�

Beispiel aus dem CFP und AFPI Abschnitt�

RNDF �� fndf even�X � succ�X� Y ��dt even�Y g

Die in diesem Fall zugeh�orige negative Propagierungsregel ist�

R�NDF �� fndf even��X � succ�X� Y � dt even��Y ��ndf evennew�X g


Im Vorgri� auf die zu f�uhrende Diskussion �uber die Statussimulation� die entsprechende

naive Transitionsregel�

RNDFnew �� fndf evennew�X � succ�X� Y ��dt even�Y ��dt even��Y g

F�ur den Inferenzprozess liegen die alten Zust�ande von succ�X� Y und ndf even�X vor�

dt even��Y ist das Delta�Literal der virtuellen Basisdaten�anderung� succ�X� Y ist eine

��original� Basisdatenrelation� �Anderungen in original Basisfakten werden nicht betrachtet�

weil diese zum einen die Betrachtungen unn�otig komplizieren und zum anderen in Hinblick

auf die e�ziente Implementierung des AFPI eine andere Problematik darstellen�

�� Propagierungsregeln f�ur DTRegeln

Der Abschnitt �uber die grundlegende Idee� sowie das Kapitel �uber das AFPI haben her�

ausgestellt� dass die positive Menge der de�nitiv wahren Fakten �DT monoton anw�achst�

das heisst� dass in Bezug auf die DTi�� S�aule� Fakten in DTi eingef�ugt werden�

Die Idee f�ur dieDT Menge besteht im Gegensatz zur NDF Menge darin� dass dieDT Men�

ge nach der Anfangsannahme mit DT� � � durch die ermittelten Folge�anderungen ��DTi

inkrementell aufgebaut wird� Zu diesem Aufbauprozess werden positive Propagierungsre�

geln eingesetzt� denn� wie beobachtet� fallen im Bereich der DT Mengen keine L�oschungen

an� Wie auch im Falle derNDF Propagierungsregeln� werden echte �Anderungen berechnet�

Beispiel �Fortzetzung �

RDT �� fdt even�X � succ�X� Y ��ndf even�Y g

Die zugeh�orige positive Propagierungsregel ist�

R�DT �� fdt even��X � succ�X� Y � ndf even��Y ��dt even�X g

Im Vorgri� die entsprechenden inkrementellen Transitionsregel zur Zustandssimulation�

RDTnew �� f dt evennew�X � dt even�X

dt evennew�X � dt even��X g

KAPITEL �� IMPLEMENTIERUNG DES AFPI MITTELS UPDATES �

In diesem Beispiel kommen die inkrementellen Transitionsregeln nicht zum Zuge� da im

Residuum lediglich das Delta�Literal inklusive einer original Basisdatenrelation enthalten

ist und kein weiteres ��dt � Literal� was eine new�Simulation ben�otigen w�urde�

Wie bei den NDF�Propagierungsregeln� liegen f�ur den Fixpunktprozess die alten Zust�ande

von succ�X� Y und dt even�X vor� ndf even��Y ist das Delta�Literal der virtuellen

Basisdaten�anderung�

�� Transitionsregeln

Im vorhergehenden Abschnitt wurde herausgestellt� dass im Falle der NDF �Regeln nur

negative Propagierungsregeln erzeugt werden m�ussen� Es werden zu l�oschende Fakten als

Folge�anderung berechnet� Die Auswertung des Residuums �ndet im alten �old Zustand

statt� die Auswertung des E�ektivit�atstest im neuen �new Zustand�

F�ur die zweite Regelmenge� die der DT �Regeln� werden einzig und alleine positive Pro�

pagierungsregeln ben�otigt� Es werden Einf�ugungen als Konsequenz�anderungen abgeleitet�

Die Auswertung des Residdums �ndet im neuen �new Zustand statt� die Auswertung des

E�ektivit�atstests im alten �old Zustand�

Die Frage� ob sich Mischformen der old�new Zustandssimulation als g�unstig erweisen� wird

anhand der folgenden Tabellen erl�autert�

��Optimistische� old�Simulation� Die Basisfakten�anderungen werden vor der Herlei�

tung der Folge�anderungen in die Datenbasis festgeschrieben� Der new�Zustand der Basis�

fakten ist materialisiert�

DT old NDF old DT �new� NDF �new�

��NDF �� Basisf� �inkr� Trans Abgel� �inkr� Trans� �� p Abgel�

��DT Abgel� �naive Trans� �� Basisf� �inkr� Trans� Abgel� �� p

F�ur die NDF �Propagierungsregeln liegt der old�Zustand der NDF �Relationen vor� sowie

der new�Zustand der virtuellen DT �Basisrelationen� auf welche nur negativ Bezug genom�

men wird� Der old�Status der DT �Basisrelationen� welcher in der Residuenauswertung

ben�otigt wird� wird inkrementell simuliert� NDF liegt f�ur den E�ektivit�atstest noch im

alten Status vor und muss somit mit Beachtung der �Anderungen neu berechnet werden�

NDF old im Residuum wird per inkrementeller Transition simuliert�


F�ur die DT �Propagierungsregeln liegen die Basisrelationen NDF new vor� die nur negativ

refernziert werden� sowie DT old ist materialisiert� DT �new� muss f�ur die Residuenauswer�

tung neu hergeleitet werden� DT old wird f�ur den E�ektivit�atstest naiv simuliert� da es

ansonsten wieder zum bekannten Strati�kationproblem kommt� NDF old wird im E�ekti�

vit�atstest inkrementell simuliert� da es sich um Basisrelationen handelt�

Inkrementelle Transitionsregeln f�ur die old�Simulation�

s�X� Y old � s�X� Y �new��s�X� Y �s�X� Y old � s�X� Y �

Speziell f�ur negative Propagierungsregeln �ohne Einf�ugungen �

s�X� Y old � s�X� Y �new�

s�X� Y old � s�X� Y �

Speziell f�ur positive Propagierungsregeln �ohne L�oschungen �

s�X� Y old � s�X� Y �new��s�X� Y �

Fazit� In der old�Simulation liegen jeweils drei F�alle vor� in denen Relationsmengen vollst�andig

neu hergeleitet werden m�ussen� sowie drei inkrementell simulierte Relationsmengen�

��Pessimistische� new�Simulation� Die Basisfakten�anderungen werden nach der Her�

leitung der Folge�anderungen in die Datenbasis festgeschrieben� Der old�Zustand der Ba�

sisfakten ist materialisiert�

DT �old� NDF �old� DT new NDF new

��NDF �� p p�� Basisf� �inkr� Trans� Abgel� �naive Trans�

��DTp

�� p Abgel� �inkr� Trans� �� Basisf� �inkr� Trans�

F�ur die Auswertung der negativen NDF �Propagierungsregeln liegen die alten Zust�ande der

NDF �Relationen� sowie die der virtuellenDT �Basisrelationen vor� DieDT �Basisrelationen

werden lediglich sowohl im Residuum� als auch im E�ektivit�atstest negativ referenziert�

F�ur die Residuumsauswertung liegen alle Relationen im alten Status vor� Der E�ek�

tivit�atstest enth�alt f�ur die NDF �Relationen naive Transitionsregeln zur Simulation des


neuen Zustandes� DT new wird inkrementell simuliert und kann per Umformung �uber De�

Morgan in die referierende Regel eingef�ugt werden� weil die DT �Basisrelationen nur als

negierte Literale vorkommen� z�B�� aus der naiven Transitionsregel

ndf evennew�X � succ�X� Y ��dt evennew�Y

wird mit der inkrementellen Transition von dt evennew�X

ndf evennew�X � succ�X� Y ��dt even�Y ��dt even��Y

F�ur die Auswertung der positiven DT �Propagierungsregeln liegen die alten Zust�ande der

DT �Relationen� sowie die der virtuellen NDF �Basisrelationen vor� Der E�ektivit�atstest

greift lediglich auf den vorliegenden materialisierten alten Status der DT �Relationen zu�

Sowohl die DT new�Relationen� als auch die NDF new�Relationen werden inkrementell si�

muliert�

Inkrementelle Transitionsregeln f�ur die new�Simulation�

s�X� Y new � s�X� Y �old��s�X� Y �s�X� Y new � s�X� Y �

Speziell f�ur positive Propagierungsregeln �ohne L�oschungen �

s�X� Y new � s�X� Y �new�

s�X� Y new � s�X� Y �

Speziell f�ur negative Propagierungsregeln �ohne Einf�ugungen �

s�X� Y new � s�X� Y �old��s�X� Y �

Fazit� In der new�Simulation liegt ein Fall vor� in denen Relationen vollst�andig neu herge�

leitet werden m�ussen� sowie drei inkrementell simulierte Relationsmengen�

Resume des Vergleichs� Die alleinige oder die gemischte Anwendung von old�Simulationen

erscheint als nicht praktikabel� denn in dieser werden zum einen mehr Relationen erneut

vollst�andig materialisiert und zum anderen wird auf die Ursprungsregelmenge zur�uckgegri�en�


um den neuen Status von involvierten Relationen herzuleiten� Die new�Simulation arbei�

tet auf den materialisierten alten Zust�anden� neue Zust�ande werden inkrementell und naiv

simuliert mit teilweisen Vereinfachungen�

Aus diesen aufgef�uhrten Gr�unden heraus wird in den weiteren Betrachtungen und Unter�

suchungen nur noch die new�Simulation benutzt�

�� Der DPAAlgorithmus mittels �Anderungspropagierung

In den vorherigen drei Abschnitten wurden die besonderen Eigenheiten zur Erstellung von

negativen NDF �Propagierungsregeln und positiven DT �Propagierungsregeln aufgezeigt�

sowie die Diskussion �uber die speziellen Eigenschaften der unterschiedlichen Zustandssi�

mulationen ausgetragen� Im Folgenden wird ein Algorithmus zur Auswertung des DPA

mittels Updates vorgestellt� der die oben genannten Besonderheiten beachtet�

Bevor dieser Algorithmus vorgestellt wird� sind zwei Abbildungsfunktionen einzuf�uhren�

die zwischen Literalen p und ihren korrespondierenden dynamischen Literalen p� oder p�

umschaltet� um diese �Anderungen in die Datenbank eintragen zu k�onnen� Wenn A �pf��g�t�� tn ist� dann ist tf�A �� fp�t�� tn g�Eine weitere Funktion bildet aus Literalen p die positive dynamische Form p�� Wenn

A � p�t�� tn ist� dann ist � A �� fp��t�� tn g�Diese Funktion wird insbesondere f�ur die Umformung zu den ersten DT Einf�ugungen

ben�otigt�

�� i ��

�� DT ��

�� NDF �� lfp�T �RNDF

�F �DT jndf �� DT� �� lfp�T �

RDT�F �NDF jdt�

�� repeat

�� i �� i ��

�� NDFnew �� lfp�T �RNDFnew

�F ��DTi�� DT �NDF jndf �� NDFi �� lfp�T �

R�NDF�F ��DTi�� DT �NDF �NDFnew jndf �

�� DT �� DT � tf��DTi��

�� NDF �� NDF n tf��NDFi �

�� DTi �� lfp�T �R�DTRDTnew

�F ��NDFi �DT �NDF jdt�� until ��DTi � ��


Z�� Abk�urzung f�ur Zeile �� stellt die oft erw�ahnte Anfangsannahme des DPA

dar�

Z�� Hier wird die gr�osste ableitbare initiale Menge von NDF �Fakten hergelei�

tet� welche kontinuierlich abgebaut wird und jeweils als alter Status f�ur die

Berechnungen dient�

Z�� berechnet die ersten Delta�Fakten f�ur das di�erenzielle Verfahren� Dieser

Schritt wurde bereits in den vorigen Abschnitten diskutiert�

Z�� Die Repeat�Schleife stellt die �aussere Fixpunktberechnung dar�

Z�� materialisiert die neuen Zust�ande� die sich aus den naiven Transitionsregeln

und eingebauten inkrementellen Transitionsregeln der DT �Relationen be�

rechnet� Dieser Schritt stellt eine Art Strati�kation f�ur die korrekte Auswer�

tung des negativ referenzierten E�ektivit�atstests dar� Die Berechnung des

neuen Zustandes basiert auf Basisfakten und deren �Anderungen und h�angt

nicht von Folge�anderungen ab� Alle weiteren negativen Literale h�angen nur

von DT �Basisrelationen ab und stellen somit kein Strati�kationsproblem

dar�

Z�� leitet den kleinsten Fixpunkt der Folge�anderungen zu den gegebenen Basis�

daten�anderungen ��DTi�� her� Die einzigste negativ referenzierte abgelei�

tete Relation ist der E�ektivit�atstest� der zuvor in Z�� vollst�andig materia�

lisiert wurde�

Z� tr�agt die Basisdaten�anderungen� nach der Philosophie der new�Simulation�

in die DT �Menge ein und baut diese nach und nach auf�


Z�� entfernt die in Z�� berechneten zu l�oschenden virtuellen Basisfakten aus

der NDF �Faktenmenge� Dieser Schritt widerspricht im ersten Hinsehen

der Vorgehensweise der pessimistischen new�Simulation indem bereits an

dieser Stelle der neue Zustand der Basisrelationen erreicht wird� Diese Vor�

gehensweise ist jedoch korrekt� denn in den DT �Propagierungsregeln wird

nur negativ auf den neuen Zustand der NDF �Basisrelationen zugegri�en�

der alte Status wird im E�ektivit�atstest nicht realisiert und somit kann die

inkrementelle Simulation des neuen Zustandes entfallen�

Z�� leitet den Fixpunkt der Einf�ugungen zu den gegebenen Basisda�

ten�anderungen ��NDFi her� Strati�kationsprobleme treten unter der

Sichtweise von Z�� nicht auf� weil inkrementelle Transitionsregeln im Resi�

duum verwendet werden�

Z�� Der �aussere Fixpunkt ist genau dann erreicht� wenn keine neuen

Einf�ugungen mehr erzeugt werden konnten� Die Di�erenz zwischen zwei

DT �S�aulen in leer� also sind die beiden S�aulen gleich�

Es ist zu bemerken� dass die beiden Regelmengen des DPA immer strati�zierbar sind�

Die beiden Regelmengen f�ur sich m�ussen nicht unbedigt strati�ziert werden� weil ledig�

lich Basisrelationen negativ referenziert werden� Der DPA mittels �Anderungspropagierung

bedingt jedoch eine Strati�kation f�ur die negativen Propagierungsregeln� weil auf den ab�

geleitete E�ektivit�atstest negativ zugegri�en wird� Der obige Algorithmus leistet eine

Strati�kation in der Art� als dass zun�achst die Transitionsregeln f�ur den neuen Zustand

berechnet werden� Dieses wird m�oglich durch die naive Transition� die abgeleitete Rela�

tionen naiv simuliert und Basisrelationen inkrementell� so dass die Transitionsregeln nicht

auf Folge�anderungen referenzieren�

Auswertung des DPA mittels �Anderungspropagierung an einem Beispiel�




R�NDF �� fndf even��X � dt even��Y � succ�X� Y ��ndf evennew�X gR�DT �� fdt even��X � ndf even��Y � succ�X� Y ��dt even�X g

RNDFnew �� fndf evennew�X � succ�X� Y ��dt even��Y ��dt even�Y g

Mit DT � ��

NDF � f ndf even�� ndf even�� ndf even�� ndf even�� ndf even�� ndf even�� g��DT� � f dt even�� g

NDFnew � f ndf evennew�� ndf evennew�� ndf evennew�� ndf evennew�� ndf evennew�� g��NDF� � f ndf even�� gDT � f dt even�� g ��DT� in DB

NDF � f ndf even�� ndf even�� ndf even�� ndf even�� ndf even�� g ��NDF� aus DB

��DT� � f dt even�� g

NDFnew � f ndf evennew�� ndf evennew�� ndf evennew�� ndf evennew�� g��NDF� � f ndf even�� gDT � f dt even�� dt even�� g ��DT� in DB

NDF � f ndf even�� ndf even�� ndf even�� ndf even�� g ��NDF� aus DB


NDFnew � f ndf evennew�� ndf evennew�� ndf evennew�� ndf evennew�� g��NDF � �

DT � f dt even�� dt even�� dt even�� g ��DT� in DB

NDF � f ndf even�� ndf even�� ndf even�� ndf even�� g Keine L�oschungen��DT � � Der �aussere Fixpunkt ist erreicht�



Neu hergeleitet werden jeweils die Mengen NDFnew� ��DT und ��NDF � Der DPA

mittels �Anderungspropagierung leitet insgesamt �� Fakten her� der ��original� DPA �� f�ur

dieses Beispiel�


�� Fazit

Das Beispiel hat gezeigt� wie die Di�erenzen zwischen jeweils zwei gleichartigen S�aulen

ausshen� In diesem Beispiel ist die Anzahle der �Anderungen immer konstant eins� Es ist

deutlich geworden� dass Einf�ugungen in der n�achsten S�aule L�oschungen bedingen und um�

gekehrt� Es wird jedoch auch deutlich� dass wenn die Simulation der neuen vollst�andigen

Zust�ande ins Spiel kommt� der Gewinn der Di�erenzenbetrachtung relativiert wird� Dies ist

im Beispiel bei den NDF �Relation der Fall� bedingt durch den E�ektivit�atstest� Die Aus�

wertung DT �Propagierungsregeln zeigt den Vorteil der �Anderungsbetrachtung auf� wenn

keine neuer Zustand erforderlich ist� das ist eine g�unstige Eigenschaft dieser Beispielregeln�

Andere positive Propagierungsregeln werden in der Residuenberechnung durch die Anzahl

der Literale� die neue Zust�ande ben�otigen� gepr�agt�

Ziel des n�achsten Kapitels wird sein ein Verfahren zu entwickeln� welches die unbedingt

relevanten Fakten der neuen Zust�ande ableitet�

Kapitel �

Implementierung des AFPI mittels

Magic Updates

Im vorigen Kapitel wurde beschrieben� wie das DPA�Verfahren mittels des Einsatzes von�Anderungspropagierung realisiert werden kann� Dieses Kapitel betrachtet den zus�atzlichen

Einsatz der Magic�Set Transformation im Zusammenhang mit �Anderungspropagierung� wie

es in �Gri�� beschrieben wird� Diese Erweiterung dient zur begrenzten Auswertung der

Transitionsregeln f�ur die neuen Zust�ande� Der erste Abschnitt zeigt den Einsatz anhand des

bekannten Beispiels even und die damit gewonnenen Einsparungen� Der zweite Abschnitt

erweitert das Beispiel um Regeln� die einen positiven Zyklus bilden� Unter der Verwen�

dung von Magic Updates k�onnen diese Regeln ein Strati�kationsproblem hervorrufen� Die

anschliessenden Abschnitte stellen L�osungen zu diesem Problem vor� die insbesondere in

das verwendete Fixpunktverfahren eingreifen�

�� Regelmengen ohne positiven Zyklus

In diesem Abschnitt wird �Anderungspropagierung unter Verwendung der Magic�Set Trans�

formation als Mittel zur Implementierung des Doubled Program Ansatzes untersucht� Es

werden Regelmengen benutzt� die keinen positiven Zyklus im Abh�angigkeitsgraphen ent�

halten� Im Hinblick auf die Unstrati�zierbarkeit der urspr�unglichen Regelmenge bedeu�

tet diese Einschr�ankumg der Regelmenge� dass in der Ursprungsregelmenge nur negative

Zyklen existieren� jedoch durch das Regelumschreiben des DPA aufgel�ost werden� Das

folgende bekannte Beispiel zeigt die Kombination des DPA mit Magic Updates�

Auswertung des DPA mittels Magic�Set �Anderungspropagierung an einem Beispiel�

��

KAPITEL �� AFPI MITTELS MAGIC UPDATES ��



R�NDF �� fndf even��X � dt even��Y � succ�X� Y ��ndf evennew�X gR�DT �� fdt even��X � ndf even��Y � succ�X� Y ��dt even�X g

RNDFnew �� fndf evennew�X � m ndf evennew b�X � succ�X� Y ��dt even��Y ��dt even�Y m ndf evennew b�X � dt even��Y � succ�X� Y g

Diese Besipieldatenbank wurde im letzten Kapitel �uber das AFPI unter Verwendung von�Anderungspropagierung diskutiert� Nun werden Anfragen mittels der Magic�Set Methode

an die Transitionsregeln gestellt� Die Transitionsregeln wurden mittels des naiven Tran�

sitionsverfahrens erstellt� Die Anfragen an den E�ektivit�atstest der negativen Propagie�

rungsregel bilden sich aus dem Delta�Literal und dem Residuum der Propagierungsregel�

Die Transitionsregeln werden entsprechend der Anfrage an den E�ektivit�atstest Magic�Set

transformiert�

Mit DT � ��

NDF � f ndf even�� ndf even�� ndf even�� ndf even�� ndf even�� ndf even�� gBerechnung der �� NDF �Fakten

��DT� � f dt even�� gDie �� DT �Fakten sind die initialen Einf�ugungen�

NDFnew � f m ndf evennew b�� gDie �� Anfrage an den E�ektivit�atstest auf alternative Ableitung�

bedingt durch die Einf�ugung von dt even��

��NDF� � f ndf even�� gDie Anfrage schl�agt fehl� ndf even�� ist echt L�oschung�

DT � f dt even�� g DT � tf��DT�

NDF � f ndf even�� ndf even�� ndf even�� ndf even�� ndf even�� gNDF � tf��NDF� � NDF wird abgebaut� DT wird aufgebaut�


KAPITEL �� AFPI MITTELS MAGIC UPDATES �

Die L�oschung von ndf even�� bedingt die Einf�ugung dt even��

NDFnew � f m ndf evennew b�� gDie �� Anfrage an den E�ektivit�atstest auf alternative Ableitung�

bedingt durch die Einf�ugung von dt even��

��NDF� � f ndf even�� gDie Anfrage schl�agt fehl� ndf even�� ist echt L�oschung�

DT � f dt even�� dt even�� g DT � tf��DT�

NDF � f ndf even�� ndf even�� ndf even�� ndf even�� g NDF � tf��NDF�

NDF wird abgebaut� DT wird aufgebaut�

��DT� � f dt even�� gDie L�oschung von ndf even�� bedingt die Einf�ugung dt even��

NDFnew � �

��NDF � �

Die Einf�ugung dt even�� bedingt keine L�oschung mehr

DT � f dt even�� dt even�� dt even�� g DT � tf��DT�

NDF � f ndf even�� ndf even�� ndf even�� ndf even�� g NDF ��NDF wird abgebaut� DT wird aufgebaut�

��DT � �

Das Abbruchkriterium ist erreicht� es gibt keine Einf�ugungen mehr�



Hergeleitet werden jeweils die Mengen ��DT � ��NDF und NDFnew� insbesondere beste�

hend aus der Anfragerelation m ndf evennew b�X und der Antwortrelation ndf evennew

f�ur den E�ektivit�atstest� Der DPA mittels Magic�Set �Anderungspropagierung leitet insge�

samt �� Fakten her� DPA mittels ��normaler� �Anderungspropagierung �� Fakten her und

der ��original� DPA �� f�ur dieses Beispiel�

F�ur die formale Aufwandsberechnung dieses Beispiels wird angenommen� dass die Basis�

fakten succ�� succ�n� �� n gegeben sind�Der DPA in seiner urspr�unglichen Implementierung leitet �

n�

�n Fakten ab� Der DPA

mittels Magic Updates hingegen ben�otigt �n Ableitungen�


Anhand dieses Beispiels wird gezeigt� wie im Falle von negativen Propagierungsregeln�

Anfragen an den E�ektivit�atstest gestellt werden� Diese Anfragen bedeuten� dass an den

neuen Zustand angefragt wird� ob die zu l�oschenden Fakten �Folge�anderungen im neuen

Zustand �uber eine alternative Art hergeleitet werden k�onnen� Ist dies nicht der Fall� so

sind die Folge�anderungen wahre �Anderungen� Die Auswertung der Anfrage wird durch die

Magic�Set Methode auf relevante Fakten begrenzt� Die Forderung der vorigen Kapitel� die

neuen Zust�ande f�ur den E�ektivit�atstest nicht vollst�andig zu materialisieren� ist f�ur dieses

Beipiel erf�ullt worden� Ein Fakt darf dann gel�oscht werden� wenn die Antwort zur Anfrage

an den E�ektivit�atstest� respektive neuen Zustand� fehl schl�agt� bzw� die Antwortmenge

leer ist�

Die Auswertung der Regelmengen des DPAmittels Magic�Set �Anderungspropagierung ohne

positiven Zyklus kann durch den im letzten Kapitel vorgestellten Algorithmus durchgef�uhrt

werden� Das ist m�oglich� weil durch die Magic�Set Transformation f�ur diese Regelklasse

kein Strati�zierungsproblem gibt�

�� Regelmengen mit positiven Zyklen

Regelmengen mit positiven Zyklen im Abh�angigkeitsgraphen sind unter Verwendung des

DPA mit Magic�Set �Anderungspropagierung nicht strati�zierbar� Diese k�onnen folglich

nicht mit den herk�omlichen Fixpunktverfahren f�ur strati�zierbare Regelmengen berechnet

werden� welche zur Berechnung der inneren Fixpunkte der AFP�S�aulen verwendet werden�

Es wird angenommen� dass in der Ursprungsregelmenge mindestens ein negativer Zyklus

enhalten ist� Die Nichtstrati�zierbarkeit steht im direkten Zusammenhang mit der Magic�

Set Transformation� Diese Problematik wurde bereits im Abschnitt ��Magic�Updates� des

vorletzten Kapitels ausf�uhrlich besprochen�

Die Problematik l�asst sich so beschreiben� dass die Folge�anderung �uber den negativ refe�

renzierten E�ektivit�atstest und der Anfragerelation an den selbigen Test� einen negativen

Zyklus bilden� Dieses Strati�kationsproblem gilt insbesondere nur f�ur die negativen Propa�

gierungsregeln der NDF �Regelmenge� weil dort die einzige abgeleitete negativ referenzierte

Relation� der E�ektivit�atstest� vorhanden ist� Die Problematik wird anhand eines Beispiels

diskutiert�

Beispielregelmenge mit positiver Rekursion�

Die Beispieldatenbank aus dem letzten Abschnitt wurde um die Regeln der transitiven


H�ullenberechnung erweitert� Es werden die transitiven Pfade berechnet� die als Ziel eine

ungerade Zahl haben�

R �� f even�X � succ�X� Y ��even�Y p�X� Y � succ�X� Y ��even�Y p�X� Y � succ�X�Z � p�Z� Y ��even�Y g

Das even�Beispiel wird um die transitive Pfadberechnung erweitert�

F �� fsucc�� succ�� succ�� succ�� succ�� succ�� g

RNDF �� f ndf even�X � succ�X� Y ��dt even�Y ndf p�X� Y � succ�X� Y ��dt even�Y ndf p�X� Y � succ�X�Z � ndf p�Z� Y ��dt even�Y g

RDT �� f dt even�X � succ�X� Y ��ndf even�Y

dt p�X� Y � succ�X� Y ��ndf even�Y

dt p�X� Y � succ�X�Z � dt p�Z� Y ��ndf even�Y g

Das sind die beiden umgeformten Regelmengen f�ur das DPA�Verfahren�

R�NDF �� f ndf even��X � dt even��Y � succ�X� Y ��ndf evennew�X

ndf p��X� Y � dt even��Y � succ�X� Y ��ndf pnew�X� Y

ndf p��X� Y � ndf p��Z� Y � succ�X�Z ��dt even�Y ��ndf pnew�X� Y

ndf p��X� Y � dt even��Y � succ�X�Z � ndf p�Z� Y ��ndf pnew�X� Y g

Das sind die negativen Propagierungsregeln der NDF �Regeln�

Ein Pfad wird gel�oscht� wenn eine Ziel�Zahl de�nitv gerade geworden ist�

oder wenn Pfad als Folge�anderung gel�oscht wird�

R�DT �� f dt even��X � ndf even��Y � succ�X� Y ��dt even�X dt p��X� Y � ndf even��Y � succ�X� Y ��dt p�X� Y dt p��X� Y � dt p��Z� Y � succ�X�Z ��ndf even�Y ��dt p�X� Y dt p��X� Y � ndf even��Y � succ�X�Z � dt p�Z� Y new��dt p�X� Y g

Das sind die positiven Propagierungsregeln der DT �Regeln�


Ein Pfad wird g�ultig� wenn eine Ziel�Zahl de�nitv nicht gerade geworden ist�

oder wenn Pfad als Folge�anderung hinzugef�ugt wird� In einem Rump�iteral wird

neue Zustand dt p�Z�Y new ben�otigt�

RNDFnew �� f ndf evennew�X � m ndf evennew b�X � succ�X� Y ��dt even��Y ��dt even�Y m ndf evennew b�X � dt even��Y � succ�X� Y

ndf pnew�X� Y � m ndf pnew bb�X� Y � succ�X� Y ��dt even�Y ��dt even��Y ndf pnew�X� Y � m ndf pnew bb�X� Y � succ�X�Z � ndf pnew�Z� Y ��dt even��Y ��dt even�Y

Das sind die Magic�Set tranformierten Transitionsregeln�

m ndf pnew bb�Z� Y � m ndf pnew bb�X� Y � succ�X�Z

Das ist die Anfrage� die sich aus der Transitionsregel ergibt�

m ndf pnew bb�X� Y � dt even��Y � succ�X� Y

m ndf pnew bb�X� Y � ndf p��Z� Y � succ�X�Z ��dt even�Y m ndf pnew bb�X� Y � dt even��Y � succ�X�Z � ndf p�Z� Y g

Das sind die Anfragen aus den negativen Propagierungsregeln�

RDTnew �� f dt pnew�X� Y � m dt pnew bb�X� Y � p�X� Y

dt pnew�X� Y � m dt pnew bb�X� Y � p��X� Y

Das sind die Magic�Set transformierten inkrementellen� Transitionsregeln

m dt pnew bb�Z� Y � ndf even��Y � succ�X�Z g

Das ist die Anfrage an den neuen Zustand�

Der positive Zyklus ist �uber die Regel

p�X� Y � succ�X�Z � p�Z� Y ��even�Y g


gegeben�

In diesem erweiterten Beispiel ist der negative Zyklus der Folge�anderung

ndf p��X� Y � ndf p��Z� Y � succ�X�Z ��dt even�Y ��ndf pnew�X� Y

unter anderem �uber die E�ektivit�atstestregel

ndf pnew�X� Y � m ndf pnew bb�X� Y � succ�X� Y ��dt even�Y ��dt even��Y

und der Anfrageregel

m ndf pnew bb�X� Y � ndf p��Z� Y � succ�X�Z ��dt even�Y

gegeben�

Der ��normale� DPA leitet die Bedeutung der Beispieldatenbank wie folgt her �Die Relation

��succ� wird mit ��s� und ��even� wird mit ��e� abgek�urzt �

Mit DT� � ��

NDF� � f ndf e�� ndf e�� ndf e�� ndf e�� ndf e�� ndf e�� ndf p�� ndf p�� ndf p�� ndf p�� ndf p�� ndf p��

ndf p�� ndf p�� ndf p�� ndf p�� ndf p�� ndf p��

ndf p�� ndf p�� ndf p�� ndf p�� gDT� � f dt e�� dt p�� dt p�� dt p�� dt p�� dt p�� g

NDF� � f ndf e�� ndf e�� ndf e�� ndf e�� ndf e�� ndf p�� ndf p�� ndf p�� ndf p�� ndf p�� ndf p��

ndf p�� ndf p�� ndf p�� ndf p�� ndf p�� ndf p�� gDT� � f dt e�� dt e�� dt p�� dt p�� dt p�� dt p�� dt p��

dt p�� dt p�� dt p�� g

NDF � f ndf e�� ndf e�� ndf e�� ndf e�� ndf p�� ndf p�� ndf p�� ndf p�� ndf p�� ndf p��

ndf p�� ndf p�� ndf p�� ndf p�� gDT � f dt e�� dt e�� dt e�� dt p�� dt p�� dt p�� dt p�� dt p��

dt p�� dt p�� dt p�� dt p�� g


NDF � f ndf e�� ndf e�� ndf e�� ndf e�� ndf p�� ndf p�� ndf p�� ndf p�� ndf p�� ndf p��

ndf p�� ndf p�� ndf p�� ndf p�� gDT � f dt e�� dt e�� dt e�� dt p�� dt p�� dt p�� dt p�� dt p��

dt p�� dt p�� dt p�� dt p�� g

DT � DT Der �aussere Fixpunkt ist erreicht�

Der ��mormale� DPA leitet f�ur diese Beispieldatenbank unter alleiniger Betrachtung der

RNDF und RDT in den DPA�S�aulen �� Fakten ab� Die Bedeutung enth�alt �� wahre und

zwei unde�nierte Fakten�

Welches Fixpunktverfahren ist jedoch in diesem Fall f�ur die Berechnung des DPA mittels

Magic�Set �Anderungspropagierung geeignet� Eine L�osung ist der Einsatz einer AFPI�

Implementierung zur Berechnung der nicht strati�zierbaren Regeln in den NDF�S�aulen�

also ein AFPI im AFPI� Die Positiven Zyklen sind auch in einer NDF�S�aule mittels DPA�

Berechnung enthalten� Somit kommt keine Magic Updates in Frage� im Gegensatz dazu

werden negative Zyklen durch das DPA in der NDF�S�aule aufgel�ost�

Eine wichtige Eigenschaft der transformierten Regeln f�ur die Entwicklung von L�osungsvorschl�ange

in den n�achsten Abschnitten� ist die Eigenschaft� dass die Semantiken der inneren DPA�

Fixpunkte� die mittels Magic Updates abgeleitet werden� immer zwei�wertig sind� Die�

se Eigenschaft wurde bereits im Abschnitt des vorletzten Kapitels �uber Magic�Updates

f�ur generelle strati�zierbare Regelmengen aufgezeigt� Diese Eigenschaft gilt gerade auch

f�ur die beiden DPA�Regelmengen� weil zum einen die DT � und NDF �Relmengen immer

strati�zierbar sind� zum anderen sind die daraus erstellten Propagierungsregeln mit naiver

Transitionsregelerstellung auch strati�zierbar �siehe Kapitel �uber �Anderungspropagierung �

Die daraus erzeugten Magic�Set Regeln m�ussen nicht unbedingt strati�zierbar sein� Die

Bedeutung dieser Regelmenge ist dann jedoch zwei�wertig�

�� L�osungsvorschlag � Verwendung von T�D

Dieser L�osungansatz setzt an der Berechnung des inneren Fixpunktes derNDF �Regelmenge

an und de�niert f�ur deren Materialisierung einen eigenen Fixpunktoperator�


T �D�X �� TR�X � F

TR ist der in Kapitel � de�nierte kollektive Ableitungsoperator� T�D ist im Gegensatz zu T

�R

aus Kapitel � nicht kumulativ� Dies bedeutet� dass die Ergebnisse der Ableitungsrunden

nicht angesammelt werden� T �D ist wie T

�R f�ur strati�zierbare deduktive Datenbanken mo�

noton wachsend� Im Falle von nicht strati�zierbaren Datenbanken ist T �D nicht monoton

wachsend� Deshalb terminiert unter Umst�anden dieser Fixpunktoperator nicht� Ist f�ur

eine gegebene deduktive Datenbank bekannt� dass deren Regelmenge nicht strati�zierbar

ist und dass die Bedeutung der Datenbank zwei�wertig ist� so berechnet T �D den korrekten

Fixpunkt�

Zwei�wertige� nicht strati�zierbare Beispieldatenbank�

R �� fe�X � s�X� Y ��e�Y g�F �� fs�� s�� s�� s�� s�� g

Die Ableitungsrunden�

�� Runde� fe�� e�� e�� e�� e�� g�� Runde� fe�� g�� Runde� fe�� e�� e�� e�� g�� Runde� fe�� e�� g�� Runde� fe�� e�� e�� g�� Runde� fe�� e�� e�� g�� Runde � �� Runde Der kleinste Fixpunkt ist erreicht�

Dieses Beispiel zeigt� dass die Faktenmengen der Ableitungsrunden nicht monoton anwach�

sen� sondern alternieren� Dieses Alternieren �ahnelt stark den �Uber� und Untersch�atzungen

der negativen Referenzmengen des alternierenden Fixpunktverfahrens� Der kleinste Fix�

punkt ist genau dann erreicht� wenn die letzten beiden Ableitungsrunden das gleiche Re�

sultat ausgeben�

Im Falle der NDF �Regeln mit Magic�Set �Anderungspropagierung und dessen Nichtstrati�

�zierbarkeit ist bekannt� dass die Semantik dieser Regelmenge zwei�wertig ist�

Diesen angewandt auf das komplexere DPA�Beispiel des letzten Abschnitts mittels Magic

Updates mit den gegebenen Fakten und Regelmengen� wobei die Relation ��succ� mit ��s�


und ��even� mit ��e� abgek�urzt wird�

Mit DT � ��

NDF � f ndf e�� ndf e�� ndf e�� ndf e�� ndf e�� ndf e�� ndf p�� ndf p�� ndf p�� ndf p�� ndf p�� ndf p��


ndf p�� ndf p�� ndf p�� ndf p�� gBerechnung der �� NDF �Fakten

��DT� � f dt e�� dt p�� dt p�� dt p�� dt p�� dt p�� gBerechnung der �� Einf�ugungen

NDFnew � f m ndf enew b�� m ndf pnew bb�� m ndf pnew bb�� m ndf pnew bb��

m ndf pnew bb�� m ndf pnew bb�� m ndf pnew bb�� g��NDF� � f ndf e�� ndf p�� ndf p�� ndf p�� ndf p�� g

Gleichzeitige Auswertung der NDF Prop�regeln und der Trans�regeln mittels T �D�

Die Anfragen werden berechnet und beantwortet�

DT � f dt e�� dt p�� dt p�� dt p�� dt p�� dt p�� gNDF � f ndf e�� ndf e�� ndf e�� ndf e�� ndf e��


ndf p�� ndf p�� ndf p��

ndf p�� ndf p�� ndf p�� gNDF wird abgebaut� DT wird aufgebaut�

DTnew � f m dt pnew bb�� m dt pnew bb�� m dt pnew bb�� m dt pnew bb��

m dt pnew bb�� m dt pnew bb��

dt pnew�� dt pnew�� dt pnew�� g��DT� � f dt e�� dt p�� dt p�� dt p�� g

Gleichzeitige Auswertung der DT Prop�regeln und der Trans�regeln�


NDFnew � f m ndf enew b�� m ndf pnew bb�� m ndf pnew bb�� m ndf pnew bb��

m ndf pnew bb�� m ndf pnew bb�� m ndf pnew bb�� g��NDF� � f ndf e�� ndf p�� ndf p�� g

Gleichzeitige Auswertung der NDF Prop�regeln und der Trans�regeln mittels T �D�


DT � f dt e�� dt e�� dt p�� dt p�� dt p�� dt p�� dt p��


dt p�� dt p�� dt p�� gNDF � f ndf e�� ndf e�� ndf e�� ndf e��

ndf p�� ndf p�� ndf p�� ndf p��



DTnew � f m dt pnew bb�� m dt pnew bb�� m dt pnew bb�� m dt pnew bb��

m dt pnew bb�� m dt pnew bb�� dt pnew�� g��DT� � f dt e�� dt p�� g

Gleichzeitige Auswertung der DT Prop�regeln und der Trans�regeln�


NDFnew � �

��NDF � �

Einf�ugungen bedingen keine L�oschungen mehr�

DT � f dt e�� dt e�� dt e�� dt p�� dt p�� dt p�� dt p�� dt p�� dt p�� dt p�� dt p�� dt p�� g

NDF � f ndf e�� ndf e�� ndf e�� ndf e�� ndf p�� ndf p�� ndf p�� ndf p��



DTnew � �

��DT � �

Das Abbruchkriterium ist erreicht�

Das Endergebnis des Beispiels� Bedeutung der gegebenen deduktiven Datenbank� berech�

net durch DPA mittels Magic�Set �Anderungspropagierung� stimmt mit der Berechnung des

��normalen� DPA �uberein� Die Anzahl der Fakten in den inneren Fixpunkten des DPA sind

�� und die des DPA Magic Updates sind ��

Der Algorithmus entspricht in grossen Teilen dem des DPAmittels �Anderungspropagierung�

mit der Ausnahme� dass der E�ektivit�atstest der negativen NDF �Propagierungsregeln

nicht vorher separat materialisiert wird� RNDF und RNDFnew werden �uber ein und die

selbe Fixpunktberechnung des T �D abgeleitet�


�� i ��

�� DT ��




�� repeat

�� i �� i ��

�� NDFi �� lfp�T �R�NDFRNDFnew

�F ��DTi�� DT �NDF jndf �� DT �� DT � tf��DTi��




Dieses Beispiel zeigt zus�atzlich auf� dass die Magic�Set Transformation ihre Nachteile be�

sitzt� Betrachtet man sichdie konkrete Auswertung einer Anfrageregel� die zu einer positi�

ven Propagierungsregel geh�ort�

m dt pnew bb�Z� Y � ndf even��Y � succ�X�Z




so stellt man fest� dass an diesem Punkt viele Anfragefakten produziert werden� dessen

Antwort nicht im neuen Zustand sein wird� Die Ursache ist die ung�unstige Variablen�

bindung f�ur die Anfragesubstitution� Es existieren Techniken� die durch Umstellung der

Rump�iterale� eine ��g�unstigere� Bindung zu erreichen versuchen� es wird folglich eine an�

dere SIP�Strategie benutzt� Die Diskussion �uber SIP�Strategien ist nicht Gegenstand dieser

Diplomarbeit�

Ein weiterer Punkt in der Diskussion um die Verwendung von T �D� ist der Punkt der

Monotonie�Eigenschaft� Im kleinen Einf�uhrungsbeispiel wurde auf das ��Alternieren� der

Ableitungsmengen hingewiesen� Es wurde beschrieben� dass bei einer zwei�wertigen Se�

mantik T �D terminiert� Das ist bei Magic Updates der Fall� Es stellt sich jedoch die Frage

wie ��aufwendig� es ist� den kleinsten Fixpunkt zu erreichen� wenn zum Beispiel in der

ersten Ableitungsrunde ein negatives Delta�Fakt hergeleitet wurde� was nach vollst�andiger


Materialisierung des E�ektivit�atstest nicht abeleitet werden durfte� weil es im neuen Zu�

stand eine alternative Ableitung f�ur das Fakt existiert� Das Endergebnis wird korrekt sein�

jedoch k�onnen w�ahrend den Iterationsrunden zu vielmehr Anfrage� und Antwortfakten

hergeleitet werden�

Der vorgeschlagene Fixpunktoperator berechnet die Bedeutung der unstrati�zierbare Magic�

Set tranformierte NDF �Propagierungs� und Transitionsregeln korrekt� Der Nachteil dieses

Operators sind die m�oglichen alternierenden Faktenmengen der Ableitungsrunden�

�� L�osungsvorschlag � �Ubersch�atzung der negati

ven DeltaFakten

W�ahrend der Diskussion um L�osungsvorschl�age wurden die folgenden Gedanken in Be�

tracht gezogen�

Im letzten Abschnitt wurde der Ansatz anhand eines alternativen Fixpunktoperators rea�

lisiert� Der nun zu betrachtende Ansatz bel�asst den Fixpunktoperator� z�B� T �R� sondern

modi�ziert Literale im Regelrumpf von Propagierungsregeln�

Der Rumpf einer negativen Propagierungsregel besteht aus dem Delta�Literal und dem Re�

siduum� sowie dem negativ referenzierten E�ektivit�atstest� Das Delta�Literal zusammen

mit dem Residuum bilden die Anfragerelation an den E�ektivit�atstest� Im Falle von selbst

rekursiven Regeln gibt es mindestens eine Regel dessen Delta�Literal mit dem Kop�iteral

der negativen Propagierungsregel �ubereinstimmt� Dieses Delta�Fakt h�angt nach Anwen�

dung der Magic�Set Transformation negativ von sich selbst ab� z�B�

ndf p��X� Y � ndf p��Z� Y � s�X�Z ��dt e�Y ��ndf pnew�X� Y

Ziel der Idee ist es� das Delta�Literal so zu �andern� so dass kein Strati�kationsproblem

auftritt� Das Delta�Literal wird durch eine �Ubersch�atzung ersetzt� im Beispiel durch�

ndf p��X� Y � ndf p�Z� Y ��dt p�Z� Y ��dt p��Z� Y � �z ��Ubersch�atzung

� s�X�Z ��dt e�Y ��ndf pnew�X� Y

Diese �Ubersch�atzung bedeutet� dass der alte� aktuelle Zustand der ndf p Relation weni�

ger der Fakten von p� die bereits als de�nitiv wahr bekannt sind� als neue Delta�Fakten�

also als L�oschungen angenommen werden� Die daraus resultierenden Folge�anderungen wer�


den durch den E�ektivit�atstest gepr�uft� Diese �Ubersch�atzung wird unter anderem damit

begr�undet� dass in der �Ubersch�atzung die Folg�anderungen der Folge�anderungen� usw� be�

reits enthalten sein werden� Die umgestalltete Anfragerelation besitzt dann folgende Form�

m ndf pnew bb�X� Y � ndf p�Z� Y ��dt p�Z� Y ��dt p��Z� Y � �z ��Ubersch�atzung

� s�X�Z ��dt e�Y

Einen Auschnitt der Beispielberechnung in dem die L�oschungen aus den NDF �Fakten be�

rechnet wird� wird nun betrachtet� Die Herleitung des Fixpunktes �ndet mittels DPA mit

Magic Updates und T �R als Fixpunktoperator statt� Zur Vermeidung des Strati�kations�

problems wird die vorgestellte Methode der �Ubersch�atzung von Delta�Fakten angewandt�

NDFnew � f m ndf enew b��

m ndf pnew bb�� m ndf pnew bb�� m ndf pnew bb��




m ndf pnew bb��

ndf pnew�� ndf pnew�� ndf pnew��

Das sind die von der �Ubersch�atzung erzeugten Anfragen und Antworten�

ndf pnew�� ndf pnew�� ndf pnew�� g��NDF�� f ndf e�� ndf p�� ndf p�� ndf p�� ndf p�� g

Das sind die von der �Ubersch�atzung erzeugten echten L�oschungen�

Es werden �� Fakten als Fixpunkt in der NDF��S�aule hergeleitet� Im Vergleich dazu

materialisiert der ��normale� DPA �� Fakten und der DPA mittels Magic Updates und T �D

erzeugt �� Fakten� Das Absch�atzungsverfahren ist in diesem Beispiel schlechter�

Dieses Ergebnis ist intuitiv nicht so erwartet worden� Das schlechte Ergebnis wird mit der

Tatsache begr�undet� dass durch die transitive Regel p� die Folge�anderungen der aus der

Basisrelation s�X� Y �ubernommenen Fakten� berechnet werden� Es wird die Anfrage mit

den alten ndf p weniger der Basisfakten s�Y�X weniger der de�nitiv wahren p�Fakten an

den E�ektivit�atstest gestellt� In dieser Anfragemenge sind auch all die Fakten enthalten�

die im neuen Zustand wieder zu �nden sind� Folglich wird der neue Zustand in grossen

Teilen f�ur den E�ektivit�atstest materialisiert� Anders betrachtet wird bis auf konstante

Einschr�ankungen die Di�erenz zwischen dem alten und neuen Zustand der Relationen ge�

bildet� was durch die individuellen Delta�Relationen und der Magic�Set Auswertung des


E�ektivit�atstest vermieden werden sollte�

Eine weitere Frage ist die Vorgehensweise bei indirekt rekursiven Relationen� die einen

positiven Zyklus im Abh�angigkeitsgraphen bilden� z�B�

p��X� Y � s��X�Z � � � �

s��X� Y � p��Z�X � � � �

Werden beide Delta�Relationen durch ihren eingeschr�ankten alten Zustand �ubersch�atzt�

oder nur eine Delta�Relation� wenn ja� welche Relation� Aus Gr�unden des eben vorgestell�

ten erh�ohten Ableitungsaufwands sind die Antworten auf diese Fragen obsolet�

Das vorgestellte �Ubersch�atzungsverfahren l�ost das Strati�kationsproblem� Das Verfahren

ist jedoch nicht praktikabel� weil es durch die Mengendi�erenz zischen alten und materia�

lisierten neuen Status im Vergleich zum ��normalen� DPA schlechter ist�

�� L�osungsvorschlag � Sequenzieller Fixpunktope

rator

Der im Rahmen der Diskussion zur Diplomarbeit favorisierte L�osungsvorschlag zur Behe�

bung des Strati�kationsproblem setzt wiederum am Fixpunktverfahren zur Materialisie�

rung der NDFnew und �NDF Regeln an�

Die ��NDF Folge�anderungen im DPA mittels �Anderungspropagierung wurden in zwei

Fixpunktphasen hergeleitet� Die erste Phase ist zust�andig f�ur die vollst�andige Materialisie�

rung der Transitionsregeln im E�ektivit�atstest� Die Zweite Phase ben�otigt die in der ersten

Phase gewonnenen Fakten f�ur die korrekte Auswertung der negativen Propagierungsregeln��Uber den E�ektivit�atstest wird negativ auf die Ergebnisse des ersten Phase zugegri�en�

umgekehrt greift die erste Phase nicht auf Ergebnisse der Folge�anderungsberechnung zu�

Im Falle des Strati�kationsproblems liegt zwischen den negativen Propagierungsregeln und

den Transitionsregeln ein negativer Zyklus vor� deren Semantik zwei�wertig ist�

Die Idee besteht darin� zun�achst den Fixpunkt der Transitionsregeln des E�ektivit�atstests

zu berechnen� Die Ableitungen neginnen in der ersten Runde mit den Anfragen� die aus

den virtuellen Basisfakten�anderungen herr�uhren� Danach werden die negativen Propagie�

rungsregeln in einer Ableitungsrunde angewandt� Aus diesen ermittelten Folge�anderungen

entstehen wiederum neue Anfragen an den E�ektivitestest und somit an die Transitions�

regeln� F�ur diese neuen Anfragen wird dann wieder der Fixpunkt der Transitionsregeln


gebildet� danach werden wieder die Folge�anderungen berechnet� usw� Der ��aussere� Fix�

punkt ist dann erreicht� wenn sich im Vergleich zur letzten Ableitungsrunde keine neuen

Folge�anderungen mehr ergeben�

Sinn und Zweck des neuen Fixpunktoperators ist es� die relevanten Anfragen an den Ef�

fektivit�atstest zu erzeugen� die aus den virtuellen Basisfakten�anderungen� sowie aus den

Folge�anderungen herr�uhren� Im Gegensatz dazu leitet T �D in jeder Ableitungsrunde si�

multan Fakten her� die sowohl aus den negativen Propagierungsregeln� als auch aus den

Transitionsregeln stammen� Dieses kann dazu f�uhren� dass aufgrund des nicht vollst�andig

materialisierten neuen Zustandes und der negativen Referenz auf den E�ektivit�atstest�

Anfragen gebildetet werden� die nicht notwendig sind� Das Ergebnis ist korrekt�

De�nition �� Sequenzieller Ableitungsoperator�� Sei D � hF �Ri eine deduktive

Datenbank� R��R� zwei disjunkte Teilregelmengen von R und I HD� Der sequenzielle

Ableitungsoperator ist dann de�niert als�

TR��R��I �� TR�

� lfp �T �R�� I

Die entsprechende Ab�anderung des DPA�Algorithmuses mittels �Anderungspropagierung�

�� i ��

�� DT ��




�� repeat

�� i �� i ��

�� NDFi �� lfp�TR�NDF �RNDFnew �F ��DTi�� DT �NDF jndf �� DT �� DT � tf��DTi��




Die Anwendung des Fixpunktoperators T �R innerhalb des neu de�nierten Ableitungsope�

rators ist f�ur naive Transitionsregeln g�ultig� weil im Rahmen der Transitionsregeln f�ur

negative Propagierungsregeln negative Literale nur in Bezug auf virtuelle Basisfakten vor�

kommen�


Die Auswertung der Beispieldatenbank mittels sequenziellem Fixpunktoperator liefert ge�

nau die gleichen DPA�Fixpunkts�aulen wie T �D�

Der Vorteil des sequenziellen Fixpunktoperators ist� dass Folge�anderungen dann abgelei�

tet werden� wenn die Antwort des E�ektivit�atstest vorliegt� Die Antwort wird aus den

Folge�anderungen der letzten Ableitungsrunde materialisiert�

�� T�D versus sequenzieller Fixpunktoperator

Die beiden Fixpunktoperatoren berechnen die gleichen Fixpunkte der ��NDF �Folge�anderungen�

Die sich an diesem Punkt stellende Frage ist die nach dem Ableitungsaufwand� Wie lang

ist der Weg zur Erreichung des Fixpunktes� das heisst� mit wievielen Ableitungsrunden

und abgeleitet Fakten wird der kleinste Fixpunkt hergeleitet�

Unter der Annahme� dass ein Fixpunkt einer Regelmenge zu einer Faktenmenge bei gege�

benem Ableitungsoperator genau dann erreicht ist� wenn zwei Ableitungsrunden das selbe

Ergbnis liefern� wird anhand der Beispieldatenbank intuitiv argumentiert� Betrachtet wird

die Fixpunktberechnung der ersten ��NDF� Menge�

DPA mittels Magic�Set �Anderungspropagierungs unter Verwendung von T �D�

�� Runde� ndf e�� m ndf enew��


Das sind die Folge�anderungen� simultan berechnet mit den Anfragen

m ndf pnew�� m ndf pnew�� m ndf pnew�� m ndf pnew��

Das sind Anfragen� die Anwortrelationen sind leer




m ndf pnew�� m ndf pnew�� m ndf pnew�� m ndf pnew�� m ndf pnew��







m ndf pnew��






m ndf pnew��


�� Runde � �� Runde� der Fixpunkt ist erreicht� Die Summe der Fakten in den Ableitungs�

runden betr�agt �� Die Relationen der E�ektivit�atstests sind leer� weil alle abgeleiteten

Folge�anderungen echt sind� es wurden keine alternative Ableitungen f�ur die angefragten zu

l�oschenden Fakten gefunden�

DPA mittels Magic�Set �Anderungspropagierungs unter Verwendung von TR��R��

�x�a� � � � � x�z bezeichnen die inneren Ableitungsrunden

��a� Runde� m ndf enew�� m ndf pnew�� m ndf pnew�� m ndf pnew�� m ndf pnew��

��b� Runde� m ndf enew�� m ndf pnew�� m ndf pnew�� m ndf pnew�� m ndf pnew��

m ndf pnew��

��c� Runde� m ndf enew�� m ndf pnew�� m ndf pnew�� m ndf pnew�� m ndf pnew��

m ndf pnew�� m ndf pnew��

��d� Runde� m ndf enew�� m ndf pnew�� m ndf pnew�� m ndf pnew�� m ndf pnew��


��a� bis ��d� berechnen den Fixpunkt Anfrage� und Transitionsregeln

�� Runde� ndf e�� ndf p�� ndf p�� ndf p�� ndf p��

Die Folge�anderungen werden abgeleitet�

Ver�andern die Folge�anderungen den Fixpunkt der Transitionsregeln�

��a� Runde� m ndf enew�� m ndf pnew�� m ndf pnew�� m ndf pnew�� m ndf pnew��

��b� Runde� m ndf enew�� m ndf pnew�� m ndf pnew�� m ndf pnew�� m ndf pnew��


m ndf pnew��

��c� Runde� m ndf enew�� m ndf pnew�� m ndf pnew�� m ndf pnew�� m ndf pnew��


��d� Runde� m ndf enew�� m ndf pnew�� m ndf pnew�� m ndf pnew�� m ndf pnew��


��a� bis ��d� berechnen den Fixpunkt Anfrage� und Transitionsregeln

�� Runde� ndf e�� ndf p�� ndf p�� ndf p�� ndf p��

Die Folge�anderungen werden abgeleitet�

Es gibt keine neuen Folge�anderungen�

�� Runde � �� Runde� der kleinste Fixpunkt ist erreicht� Die Summe der Fakten in den

Ableitungsrunden betr�agt ��

Der direkte Vergleich beider Fixpunktimplementierungen bez�uglich der Beispieldatenbank

zeigt auf� dass T �D f�ur die diese Beispieldatenbank schneller den Fixpunkt erreicht� Ins�

besondere liegt dieser Umstand an der gegebenen Regel� und Faktenmenge� Gerade f�ur

diesen Fall sind die Antwortrelationen des E�ektivit�atstests leer und der T �D ��r�at� deshalb

apriori die echten Folge�anderungen richtig�

Der Nachteil des sequenziellen Fixpunktoperators ist die wiederholte innnere Fixpunktbe�

rechnung mit entsprechenden Fixpunkttest� weil nicht klar ist� ob durch die abgeleiteten

Folge�anderungen� sich der kleinste Fixpunkt der Transitionsregeln und Fakten ver�andert

hat�

Der Nachteil des T �D ist das Verhalten bei nicht leerem E�ektivit�atstest� F�ur solchen einen

Fall werden Folge�anderungen und Anfragen berechnet� die nicht notwendig sind� Inwiefern

sich das Problem auf die Anzahl der Ableitungsrunden auswirkt� h�angt sehr stark von

der Regel� und Faktenkonstellation ab� Beide Fixpunktverfahren stellen eine L�osung des

Strati�kationsproblems f�ur den DPA mittels Magic Updates dar�


�� L�osungsvorschlag � Angepasster schwacher Fix

punkt

Die Autoren Kerisit und Pugin haben in ihrer Ver�o�entlichung �KP�� gezeigt� dass nach ei�

ner Magic�Set Transformation einer strati�zierbaren Regelmenge eine nicht strati�zierbare

Regelmenge als Ergebnis herauskommen kann und ein entsprechendes e�zientes Fixpunkt�

verfahren f�ur die Problemklasse entwickelt� Ist dieser Fall eingetreten� so ist die Semantik

dieser schwach �un� strati�zierbaren Regelmenge immer zwei�wertig� Diese Regelmenge ist

auswertbar mit dem sogenannten ��schwachen Fixpunktverfahren��

In diesem Zusammenhang ist eine Regelmenge ��schwach strati�zierbar�� wenn es f�ur eine

Regelmenge eine Strati�kation gibt� f�ur die gilt�

Die Schicht P enth�alt nur Regeln mit positiven Literalen und in den dar�uber gelegenen

Schichten N�� Ni kommen nur Regeln vor� die mindestens ein negatives Literal bein�

halten�

De�nition �� Schwacher Ableitungsoperator�� Sei D � hF �Ri eine deduktive Da�tenbank� I HD eine variable Faktenmenge� P�N�� Nn eine schwache Strati�kation

auf R und TR der Ableitungsoperator f�ur strati�zierbare Regelmengen� Der schwache Ab�

leitungsoperator ist dann de�niert als�

TweakR �I �� if �TP �I � I � I �� then TP �I

else if �TN��I � I � I �� then TN�

�I else if �TN�

�I � I � I �� then TN��I

��

else TNn�I � I

Der kumulative schwache Fixpunktoperator ist dann de�niert als�

T �weakR �F �� Tweak

R �F � F

Die Funktionsweise des schwachen Fixpunktoperators kann wie folgt beschrieben werden�

Zun�achst wird der Fixpunkt der untersten� positiven Schicht gebildet� indem die Ablei�

tungsrunde TP �I mit der Input�Faktenmenge verglichen wird� Sind diese gleich� so istder Fixpunkt der P �Schicht erreicht� es wird in der n�achsten Schicht fortgefahren� Sind

diese beiden Mengen nicht gleich� so ist der Fixpunkt nicht erreicht� das Ergebnis der

Ableitungsrunde wird f�ur den kumulativen Fixpunktoperator ausgegeben�


In den oberen negativen Schichten wird eine Ableitungsrunde berechnet� Dieses Resultat

wird mit dem Input auf einen Fixpunkt getestet� Ist der Fixpunkt erreicht� so wird mit der

n�achsten Schicht weiter gemacht� Ist der Fixpunkt nicht erreicht� so wird das Ergebnis aus�

gegeben und mit der untersten Schicht wieder begonnen� weil die Ergebnisse der aktuellen

Schicht die Fixpunkte der unteren Schichten beein�ussen k�onnen� von denen sie negativ

abh�angig sind� Eine �ubergeordnete Schicht greift mindestens �uber ein Literal negativ auf

das Ergebnis einer unteren Schicht zu� Untere Schichten sind positiv abh�angig von oberen

Schichten�

Diese beschriebene Verfahren kann auf das Strati�kationsproblems f�ur negative Propa�

gierungsregeln mit Magic�Set Transformation angewendet werden� Hier sind dann die

Schichten bereits festgelegt� Die positive P Schicht besteht aus den naiven Transitionsre�

geln RNDFnew mit Magic�Set Transformation� Die negative N� Schicht setzt sich aus den

negativen Propagierungsregeln R�NDF zusammen� Die negativen Literale in den Transi�

tionsregeln beziehen sich immer auf virtuelle Basisrelationen und bed�urfen daher keiner

speziellen Behandlung� wie es eigentlich die De�nition der schwachen Strati�zierbarkeit

vorsieht� F�ur diesen Fall wird ein eigener angepasster schwacher Fixpunktoperator de��

niert�

TNDFweakR��R�

�I �� if �TR��I � I � I �� then TR�

�I else TR�

�I � I

Der kumulative schwache Fixpunktoperator ist dann de�niert als�

T �NDFweakR��R�

�F �� TNDFweakR��R�

�F � F

Der angepasste schwache Fixpunktoperator arbeitet im gleichen Sinne wie der sequenziel�

le Fixpunktoperator� Beide berechnen den Fixpunkt der Transitionsregeln� danach �ndet

eine Ableitungsrunde der negativen Propagierungsregeln statt� Der Fixpunkt ist dann

erreicht� wenn die Fixpunkte der Schichten erreicht sind� Der angepasste schwache Fix�

punktoperator vermeidet jedoch eine gewisse Anzahl an Fixpunkttests� Das zeigt intuitiv

die Teilauswertung der Beispieldatenbank� Es ist zu beachten� dass die Ergebnisse der Ab�

leitungsrunden kumuliert werden� Auf den kumulierten Ergebnissen wird der Fixpunkttest

der Schichten durchgef�uhrt� Die kumulierten Fakten werden nicht angegeben� Die Ablei�

tungsrunden�

R�� m ndf enew�� m ndf pnew�� m ndf pnew�� m ndf pnew�� m ndf pnew��



m ndf pnew��





R�� ist der Fixpunkttest� der Fixpunkt der �� Schicht ist erreicht�

Weiter eine Schicht h�oher�

R�� ndf e�� ndf p�� ndf p�� ndf p�� ndf p��

R�� der Fixpunkttest von Schicht � ist nicht erf�ullt�

Weiter in Schicht ��



R�� ist der Fixpunkttest� der Fixpunkt der �� Schicht ist erreicht�

Weiter eine Schicht h�oher�

R�� ndf e�� ndf p�� ndf p�� ndf p�� ndf p��

Der Fixpunkttest von Schicht � ist erf�ullt�

Der Fixpunkt beider Schichten ist erreicht� der gemeinsame Fixpunkt ist erreicht�

Der angepasste schwache Fixpunktoperator leitet insgesamt durch die Vermeidung von

Ableitungsrunden f�ur die Fixpunkttests �� Fakten zur Fixpunkt�ndung her� Im Vergleich

dazu ben�otigte T �D �� Fakten und der sequenzielle Fixpunktoperator ��

Aus der Perspektive der Beispieldatenbank her zu argumentieren� ist der angepasste schwa�

che Fixpunkt wegen seiner Einsparungen in den Fixpunkttest im Vergleich zum sequen�

ziellen Fixpunktoperator e�zient� Der angepasste schwache Fixpunkt kann durchaus als

eine Implementierung des sequenziellen Fixpunktoperators aufgefasst werden�

Der Vorteil dieses Fixpunktoperators ist die Vermeidung von Ableitungsrunden� die dem


Fixpunkttest dienen�

�� Resume

Die Anforderungen des vorigen Kapitels den E�ektivit�atstest� also die Berechnung des neu�

en Zust�ande der Relationen auf ��relevante� Fakten zu beschr�anken ist erf�ullt worden� Das

Mass der E�zienz h�angt im wesentlichen von der gegebenen Regel� und Faktenmenge ab�

Die E�zienz wird durch die Di�erenz zwischen zwei gleichartigen DPA�S�aulen massgeblich

gepr�agt� Schw�achen der Magic�Set Transormation wurden in diesem Zusammenhang aufge�

zeigt� Die Strati�kationsproblematik einer Regelmenge mit positiven Zyklen wurde durch

vier L�osungsvorschl�age diskutiert� Durch die gegebenen Annhamen und Voraussetzungen

erweist sich der Einsatz des angepassten schwachen Fixpunktoperators als eine geschickte

L�osung des Strati�kationsroblems�

Kapitel

Zusammenfassung und Ausblick

Ziel dieser Diplomarbeit war die Untersuchung� wie das alternierende Fixpunktverfahren

nach van Gelder �VG�� VG�� in der Implementierung des Doubled Program�Ansatzes

von �KSS�� KSS�� mittels Magic Updates e�zienter realisiert werden kann�

Im Verlauf dieser Arbeit wurde zun�achst allgemein auf deduktive Datenbanken eingegan�

gen� Es wurden Verfahren zur Bedeutungsbestimmung strati�zierbarer deduktiver Daten�

banken pr�asentiert� Im weiteren Verlauf wurde anhand von Beispielen die Problematik der

Bedeutungsbestimmung nicht strati�zierbarer Datenbanken erl�autert� Es wurde gezeigt�

dass f�ur diese Art deduktiver Datenbanken drei�wertige Semantiken geeignet sind� Dabei

h�angt es von den gegebenen Fakten ab� ob unde�nierte Fakten ein Teil der Bedeutung

ausmachen� Zur Bestimmung der allgemeinen Bedeutung einer deduktiven Datenbank

wurde die Herbrand�Basis verwendet� welche alle Fakten enth�alt� die aus den verwendeten

Relationssymbolen und Konstanten konstruiert werden k�onnen�

Fixpunktverfahren� die nicht strati�zierbare Datenbanken auswerten� unterteilen die zu�

geh�orige Herbrand�Basis in Teilmengen wahrer� unde�nierter und falscher Fakten� Not�

wendig ist dabei lediglich die Ermittlung zweier Mengen� da die dritte implizit gegeben

ist�

Aus der Vielzahl m�oglicher Fixpunktverfahren wurden zwei Verfahren n�aher erl�autert� die

diese Einteilung leisten� Es wurde das Conditional Fixpunkt�Verfahren von Bry vorgestellt�

welches durch eine einmalige Fixpunktphase ohne Auswertung negativer Literale und dar�

aus resultierende bedingte Fakten charakterisiert ist� Letztere k�onnen in der zweiten Phase

durch Auswertung der aktuell wahren und falschen Fakten in der Datenbank reduziert wer�

den� Als Ergebnis wurden dann die Mengen der unde�nierten �bedingten Fakten und der

wahren Fakten ausgegeben� Ein Nachteil dieses Verfahrens ist die m�oglicherweise sehr gros�

�

KAPITEL � ZUSAMMENFASSUNG UND AUSBLICK �

se Anzahl abgeleiteter bedingter Fakten� da bei allen unde�nierten Fakten der implizite

Grund im Bedingungsteil erhalten wird�

Das zweite vorgestellte Verfahren basiert auf dem alternierenden Fixpunkt� dessen Berech�

nung durch die abwechselnde �Uber� und Untersch�atzung falscher Fakten gekennzeichnet

ist� Eine Implementierung des AFPI ist der Doubled Program�Ansatz� der das explizite

Arbeiten mit der Herbrand�Basis vermeidet� Er tranformiert die Regeln in zwei strati�zier�

bare Regelmengen� die getrennt voneinander ausgewertet werden und sich gegenseitig als

negative Referenzmenge dienen� Ein wesentlicher Nachteil dieses Ansatzes ist die wieder�

holte Fixpunktbildung � Ziel dieser Arbeit war es� die Zahl der Herleitungen zu reduzieren

und nicht immer die vollst�andigen Fixpunkte zu materialisieren zu m�ussen�

Hierzu wurde eine Technik zur �Anderungspropagierung mit der Magic�Set Methode kombi�

niert� Die Kombination vermeidet die vollst�andige Simulation des neuen Datenbankzustan�

des und berechnet die relevanten Fakten� welche gerade notwendig sind Folge�anderungen

herzuleiten�

Folgende Kapitel untersuchten� in wieweit die Methode zur �Anderungspropagierung die

Implementierung des DPA verbessert� Es wurde herausgestellt� dass die NDF �S�aulen mo�

noton abnehmend sind� da im Vergleich zur Vorg�anger NDF �S�aule nur Fakten gel�oscht

werden � Anderseits wuchsen die DT �S�aulen monoton an� weil ausschliesslich nur Fakten

eingef�ugt werden� L�oschungen in der NDF �S�aule f�uhren zu Einf�ugungen in die DT �S�aule�

und Aufgabe der �Anderungspropagierung war es� die Einf�ugungen in dem einen Fall und

die L�oschungen in dem anderen Fall per Basisdaten�anderungen mitzuteilen� Insofern mus�

ste nur die Konsequenzen aus den �Anderungen berechnet werden� so dass eine vollst�andige

Materialisierung der S�aulen nicht mehr notwendig war� Dieser Ansatz verringerte jedoch

zun�achst nicht den Gesamtaufwand des Verfahrens� da der Wegfall wiederholte Ableitungen

hergeleiteter Fakten f�ur die �Anderungspropagierung� insbesondere f�ur die Zustandssimula�

tion gegen�uber stand� Es war demnach an dem vorgef�uhrten Beispiel zu erkennen� welche

Einsparungen potenziell enthalten sind�

Diese Erkenntnisse wurden f�ur das n�achste Kapitel genutzt� in dem das DPA um Magic

Updates erweitert wurde� Die Betrachtung des even Beispiels zeigte den Vorteil dieser

Kombination� Im Wesentlichen wurden nur noch die �Anderungen betrachtet� sowie ein

kleiner Verwaltungsaufwand f�ur die Magic�Set Relationen� Eine Erweiterung des Beispiels

um die Berechnung der transitiven H�ulle zeigte jedoch ein Strati�kationsproblem� Re�

geln mit positivem Zyklus sind f�ur dieses Problem im Zusammenhang mit Magic Updates

verantwortlich� In den folgenden Abschnitten wurden L�osungsvorschl�age unterbreitet� die

insbesondere an abge�anderten Fixpunktoperatoren ansetzten� Diese Operatoren hatten

zum Ziel� den Magic�Set transformierten E�ektivit�atstest vollst�andig vor der Berechnung

KAPITEL � ZUSAMMENFASSUNG UND AUSBLICK �

der Folge�anderungen durchzuf�uhren� da diese sich negativ darauf bezogen� Diese Schritte

wurden dann wiederholt angewandt� Das Beispiel zeigte dabei� dass die Anwendung des

schwachen Fixpunktoperators die wahrscheinlich beste L�osung darstellt�

Ausblick� Das gesamte Verfahren� sowie die vorgeschlagenen Fixpunktoperatoren m�ussen

implementiert werden und auf Tauglichkeit mittels verschiedener Testdatenbanken gepr�uft

werden�

Ferner ist die Rolle der Magic�Set Transformation zu untersuchen und diese hinsichtlich

der erzeugten Unteranfragen zu verbessern� Die Beispiele in dieser Arbeit hatten gezeigt�

dass Magic�Set transformierte Regeln Anfragen produzieren k�onnen� die so keinen ��Sinn�

machen und damit das Ergebnis ��verschlechtern��

Desweiteren sollte der Fragestellung nachgegangen werden� ob und wie man ein modi�zier�

te Art von �Anderungspropagierung einsetzen kann� welche die alternative Ableitbarkeit

von zu l�oschenden Fakten mit weniger Schritten heraus�ndet� Im Zusammenhang damit

steht die Frage wie die transformierten Regelmengen kleiner gehalten werden k�onnen�

Fazit� Bekannte Techniken und Verfahren aus der deduktiven Datenbankforschung wurden

in ihrer Kombination dazu genutzt das alternierende Fixpunktverfahren in seiner DPA�

Realisierung e�zient zu gestalten� Diesem Anspruch wurde gen�uge getan�

Literaturverzeichnis

�BMSU�� F� Bancilhon� D� Maier� Y� Sagiv� and J� Ullman� Magicset and other strange

ways to implement logic programs� in Proc� of the �th ACM SIGMOD�SIGACT

Symp� on Principles of Database Systems� ��

�Bry�� Francois Bry� Logic Programming as Constructivism� A Formalization and

ist Application to Databases� In Proceedings of the Eighth ACM SI�GACT�

SIGMOD�SIGART Symposium on Principles of Database Sy�stems� March ��

�� Philadelphia� Pennsylvania� pages �� ACM Press� ��

�Bry�� Francois Bry� Negation in Logic Programming� A Formalization in Construc

tive Logic� In Dimitris Karagiannis� editor� Information Systems and Arti�cial

Intelligence� Integration Aspects� volume �� of LNCS� pages �� Springer�

��

�Gri�� U� Griefahn� Reactive Model Computation� A Uniform Approach to the Imple

mentation of Deductive Databases� Bonn� ��

�KP�� Kerisit� J�M� and Pugin J�M� E�cient query answering on strati ed databases�

In Proceedings of the Int� Conf� on Fifth Generation Computer Systems� ��

�KSS�� Kemp� Srivasta und Stuckey� Magic sets and bottomup evaluation of well

founded models� In Proceedings of the �� International Symbosium on Logic

Programming� San Diego� California� ��

�KSS�� Kemp� Srivasta und Stuckey� Bottomup evaluation and query optimization of

wellfounded models� Theoretical Computer Science� ��

�VG�� A�v�Gelder� The alternating xpoint of logic programs with negation� In Procee�

dings of the � th ACM SIGMOD�SIGACT�SIGART Symposium on Principles

of Database Systems� Philadelphia �� ACM Press ��

�

LITERATURVERZEICHNIS �

�VG�� A�v�Gelder� The alternating xpoint of logic programs with negation� Journal

of Computer Sciences� ��

�VGRS�� Van Gelder� A�� K�A� Ross� and J�S� Schlipf� The WellFounded Semantics for

General Logic Programs� Journal of the ACM �� !��

�ZF�� U� Zukowski� B� Freitag� The Di�erential Fixpoint of General Logic Programs�

Proc� of the Workshop on Deductive Databases and Logic Programming� �th

Workshop in conjunction with JICSLP"�� Bonn� Germany� September � ! ��

�� volume �� of GMD�Studien� pages �� St�Augustin� Germany� ��

�Tar�� A� Tarski� A latticetheoretic xpoint theorem and its applications� Paci�c J�

Math� ��!��

Documents

Rheinisc - idb.uni-bonn.de · Resume Zusammenfassung und Ausblic k. Einleitung Die Seman tik deduktiv er Daten bank en wird gew ohnlic h mittels Fixpunktop eratoren de niert w elc