Graphdatenbank

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Eine Graphdatenbank (oder graphenorientierte Datenbank) ist eine Datenbank, die Graphen benutzt, um stark vernetzte Informationen darzustellen und abzuspeichern. Ein solcher Graph besteht aus Knoten und Kanten, den Verbindungen zwischen den Knoten. Die zwei bekanntesten Konzepte für Graphdatenbanken sind das Resource Description Framework (RDF) und Labeled-Property Graph (LPG).

Graphdatenbanken bieten eine Reihe von spezialisierten Graphalgorithmen, um komplizierte Datenbankabfragen zu vereinfachen. So bieten sie beispielsweise Algorithmen, um Muster zu finden (Graph Pattern), Graphen zu traversieren, d. h. alle direkten und indirekten Nachbarn eines Knotens zu finden, kürzeste Pfade zwischen zwei Knoten zu berechnen, bekannte Graphstrukturen wie beispielsweise Cliquen zu finden oder Hotspots besonders stark vernetzter Regionen im Graph zu identifizieren.

Grundlagen[Bearbeiten | Quelltext bearbeiten]

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.

Graphdatenbank-beispiel1.png

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.

Graph-Modelle[Bearbeiten | Quelltext bearbeiten]

Labeled-Property-Graph[Bearbeiten | Quelltext bearbeiten]

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.

Resource Description Framework[Bearbeiten | Quelltext bearbeiten]

Im RDF (Resource Description Framework) werden Graphen mit Hilfe von Triples und Quads modelliert. Triples bestehen aus drei Elementen in der Form Knoten-Kante-Knoten, welche einen komplexen Graphen bilden. Quads erweitern Triples um zusätzliche Kontextinformationen, wodurch Triples leichter in Gruppen zusammengefasst werden können. 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 komplizierte Graphen, aber auch Schemata für Graphen entwickelt werden. Mit Hilfe von Ontologien, d. h. kontrollierten Wörterbüchern bekannter Begriffe und ihrer Bedeutung, kann einem Computer hiermit in gewisser Weise die Fähigkeit gegeben werden, logische Schlussfolgerungen (Inferenz) zu ziehen und neue Informationen im Graph zu hinterlegen.

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.

Abgrenzung[Bearbeiten | Quelltext bearbeiten]

Relationale Datenbanken[Bearbeiten | Quelltext bearbeiten]

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.

Objektorientierte Modelle[Bearbeiten | Quelltext bearbeiten]

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.

Algorithmen[Bearbeiten | Quelltext bearbeiten]

Wichtige Algorithmen zur Abfrage von Knoten und Kanten sind:

Abfragesprachen[Bearbeiten | Quelltext bearbeiten]

Bisher gibt es 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.
  • SPARQL - vom W3C spezifizierte Abfragesprache für RDF-Datenmodelle

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]