Hierarchische Daten in einer relationalen Datenbank

Einführung

Egal, ob wir Excel oder MySQL oder Oracle DB nutzen, das Prinzip dieser Tools ist dasselbe: wir reduzieren ein Objekt auf seine wesentlichen Eigenschaften, setzen diese Objekte zueinander in Beziehung und beantworten dann bestimmte Fragestellungen auf dieses Konstrukt.

Technisch gesehen sind Objekte („entities“) in einer Tabelle zusammen gefasst, die Eigenschaften sind die Spalten dieser Tabelle.  Die Beziehungen („relationships“) werden über Referenzen als weitere Spalte abgebildet. Bei komplexeren Beziehungen werden auch weitere Hilfstabellen aufgebaut. Um die Referenzierung zu erleichtern, werden oftmals eindeutige Schlüssel („primary key“) definiert, die wiederum als Fremdschlüssel („foreign key“) genutzt werden. Wer weitere Grundlagen benötigt, möge sich die Links zu den Relationalen Datenbanken (siehe unten) anschauen.

Aufbauend auf diesem Modell soll nun eine Hierarchie abgebildet werden. Als Beispiel dient mir hier die politische Aufteilung des  Bundeslandes Bayern.

Ich beschreibe zuerst, wie ich das Modell aufbaue und diskutiere dann Vor- und Nachteile bei der Implementierung bestimmter Fragestellungen. Ich möchte zeigen, dass relationale Datenbanken nur sehr bedingt für hierarchische Systeme geeignet sind. Dies und mögliche Alternativen diskutiere ich zum Schluss dieses Blogs.

Das Modell

Hier ist ein Beispiel: die folgende Tabelle zeigt eine Tabelle mit Bundesländern und deren Bezirken. Die Beziehung („relation“) habe ich dadurch eingebaut, dass die Spalte „Teil_von“ aussagt, zu welchem Bundesland die entsprechenden Bezirke gehören. Die Verknüpfung habe ich durch einen eindeutigen Identifier (ID) hergestellt.

ID Name Typ Teil_von
1 Bayern Bundesland
2 Oberbayern Bezirk 1
3 Niederbayern Bezirk 1
4 Oberpfalz Bezirk 1
5 Oberfranken Bezirk 1
6 Unterfranken Bezirk 1
7 Mittelfranken Bezirk 1
8 Schwaben Bezirk 1

Das Beispiel zeigt bereits das Problem dieser Art der relationalen Abbildung: irgendwie passen diese Elemente nicht so recht zusammen. In der Regel werden daher mehrere Tabellen angelegt, die diese Darstellung vereinfachen (z.B. Bundeslaender, Bezirke). Diesen Vorgang nennt man „Normalisierung“.

Was passiert nun, wenn wir eine weitere Ebene einziehen wollen? Im Beispiel wären dies Kreisstädte und Landkreise. Dafür könnte man zwei weitere Tabellen angelegt werden.

Dieses Spiel lässt sich beliebig oft wiederholen, indem man zum Beispiel noch Stadtteile und Gemeinden abbildet.

An dieser Stelle haben wir nun eine Hierarchie von politischen Gebieten, das wie folgt aussieht:

hierarchie-politischegebiete-150x150

Zur Erläuterung: Kreisstädte haben entweder keinen Landkreis oder sind der Verwaltungssitz eines Landkreises.

Diskussion

Die Sinnhaftigkeit dieses Modells möchte ich nun dahingehend prüfen, ob es möglich ist, bestimmte Fragestellungen zu beantworten. Das Ziel sollte sein, möglichst einfache Algorithmen definieren zu können. Die Wartbarkeit oder Anpassungsfähigkeit sollte dabei nicht eingeschränkt werden. Im einfachsten Fall sollte die Datenbank die Fragestellung mit Bordmitteln abbilden und somit beantworten können.

Vorteile des relationen Modells

  • eindeutige Tabellen, denen wir je nach Anwendungszweck auch noch weitere Eigenschaften zuordnen können
  • einfache Beziehungen: jeder spezifischere Element (z.B. eine Gemeinde) ist genau einem allgemeinerem Element (z.B. genau einem Landkreis) zugeordnet
  • Abfragen wie „Alle Bezirke von Bayern“ oder „Alle Gemeinden im Landkreis Traunstein“ sind ohne großen Aufwand möglich

Nachteile des relationalen Modells

Komplexität entsteht in diesem Modell, wenn man über die Hierarchie suchen muss. Hier sind ein paar Beispiele:

  • die Suche eines beliebigen Elements der Hierarchie nach seinem Namen (z.B. „Tutzing“).
  • Die Hierarchie dieses Elements soll ausgegeben werden können.

Im konkreten Fall könnte man am einfachsten jede einzelne Tabelle abfragen. Dies wären sechs Abfragen.

Über den Fundort des Ergebnisses, wäre es dann wiederum möglich, die Hierarchie abzubilden. Dies bedeutet bei Ergebnissen auf Gemeinde- oder Stadtteil-Ebene eine Verknüpfung mit drei weiteren Tabellen.

Dies sind nun die Nachteile:

  • mehrere Requests, die programmatisch ausgewertet werden müssen
  • Aufbau von (teuren) Verknüpfungen über mehrere Tabellen
  • kontext-abhängige Abfragen

Für das o.g. Beispiel „Tutzing“ wäre die Hierarchie wie folgt: „Gemeinde Tutzing“, „Landkreis Starnberg“, „Bezirk Oberbayern“, „Bundesland Bayern“

Ergebnis und Ausblick

  • die Abbildung von hierarchischen Strukturen in Tabellen ist möglich
  • einfache Anfragen auf einer oder zwei Ebenen sind einfach zu realisieren
  • Suchen auf einer Ebene und damit auf einer Tabelle sind einfach
  • Suchen entlang der Hierarchie sind komplex und schwer abzubilden
  • die Abbildung komplexerer Fragestellungen stößt schnell an die Grenzen der Sprachmittel von relationalen Datenbanken

Zur Abbildung von hierarchischen Datenstrukturen ist das relationale Datenmodell somit nur bedingt geeignet.

Ausblick: eine gute Alternative bieten hier Graphen-Datenbanken. Es lohnt sich ein Blick auf Datenbanken wie Neo4j oder OrientDB.

Links