Graphdatenbank

Ein einfaches Beispiel für einen Graphen sind Beziehungen zwischen Menschen (siehe dazu auch Soziogramm). Die Knoten repräsentieren Menschen; jedem Knoten wird dabei der Name der Person zugeordnet. Die Kanten repräsentieren Beziehungen. Sie sind durch einen Typ (kennt, liebt, hasst) ausgezeichnet.

Obiger Graph ist ein gerichteter, benannter Multigraph. Die Kanten mit der Bezeichnung kennt sind im Allgemeinen symmetrisch, wogegen dies für die Beziehungen liebt und hasst jedoch nicht zwangsläufig stimmen muss.

Ein anderes Beispiel sind Netzwerkverbindungen. Jeder Knoten entspricht einem Computer, Switch oder Router. Jede Kante einer Verbindung. Jede Verbindung hat eine Bandbreite. In diesem Fall spricht man auch von gewichteten Graphen.

In einem Labeled-Property-Graph oder einfach Property-Graph können sowohl Knoten als auch Kanten Eigenschaften, sogenannte Properties (bspw. Gewicht: 10 kg, Farbe: Rot, Name: Alice), besitzen. Durch diese Spezialisierung auf Property-Graphen unterscheiden sie sich von den klassischen Datenmodellen der Relationalen Datenbanken.

Im Resource Description Framework (RDF) werden Graphen mit Hilfe von Triplen repräsentiert. Ein Triple besteht aus drei Elementen in der Form Knoten-Kante-Knoten (Subjekt --Prädikat-> Objekt), die als Ressourcen in Form einer weltweit eindeutigen URI oder als anonyme Ressource definiert werden. Um innerhalb einer Datenbank verschiedene Graphen zu verwalten, werden die Triple als Quads gespeichert. Ein Quad erweitert dabei jedes Triple um eine Referenz auf den zugehörigen Graphen. Das oben genannte Beispiel lässt sich etwa wie folgt darstellen:

 Alice --kennt-> Bob
 Bob  --hasst-> Alice
 Bob  --hasst-> Dave
 Carol --kennt-> Alice
 Carol --liebt-> Dave
 Dave --liebt-> Carol

Mit Hilfe dieser einfachen Bausteine aus (Subjekt --Prädikat-> Objekt) können sehr komplexe Graphen entwickelt werden, die bei entsprechender Modellierung auch automatische Schlussfolgerungen ermöglichen. Aufbauend auf RDF wurde mit RDF-Schema ein Vokabular entwickelt, um schwache Ontologien zu formalisieren und darüber hinaus lassen sich mit der Web Ontology Language auch vollständig entscheidbare Ontologien beschreiben. Um die Datenqualität und die Einhaltung eines Schemas in komplexen Graphstrukturen zu gewährleisten empfiehlt die W3C den Einsatz von SHACL.

RDF findet eine weite Verbreitung in vielen Webtechniken, wie RSS und im semantischen Web.

SPARQL ist eine standardisierte Abfragesprache im Semantic Web, mit deren Hilfe RDF-Graphen erzeugt, modifiziert und abgefragt werden können.

Relationale Datenbanken verwalten Relationen (Tabellen) und Tupel (Zeilen). Jede Zeile in einer Tabelle ist ein Datensatz. Jede Zeile besteht aus einer Reihe von Attributswerten (Eigenschaften), den Spalten der Tabelle. Das Relationenschema legt dabei die Anzahl und den Typ der Attribute für eine Relation fest. Beziehungen zwischen Tabellen werden durch Schlüssel realisiert.

Mit SQL existiert eine einheitliche Abfragesprache für relationale Datenbankmanagementsysteme. SQL erlaubt die Selektion von Zeilen mit bestimmten Eigenschaften.

Es ist möglich, Graphen in relationalen Datenbanken abzubilden. Für obiges Beispiel eines sozialen Netzwerks wählt man für die Personen eine Tabelle PERSON und für die Kanten eine Tabelle BEZIEHUNG. Mit SQL lassen sich alle Knoten (Personen) oder Kanten (Beziehungen) mit vorgegebenen Eigenschaften finden. Um alle indirekten Bekannten zu finden oder einen Pfad zwischen zwei Personen zu bestimmen, können Recursive Common Table Expressions eingesetzt werden (ANSI-SQL 99, DB2, Oracle 11gR2, PostgreSQL, SQL-Server 2008). Damit lassen sich uni- und bidirektionale Graphen durchsuchen. Enthält die Tabelle mit den Kanten auch eine Gewichtung, lässt sich so auch der optimale (kürzeste) Pfad zwischen zwei Knoten mit einer SQL-Abfrage ermitteln.

Demgegenüber verwenden Graphdatenbanken performantere Traversionsalgorithmen zur Selektion bestimmter Knoten. Ausgehend von einem oder mehreren Knoten werden alle oder ausgewählte ausgehende Kanten traversiert.

Mit dem Aufkommen objektorientierter Programmiersprachen wurden zunehmend Objektdatenbanken angeboten. Damit können Objekte aus objektorientierten Sprachen direkt in der Datenbank gehalten werden. Dieses Vorgehen hat Vorteile gegenüber dem relationalen Entwurf, wenn man komplexe Datenobjekte speichern möchte, die nur schwer auf die flachen relationalen Tabellenstrukturen abgebildet werden können. Graphen lassen sich in Objektdatenbanken abbilden, indem man die ausgehenden Kanten als Liste der Zielknoten hält. Es ist jedoch bei diesem Vorgehen nicht möglich, den Kanten selbst Eigenschaften zuzuweisen.