Graphdatenbank

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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. Sowohl Knoten als auch Kanten können Eigenschaften, sogenannte Properties (bspw. Gewicht: 10kg, Farbe: Rot, Name: Alice), besitzen. In diesem Zusammenhang spricht man folglich auch von einem Property-Graphen. Durch diese Spezialisierung auf Property-Graphen unterscheiden sich Graphdatenbanken von den klassischen Datenmodellen der Relationalen Datenbanken aber auch der RDF/Triple-/Quad-Stores, welche vorwiegend im Semantic Web Anwendung finden.

Graphdatenbanken bieten eine Reihe von spezialisierten Graphalgorithmen um komplizierte Datenbankabfragen zu vereinfachen. So bieten sie beispielsweise Algorithmen um 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 vernetzer Regionen im Graph zu identifizieren.

Grundlagen[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, Router. Jede Kante einer Verbindung. Jede Verbindung hat eine Bandbreite. In diesem Fall spricht man auch von gewichteten Graphen.

Abgrenzung[Bearbeiten]

Relationale Datenbanken[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, Oracle 11gR2, 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.

Semantisches Web, RDF (Resource Description Framework)[Bearbeiten]

Beim semantischen Web handelt es sich um Graphdatenbanken welche Graphen nicht auf Basis von Knoten, Kanten und Properties modellieren, sondern mit Hilfe sogenannter Triples bzw. Quads. Triples sind hierbei die elementaren Bausteine aus denen ein komplexer Graph zusammengesetzt werden kann. Quads erweitern Triples um zusätzliche Kontextinformationen, wodurch Triples leichter in Gruppen zusammengefasst werden können. Das oben genannte Beispiel lässt sich beispielsweise 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 (z.B: A --liebt-> B && B --liebt-> A => A --SindEinPaar-> B).

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

Im Vergleich zum Graphdatenbanken nach dem Property-Graph-Modell ist der Semantic Web Ansatz also sehr viel freier und flexibler, kann jedoch sehr schnell enorm an Übersichtlichkeit verlieren wenn alle Möglichkeiten des RDS-Schematas und Inferenz verwendet werden. Hier bietet ein Property-Graph einen anschaulicheren Ansatz. Einige RDF-Stores gehen deshalb dazu über, neben den klassischen semantischen Werkzeugen auch die bekannten Schnittstellen der Graphdatenbanken anzubieten.

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

Algorithmen[Bearbeiten]

Wichtige Algorithmen zur Abfrage von Knoten und Kanten sind:

Abfragesprachen[Bearbeiten]

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[Bearbeiten]

Weblinks[Bearbeiten]