.. SPDX-FileCopyrightText: 2021 cusy GmbH .. .. SPDX-License-Identifier: BSD-3-Clause Graphdatenbanksysteme ===================== Graphdatenbanken sind spezialisiert auf vernetzte Informationen und möglichst einfache und effiziente :term:`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, | Stammdatenverwaltung, soziale | Fraud Detection, IoT, | | | GIS-Systeme, ERP, … | Netzwerke, `Time Series`_, | Identitätsmanagement, | | | | `Key Value`_, | E-Commerce, Netzwerk, Logistik,| | | | Verkehrsmanagement | CMS | +------------------------+--------------------------------+--------------------------------+--------------------------------+ | **Entwicklungssprache**| Java | Java | C++, JavaScript | +------------------------+--------------------------------+--------------------------------+--------------------------------+ | **Lizenzen** | AGPL u. kommerziell | Apache License 2.0 | Apache License 2.0 | +------------------------+--------------------------------+--------------------------------+--------------------------------+ | **Datenmodell** | :term:`Property-Graph-Modell` | Multi-Model | Multi-Model: Dokumente, Graphen| | | | | und :term:`Schlüssel/Wert-Paar`| +------------------------+--------------------------------+--------------------------------+--------------------------------+ | **Query-Language** | REST, `Cypher`_, `Gremlin`_ | `Extended SQL`_, `Gremlin`_ |`ArangoDB Query Language (AQL)`_| +------------------------+--------------------------------+--------------------------------+--------------------------------+ | **Transaktionen, | * :term:`Two-phase locking | :term:`ACID` | :term:`ACID`, | | Nebenläufigkeit** | (2PL)`, | | :term:`MVCC – Multiversion | | | * einzelner Server: | | Concurrency Control` | | | :term:`ACID`, | | | | | * verteilte Systeme: | | | | | :term:`BASE` | | | +------------------------+--------------------------------+--------------------------------+--------------------------------+ | **Replikation, | Master-Slave mit Master | Multi-Master-Replikation, | Master-Slave-Replikation, | | Skalierung** | Failover | Sharding | Sharding | | | | | | +------------------------+--------------------------------+--------------------------------+--------------------------------+ | **Anmerkungen** | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +------------------------+--------------------------------+--------------------------------+--------------------------------+ .. seealso:: * `Apache TinkerPop Home `_ * `TinkerPop Documentation `_ * `github.com/apache/tinkerpop `_ * `Practical Gremlin – An Apache TinkerPop Tutorial `_ * `gremlinpython `_ .. _`Neo4j`: https://neo4j.com .. _`OrientDB`: https://orientdb.org/ .. _`neo4j/neo4j`: https://github.com/neo4j/neo4j .. _`ArangoDB`: https://arangodb.com .. _`orientechnologies/orientdb`: https://github.com/orientechnologies/orientdb .. _`arangodb/arangodb`: https://github.com/arangodb/arangodb .. _`Time Series`: https://orientdb.org/docs//2.0/orientdb.wiki/Time-series-use-case.html .. _`Key Value`: https://orientdb.org/docs//2.0/orientdb.wiki/Key-Value-use-case.html .. _`neo4j.com/docs/`: https://neo4j.com/docs/ .. _`orientdb.org/docs/`: https://orientdb.org/docs/ .. _`docs.arangodb.com`: https://docs.arangodb.com/stable/ .. _`Extended SQL`: https://orientdb.org/docs/2.2.x/SQL.html .. _`Cypher`: https://neo4j.com/docs/1.4/cypher-query-lang.html .. _`Gremlin`: https://github.com/tinkerpop/gremlin/wiki .. _`ArangoDB Query Language (AQL)`: https://docs.arangodb.com/stable/aql/