NoSQL: Graphendatenbanken (Ergänzung)

Ich hatte bereits vor einigen Monaten einmal über Graphendatenbanken gebloggt, allerdings in einer wesentlich praxisnaheren Form am Beispiel von neo4j. Den Mangel an Allgemeinheit möchte ich in einem zweiten Artikel ausgleichen.

Durch die Vielzahl neuer Anforderungen entsteht abseits der “herkömmlichen” relationalen Datenbanken zunehmend ein Markt für Graphendatenbanken. Diese sind, wie der Name schon schließen lässt, auf die Speicherung und den Abruf von Informationen in und aus Graphen optimiert. Graphen zeigen sich dabei als eine besonders nützliche Speicherform für viele moderne Probleme – neben dem allseits bekannten Freundschaftsspeicher bei Facebook auch in der Bioinformatik oder anderen Bereichen.

Grundlagen: Graphen

Um Graphdatenbanken zu verstehen, benötigt man zunächst ein rudimentäres Verständnis vom Aufbau von Graphen. In ihrer einfachsten Form bestehen diese aus sogenannten Kanten und Knoten, wobei eine Kante jeweils zwei Knoten miteinander verbindet. So entsteht schließlich ein Netz aus miteinander verbundenen Knoten. Diese Kanten können entweder gerichtet oder ungerichtet sein, das heißt man kann sie entweder nur vom einen Graphen zum anderen oder in beide Richtungen ablaufen. Graphen zur Modellierung von Freundschaften würden im Allgemeinen eher ungerichtete Kanten verwenden, solche zur Modellierung von Straßennetzen eher gerichtete (vgl. Einbahnstraßen).

In manchen Fällen werden die Kanten zusätzlich auch noch mit Bezeichnern erweitert, sodass ein Netz mit Bedeutung zwischen den Verbindungen entsteht. Dies kann man bspw. Im RDF-Modell sehen, welches aus Tripeln der Form (Subjekt, Prädikat, Objekt) besteht. Dabei bezeichnet das Prädikat der Verbindung zwischen Subjekt und Objekt (im Falle vom Freundschaften z.B. “a likes b”, oder bei Beziehungen “a loves b”). Diese Kanten können jeweils wieder gerichtet oder ungerichtet sein.

Vergleich zu anderen Systemen

Graphendatenbanken werden in “NoSQL” (von Edlich et al.) zumindest in ihrer erweiterten Form mit Objektdatenbanken verglichen. Dies rührt daher, dass Graphendatenbanken neben der Verlinkungen zwischen Elementen auch zusätzliche Werte speichern können (häufig als “properties” bezeichnet). Will man Graphen mit Objektrelationen vergleichen, dann kann man die properties als Attribute mit nativem Datentyp und die Verlinkungen als Attribute mit Objekten als Datentyp vergleichen.

Algorithmen zur Traversierung

Eine optimale Graphendatenbank implementiert bereits Algorithmen zum Durchsuchen des Graphen, z.B. Breiten- und Tiefensuche. Dies erhöht die Geschwindigkeit im Vergleich zu eigenen Abfragesystemen, bei denen für jeden Schritt eine neue Abfrage an den Server gestellt werden muss. Je nach Größe des Graphen kann allerdings möglicherweise nur eine Teilmenge aller Knoten durchsucht werden. Man stelle sich nur vor eine Endbenutzer-Applikation sollte einen Graphen von einer Milliarde Knoten komplett durchsuchen, dies würde den zeitlichen Rahmen sprengen. Deshalb wird die maximale Tiefe der Suche häufig begrenzt.

Skalierung

Die Skalierung von Graphen ist ein kompliziertes Thema. In herkömmlichen Datenbanken benötigt man üblicherweise keine Suchen über Relationen, sondern nur bereits bekannte Relationen. Dadurch ergibt sich bei Graphendatenbanken ein komplett neues Problem hinsichtlich der Skalierung: Die Daten müssen nicht nur auf mehrere Server zur besseren Lastverteilung gestreut werden, sondern der gesamte Graph an sich muss möglichst in einer handhabbaren Größe gehalten werden.

Das heißt, dass ab einem bestimmten Zeitpunkt möglicherweise Knoten in zwei Subgraphen aufgespalten werden müssen, um überhaupt noch eine brauchbare Traversierung zu ermöglichen. Dies stellt insbesondere deshalb ein Problem dar, als Daten häufig in solch einer Verteilung vorliegen, dass 20% der Knoten 80% Relevanz besitzen und 80% der Knoten 20% Relevanz (vgl. “NoSQL”, Edlich et al.). Eine Entscheidung ist nur dann möglich, wenn man genau weiß, welche Abfragen man an den Graphen stellt und welche Verbindungen für diese Abfragen von besonderer Bedeutung sind. Dann kann man mittels verschiedener Methoden versuchen, einzelne Knoten in Subgraphen zusammenzuschließen (z.B. durch k-means clustering).