Abb.1 : DWH mit materialisierten Sichten (Quelle: [LQA97])
In den letzten Jahren gewann das Thema Data Warehousing (DWH) immer mehr an Bedeutung. In einem DWH werden Daten von verteilten, heterogenen Datenbanken gesammelt. Diese Datenmengen können sehr mächtig sein und es kann eine große Anzahl von Anfragen auf ihnen gestellt werden. Um ein DWH effektiv zu nutzen, werden materialisierte Sichten verwendet.
Dieser Text ist in vier Abschnitte aufgeteilt. In der Einführung werden folgende Fragen beantwortet:
Im vierten und letzten Teil findet man eine Zusammenfassung und Informationen über Ausblicke sowie Literaturhinweise.
Ein DWH beinhaltet in der Regel große Mengen an Daten. Weiterhin werden häufige und komplexe Anfragen auf dem DWH gestellt. Dies erfordert eine hohe Effizienz beim Zugriff auf die Daten, d.h. bei der Beantwortung von Anfragen. Die Verwendung von redundanten Strukturen und Parallelismus bei der Bearbeitung von Anfragen kann die Effizienz erhöhen. Sichten (Views) sind aus Basisrelationen abgeleitete virtuelle Relationen. Es gibt zwei Ansätze zum integrierten Zugriff auf mehrere, verteilte und heterogene DBS:
Materialisierte Sichten ist eine Technik dabei, welche den Anfrageprozeß effizienter machen kann. Eine Sicht zu materialisieren heißt, das Ergebnis einer Sicht (die Tupel) im DWH zu speichern. Unmaterialisierte Sichten sind virtuelle Sichten.
Abb.1 : DWH mit materialisierten Sichten (Quelle: [LQA97])
Die Abb.1 zeigt auf abstrakter Weise die Verwendung von materialisierten Sichten. Von mehreren Quellen aus werden ausgewählte Relationen extrahiert. Nach einer Bearbeitung (nur Daten von Interesse; heterogene Quellen) werden diese als Basisrelationen im DWH abgespeichert. Auf den DWH werden Anfragen gestellt. Die materialisierten Sichten liegen zwischen den Anfragen und den Basisrelationen.
Der Vorteil, der sich aus materialisierten Sichten ergibt, ist die schnellere Antwortzeit besonders bei hoher Anfragerate und hoher Komplexität der Anfragen, da das Ergebnis nicht neu berechnet werden muß, sondern nur die gespeicherten Tupel abgerufen werden. Die Nachteile sind zusätzliche Kosten für die Speicherung (redundante Struktur) und die Pflege der materialisierten Sichten bei einem Update auf Basisrelationen.
Es stellt sich die Frage, welche Anfragen beantwortet werden sollen, d.h. welche Anfragen sollen bei der Ermittlung der zu materialisierenden Sichten betrachtet werden. Durch Statistiken oder einfach aus dem Zweck des DWH lassen sich diejenigen Anfragen auswählen, welche eine komplexe Struktur haben und bzw. oder häufig gestellt werden.
Nun stellt sich die Frage, welche Sichten zu materialisieren sind. Es sollten alle ausgewählten Anfragen mittels materialisierten Sichten effizienter beantwortet werden. Jedoch kann es auch vorkommen, daß durch die Verwendung der materialisierten Sichten das DWH ineffizienter wird. Wenn hier von Sichten gesprochen wird, sind damit eigentlich Teilsichten gemeint. Die Erklärung folgt später. Wenn man alle Sichten materialisiert (alle Ergebnisse der Anfragen), erhält man die beste Leistung, da keine Zugriffe auf den Basisrelationen notwendig sind. Jedoch sind die Kosten für die Pflege der Sichten sehr hoch. Läßt man alle Sichten virtuell, bleibt die Leistung schlecht, aber es entstehen auch keine Kosten für die Pflege. Um eine optimale Lösung mit hoher Leistung und niedrigen Kosten zu erhalten, muß eine bestimmte Auswahl der Sichten materialisiert werden. Es kann aber auch möglich sein, daß die Pflege so kostenintensiv ist, daß die Verwendung von materialisierten Sichten ineffizient wird. Welche Kriterien muß nun die Auswahl haben?
Weiterhin muß geklärt werden, wie und wann Sichten gepflegt werden sollen. Pflege der materialisierten Sichten wird nötig durch Updates auf Basisrelationen. Nun muß ein effizientes Update der materialisierten Sichten gefunden werden, da bei der Pflege entstehende DB-Operationen in Konflikt mit gestellten Anfragen kommen können. Die Pflege der Sichten kann bei Nichtbenutzung des DWH (z.B. bei Nacht) geschehen. Jedoch muß die Pflege nach einer bestimmten Zeit fertig sein. Außerdem ist durch die Globalisierung ein Zugriff bei Nacht erwünscht. Eine zweite Möglichkeit ist die direkte Pflege nach einem Update auf die Basisrelationen. Wann die materialisierten Sichten zu pflegen sind, hängt somit vom Verwendungszweck des DWH ab.
Das Ziel ist es, daß die ausgewählten Anfragen mittels materialisierter Sichten effizienter beantwortet werden können und die Kosten für die Nutzung minimal werden. Dabei muß eine bestimmte Auswahl der zu materialisierenden Sichten gefunden werden. Man beachte dabei die Kosten für das Abarbeiten der Anfragen und für die Pflege. Weiterhin muß ein effizienter Algorithmus zum Updaten der materialisierten Sichten angewendet werden. Die Anwendung von bestimmten Algorithmen zur Auswahl und Pflege von materialisierten Sichten ist das Thema dieses Textes.
In der Literatur werden eine Reihe von verschiedenen Algorithmen zur Auswahl der zu materialisierenden Sichten vorgestellt. Zunächst wird jedoch das allgemeine Problem spezifiziert.
Ein DWH beinhaltet mehrere Basisrelationen R. Über den DWH werden Anfragen Q gestellt. Dabei können einige temporäre Ergebnisse Tmp für mehrere Anfragen genutzt werden. Diese temporären Ergebnisse werden nun im weiteren Text Sichten genannt. Auf den Resultaten Res werden dann durch weitere Projektionen und Selektionen die Anfragen beantwortet. Ein graphisches Beispiel gibt Abb.2.
Abb.2 : Mehrfach-Anfragen-Prozeß-Plan (Quelle: [YKL97])
Werden alle temporären Resultate, also Sichten, materialisiert, entstehen sehr geringe Kosten für den Anfrageprozeß. Es werden nur die gespeicherten Tupel abgerufen. Jedoch ist die Pflege sehr aufwendig, d.h. mit hohen Kosten verbunden, da diese Tupel eine große Anzahl von redundanten Strukturen sind. Im Beispiel bringt die Materialisierung von Temp6 keine Leistungserhöhung, da bei der Anfrage auf Temp7 oder auf Temp8 zugegriffen wird. Materialisiert man keine Sichten, so kommen zwar keine Kosten für die Pflege zustande, aber der Anfrageprozeß ist nur mit sehr hoher Rechenleistung zu bewältigen, besonders bei der Verwendung von komplexen Anfragen mit vielen Joins auf mächtigen Basisrelationen. Es muß eine geeignete Auswahl der zu materialisierenden Sichten gefunden werden. Dabei sollen die Kosten für die Bearbeitung der Anfragen und Pflege der Sichten minimal sein.
| materialisierte Sichten | Kosten für Anfrage | Kosten für Pflege | Kosten total |
|---|---|---|---|
| keine | 8.980.860k | 0 | 8.980.860k |
| tmp3, tmp4, tmp8 | 7.201.547k | 1.350.125k | 8.551.672k |
| tmp3, tmp5 | 416.747k | 16.032.204k | 16.448.951k |
| tmp3, tmp4, tmp7 | 7.276.497k | 1.220.055k | 8.496.552k |
| tmp3, tmp7 | 8.281.547k | 126.122k | 8.407.669k |
| res1, res2, res3, res4 | 1.447k | 17.384.934k | 17.386.381k |
Zur Veranschaulichung ein durchgerechnetes Beispiel in Tabelle1 für die oben gezeigte Abb.2. Als Kostenmaß dient dabei die Anzahl der Tupel, die für die Anfrageverarbeitung bzw. die Sichtenpflege verarbeitet werden müssen, falls die entsprechende Auswahl von Sichten materialisiert sind.
Es ist ersichtlich, daß ohne materialisierte Sichten der Anfrageprozeß sehr großen Rechenaufwand nach sich zieht (rund 9G Tupel). Wenn man alle Resultate materialisiert, entstehen hohe Kosten für die Pflege (rund 17G Tupel), aber die geringsten Kosten für den Anfrageprozeß. Es muß eine geeignete Auswahl getroffen werden. In der dritten und fünften Zeile wurden jeweils zwei Teilsichten materialisiert, jedoch die Gesamtkosten sind um den Faktor zwei verschieden. Die Ersparnis ist hier gegenüber der Verarbeitung ohne materialisierten Sichten sehr gering. Es gibt Fälle, in welchen die Ersparnis sehr hoch ist, aber auch Fälle, in welchen es keinen Kostengewinn gibt. In diesem Fall ist es abzuraten, materialisierte Sichten zu nutzen.
Es muß also eine geeignete Auswahl gefunden werden. Dieses Auswahlverfahren ist jedoch hoch komplex. Die Häufigkeit der Anfragen und die Häufigkeit von Updates auf Basisrelationen ist dabei auch entscheidend und kann mit Hilfe von Statistiken ermittelt werden. Der allgemeiner Algorithmus muß folgendermaßen aussehen:
Ein MVPP-Graph ("Multiple View Processing Plan") zeigt die Strategie der Verarbeitung von Anfragen im DWH (siehe Abb.2). Als erstes jedoch einige Spezifikationen.
Zur Beschreibung eines MVPP benötigt man ein Sechs-Tupel (V, A, Cqa, Crm, fQ, fU). V sei die Menge aller Knoten (Basisrelationen, Sichten, Anfragen) und A sei die Menge aller Bögen über V. Es sei u->v, wenn ein Knoten u zur Berechnung von v benötigt wird. L sei nun die Menge aller Knoten, welche eine Basisrelation beschreiben. Für jedes v aus L sei fU(v) die Häufigkeit von Updates auf die Basisrelation. R sei nun die Menge aller Anfragen. Für jedes v aus R sei fQ(v) die Häufigkeit der Anfrage. Cqa(v) beschreibt die Kosten für die Berechnung (access) von v beim Zugriff auf Anfrage (query) q. Crm(v) beschreibt die Kosten für die Pflege der materialisierten Sicht (materialized view) v bei einem Update auf Basisrelation (base relation). Ein Beispiel ist der oben gezeigte Graph (siehe Abb.2). Die Anfragen sind mit Nummern gekennzeichnet, welche deren Häufigkeit anzeigen.
Ein MVPP ist ein gerichteter, azyklischer Graph. Es gibt mehrere mögliche Graphen für dieselben Basisrelationen und Anfragen. Es wird nun mit dem "0-1 Integer Programming Solution" Algorithmus der kostengünstigste MVPP ermittelt. Nach diesem werden die zu materialisierenden Sichten ausgewählt. Für diese Algorithmen benötigt man Kostenfunktionen. Die Kostenanalyse sieht wie folgt aus:
Der Wert nv sei die Anzahl der Anfragen, welche auf v liegen. Es sei bemerkt, daß Cqa(v)=0, wenn die Anfrage q nicht auf die Sicht v zugreifen muß. Ebenso ist Crm(v)=0, wenn die Sicht v die Basisrelation r nicht benutzt.
Ziel ist es, das Sechs-Tupel, besser die Menge A, zu finden, so daß Ctotal minimal wird. Dies ist abhängig von
Dieser Algorithmus besteht aus drei Teilen. Als erstes werden select, project und aggregation Operationen der Sichten "hochgezogen" zu den Resultaten (pull up). Daraufhin wird der MVPP transformiert zum optimalen MVPP. Als letztes werden die select, project und aggregation Operationen wieder "runtergeschoben" (push down).
Das pull up und push down basiert auf Relationenalgebra. Die Transformation geschieht mit Hilfe vom "0-1 Integer Programming Solution" Algorithmus. Da alle select-, project- und aggregation- Operationen hochgeschoben sind, betrachtet man nur noch join-Operationen. Durch diesen Algorithmus wird der optimale Anfrageprozeß unter den gegebenen Annahmen ermittelt. Materialisierte Sichten bleiben erstmal außen vor. Weitere Notationen sind nun nötig.
Es gibt k globale Anfragen (q1, q2, ..., qk). Für alle Anfragen q gibt es eine Menge von möglichen Join Plan Trees p (binäre Bäume mit Join Operationen als Knoten). Für alle Bäume einer Anfrage q sei p eine geordnete Liste der Form p(R,S) mit R, S sind Teilbäume von p. Für alle Join Plan Trees p sei s Join Pattern oder Teilbaum von p. Die Menge aller Join Plan Trees einer Anfrage q sei p(q) = {pi : pi sei Join Plan Tree von q}. Die Menge aller möglichen Join Plan Trees n aller Anfragen sei P = Vereinigung[i=1...k] p(qi). Die Menge aller Join Patterns eines Join Plan Trees p sei s(p) = {si : si sei Join Pattern von p}. Die Menge aller möglichen Join Patterns m aller Join Plan Trees sei S = Vereinigung[i=1...n] s(pi). Hierzu ein Beispiel zu den MVPP von oben (siehe Abb.2).
Man erhält zwei Mengen. Die Menge P mit allen möglichen Join Plan Trees (Abfragebäume der Anfragen) und die Menge S mit allen möglichen Join Patterns (Teilbäume der Join Plan Trees). Nun wird ein Algorithmus angewandt, der die günstigsten Join Plan Trees ermittelt. Zuerst werden zwei Matrizen konstruiert. Die Dimensionen sind n (Anzahl der Join Plan Trees), k (Anzahl der Anfragen) und m (Anzahl der Join Patterns).
Beispiel von oben:
| A= | ( 1 0 0 0 0 0 0 ) ( 0 0 1 1 0 0 0 ) ( 0 1 0 0 0 0 0 ) ( 0 0 0 0 1 1 1 ) | B= | ( 1 0 1 0 1 1 0 ) ( 0 0 1 0 0 1 0 ) ( 0 0 0 1 0 0 1 ) ( 0 0 0 1 0 0 1 ) ( 0 1 0 0 1 0 0 ) ( 0 0 0 0 1 0 0 ) ( 0 0 0 0 0 1 0 ) ( 0 0 0 0 0 0 1 ) |
|---|
Der "0-1 Integer Programming Solution" Algorithmus findet die Menge an Join Plan Trees, welche alle Anfragen beantworten, und die Kosten für die Anfragenbearbeitung sind minimal. Dabei wird pro Anfrage ein Join Plan Tree ausgewählt, jedoch kann man unter Umständen ein Join Pattern für mehrere Anfragen nutzen. Man betrachte dabei die kleinsten Kosten der Join Patterns. Tabelle2 vergleicht die Kosten der Join Patterns vom begleitenden Beispiel. Die Variable xi sei binäre Variable mit 1 wenn Join Plan Tree pi betrachtet wird.
| Patterns | s1 | s2 | s3 | s4 | s5 | s6 | s7 | s8 |
|---|---|---|---|---|---|---|---|---|
| nv | 3 | 2 | 2 | 2 | 2 | 1 | 1 | 1 |
| Ecost | 3.3*106 | 6*1013 | 6*109 | 6*1013 | 3*1011 | 1.2*1018 | 1.2*1018 | 1.2*1018 |
Die Auswahl von Join Plan Trees geschieht auf dem Weg, daß das kleinste x0 gesucht wird.
min x0=Summe[i=1...m] (Ecost(si))*{Summe[j=1...n] (bij*xj)} mit Summe[j=1...n] (aij* xi)=1 für jede Anfrage qi und Ecost(si)=Summe[q aus R](fQ*Cqa(si)/nsi Kosten für jedes Join Pattern.
Diese Kostenfunktion wurde oben definiert (siehe Abschnitt 3.2.1.). Das Ergebnis ist die Liste von Join Plan Trees und damit der optimalen MVPP, d.h. die Anfragenbearbeitung mit den geringsten Kosten für die Berechnung der Anfragen. Im Beispiel sind das: p1, p2, p3, p6.
Es sei nun der optimale MVPP gegeben. Es werden die zu materialisierenden Sichten ausgewählt. Vorher jedoch noch einige Notationen. Ov sei die Menge der globalen Anfragen, welche v benutzen. Iv sei die Menge der Basisrelationen, durch welche v erzeugt wird. Sv sei Menge der Knoten, welche zum Erzeugen von v gebraucht werden. Dv sei die Menge der Knoten, welche von v aus noch erzeugt werden. Das Gewicht eines Knotens sei w(v)=Summe[q aus Ov](fQ(q)*Cqa(v)-Summe[r aus Iv](fU(r)*Crm(v)). Diese Formel berechnet die Ersparnis, falls v materialisiert ist. LV sei Liste von Knoten basierend auf absteigender Reihenfolge von allen positiven w(v). Wenn w(v) negativ ist, ist es sehr ineffizient diese Sicht zu materialisieren, da die Pflege der Sicht teurer wäre als die Berechnung der Anfragen, welche v benutzen.
Im fünften Schritt wird ein Knoten betrachtet in Bezug auf die Kosten Cs. Diese sind Kosten für Materialisierung und Pflege inklusive der Kosten im Fall, daß schon Sichten, welche zur Berechnung von v gebraucht werden, ausgewählt sind. Ein positiver Wert heißt Kostengewinn und die Sicht wird in M aufgenommen. Im siebenten Schritt wird der Suchraum weiter eingeschränkt. Wenn alle direkt folgenden Teilsichten, d.h. die aus einem Knoten berechnet werden, materialisiert sind, bringt es keinen Gewinn, die Sicht zu materialisieren. Deshalb werden diese Sichten im neunten Schritt gesucht und eliminiert. M ist die Menge der zu materialisierenden Sichten.
Zuerst wird der optimale MVPP ausgewählt. Der "0-1 Integer Programming Solution" Algorithmus findet diese optimale Lösung zur Anfragebearbeitung unter den gegebenen Voraussetzungen. Jedoch wird die Menge der Join Plan Trees und Join Patterns sehr mächtig bei vielen und sehr komplexen Anfragen. Da aber das Problem auf Matrizen mit nur Nullen und Einsen transformiert wurde, wird die Berechnung der Auswahl nicht so rechenaufwendig. Es ist auch möglich den MVPP auf anderem Wege zu ermitteln. Dieser Algorithmus würde aber den Rahmen hier sprengen. Jedoch wird dabei nicht sichergestellt, ob man den optimalen MVPP erhält. Im zweiten und eigentlichen Schritt zur Auswahl werden durch einen sehr einfachen Algorithmus die zu materialisierenden Sichten ausgewählt. Dieser Algorithmus kann aber auch sehr rechenaufwendig werden, da alle Knoten aus LV betrachtet werden.
Nun wird ein zweiter Algorithmus dargestellt. Dieser vergleicht Zustände des DWH. Ein Zustand oder eine DWH-Konfiguration wird durch ein Tupel C=(V,QV) bestimmt. V ist die Menge der materialisierten Sichten und QV beschreibt die Menge der Anfragen Q, welche durch die Sichten V beantwortet werden. Der Startzustand ist gegeben durch C=(Q,QQ). Das bedeutet, daß alle Anfragenresultate materialisiert sind und bei Anfrage nur abgerufen werden muß. Daraus ergeben sich minimale Kosten für die Anfrageverarbeitung, aber maximale Kosten für die Pflege. Durch Transformationen in andere Zustände erhält man andere Kosten. Dabei werden mittels eines Graphen die Sichten und die Anfragen transformiert. Der Endzustand ist gegeben durch C=(R,Q). Daraus folgt, daß es keine materialisierten Sichten gibt und die Anfragen immer neu berechnet werden müssen. An dieser Stelle muß erwähnt werden, daß die Autoren eine etwas andere Definition des DWH benutzen, als Sammlung von materialisierter Sichten, als die Autoren vom ersten Algorithmus. Im Zustand C=(R,Q) sind nur noch die Basisrelationen materialisiert. Bei Anfrage müssen die Tupel komplett neu berechnet werden. Dabei kann man auf verschiedene Weise zum Zustand C=(R,Q) gelangen und die Anfragen Q können auf verschiedene Weise die Berechnung durchführen, d.h. wenn man auf verschiedene Weise zum Endzustand gelangen kann, können die Anfragen verschiedene Ausführungspläne haben. Das Ziel ist, den Zustand mit den geringsten Gesamtkosten zu suchen.
Der abstrakte Algorithmus hat folgendes als Eingabe: R={R1,...,Rn} sei die Menge der Basisrelationen. Q={Q1,...,Qo} sei die Menge der Anfragen und fQi sei das Gewicht einer Anfrage Qi (relative Häufigkeit der Anfrage). T={T1,...,Tq} sei die Menge der Transaktionstypen über R (Ti wird bestimmt durch geänderte Basisrelation, Typ der Änderung und Größe jeder Änderung) und fTi sei das Gewicht eines Transaktionstypes Ti (relative Häufigkeit von Updates). Die Ausgabe: V={V1,...,Vm} sei die Menge der Sichten.
Alle Anfragen werden durch Sichten beantwortet. Die Kosten der Anfragen berechnen sich E(QV)=Summe[i=1...o](fQi*E(QVi)) und die Kosten der Pflege M(V)=Summe[i=1...q](fTi*M(Ti)). E und M sind wieder Kostenfunktionen (analog zu 3.2.1.).
Der Algorithmus untersucht Zustände, d.h. verschiedene DWH Konfigurationen, der Form s=(V,QV). Man betrachtet dabei ðF=(R1 * ... * Rk) als eine Anfrage. F sei eine Formel für Konjunktion von Vergleichen der Form (x op y + c) oder (x op c), mit c als Konstante, x, y als Attributnamen und op als Operator aus (=, <, <=, >, >=, (nicht ungleich)). Disjunktionen, Ungleichheit und Negation können durch geeignete Umformungen eliminieren werden.
GV sei ein Mehrfachanfragengraph über den Sichten V. S=(V,QV) beschreibt eine Konfiguration des DWH, die durch einen Zustand des Graphen mit s=(GV,QV) beschrieben wird. GV ist wie folgt definiert. Die Knoten beschreiben Relationen und die Kanten beschreiben Joins bzw. Selektionen in den Sichten. Der Graph beschreibt also die Struktur der Sichten.
QV sei nun wieder die Menge der Anfragen, welche durch V beantwortet werden. Für jedes join-Prädikat FP in einer Sicht Vi der Form ðF(Rk*...*Rl) gibt es eine Kante zwischen Ri und Rj bezeichnet mit V:FP (join edge). Für jedes select-Prädikat FP in einer Sicht V der Form ðF(Rk*...*Rl) gibt es eine Kante von Ri zu Ri bezeichnet mit V:FP (selection edge). Für jede Sicht V=Ri gibt es eine Kante von Ri zu Ri bezeichnet mit V:T mit T sei eine gültige Formel (selection edge). Somit hat ein Mehrfachanfragengraph alle Informationen über die Sichten.
Nun können Transformationen auf dem Graphen angewandt werden. Der Graph einer Sicht kann auch als Graph mehrerer (Teil)Sichten angesehen werden mit V={V1,...,Vm}. Jede Kante bzw. eine Menge von Kanten kann als Sicht angesehen werden. Mittels drei Regeln entstehen Übergänge in weitere Zustände. Dabei werden auch die Anfragen umgeschrieben. Eine Kante sei e.
Bei Anwendung einer der drei Transformationsregeln auf s=(GV,QV) erhält man einen neuen Zustand s'=(GV',QV') mit einer Menge von Sichten V' mit der Garantie, daß alle Anfragen mit materialisierten Sichten beantwortet werden. Nach der Konstruktion des Graphen werden die Sichten wie die Anfragen definiert, d.h. alle Anfragenresultate materialisiert.
Ein Beispiel (mit dem * als Join-Zeichen) für Transformationen. Man betrachte eine Anfrage Q1=R*(A=C)(select(D>5)S) für die Relationen R(A,B) und S(C,D). Damit ist die Menge Q={Q1} und R={R,S}. Der Startzustand ist C0=(Q,QQ), d.h. V=Q1 und damit V={V}. Der entsprechende Mehrfachanfragengraph wird in Abb.3 gezeigt.
Abb.3 : Graph zum Bsp.
Nach einem join egde cut auf die Join-Kante im Graph (siehe Abb.4) ist die Menge der materialisierten Sichten V={V1,V2}={R,select(D>5)S} und die Anfrage Q1 wird berechnet als Q1=V1*(A=C)V2. Nach einen selection edge cut auf die Selection-Kante V2:(B>5) ist die Menge V={V1,V3} und die Anfrage Q1 wird berechnet aus Q1=V1*(A=C)select(D>5)V2. Es sind nur noch die Basisrelationen materialisiert und die Anfrage Q1 wird vollständig neu berechnet.
Abb.4 : Graph nach Transformationen
In Abb.5 wird eine andere Reihenfolge der Transformationen des in Abb.3 bestehenden Graphen durchgeführt. Nach einem selection edge cut der Selection-Kante V:(D>5) ist die Menge der zu materialisierenden Sichten V={V,V}={R*(A=C)S,S} und die Anfrage Q1 wird berechnet als Q1=select(D>5)V. Nach dem folgenden join edge cut auf die Join-Kante ist die Menge der zu materialisierenden Sichten V={V1,V3}={S,R} und die Anfrage Q1 wird berechnet als Q1=select(D>5)(R*(A=C)S). Die beiden Endzustände nach den Abb.4 und Abb.5 besitzen die gleiche Menge an materialisierten Sichten, jedoch verschieden Ausführungspläne für die Anfrage Q1.
Abb.5 : Graph nach Transformationen
In der Abb.6 ist ein Beispiel für das view merging aufgezeigt. Man betrachte nun zwei Anfragen Q={Q1,Q2} mit Q1=R*(A=C)(select(D>5)S) und Q2=R*(A>=C)(select(D=6)S) auf den Basisrelationen R und S. Die Menge der zu materialisierenden Sichten ist V={V1,V2}={Q1,Q2}. Nach dem view merging ist die Menge der materialisierten Sichten V={V3}={R*(A>=C)(select(D>5)S} und die Anfragen werden berechnet als Q1=select((A=C)V3) und Q2=select((D=6)V3).
Abb.6 : Graph nach Transformation
Durch die "edge cut"-Operationen werden die materialisierten Sichten verkleinert, d.h. es wird immer weniger materialisiert und immer mehr muß berechnet werden zur Anfrageverarbeitung. Durch die "view merging"-Operation werden mehrfache Sichten aus dem Graphen entfernt.
Nun betrachtet man vom Anfangszustand s0=(GQ,QQ) aus alle möglichen Zustände mit den entsprechenden Kosten, bis man zu den Endzuständen gelangt. In einem Endzustand ist keine Transformation mehr möglich. Der Algorithmus sucht alle möglichen Zustände vom Ausgangszustand aus. Dabei werden die Kosten berechnet. Da es drei verschiedene Transformationsarten gibt, ist die Reihenfolge der Transformation bis zum Endzustand nicht vorgegeben. Dadurch berechnen zwar alle Endzustände die gleichen Tupel, aber auf verschiedenen Wegen. Wenn keine Transformationen mehr möglich sind, sucht man den Zustand s=(GV,QV) mit minimalen Kosten. Jedoch kann die Anwendung dieses Algorithmus bei einer hohen Anzahl von komplexen Anfragen sehr teuer werden, da wieder alle Zustände betrachtet werden. Außerdem müssen die Anfragen in einer bestimmten Form sein bzw. gebracht werden. Das hat zur Folge, daß Anfragen sehr unübersichtlich werden können.
Ein Update auf Basisrelationen zieht ein Update auf die materialisierten Sichten nach sich. Für manche DWH ist es wichtig, daß nach einem Update auf einer Basisrelation sofort das Update der Sichten erwartet wird. Für andere reicht ein Update pro Tag (z.B. bei Nacht) aus. Dies ist natürlich anwendungsabhängig. Die Pflege der Sicht heißt neue Berechnung der Sicht. Eine Rematerialisierung der Sicht, d.h. eine völlige Neuberechnung, ist meist zu teuer, da die Updates oft klein in Bezug auf die Größe der Basisrelation sind. Wenn man nur den nötigen Teil der Sichten neu berechnet, d.h. den Teil der vom Update betroffen ist, ist dies weitaus billiger. Pflegeoperationen der Sichten und Anfragen können sich gegenseitig blockieren. Deshalb ist es am besten, nur bei Nichtbenutzung (in der Nacht) die Sichten zu pflegen. Zwei Probleme entstehen aber:
Es gibt viele Methoden, welche vor der Pflege Fallunterscheidungen (Art des Updates, Art der Sicht) durchführen, um dann verschiedene Algorithmen anzuwenden. Der ECA (unten) arbeitet ohne Fallunterscheidung. WH und Basisrelationen (Quelle) sind voneinander getrennt. Mögliche Protokolle:
Um die Probleme der Pflege zu zeigen, werden drei Beispiele (aus [ZGHW95]) erklärt. Zunächst die Erklärung der Syntax. Eine Basisrelation wird beschrieben durch Name = (Attributnamen):(Tupel), eine Sicht durch Name = Projektion[Attributname](Joins(*) zwischen Basisrelationen) und ein Update durch Name = Updateart(auf Basisrelation, mit Tupel). Der Name wird hier durch Indizes spezifiziert.
Im ersten Beispiel wird das Update korrekt behandelt.
Im zweiten Beispiel tritt eine Anomalie auf. V=([1],[4]) wäre korrekt. Das Problem liegt daran, daß die Anfrage Q1 auf den Basisrelationen nach dem Update U2 berechnet wird (View Maintenance Anomaly). Würden mehrere Updates immer in einem genügend großen Abstand auftreten, so daß jede Anfrage zur Pflege berechnet wird, bevor ein neues Update auftritt, ist der Algorithmus korrekt.
Der Algorithmus ist in diesem Beispiel nicht korrekt. Die Sicht müßte keine Tupel enthalten V=(). Mögliche Lösungen, um die Sichten korrekt zu halten, wären:
Anwendung eines korrekteren Algorithmus (z.B. ECA)
Der einfache Algorithmus wie er in den oberen drei Bsp. benutzt wurde, besteht aus vier Ereignissen, die eintreten können. Quelle und WH sind getrennt.
Bei diesem einfachen Algorithmus können Anomalien auftreten, wie die Beispiele oben gezeigt haben. Nun muß dieser Algorithmus noch modifiziert werden, um diese Anomalien zu entfernen. Betrachtet man die Ereignisse im WH, sei UQS die Menge an Anfragen, welche das WH nach Eintreffen des Updates abgeschickt hat, jedoch noch keine Antwort von der Quelle zurückkam. Es werden erweiterte Anfragen generiert, um Anomalien auszuschließen. Diese Anfragen "sehen" die Quelle so wie nach dem Update zur Anfrage und nicht im aktuellen Zustand. Wir nehmen an, daß alle Updates vor der Anfragebeantwortung angewendet wurden. Es werden also eine Menge von Updates "gleichzeitig" behandelt. In collect werden die Antworten gesammelt, und nach dem Eintreffen der letzten Antwort wird mit Hilfe von collect die Sicht gepflegt.
Hierzu ein weiteres Beispiel.
Die Vorteile des ECA sind zum einen, daß er Kosten und Zeit spart, als wenn man die Sichten rematerialisieren würde, und zum anderen, daß das DWH nicht für die Pflege gesperrt werden muß. Wenn Updates nicht häufig auftreten, kann der einfache Algorithmus verwendet werden. Der Nachteil des ECA ist, daß er nicht immer korrekt arbeitet, aber in der Praxis meist ausreichend ist. Leider gaben die Autoren kein Beispiel dafür an. Es gibt zwei verwandte Algorithmen. Der LCA (Lazy Compensating Algorithm) arbeitet immer korrekt aber ist nicht so effizient in der Anwendung. Er arbeitet mit einem weitaus komplexeren Verfahren, welches den Rahmen hier aber sprengen würde. Der ECA-Key-Algorithmus wird im nächsten Abschnitt erklärt.
Selbstpflege der Sichten heißt die Pflege ohne Benutzung der Basisrelationen. Diese Möglichkeit hängt ab von der Art des Updates und von den verwendeten Attributen in der Sicht. Wenn eine Sicht alle Schlüsselattribute der verwendeten Basisrelationen betrachtet und das Update ein delete ist, dann kann die Sicht mit Hilfe des ECA-Key-Algorithmus sich selber pflegen. Dieser Algorithmus arbeitet wie folgt:
Dazu ein weiteres Beispiel.
Bei einem delete-Update erspart man sich die Anfrage des WH auf die Quelle. Wenn ein insert-Update auftritt, erspart man sich die Berechnung der erweiterten Anfragen. Man kann diesen Algorithmus aber nur anwenden, wenn die in der Projektion verwendeten Attribute einer Sicht Schlüsselattribute der Basisrelationen sind.
Die Verwendung von materialisierten Sichten erhöht die Effizienz bei der Anfrageverarbeitung im DWH. Jedoch ist die Auswahl und die Pflege kein triviales Problem.
Es wurden zwei Algorithmen dargestellt, welche eine Auswahl der zu materialisierenden Sichten treffen. Beide können großen Rechenaufwand nach sich ziehen, wenn die Anzahl der Anfragen hoch ist und die Anfragen selber komplexe Struktur besitzen. In [LQA97] wird ein Algorithmus dargestellt, der den Suchraum (alle möglichen Zustände mit ihren Kosten) stark einschränken kann. Jedoch ist dieser unpraktisch für viele Probleme in der realen Welt. In der Literatur gibt es mehrere verschiedene Algorithmen. Ein Ziel ist es, Algorithmen zu finden, welche den Suchraum stark einschränken, d.h. nicht alle Zustände vergleichen, und dabei aber eine gute Lösung finden.
Eine Rematerialisierung der Sichten ist meist zu teuer. Die Kosten für die Pflege können stark reduziert werden, wenn man nur den Teil der Sichten pflegt, welcher auch von dem Update betroffen ist. [GM95] gibt eine guten Überblick über die Probleme, Techniken und Anwendungen der Pflege. Die Selbstpflege reduziert die Kosten sehr stark, da auf die Basisrelationen nicht zugegriffen werden muß. Jedoch ist diese nicht bei vielen Sichten und nicht bei allen Typen von Updates/Transaktionen anwendbar. In [Hu97] werden Algorithmen vorgestellt, welche die Möglichkeit der Selbstpflege entscheiden können. Ziel ist es, Algorithmen zu finden, welche die Pflege billiger gestalten.