Data Warehouse Technologien

indem abwechselnd von den verschiedenen Zugriffsattributwerten die Bits ge-

nommen werden, um einen kombinierten Bit-String zu berechnen.

Beim MDH-Verfahren wird nun je ein Bit-String pro beteiligtes Attribut

berechnet. Anschließend werden die Anfangsstücke nun nach dem Prinzip des

Bit-Interleaving zyklisch abgearbeitet, und so ein Hash-Wert reihum aus den

Bits der Einzelwerte zusammengesetzt.

0 101 01... 1 0... 0 1 0... 0

1 01 1 01 0

x

1

x

2

x

3

h

7

Abbildung 7.17: Mehrdimensionales Hashen MDH

Abbildung 7.17 verdeutlicht diese Konstruktion eines gemeinsamen Bit-

Strings (bzw. eines Präfixes fester Länge, der für eine konkrete Wachstumspha-

se benötigt wird). Gezeigt wird die Komposition der Hash-Funktion h

i

für drei

Dimensionen und den Wert i = 7, wobei i den „Ausbaugrad“ der dynamischen

Hash-Tabelle bildet. Man beachte, dass die Bit-Strings von hinten nach vor-

ne aufgebaut werden, um sie direkt als Binärkodierung ganzer Zahlen nutzen

zu können. Diese Zahlen adressieren dann direkt ein Array von Hash-Buckets.

Beim Schritt auf i = 8 würde ein weiteres Bit von x

2

verwendet.

Wie lineares Hashen hat MDH bei Exact-Match-Anfragen einen Aufwand

der Größenordnung O(1). Eine Partial-Match-Anfrage, bei der t von k Attribu-

ten festgelegt sind, hat einen Aufwand von O(n

1−

t

k

) entsprechend der benötig-

ten Exact-Match-Anfragen. Diese ergibt sich aus der Zahl zu untersuchender

Seiten, wenn bestimmte Bits „unknown“ sind. Spezialfälle sind O(1) für t = k

und O(n) für t = 0.

7.5.3 KdB-Baum

Der KdB-Baum ist ein früh entwickeltes, mehrdimensionales Indexverfahren,

das sich in praktischen Systemen nicht wirklich durchgesetzt hat, das aber gut

geeignet ist, um Prinzipien zu zeigen, die auch in anderen mehrdimensionalen

Verfahren eingesetzt werden.

Der KdB-Baums ist ein k-dimensionaler Indexbaum, bei dem jeder Index-

knoten einen binären Teilbaum darstellt, der reihum nach mehreren Attributen

verzweigt. Derartige Teilbäume entsprechen sogenannten kd-Bäumen, die für

7.5 Mehrdimensionale Indexstrukturen 217