Abfragesprachen für Graphendatenbanken

Inhaltsverzeichnis

Graphendatenbanken sind darauf optimiert, stark miteinander vernetzte Informationen effizient zu speichern und greifbar zu machen. Welchen Ansprüchen müssen Abfragesprachen genügen, damit sie für die Arbeit mit diesen Datenbanken geeignet sind?

Bei der Aufarbeitung realer Informationen zeigt sich, dass ein hoher, aber unterschätzter Wert in den Beziehungen zwischen Elementen steckt. Seien es Ereignisse aus Geschichte und Politik, Personen in realen und virtuellen sozialen Netzen, Proteine und Gene, Abhängigkeiten in Märkten und Ökonomien oder Rechnernetze, Computer, Software und Anwender – alles ist miteinander verbunden. Der Graph ist ein Datenmodell, das solche Verbindungsgeflechte abbilden kann. Leider lässt sich das Modell mit relationalen und Aggregat-orientierten NoSQL-Datenbanken ab einer gewissen Komplexität jedoch schwer handhaben.

Graphendatenbanken sind dagegen darauf optimiert, solche stark miteinander vernetzten Informationen effizient zu speichern und greifbar zu machen. Auch komplexe Fragen lassen sich durch ausgefeilte Abfragen schnell beantworten. Hierbei kommt es auf die geeignete Abfragesprache an.

Etwas Theorie und Geschichte vorab

Set Leonhard Euler, der Begründer der Graphentheorie, 1735 über die Sieben Brücken von Königsberg reflektierte, ist bekannt, dass sich Graphen in vielen Bereichen anwenden lassen. Besonders in der Mathematik sind die theoretischen Betrachtungen von Graphen seit langer Zeit ein beliebtes Thema.

Später wurden Graphen-Algorithmen wie die Wege-Suche nach Edsger W. Dijkstra und A* oder PageRank (viele Random Walks) genutzt, um praktischere Probleme zu lösen. Auch die soziale Netzwerkanalyse (SNA) nutzt Graphen-Algorithmen, um einflussreiche oder verbindende Mitglieder eines Netzwerks zu finden beziehungsweise per Cluster-Suche in sich stark, aber nach außen schwach vernetzten Subgraphen (Cluster) auszumachen.

Ein Graph lässt sich ganz allgemein als eine Menge von Knoten betrachten, die durch Kanten miteinander verbunden sind. Es gibt äußerst unterschiedliche Graphen-Modelle, im Folgenden soll jedoch nur auf die bekannten Ansätze eingegangen werden: das RDF-System und das Property Graph Model.

Eingetaucht in das Internet

Auch das Konzept von Semantic Web oder Linked Data mit RDF (Resource Description Framework) als grundlegendem Baustein basiert auf einem Graphenmodell, das implizit aus Fakten entsteht. Jeder Fakt stellt ein Tripel aus Subjekt, Prädikat und Objekt dar. Ein Beispiel:

"iX hat den Titel Magazin für professionelle Informationstechnik"
<http://heise.de/ix> <http://purl.org/dc/elements/1.1/title> 
     "iX - Magazin für professionelle Informationstechnik"

"Heise publiziert iX"
<http://heise.de> <http://purl.org/dc/elements/1.1/publisher> 
     <http://heise.de/ix>

"Heise ist in Hannover"
<http://heise.de> <http://purl.org/dc/terms/1.1/location> 
     <http://hannover.de>

Damit alle drei Elemente global eindeutig identifizierbar und adressierbar sind, werden sie entweder als URIs oder als Literale dargestellt. Diese Fakten stellen die komplett normalisierte Form der enthaltenen Informationen dar. Es gibt kein Objekt mit einer Identität, das nicht als URI verfügbar ist. Ein RDF-Graph ist immer voll normalisiert, da jede Information als Referenz modelliert wird.

Die Menge der Tripels lässt sich auch als Graph visualisieren, wobei man Subjekte beziehungsweise Objekte mit gleichen URIs zu Knoten zusammenfasst.

Für einen pragmatischen, weniger normalisierten Ansatz steht das Property Graph Model. Jedem, der schon einmal Objektmodelle oder ER-Diagramme gesehen hat, sollte es bekannt vorkommen. Es aggregiert primitive Informationen als Attribut-Wert-Paare sowohl an den Knoten als auch an den gerichteten, typisierten Verbindungen (Kanten, Beziehungen). Das gewährleistet, dass die Graphenstruktur nur die wirklich wichtigen Verbindungen der Domäne enthält und die den Elementen zugehörigen Informationen an den Elementen (Knoten, Verbindungen) selbst speichert. Ein weiteres Strukturelement im Umgang mit Graphen sind Pfade als lineare Abfolge von Knoten und Beziehungen, die zum Beispiel bei der Navigation von einem Start- zu einem Endknoten identifiziert werden.

Eine spezielle, eingeschränkte Form von Graphen sind Bäume oder Hierarchien. Ausgehend von einem Wurzelknoten werden über mehrere Ebenen Informationen in Zwischenknoten gespeichert, bis zu den Blattknoten, die das Ende des Baums darstellen. Verschachtelte Dokumente wie XML oder JSON lassen sich leicht als Bäume wiedergeben, sind jedoch auf jeweils einen einzelnen Baum beschränkt und nur über lose Verknüpfungen miteinander verbunden. Aggregate aus dem Domain-Driven Design können oft auch als Dokumente oder Bäume abgebildet werden.