Data Warehouse Technologien

7.6 Indexierung von Hierarchien

In den bisherigen Indexverfahren wurde jeweils von einer in einer Sortierrei-

henfolge angeordneten, aber flachen, Liste von zu indexierenden Werten ausge-

gangen. Die hierarchische Struktur der Daten innerhalb einer Dimension wur-

de nicht unterstützt. In diesem Abschnitt schauen wir uns Verfahren an, die

diese hierarchische Struktur unterstützen.

7.6.1 Kodierung von Hierarchien

Die meisten Indexstrukturen, die Bereichsanfragen unterstützen, erfordern ei-

ne totale Ordnung der indexierenden Werte. Umgekehrt kann jede Darstellung

von Werten, die zu einer totalen Ordnung führt, genutzt werden, sofern die to-

tale Ordnung tatsächlich bereichserhaltend ist. Übertragen auf hierarchische

Daten, wie sie in einer Klassifikationshierarchie auftreten, müssten wir eine

totale Ordnung finden, sodass die Elemente etwa auf der feinsten Granula-

ritätsstufe derart angeordnet sind, dass Elemente vom gleichen Vaterknoten

auch benachbart bleiben. Dies geht natürlich nicht für parallele Hierarchien.

Verschiedene derartige Kodierungen sind denkbar:

• Analog zur Kodierung von URL und Dateipfaden kann man die Werte

der Dimensionsstufen konkatenieren. Dies führt dann zu Indexwerten der

Form Wein.Rotwein.Burgunder und Wein.Rotwein.Bordeaux.

Nachteil ist der Aufwand zur Speicherung langer Indexwerte in der Index-

struktur.

• Man kann die Konkatenation auch nach einer Abbildung auf Zahlwerte (je-

weils in lexikografischer Ordnung) vornehmen. Ein derartiger Wert könnte

dann 1.3.15 sein.

Vorteil ist die kompaktere Repräsentation. Nachteil ist, dass die Kodierung

sich bei neuen Dimensionselementen ändert und viele Indexwerte ange-

passt werden müssen. Dem letzteren Nachteil kann man mit einer Kodie-

rung mit DeweyID entgegnen, indem jeweils Zahlen freigelassen werden,

um geeignete Werte(bereiche) „zwischenschieben“ zu können (etwa von

[HHMW05, HHMW07] im Zusammenhang der Nummerierung von XML-

Knoten vorgeschlagen).

• Weiß man, dass in jeder Gruppe (Werte mit demselbem Vaterelement) et-

wa maximal 100 Werte auftreten, kann man auch direkt eine ganze Zahl

konstruieren. Im vorigen Beispiel kann also für n = 100 die Zahl 010315

genutzt werden. Dies ist die kompakteste interpretierbare Darstellung.

Die vorgeschlagenen Varianten unterscheiden sich stark betreffend Platzbedarf

der gespeicherten Kodierungen, aber auch in der Interpretierbarkeit durch den

226 7 Indexstrukturen