Graph Databases
In every model so far, relationships were a side issue: a foreign key, an embedded array, or not supported at all. In a graph database relationships are the main thing. This scriptum answers:
- When are relationships the question?
- What does the property graph model look like?
- Why are graph databases fast at following relationships?
- How do you read a first Cypher query?
- How do we classify graph databases?
This is the first contact only. In the next block we look at graphs in depth: graph theory, creating graphs with Cypher, and graph algorithms.
1. When relationships are the question
| Question | Domain |
|---|---|
| Who are the friends of my friends? | social networks |
| Customers who bought this also bought …? | recommendations |
| Are these 20 bank accounts secretly connected? | fraud detection |
| What is the fastest route from Krems to Linz? | navigation, logistics |
| Which services break if this server goes down? | IT infrastructure, dependencies |
| Which component is used in which product? | bill of materials |
All of these ask: “How is A connected to B — over how many steps?“
2. The property graph model
| Element | Description | Example |
|---|---|---|
| Node | a thing / entity | Anna, the Keyboard |
| Label | the type of a node (a node may have several) | :Person, :Product |
| Relationship | a directed connection between exactly two nodes, with exactly one type | FRIENDS_WITH, BOUGHT |
| Property | key-value pair on a node or a relationship | name: "Anna", since: 2024 |
Direction: every relationship is stored with a direction, but you can query it in both directions. For symmetric relationships like
FRIENDS_WITHwe store it once and ignore the direction when querying.
2.1 The other graph model: RDF
Besides property graphs there are RDF triple stores (semantic web, knowledge graphs, e.g. Wikidata). Everything is a triple subject – predicate – object:
<Anna> <friendsWith> <Ben> .
<Anna> <livesIn> <Krems> .
Query language: SPARQL. We focus on property graphs (Neo4j).
3. Why graph databases are fast at relationships
- Relational: a relationship is a value in a column. To follow it, the database searches an index — for every single step again. With every extra step the intermediate result grows.
- Graph (native storage): every node stores direct references to its relationships and neighbours — index-free adjacency. Following a relationship is a pointer hop.
| Relational (JOIN) | Graph (traversal) | |
|---|---|---|
| Cost per step | index lookup, grows with table size (O(log n)) | pointer hop, independent of graph size (O(1)) |
| Total cost depends on | size of the tables involved | size of the part of the graph you visit |
| Query for 2, 3, 4 … steps | one more self-JOIN per step | change one number |
Graph databases are not magic: a query that visits a million nodes is slow everywhere. The advantage is that the cost depends on what you touch, not on how big the database is.
4. A first look at Cypher
Cypher is Neo4j’s query language. Its patterns look like ASCII art:
(a:Person) a node with label Person
-[:FRIENDS_WITH]-> a directed relationship of type FRIENDS_WITH
-[:FRIENDS_WITH]- the same, direction ignored
(a)-[:BOUGHT]->(p:Product) a pattern: a Person who BOUGHT a Product
Reading a query:
MATCH (a:Person {name: "Anna Berger"})-[:FRIENDS_WITH]-(friend)
RETURN friend.name, friend.city
ORDER BY friend.name“Find the person named Anna Berger, follow her FRIENDS_WITH relationships in either direction, and return the name and city of every friend.”
Variable path length — the thing SQL cannot express nicely:
MATCH (a:Person {name: "Anna Berger"})-[:FRIENDS_WITH*1..3]-(p)
RETURN count(DISTINCT p)“How many people can Anna reach in 1 to 3 steps?” — For 4 steps, change 3 to 4. In SQL you would need another self-JOIN.
Since 2024 there is an ISO standard for graph query languages: GQL (ISO/IEC 39075). It is largely based on Cypher — so Cypher knowledge is future-proof.
5. Consistency, CAP and scaling
- Neo4j has full ACID transactions — like a relational database.
- A single Neo4j server is CA (no partition possible).
- A Neo4j cluster (Enterprise Edition) replicates writes with the Raft consensus protocol: a majority must confirm → CP.
- Scaling is the weak point: a graph is hard to cut into shards — every relationship between two shards becomes a slow network call. Graph databases mostly scale up and add read replicas (X-axis).
6. When not to use a graph database
- Simple lists and reports without deep relationships (“all orders of October”) → relational.
- Huge amounts of independent records (sensor data, logs) → wide-column / columnar.
- Lookups by one key only (sessions, cache) → key-value.
- Large aggregations over all data (
SUMover 100 million sales) → columnar analytics.
7. Classification: graph databases
| Criterion | Graph |
|---|---|
| Data model | nodes and relationships, both with properties (property graph); alternatively RDF triples |
| Schema | flexible; optional constraints (unique, existence) |
| Query language | Cypher / GQL (ISO 2024), Gremlin, SPARQL for RDF |
| Relationships | stored as first-class elements, traversed by pointer (index-free adjacency) |
| Transactions | ACID (Neo4j) |
| CAP (default) | single server CA, cluster CP (Raft) |
| Scaling | mostly vertical + read replicas; sharding is hard |
| Strengths | deep and variable-length relationships, pattern matching, recommendations, paths |
| Weaknesses | horizontal scaling, bulk aggregations, simple tabular data |
| Typical use | social networks, recommendations, fraud detection, routing, dependency analysis, knowledge graphs |
| Examples | Neo4j, Memgraph, Amazon Neptune, ArangoDB (multi-model), GraphDB (RDF) |
8. The complete grid
| Criterion | Relational | Document | Key-value | Graph | Wide-column |
|---|---|---|---|---|---|
| Data model | tables | JSON trees | key → value | nodes + relationships | row key → many columns |
| Schema | fixed | flexible, optional validation | none | flexible, optional constraints | table defined, columns per row flexible |
| Query language | SQL | MongoDB API | GET / SET | Cypher / GQL | CQL (SQL-like, no JOINs) |
| Relationships | FK + JOIN | embedding / references | none | stored, traversed | none (denormalised) |
| Transactions | ACID | atomic per document | atomic per command | ACID | atomic per row |
| CAP (default) | CA / CP | CP | AP | CA / CP | AP (tunable) |
| Scaling | vertical | sharding by shard key | hash slots | vertical + replicas | horizontal, by partition key |
| Strength | ad-hoc queries, integrity | whole aggregates, flexibility | speed, simplicity | deep relationships | massive writes |
| Weakness | write scaling, JOIN cost | duplicates, many-to-many | access only by key | scaling out | queries only by key |
| Typical use | ERP, banking, orders | catalogues, profiles, CMS | cache, sessions, counters | social, recommendations, fraud | IoT, logs, messaging |
| Example | MySQL | MongoDB | Valkey | Neo4j | Cassandra |
9. Summary
- Graph databases make relationships first-class: stored, typed, with properties.
- Property graph: nodes (with labels), directed relationships (with one type), properties on both.
- Index-free adjacency: following a relationship costs the same no matter how big the database is.
- Cypher describes patterns as ASCII art; variable path lengths like
*1..3replace chains of self-JOINs. - Neo4j is ACID, CA as single server, CP as cluster — but hard to shard.
10. Self-check questions
- Give three questions that are “relationship questions”.
- Name the four building blocks of a property graph.
- Can a relationship have properties? Give an example.
- Can a relationship be undirected in Neo4j?
- What is index-free adjacency?
- Why does a relational “friends of friends of friends” query get slower when the
friendshiptable grows, but the graph query does not (as much)? - Read this Cypher pattern aloud:
(c:Customer)-[:BOUGHT]->(p:Product)<-[:BOUGHT]-(other:Customer) - What does
*1..3mean in a Cypher pattern? - What is GQL?
- Why are graph databases hard to scale horizontally?
- Name a task for which a graph database would be a bad choice.
</>
Short answers
- e.g. friends of friends, product recommendations, shortest route, fraud rings, dependency chains.
- Nodes, labels, relationships (with a type), properties.
- Yes, e.g.
FRIENDS_WITH {since: 2024},BOUGHT {on: 2026-09-12}. - No — every relationship is stored with a direction, but queries can ignore the direction (
-[:FRIENDS_WITH]-). - Every node directly references its neighbours, so following a relationship needs no index lookup.
- Every JOIN step searches an index whose cost depends on the table size; a graph step follows a stored pointer, so the cost depends only on the visited part of the graph.
- “A customer c bought a product p, which was also bought by another customer other.”
- The relationship may be repeated between 1 and 3 times — paths of length 1, 2 or 3.
- The ISO standard graph query language (2024), largely based on Cypher.
- Relationships between nodes on different servers become slow network calls; a graph cannot be cut cleanly.
- e.g. a simple cache, summing millions of sales, storing log data.