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äsentiert werden, dieses ist jedoch nicht immer das beste.

Datenbanksysteme

Typische Graphdatenbanken sind Neo4j, OrientDB InfiniteGraph und ArangoDB.

Home

Neo4j

OrientDB

ArangoDB

GitHub

neo4j/neo4j

orientechnologies/orientdb

arangodb/arangodb

Docs

neo4j.com/docs/

orientdb.org/docs/

docs.arangodb.com

Anwendungsgebiete

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

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

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

Entwicklungssprache

Java

Java

C++, JavaScript

Lizenzen

AGPL u. kommerziell

Apache License 2.0

Apache License 2.0

Datenmodell

Property-Graph-Modell

Multi-Model

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

Query-Language

REST, Cypher, Gremlin

Extended SQL, Gremlin

ArangoDB Query Language (AQL)

Transaktionen, Nebenläufigkeit

ACID

ACID, MVCC – Multiversion Concurrency Control

Replikation, Skalierung

Master-Slave mit Master Failover

Multi-Master-Replikation, Sharding

Master-Slave-Replikation, Sharding

Anmerkungen

Siehe auch