Data Warehouse Technologien

Input : Anzahl der Gruppierungsattribute N

Aggregationsgitter mit P - und S-Kosten der Kanten

1 foreach Ebene k = 0 . . . N − 1 do

/

*

Erzeuge Plan für Generierung von Ebene k aus k + 1

*

/

2 Erzeuge k zusätzliche Kopien für jeden Knoten v aus Ebene k + 1;

3 Verbinde jede Kopie mit der gleichen Menge der k-Knoten wie der

Originalknoten v;

4 Weise P (e

ij

)-Kosten der Kante vom Originalknoten v und

S(e

ij

)-Kosten den Kanten der Knotenkopien zu;

5 Finde die Zuordnungen zwischen k + 1 und k mit den minimalen

Kosten (Kuhn-Munkres-Algorithmus);

6 foreach Gruppierungskombination G in Ebene k + 1 do

7 Lege Sortierreihenfolge von G durch Reihenfolge des über eine

P -Kante verbundenen Knotens aus k fest;

8 end

9 end

Algorithmus 8.1: PipeSort-Algorithmus zur CUBE-Berechnung

Dieses Verfahren profitiert von mehreren Optimierungen:

• Der Aufwand für Sortieroperationen verteilt sich auf die Berechnung meh-

rerer Gruppierungen.

• Die Kosten für Scans auf den Basisrelationen werden ebenfalls durch die

gemeinsame Berechnung mehrerer Gruppierungen amortisiert.

• Gruppierungsergebnisse können im Hauptspeicher zwischengespeichert

und für die Ableitung einer weiteren Gruppierung genutzt werden.

Ähnliche Optimierungen sind für eine Hash-basierte Berechnung möglich. De-

tails hierzu sowie zum PipeHash-Algorithmus sind in [AAD

+

96] zu finden.

8.3 Materialisierte Sichten

Aufgrund der vergleichsweise einfachen Schemata (Star- oder Snowflake-

Schema) und der Art der Datennutzung (Analysen auf Basis von Aggregatio-

nen) ist ein Data Warehouse typischerweise durch eine Vielzahl gleicher oder

ähnlicher Anfragen auf immer denselben Relationen charakterisiert. Daher

bietet sich die Einführung von Sichten zur Vereinfachung der Anfrageformu-

lierung an. Weiterhin beinhalten die Anfragen zu einem großen Teil lesenden

8.3 Materialisierte Sichten 241