Data Warehouse Technologien

Betrachtung alternativer materialisierter Sichten, sodass die beste Ersetzung

gewählt werden kann.

8.3.2 Auswahl materialisierter Sichten

Die zweite wichtige Aufgabe bei der Verwendung materialisierter Sichten ist

die Auswahl der zu materialisierenden Anfrageteile. Hierbei ist zwischen dem

Gewinn durch das Einsparen der erneuten Berechnung und dem zusätzlichen

Aufwand in Form von Speicherplatz aufgrund der Redundanzen sowie der Ak-

tualisierung bei Änderungen der Basisrelationen abzuwägen. Grundsätzlich er-

fordert dies demzufolge einerseits Kenntnis über die auszuführenden Anfragen

(den Workload) und andererseits die Berücksichtigung der Ersetzbarkeit bzw.

Ableitbarkeit der einzelnen Anfrageteile, d.h., wie oben beschrieben u.a. die

Additivität von Aggregatfunktionen oder die Ableitbarkeit von Gruppierungs-

kombinationen.

Einen sinnvollen Ausgangspunkt für derartige Betrachtungen bildet ein

sogenanntes Aggregationsgitter, das einen Teilmengenverband über den Grup-

pierungsattributen repräsentiert. Die Knoten in diesem Gitter stehen für Ag-

gregationen bzw. Gruppierungen, die gerichteten Kanten geben an, welche Ag-

gregationen bzw. Gruppierungen aus welchen anderen berechnet werden kön-

nen. Eine derartige Kante entspricht somit der direkten Ableitbarkeit von Grup-

pierungskombinationen. Die Ableitbarkeit kann dabei sowohl auf den Grup-

pierungsattributen (beispielsweise kann der Gesamtverkaufssumme pro Pro-

duktgruppe, d.h. Gruppierung nach Produktgruppe, aus der Gruppierungskom-

bination { Produktgruppe, Filiale } abgeleitet werden) als auch entlang der

Dimensionshierarchien (die Verkaufszahlen der Monate können genutzt wer-

den, um die Jahresergebnisse zu berechnen) betrachtet werden, woraus sich

ein sehr komplexes Gitter ergibt. Abbildung 8.13 zeigt das Aggregationsgitter

für die drei Gruppierungsattribute Produktgruppe, Filiale, Jahr.

{Produktgruppe,Filiale,Jahr}

{Produktgruppe,Jahr} {Produktgruppe,Filiale} {Filiale,Jahr}

{Jahr}{Produktgruppe} {Filiale}

{}

Abbildung 8.13: Aggregationsgitter

250 8 Anfrageverarbeitung und materialisierte Sichten

Jeder Knoten im Aggregationsgitter entspricht nun einer Möglichkeit, ei-

ne materialisierte Sicht zu bilden. Leider wächst die Zahl der Knoten im Ag-

gregationsgitter exponentiell mit der Zahl der Gruppierungsattribute (d.h. der

Dimensionen), sodass aus Aufwandsgründen eine Auswahl getroffen werden

muss. Ein erster Schritt ist hierbei die Reduktion des Aggregationsgitters durch

die Berücksichtigung funktionaler Abhängigkeiten. Wenn beispielsweise gilt

A

1

→ A

2

, dann repräsentieren die Knoten (A

1

) und (A

1

, A

2

) sowie (A

1

, A

3

) und

(A

1

, A

2

, A

3

) jeweils das Gleiche. Derartige Abhängigkeiten lassen sich u.a. über

die verschiedenen Ebenen einer Klassifikationshierarchie identifizieren, so et-

wa:

Produktbezeichnung → Produktgruppe → Produktkategorie

Die eigentliche Auswahl kann dann entweder statisch (durch Analyse eines ge-

gebenen Workloads) oder dynamisch zur Laufzeit (vergleichbar mit einem Ca-

ching von Materialisierungen) erfolgen. An dieser Stelle wollen wir nur kurz

einen statischen Ansatz skizzieren, der von Harinarayan, Rajaraman und Ull-

man [HRU96] vorgeschlagen wurde. Die Grundidee ist es, zunächst Kosten und

Nutzen einer Materialisierungskonfiguration (eine Menge von zu materialisie-

renden Aggregations- bzw. Gruppierungsknoten) zu bestimmen.

Für eine Materialisierungskonfiguration M = {m

1

, . . . , m

k

} aus Materiali-

sierungspunkten m

i

setzen sich die Gesamtkosten aus den Aktualisierungskos-

ten U(M) und den Anfragekosten C

Q

(M) für einen Workload Q = {q

1

, . . . , q

n

}

zusammen. Die Anfragekosten pro Anfrage q beziehen die Häufigkeit f (q

i

) so-

wie die minimalen Kosten c

q

(n) bezüglich einer Materialisierung m ∈ M ein,

d.h.

C

Q

(M) =

X

q

i

∈Q

f(q

i

) · min

m∈M

c

q

(m)

Für die Anfragekosten c

q

gilt dabei die Monotonieeigenschaft, die besagt, dass

die Kosten für die Bearbeitung von c

q

unter Verwendung einer Materialisierung

m

i

kleiner sind als die für m

j

, falls m

i

aus m

j

abgeleitet werden kann:

m

i

⇒ m

j

→ c

q

(m

i

) < c

q

(m

j

)

Auf dieser Basis kann der Nutzen B

Q

(m, M ) einer zusätzlichen Materialisie-

rung m für einen Workload Q wie folgt bestimmt werden:

B

Q

(m, M ) =

(

C

Q

(M) − C

Q

(M ∪ {m}) falls C

Q

(M ∪ {m}) < C

Q

(M)

0 sonst

Leider ist das eigentliche Auswahlproblem NP-vollständig. Daher basiert

der vorgeschlagene Algorithmus auf dem Greedy-Prinzip: Für ein gegebenes

8.3 Materialisierte Sichten 251