Data Warehouse Technologien

Bei der Annahmen, dass alle Werte von 00000 bis 99999 genutzt werden,

benötigte eine direkte Umsetzung 100.000 Spalten. Ein Zweikomponenten-

Bitmap-Index für die ersten zwei Ziffern und die drei letzten Ziffern schon nur

noch 1.100 Spalten. Geht man auf fünf Komponenten, erhält man nur noch 50

Spalten – jeweils 10 für jede Ziffernposition. Beide Realisierungen können Be-

reichsanfragen der Form „PLZ = 39

***

“ sehr gut unterstützen. 2

Rein akademisch kann man diese auch binärkodiert auf Ziffern aufteilen

(benötigt bis 2

17

) und erhält 34 Spalten. Dies wäre aber nur für Punktanfragen

nutzbar. Eine Kodierung zur Basis 3 benötigt sogar nur 33 Vektoren.

7.3.5 Bereichskodierter Bitmap-Index

Standard- und Mehrkomponenten-Bitmap-Indexe sind sehr gut für Punktan-

fragen geeignet. Bei Bereichsanfragen für große Bereiche hingegen sind sie in-

effizient, da dann viele Bit-Vektoren verknüpft werden müssen. Hier setzt die

Idee der bereichskodierten Bitmap-Indexe an:

Im Bit-Vektor wird ein Bit dann auf 1 gesetzt, wenn der Wert des At-

tributs des zu dieser Position gehörigen Tupels kleiner oder gleich dem

gegebenen Wert ist.

JBeispiel 7-8I Eine Bereichsanfrage 2 ≤ attr ≤ 7 in unserem Standardbei-

spiel benötigt zur Beantwortung nun nur noch zwei Bit-Vektoren: B-1 und B-7.

Genauer ist der Ergebnis-Bit-Vektor durch

((¬B-1) ∧ B-7)

definiert. 2

Allgemein müssen bei Bereichsanfragen nun maximal zwei Bit-Vektoren gele-

sen werden (nur einer bei nur einseitig begrenzten Bereichen). Allerdings er-

höht sich der Aufwand für Punktabfragen: Hier müssen nun genau zwei Bit-

Vektoren gelesen werden.

Eine Beispielausprägung für den bereichskodierten Bitmap-Index ist in

Abbildung 7.10 angegeben.

Die Bereichsanfrage F ebruar ≤ Datum ≤ August benötigt nur die bei-

den Vektoren B-0 und B-7: Der Ergebnis-Bit-Vektor ist durch ((¬B-0) ∧ B-7)

bestimmt.

7.3.6 Mehrkomponenten-bereichskodierter Bitmap-Index

Die Kombination der beiden bisher vorgestellten Techniken ist nun nahelie-

gend. Das Resultat nennen wir Mehrkomponenten-bereichskodierter Bitmap-

208 7 Indexstrukturen

Monat Dez Nov Okt Sep Aug Jul Jun Mai Apr Mär Feb Jan

M B-11 B-10 B-9 B-8 B-7 B-6 B-5 B-4 B-3 B-2 B-1 B-0

Juni - 5 1 1 1 1 1 1 1 0 0 0 0 0

April - 3 1 1 1 1 1 1 1 1 1 0 0 0

Jan. - 0 1 1 1 1 1 1 1 1 1 1 1 1

Feb. - 1 1 1 1 1 1 1 1 1 1 1 1 0

April - 3 1 1 1 1 1 1 1 1 1 0 0 0

Dez. - 11 1 0 0 0 0 0 0 0 0 0 0 0

Aug. - 7 1 1 1 1 1 0 0 0 0 0 0 0

Sept. - 8 1 1 1 1 0 0 0 0 0 0 0 0

Abbildung 7.10: Bereichskodierter Bitmap-Index

Index, oder kurz MKBKBMI. Um einen MKBKBMI zu konstruieren, wird zu-

nächst ein Mehrkomponenten-Bitmap-Index angelegt. Auf jede derart entste-

hende Gruppe von Bit-Vektoren wird dann die Bereichskodierung angewendet.

Aufgrund der Mehrkomponenten-Technik erhalten wir einen geringeren

Speicherbedarf, da eine kleinere Anzahl von Bit-Vektoren gespeichert werden

muss. Die Bereichskodierung erlaubt zudem effiziente Unterstützung für Be-

reichsanfragen. Genau genommen wird durch die Bereichskodierung zudem in

jeder Gruppe von Bit-Vektoren (Komponenten) ein Vektor überflüssig (der den

Wert n − 1 bzw. m − 1 repräsentiert, da dort immer alle Bits auf 1 gesetzt sein

müssen); also werden insgesamt nur n + m − 2 Bit-Vektoren benötigt.

Als Beispiel für den Mehrkomponenten-bereichskodierten Bitmap-Index

betrachten wir wieder unsere zwölf Monate, die wir ja schon in einen

Mehrkomponenten-Bitmap-Index realisiert hatten.

Unsere Beispieldaten ergeben nun den in Abbildung 7.11 abgebildeten

Bitmap-Index (man beachte, dass nun nur 2 + 3 statt zuvor 3 + 4 Vektoren

benötigt werden):

Monat B-1-1´ B-0-1´ B-2-0´ B-1-0´ B-0-0´

5 1 0 1 1 0

3 1 1 0 0 0

0 1 1 1 1 1

11 0 0 0 0 0

Abbildung 7.11: Mehrkomponten-bereichskodierter Bitmap-Index

Die folgenden Zusammenhänge zeigen, warum wir auf die beiden weggelas-

senen Vektoren tatsächlich verzichten können (am Beispiel des neuen Vektors

B-2-1´, der nicht gespeichert werden muss):

• B-0-1´ = B-0-1

• B-1-1´ = B-1-1 ∨ B-0-1

• B-2-1´ = B-2-1 ∨ B-1-1´ = B-2-1 ∨ B-1-1 ∨ B-0-1 = 1

7.3 Bitmap-Indexe 209