Data Warehouse Technologien

Um die dynamische Anpassung des Grid-Files effizient zu gestalten

und die Nachbarschaftserhaltung zu gewährleisten, sind Grid-Region k-

dimensionale, konvexe Gebilde. Grid-Regionen sind paarweise disjunkt.

Wie kann nun die dynamische Anpassung eines Grid-Files gewährleistet wer-

den?

• Der Ausgangszustand eines leeren Grid-Files beginnt mit einer Zelle, die

eine Region bildet, die genau eine Datenseite referenziert.

• Datensätze können eingefügt werden, bis die Seite, in die sie eingefügt

wird, nicht mehr in der Lage ist, einen neuen Datensatz zu speichern.

Ein derartiger Seitenüberlauf führt zum Teilen von Seiten. Beim Teilen

von Seiten müssen zwei Fälle unterschieden werden: Falls die zur Seite

gehörende Grid-Region nur eine Zelle umfasst, muss das Gitter durch ei-

ne Unterteilung des Intervalls auf einer Skala verfeinert, und damit das

Grid-Directory und die Regionenaufteilung aktualisiert werden. Falls die

betroffene Region aus mehreren Zellen besteht, erfolgt eine Zerlegung die-

ser Region in kleinere Regionen.

• Beim Seitenunterlauf können zwei Regionen zusammengefasst werden,

falls das Ergebnis eine konvexe Region ist. Ebenfalls kann das Gitter ver-

gröbert werden.

Für die Performanz des Grid-Files sind insbesondere die Strategien beim Ver-

feinern der Skalen und beim Aufteilen von Regionen sehr wichtig, da sie zu

gleichmäßig ausgelasteten Speicherseiten führen müssen. Ausgefeilte Strate-

gien beim Löschen sind in DW-Systemen hingegen nicht relevant.

7.5.2 Mehrdimensionales Hashen MDH

Das mehrdimensionale Hashen, kurz MDH, basiert auf dynamischen Hash-

Verfahren. Dynamische Hash-Verfahren passen die Hash-Funktion an das

Wachstum der Daten an, sodass sie im Gegensatz zum klassischen Hashen

skalierbar sind. Dynamische Hash-Verfahren werden ausführlich in [SSH11]

behandelt.

Mehrere Hash-Verfahren realisieren die Anpassung der Hash-Funktion

dadurch, dass als (vorläufige) Hash-Werte Bit-Folgen konstruiert werden, von

denen unterschiedlich lange Anfangsstücke als Hash-Werte für unterschied-

liche Wachstumsstufen der Hash-Tabelle dienen. Ein Wechsel von Anfangs-

stücken der Länge k auf Stücke der Länge k+1 realisiert einen Wechsel von der

Adressierung von 2

k

Speichereinheiten zu 2

k+1

Einheiten. Konkret nutzt MDH

dabei das lineare Hashen.

Lineares Hashen wandelt einen Attributwert in einen Bit-String um. Wie

kann man nun dieses modifizieren, um mehrere Dimensionen zu berücksichti-

gen? Die naheliegende Idee ist es, das sogenannte Bit Interleaving zu nutzen,

216 7 Indexstrukturen