Nächste Seite: 4.3 Fazit Vorige Seite: 4.2.2 Die Methode von

4.2.3 Counting- und DRed-Algorithmus

 

In [GMS93] werden zwei Algorithmen zur inkrementellen Sichtenwartung präsentiert. Der Counting-Algorithmus zählt die unterschiedlichen Herleitungen eines Elements in der Sicht und speichert diesen Wert zusätzlich ab. Bei Änderungen werden diese Werte von den Basisprädikaten ausgehend aktualisiert. Wenn der Wert 0 ist, wird das zugehörige Element gelöscht. Sichere und stratifizierte Negation und Aggregation (z.B. Summierung und Durchschnitt von Attributen) sind in der Sichtendefinition erlaubt. Da es in rekursiven Sichten eine unendliche Anzahl von verschiedenen Herleitungspfaden geben kann, ist dieser Algorithmus nur auf nicht-rekursive Sichten anwendbar.

Die Basisrelation link entspricht der Menge . Das Prädikat hop wird definiert als Join von zwei Verbindungen:

Darauf basierend definiert man nun das Prädikat :

Die abgeleiteten Relationen sind somit

Ein *2 hinter einem Tupel bedeutet, daßes für dieses Tupel zwei alternative Ableitungspfade gibt.

Seien nun die Änderungen der Basisrelation gegeben durch , d.h. (a,b) wird gelöscht, (d,f) und (a,f) werden eingefügt. Daraus ergibt sich als neue Extension für die Basisrelation

Die Mengenoperation vereinigt zwei Mengen und beachtet dabei auch die Counts der einzelnen Tupel. Die Delta-Regeln für ein Prädikat werden aus den Original-Regeln durch ersetzen eines Literals im Rumpf durch das entsprechende Delta-Literal erzeugt. Für jede Regel r der Form

werden die Delta-Regeln generiert, die das Prädikat definieren:

Zunächst werden die Delta-Regeln für v1 bestimmt und berechnet, da die Regel v2 selbst von der Regel v1 abhängt.

Das ergibt dann und damit . Nun können die Delta-Regeln für v2 angewendet werden:

Daraus folgt und .

Der DRed-Algorithmus (delete and rederive) kann im Gegensatz zum Counting-Algorithmus auch rekursive Sichten warten. Der Algorithmus besteht aus drei Phasen: zuerst wird eine Obermenge der tatsächlich zu löschenden Tupel gelöscht und anschließend die Tupel mit alternativen Ableitungspfaden wieder eingefügt. In der dritten Phase werden die Einfügungen für intensionale Prädikate mit einer Variante der semi-naiven Methode [Ull88] berechnet. Die Regelmenge mußfür die Auswertung in disjunkte Schichten unterteilt werden, so daßdie Regeln einer Schicht nur von den unteren Schichten abhängig sind. Für jede Schicht müssen dann die einzelnen Schritte des DRed-Algorithmus angewendet werden, die nachfolgend genauer beschrieben sind:

• Lösche eine Obermenge der abgeleiteten Tupel, die gelöscht werden müssen.
  Für jede Regel r der Form

  

  erzeuge -Regeln der Form:

  

  Wenn Basisrelation ist, dann ist die gegebene Menge zu löschender Tupel. Ist schon in einer vorherigen Schicht berechnet worden, so sind in die wirklich gelöschten Tupel von enthalten, d.h. ist keine Abschätzung. Sonst ist die momentane Abschätzung der zu löschenden Tupel, die durch diese Regeln ermittelt wurde. Mit werden die bisherigen Relationen bezeichnet, ohne die aktuellen Veränderungen zu berücksichtigen. Dies gilt auch für die Basisrelationen und in den vorherigen Schichten ausgewertete Relationen. Die -Regeln werden solange angewendet, bis ein Fixpunkt erreicht ist.

• Füge die Tupel mit alternativen Ableitungen wieder ein.
  Erzeuge für jede Regel r eine -Regel:

  

  Dabei ist ist die in Schritt 1 berechnete Menge von Tupeln. Für ist der jeweils aktuelle Wert, der in Schritt 1 und 2 bisher berechnet wurde, bzw. der neue gegebene Wert der Basisrelation einzusetzen. Die -Regeln sind solange anzuwenden, bis ein Fixpunkt erreicht ist.

• Nur dann anwenden, wenn in den Basisrelationen Tupel eingefügt worden sind.
  Erzeuge für jede Regel r n -Regeln:

  

  ist wie oben der aktuelle Stand bzw. die Änderungen der Basisrelationen. entspricht dem Ergebnis aus Schritt 1 und 2, und den aktuellen Änderungen. Auch diese -Regeln sind solange anzuwenden, bis ein Fixpunkt erreicht ist.

Der DRed-Algorithmus kann ebenfalls auf Negation und Aggregation erweitert werden und auch auf nicht-rekursive Sichten angewendet werden, jedoch ist der Counting-Algorithmus für nicht-rekursive Regeln effizienter.

Auch hier wird die Sicht EmpDept verwendet. Die Definition der Regeln erfolgt wie im vorherigen Beispiel in Datalog-Syntax.

1. Schritt: Löschen einer Obermenge, der tatsächlich zu löschenden Tupel.

2. Schritt: Alternative Herleitungspfade berücksichtigen.

3. Schritt: Einfügungen berechnen

Für eine effiziente Auswertung mit diesem Algorithmus, müssen nicht nur die Sichten, sondern alle abgeleiteten Daten materialisiert sein, also auch Zwischenergebnisse bei der Berechnung der Sichten. Für den Fall, daßdiese Daten nicht materialisiert worden sind, wird in [SJ96] der RoD-Algorithmus (Rederivation on Demand) vorgestellt. Der Algorithmus ist eine Erweiterung des DRed-Algorithmus. Die Delta-Regeln werden dabei auf eine Magic-Set-ähnliche Art umgeschrieben und mit einem Bottom-Up-Fixpunktverfahren ausgewertet.