Die Datenbank mit Ecken und Kanten

Datenbanktechnologien gibt es unzählige und jede hat ihre Ecken und Kanten. Aber nur eine lässt ihre Ecken und Kanten in das Datenmodell miteinfliessen. Die Rede ist von Graphendatenbanken, deren Inhalte eine Menge von Knoten darstellt, verbunden durch Beziehungen – oder eben Ecken und Kanten.

Die Grundlagen der Graphendatenbanken sind auf die Graphentheorie zurückzuführen. Die Graphentheorie ist ein Teilgebiet der Mathematik das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht. Die Untersuchung von Graphen ist auch Inhalt der Netzwerktheorie, welche sich auf theoretischer Ebene damit auseinandersetzt, wie Netzwerke gesellschaftlich funktionieren. Graphen und Netzwerke sind allgegenwärtig, darum lassen sich zahlreiche Alltagsprobleme mit Hilfe von Graphen modellieren. Leonhard Euler versuchte mit Hilfe von Graphen das Königsberger Brückenproblem zu lösen.

Die Anfänge der Graphen-Theorie oder das Königsberger Brückenproblem
Das Königsberger BrückenproblemDas Königsberger Brückenproblem beschreibt die Fragestellung, ob es einen Weg gibt, bei dem alle sieben Brücken genau einmal überquert werden können und man zum Schluss wieder beim Ausgangspunkt ankommt. Leonhard Euler bewies 1736, dass ein solcher Weg in Königsberg nicht möglich war, da zu allen vier Ufergebieten bzw. Inseln eine ungerade Zahl von Brücken führte. Der nach ihm benannte Eulerkreis beschreibt genau diese Problematik und zeigt den Weg bzw. die Reihenfolge vom ersten bis zum letzten Knoten (Ufer) und zurück zum ersten indem jede Kante (Brücke) nur einmal verwendet werden darf. Heute werden diese Methoden der Graphentheorie zugeordnet. (Quelle: Wikipedia Königsberger Brückenproblem)

 

In sozialen Medien wie Facebook, Twitter oder LinkedIn nutzen Graphendatenbanken ihre Stärken, um Beziehungen in Form von strukturierten Daten abzulegen. Hierbei wird nicht nur die einfache Beziehung zwischen zwei Menschen aufgezeigt. Die sogenannten Knoten (oder Ecken) können jegliche Formen von Informationen annehmen, zum Beispiel Personen, Facebook-Posts, Twitter-Tweets, Zeitungsartikel, Musikbands, Sportarten usw.

Verbunden werden die Knoten über Beziehungen (oder Kanten). Diese Beziehungen beinhalten selbst weitere Informationen, über die Art der Beziehung und wie die beiden verbundenen Knoten zueinander stehen. Bei Personen kann die Kante Aufschluss darüber geben, wie lange sie sich kennen, wie sie sich kennengelernt haben oder welche Art der Beziehung sie verbindet. Nicht nur die sozialen Medien machen sich die Technologie der Graphendatenbanken zu Nutze. Dating-Plattformen wie Parship machen dies schon längere Zeit, um Personen mit gleichen Interessen und Vorlieben im realen Leben einander näherzubringen.

Wo würden wir heute ohne unsere heiss geliebten Suchmaschinen stehen, welche die alltäglichen Fragen pfeilschnell beantworten können? Die Rede ist nicht nur von Google, Bing und wie sie alle heissen, sondern von allen Suchalgorithmen, welche uns tagtäglich behilflich sind. Behilflich nicht nur dadurch, dass sie möglichst die besten Suchresultate aufgrund der eingegebenen Schlagworte liefern, sondern auch das am besten auf mich als Person abgestimmte Resultat.

Firmen wie Facebook, Spotify, Netflix oder LinkedIn verwenden deine Information, dein Verhalten, deine Beziehungen und wie sich deine Freunde und deren Freunde verhalten, um dir das auf deine Person passendste Suchresultat zu liefern. Das alles sind Knoten in einem riesigen Beziehungsnetz von Informationen, welche ein genaues und schnelles Suchresultat, nicht selten gestützt auf eine Graphendatenbanken, liefert.

Wie erstellt man ein Graph-Datenmodell?

Datenmodellierung mit einer Graphendatenbank ist intuitiv und spannend. Anders als bei relationalen Datenbanken, bei denen ein Graph nur in der Modellierungsphase (ER-Diagramm) eingesetzt wird, sind in Graphendatenbanken das Modell und die Daten eine direkte Abbildung der Domäne. Jeder Knoten (Entität oder Attribut) in einem Graph-Modell beinhaltet eine Liste von Beziehungsdatensätzen, welche die Beziehungen zu anderen Knoten darstellen. Diese Beziehungsdatensätze sind nach Typ und Richtung

Schematische Darstellung einer Assoziationstabelle
Schematische Darstellung einer Assoziationstabelle (Bild: Neo4j, Inc.)

organisiert und können zusätzliche Attribute enthalten. Nehmen wir das Beispiel einer Person, welche in verschiedenen Abteilungen arbeitet. In einer relationalen Datenbank beudeutet dies eine n:m Beziehung zwischen Person und Abteilung. Diese Relation wird mit Hilfe einer Assoziationstabelle aufgelöst, worin die Fremdschlüsselverbindungen zwischen Person und Abteilung abgelegt sind. Die Abbildung „Schematische Darstellung einer Assoziationstabelle“ zeigt diese Situation schematisch auf.

Schematische Darstellung eiens Graphendatenbanken-Modells
Schematische Darstellung eiens Graphendatenbanken-Modells (Bild: Neo4j, Inc.)

Die Graphendatenbank bietet hier den Vorteil, dass die Person und die mit ihr verbundenen Abteilungen gemeinsam in der Datenbank abgelegt sind. Im Gegensatz zu einer konventionellen relationalen Datenbank, welche zwei Join-Operatoren ausführen muss, um auf dasselbe Resultat zu kommen. Diese Fähigkeit von Graphdatenbanken, Beziehungen in der Datenstruktur abzulegen, ergibt einen Leistungsvorteil bei der Abfrage von Daten. Wie kommt man nun vom bekannten relationalen Datenmodell zu einem Graph-Modell? Die nachfolgenden Merkpunkte geben die relevanten Schritte vor.

  • Jede Entitätstabelle wird durch ein Label auf den Knoten dargestellt
  • Jede Zeile in einer Entitäten-Tabelle ist ein Knoten
  • Spalten werden zu Knoteneigenschaften
  • Technische Primärschlüssel werden entfernt, verwendet werden die sprechenden Business-Keys
  • Indizes für häufig nachgeschlagene Attribute werden erstellt
  • Fremdschlüssel werden durch Beziehungen zur anderen Tabelle ersetzt
  • Assoziationstabellen werden in Beziehungen umgewandelt und Spalten auf diesen Tabellen zu Beziehungseigenschaften
Vom relationalen Datenmodell zum Graphdaten-Modell
Vom relationalen Datenmodell zum Graphdaten-Modell (Bild: Neo4j, Inc.)

Wo liegen die Vor- und Nachteile?

Jede Datenbanktechnologie hat ihre Spezialitäten und Eigenheiten. Für Graphendatenbanken lassen sich im Wesentlichen die nachfolgenden Vor- und Nachteile nennen:

Vorteile: Schnelle Suchresultate und Flexibilität bei Datenanpassungen

  • Flexibilität: Die erfassten Daten können einfach geändert und um zusätzliche Attribute und Objekte erweitert werden
  • Suchgeschwindigkeit: Beziehungsbasierte Recherchen werden schnell durchgeführt
  • Indizierung: Graphendatenbanken werden natürlich nach Beziehungen indiziert, was einen schnelleren Zugriff im Vergleich zu relationalen Daten ermöglicht

Nachteile: Ineffizient in der Verarbeitung grosser Datenmengen

  • Datenverabeitung: Graphendatenbanken zeigen sich als ineffizient bei der Verarbeitung grosser Datenmengen
  • Clustering: Einiger der Graphendatenbanken sind nicht clusterfähig und stossen punkto Skalierung rasch an ihre Grenzen
  • Analytische Abfragen: Graphendatenbanken sind nicht für grossvolumige, analytische Abfragen optimiert

Die Graphendatenbanken sind spezialisiert auf die schnelle Suche zu einem einzelnen Datensatz, wie zum Beispiel einer Person oder einem Produkt. Wird die Abfrage jedoch analytischer und mehrschichtiger, sinkt die Effizienz der Antwort im Vergleich zu einer relationalen Datenbank. Die Praxis zeigt, dass wenn eine Graphendatenbank mit weiteren Datenbanktechnologien kombiniert werden, ihre Defizite im Bereich Datenverarbeitung und analytischen Abfragen kompensiert werden können. Für das Königsberger Brückenproblem benötigt die Graphendatenbank jedoch keine Unterstützung anderer Technologien, da ist sie mit ihren Ecken und Kanten voll im Element.

Beitrag teilen

Marco Boll

Marco Boll ist Verantwortlicher Datawarehouse bei der Zuger Kantonalbank und bloggt aus dem Unterricht des CAS Big-Data Analytics.

Alle Beiträge ansehen von Marco Boll →