Graphdatenbank

Eine Graphdatenbank (oder graphenorientierte Datenbank) ist eine Datenbank, die Graphen benutzt, um Informationen darzustellen und abzuspeichern. Graphen bestehen aus Knoten (auch Ecken genannt) und Verbindungen zwischen diesen, den Kanten. Kanten können gerichtet oder ungerichtet sein. Sowohl Knoten als auch Kanten können Eigenschaften (bspw. Gewicht, Farbe, Name) haben.

Grundlagen

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 Graph. Der Graph ist gerichtet; die Beziehung kennt ist im Allgemeinen symmetrisch, die Beziehungen liebt und hasst jedoch nicht zwangsläufig. Der Graph ist benannt, da jedem Knoten ein Name und jeder Kante ein Typ zugeordnet ist.

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

Eine Verallgemeinerung von benannten oder gewichteten Graphen sind Eigenschaftsgraphen (engl. property graphs). Ein Eigenschaftsgraph ist ein gerichteter Multigraph. Jedem Knoten und jeder Kante werden zusätzlich beliebige Eigenschaften zugeordnet. Graphdatenbanken speichern solche Eigenschaftsgraphen. Sie bieten im Allgemeinen Algorithmen, um Graphen zu traversieren, um Pfade zu berechnen und um Hot-Spots zu identifizieren. Im obigem Beispiel können Traversierungsalgorithmen benutzt werden, um alle direkten und indirekten Bekannten einer Person zu finden; Pfadberechnungen liefern die kürzeste Bekanntenbeziehung zwischen zwei Personen; Hot-Spots identifizieren gut vernetzte Personen.

Abgrenzung

Relationale Datenbanken

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.

Demgegenüber verwenden Graphdatenbanken Traversionsalgorithmen zur Selektion bestimmter Knoten. Ausgehend von einem oder mehreren Knoten werden alle oder ausgewählte ausgehende Kanten traversiert. 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. Es ist jedoch schwierig, alle indirekten Bekannten zu finden oder einen Pfad zwischen zwei Personen zu bestimmen. In SQL lässt sich dies nur formulieren, wenn man zuerst alle Pfade der Länge 1, dann alle der Länge 2, usw. betrachtet. In Graphdatenbanken wird dies einfacher durch die vorhandenen Pfadalgorithmen.

Objektorientierte Modelle

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 selber Eigenschaften zuzuweisen.

Semantisches Web, RDF (Resource Description Framework)

Beim semantischen Web handelt es sich um Graphdatenbanken mit festen Schema und standardisierter Abfragesprache SPARQL. Im Gegensatz zu allgemeinen Graphdatenbanken ist das Schema jedoch vorgegeben.

Algorithmen

Wichtige Algorithmen zur Abfrage von Knoten und Kanten sind:

• Breitensuche, Tiefensuche
• Kürzester Pfad
• Eigenvektor

Abfragesprachen

Leider gibt es bisher keinen Standard für die Abfrage von Graphdatenbanken. Das hat zu einer Vielzahl unterschiedlicher Abfragesprachen und Abfragemöglichkeiten geführt. Wichtige Vertreter sind

• Blueprints - eine Java-API für Eigenschaftsgraphen, die zusammen mit verschiedenen Graphdatenbanken verwendet werden kann.
• Cypher - eine Abfragesprache entwickelt von Neo4j.
• GraphQL - eine SQL-artige Abfragesprache
• Gremlin - eine Open-Source-Graphen-Programmiersprache, die mit verschiedenen Graphdatenbanken (Neo4j, OrientDB, DEX) genutzt werden kann.
• GReQL - eine textuelle Graphanfragesprache für Eigenschaftsgraphen, bietet Berechnung regulärer Pfade durch Pfadausdrücke.
• Pipes - ein Datenfluss-Framework für Java auf Basis von Prozessgraphen speziell für die Anfrageverarbeitung auf Property-Graphen.
• Rexster - eine HTTP/REST-Schnittstelle für den Zugriff auf Graphdatenbanken via Internet, die von mehreren Herstellern unterstützt wird.

Siehe auch

• Liste der Graphdatenbanken
• NoSQL

Weblinks

• Graph-Database.org - eine Informationsseite für Hintergründe zum Thema Graphdatenbanken.
• Graph Database Tutorial
• Graph Databases and the Future of Large-Scale Knowledge Management
• Graphs in the database: SQL meets social networks
• Social networks in the database: using a graph database
• Scaling Online Social Networks without Pains (PDF; 250 kB)
• Large-scale Graph Computing at Google
• On building a stupidly fast graph database
• Renzo Angles, Claudio Gutierrez. Survey of graph database models. ACM Computing Surveys, Feb. 2008.