erfordern. Sind zwei Spalten mit demselben Wörterbuch kodiert, kann ein Ver-
gleich (etwa in einem Verbund) direkt auf den Bitcodes erfolgen.
JBeispiel 6-10I Das Beispiel in Abbildung 6.29 zeigt die Verwendung des Dic-
tionary Encoding für Adressdaten. Die Spalte Bundesland enthält nur 16 mög-
liche Werte und kann daher in 4 Bits kodiert werden.
Berlin 0000
Meckl.-Vorp. 0001
Sachsen-Anh. 0010
0011Thüringen
Dictionary
Berlin
Ilmenau
Magdeburg
Rostock
Berlin
Ilmenau
Ilmenau
Rostock
Berlin
Ort
Meckl.-Vorp.
Sachsen-Anh.
Thüringen
Thüringen
Thüringen
Berlin
Berlin
Berlin
Bundesland
Meckl.-Vorp.
...
...
KNr
...
...
...
...
...
...
...
0011
0000
0000
0011
0010
0011
0000
0001
Bundesland
0001
Abbildung 6.29: Dictionary Encoding
2
Vorteil des Dictionary Encoding ist eine große Speicherplatzeinsparung bei
wenigen, aber häufigen Werten. Allerdings ist für die Dekodierung für jeden
Wert ein Lookup im Wörterbuch notwendig. Dafür lassen sich Operationen wie
die Selektion direkt auf den komprimierten Daten ausführen, ohne dass zu-
vor eine Dekodierung notwendig ist. Dazu wird der zu selektierende Wert zu-
nächst im Wörterbuch ermittelt und der zugehörige Code bestimmt. Anschlie-
ßend kann der zugehörige Code in der Spalte gesucht werden. So kann im obi-
gen Beispiel eine Selektion Bundesland = ’Thüringen’ durch eine Suche nach
dem Wert 0011 (also der Zahl 3) in der Spalte Bundesland ausgeführt werden.
Ein ähnliches Vorgehen ist auch bei Verbund- und Gruppierungsoperationen
möglich.
Weitere in Datenbanken übliche Kompressionstechniken können in
[SSH11] nachgelesen werden.
6.4.4 Delta-Relationen
Wie bereits ausgeführt, ist insbesondere eine komprimierte spaltenorientierte
Speicherung drauf angewiesen, dass die Liste der Surrogate, die zur Rekom-
bination der Spaltenwerte zu Tupeln notwendig ist, stabil bleibt. Ein Update
der Daten führt dabei potenziell zur kompletten Neuberechnung der Daten-
struktur. Hinzu kommt in Hauptspeicherdatenbanken, dass Updates ja auch
190 6 Speicherung
Get Data Warehouse Technologien now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.