NoSQL: Graph-Datenbanken (neo4j)

Graphen-Datenbanken dienen, wie der Name schon sagt, der optimalen Speicherung von Graphen. Viele Probleme der Informatik lassen sich mit Graphen lösen. Einer langen Erklärung bedürfen Graph-Datenbanken eigentlich nicht, da sie lediglich eine Speicherform für Graphen darstellen und sich so traversieren lassen.

Graphen-Konzept

Graphen sind grundsätzlich in Knoten (node) und Kanten (edge) aufgebaut, wobei die Kanten die Verbindungen zwischen den einzelnen Knoten darstellen. Je nach Graph sind eventuell auch Selbstreferenzierungen möglich. Diese grundsätzliche Implementierung wird zunächst vor allem durch die Hinzufügung eines Gewichtes zu den einzelnen Kanten erweitert, wodurch die Abstände flexibel werden. So ist in einem Graphen von Städten nicht jede Stadt gleich weit von der anderen entfernt, sondern die Distanz in Kilometer könnte als Gewicht der Kanten dienen. In einer weiteren Erweiterung können die Kanten weitere Werte annehmen, um die Art der Verbindung anzugeben (vgl. RDF). Zusätzlich unterscheidet man noch zwischen gerichteten und ungerichteten Graphen. Bei gerichteten Graphen verlaufen die Verbindungen nur in die angegebene Richtung, bei ungerichteten Graphen immer in beide. Ein Beispiel für einen Graphen ist ein Netzwerk aus sich gegenseitig kennenden Personen.

Vom Konzept zur Datenbank

Erweitert man das Konzept nun noch ein Stück und erlaubt die einfache Speicherung von mehreren Attributen zu jedem Knoten (ohne dass diese als eigene Knoten behandelt werden), ist man beim Funktionsumfang von neo4j angekommen. Je nach Datenbanksystem hat man dann eine unterschiedliche API zum Zugriff auf die Knoten und Kanten. Bei den meisten Systemen kommt hierbei eine Java-eigene Implementierung zum Einsatz, bei neo4j gibt es eine REST-API, sodass man die Datenbank mit jeder Programmiersprache verwenden kann.

Die einzelnen Werte lassen sich möglicherweise indizieren, sodass ein Abfragen nicht nur über den Primärschlüssel, sondern auch über weitere Eigenschaften des Knotens (oder sogar der Kante) möglich ist. Vom Ergebnisknoten oder der Ergebniskante aus kann man dann den Graphen mit verschiedenen Methoden weiterverfolgen (z.B. den Vorgänger und Nachfolger der Kante, die Kanten eines Knotens, die Nachbarn eines Knotens von bestimmtem Kantentyp, …).

Eine Index-Suche sieht bei neo4j in der REST-API so aus:

GET /index/node/my_nodes/the_key/the_value

Eine Abfrage nach Nachbarn über einen bestimmten Kantentyp so:

GET /node/123/relationships/out/KNOWS&LOVES;

Die Implementierung des gewünschten Algorithmus’ verbleibt schließlich beim Benutzer, allerdings liefern manche Datenbanksysteme auch bereits Implementierungen für bekannte Algorithmen wie Shortest-Path (Kantengewicht = 1) oder Dijkstra.