Graphdatenbanksysteme

Graphdatenbanken sind spezialisiert auf vernetzte Informationen und möglichst einfache und effiziente Graph traversal.

Graphenmodell

Ein Graph besteht aus einer Menge an Knoten und Kanten. Graphen werden genutzt, um eine Vielfalt an Problemen durch Knoten, Kanten und ihren Beziehungen darzustellen, z.B. in Navigationssystemen, in denen die Wege in Form von Graphen gespeichert werden.

Graph traversal

Graph traversal wird meist zur Suche von Knoten verwendet. Es gibt verschiedene Algorithmen für solche Suchanfragen in einem Graphen, die sich grob einteilen lassen in

  • Breiten- und Tiefensuche (engl: breadth-first search, BFS und depth-first search, DFS)

    Die Breitensuche beginnt mit allen Nachbarknoten des Startknotens. Im nächsten Schritt werden dann die Nachbarn der Nachbarn durchsucht. Die Pfadlänge erhöht sich mit jeder Iteration.

    Die Tiefensuche verfolgt einen Pfad solange, bis ein Knoten ohne ausgehende Kanten gefunden wird. Der Pfad wird anschließend zurückverfolgt bis zu einem Knoten, der noch weitere ausgehende Kanten hat. Dort wird die Suche dann fortgesetzt.

  • Algorithmische Traversierung

    Beispiele für die algorithmische Traversierung sind

    • Hamiltonweg (Traveling Salesman)

    • Eulerweg

    • Dijkstra-Algorithmus

  • Randomisierte Traversierung

    Der Graph wird nicht nach einem bestimmten Schema durchlaufen, sondern der nächste Knoten wird zufällig ausgewählt. Dadurch kann vor allem bei großen Graphen wesentlich schneller ein Suchergebnis präsentieren, dieses ist jedoch nicht immer das beste.

Datenbanksysteme

Typische Graphdatenbanken sind Neo4j, OrientDB InfiniteGraph und ArangoDB.

Home

Neo4j

OrientDB

InfiniteGraph

ArangoDB

GitHub

neo4j/neo4j

orientechnologies/orientdb

arangodb/arangodb

Docs

neo4j.com/docs/

orientdb.org/docs/

InfiniteGraph Tutorials

arangodb.com/documentation/

Anwendungsgebiete

CMS, Soziale Netzwerke, GIS-Systeme, ERP, …

Stammdatenverwaltung, soziale Netzwerke, Time Series, Key Value, Verkehrsmanagement

Erweiterung von Objectivity/DB-Installationen

Fraud Detection, IoT, Identitätsmanagement, E-Commerce, Netzwerk, Logistik, CMS

Entwicklungssprache

Java

Java

Java

C++, JavaScript

Lizenzen

AGPL u. kommerziell

Apache License 2.0

kommerziell

Apache License 2.0

Datenmodell

Property-Graph-Modell (PGM)

Multi-Model

Property-Graph-Modell (PGM)

Multi-Model: Dokumente, Graphen und Schlüssel/Wert-Paar

Query-Langauge

REST, Cypher, Gremlin

Extended SQL, Gremlin

Traverser API, PQL

ArangoDB Query Language (AQL)

Transaktionen, Nebenläufigkeit

  • Two-phase locking (2PL),

  • einzelner Server: ACID,

  • verteilte Systeme: BASE

ACID

ACID

ACID, MVCC – Multiversion Concurrency Control

Replikation, Skalierung

Master-Slave mit Master Failover

Multi-Master-Replikation, Sharding

Objectivity/DB, keine Graphpartitionierung

Master-Slave-Replikation, Sharding

Anmerkungen

InfiniteGraph ist eine, auf dem Objektdatenbanksysteme Objectivity/DB aufsetzende Graphdatenbank, wobei die Objekte durch Kanten verbunden werden. Hierbei sind auch mehrfache und bidirektionale Kanten erlaubt.

Iteratoren entsprechen dem Graph traversal.