Graph database systems#

Graph databases specialise in networked information and the simplest and most efficient possible Graph traversal.

Graph model#

A graph consists of a number of nodes and edges. Graphs are used to represent a variety of problems through nodes, edges and their relationships, for example in navigation systems in which the paths are stored in the form of graphs.

Graph traversal#

Graph traversal is mostly used to find nodes. There are different algorithms for such search queries in a graph, which can be roughly divided into

Breadth-first search, BFS and depth-first search, DFS

The breadth-first search begins with all neighboring nodes of the start node. In the next step, the neighbors of the neighbors are then searched. The path length increases with each iteration.

The depth-first search follows a path until a node with no outgoing edges is found. The path is then traced back to a node that has further outgoing edges. The search will then continue there.
Algorithmic traversal

Examples of algorithmic traversal are
- Hamiltonian path (traveling salesman)
- Eulerian path
- Dijkstra’s algorithm
Randomised traversal

The graph is not run through according to a certain scheme, but the next node is selected at random. This allows a search result to be presented much faster, especially with large graphs, but this is not always the best.

Database systems#

Typical graph databases are Neo4j, OrientDB InfiniteGraph and 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/
Application areas	CMS, social networks, GIS systems, ERP, …	Master data management, social networks, time series, key value, traffic management	Extension of Objectivity/DB installations	Fraud Detection, IoT, identity management,, e-commerce, network, logistics, CMS
Development language	Java	Java	Java	C++, JavaScript
Licenses	AGPL and commercially	Apache License 2.0	commercially	Apache License 2.0
Data model	Property graph model	Multi-Model	Property graph model	Multi-model: documents, graphs and Key/value pair
Query langauge	REST, Cypher, Gremlin	Extended SQL, Gremlin	Traverser API, PQL	ArangoDB Query Language (AQL)
Transactions, concurrency	Two-phase locking (2PL) single Server: ACID distributed systems: BASE	ACID	ACID	ACID, MVCC – Multiversion Concurrency Control
Replication, skaling	Master-slave with master failover	Multi-master replication, Sharding	Objectivity/DB, no Graph partitioning	Master-slave replication, sharding
Remarks			InfiniteGraph is a graph database on top of the Object database systems Objectivity/DB, whereby the objects are connected by edges. Multiple and bidirectional edges are also allowed here. Iterators correspond to the Graph traversal.