Graph Databases

A Relationship Problem in Disguise

Imagine you’re building a social network. Your product team wants a feature: “Show me friends of friends who also like hiking and live within 50 miles of me.” Simple requirement, right?

In a relational database, you’d need to:

1. Look up your friends (SELECT from users_friends WHERE user_id = me)
2. For each friend, look up their friends (JOIN users_friends again)
3. For each friend-of-friend, check their interests and location (JOIN with interests, JOIN with locations)
4. Apply distance calculations on retrieved rows

If you have 1 million users, each with 500 friends on average, and each friend-of-friend has their own network? You’re executing millions of join operations, each scanning potentially billions of rows. The query that should return in milliseconds now takes minutes.

This is the fundamental problem that graph databases solve. Relationships are not second-class citizens in a graph database — they are first-class citizens. They’re stored explicitly, indexed directly, and traversed without expensive join operations.

Welcome to graph databases: a data model where relationships matter as much as the entities themselves.

What Is a Graph Database?

A graph database stores and retrieves data by relationships rather than by rows and tables. The core data structure is elegant:

• Nodes: Entities (users, products, locations, accounts)
• Edges: Relationships between entities (friend_of, purchased, located_in, manages)
• Properties: Attributes on nodes and edges (name, created_at, strength of relationship)

This is fundamentally different from relational databases. A relational database models everything as tables with foreign keys. A graph database models everything as an actual graph.

Two Graph Models

Labeled Property Graphs (LPG) are the most common model in production systems:

• Each node has a label (type) and properties (attributes)
• Each edge has a type and properties
• A single graph can contain multiple node and edge types
• Examples: Neo4j, ArangoDB, Amazon Neptune, JanusGraph

RDF Triple Stores are semantic-focused:

• Everything is expressed as subject-predicate-object triples
• More rigid but powerful for knowledge representation
• Examples: SPARQL endpoint, AllegroGraph, Virtuoso

We’ll focus on labeled property graphs, as they’re more common in system design contexts.

Index-Free Adjacency

Here’s the magic behind graph databases: index-free adjacency. Rather than querying an index to find related nodes (like a foreign key join), each node directly maintains pointers to its neighbors. When you want to find a user’s friends, you don’t scan an index — you directly traverse the relationships stored on that user’s node.

This means:

• Finding neighbors of a node is O(1) in terms of disk operations (the neighbors are directly referenced)
• Traversing multiple hops (friends -> friends -> friends) scales with the path length, not the total data size
• Join costs are eliminated because relationships are pre-computed and stored

This is why graph databases excel at relationship-heavy queries where relational databases struggle.

A Social Network at a Party

Let’s use an analogy: imagine a physical social network as a party.

In a relational world, you’re the bouncer with a clipboard. To find “friends of friends of John,” you:

1. Scan your guest list to find all of John’s friends
2. For each friend, scan the list again to find their friends
3. Cross-reference against attendance records
4. Apply filters

With thousands of guests, each with hundreds of connections, your clipboard work is endless.

In a graph world, each person (node) literally holds hands with their friends (edges). You ask John: “Who are you holding hands with?” He points to Alice, Bob, Carol. You ask Alice: “Who are you holding hands with?” She points to Bob, David, Eve. No clipboard scanning needed. Following the chain of hands is direct and fast.

This is why graph databases are so effective at traversal — the relationship data structure is optimized for following connections, not scanning tables.

Technical Architecture and Storage

Graph database engines take two fundamentally different approaches:

Native Graph Engines

Store graph data in a format optimized for graph operations:

• Each node maintains explicit references to its edges
• Edges are stored to enable bi-directional traversal
• Indexes are built around graph structures, not table rows
• Examples: Neo4j (most mature), JanusGraph, ArangoDB’s graph mode

Advantages:

• Index-free adjacency means traversals don’t require index lookups
• Relationship traversal performance is consistent regardless of graph size
• Query planning is graph-aware

Disadvantages:

• Scaling writes across multiple nodes is challenging
• Transactions must coordinate across nodes that own the graph structure

Graph Layers on Other Systems

Store graph data in relational or document stores, adding graph query semantics on top:

• Amazon Neptune: Graph abstraction over AWS’s proprietary storage layer
• MongoDB with graph features: Documents with relationship queries
• PostgreSQL extensions: Apache AGE for property graphs

Advantages:

• Leverage mature operational infrastructure
• Often easier to scale writes horizontally
• Can handle mixed workloads (tabular + graph)

Disadvantages:

• Graph traversals still involve more joins than native engines
• Performance degrades more quickly with deep traversals

Query Languages and Traversal

Different graph databases use different query languages, but they share common patterns.

Cypher (Neo4j)

Cypher is the most intuitive graph query language. It uses ASCII art to represent patterns:

// Find a user and their friends
MATCH (user:User {name: "Alice"})
RETURN user

// Find friends of friends
MATCH (user:User {name: "Alice"})
  -[:FRIEND_OF]->
  (friend:User)
  -[:FRIEND_OF]->
  (foaf:User)
RETURN DISTINCT foaf.name

// Shortest path between two users
MATCH (alice:User {name: "Alice"}),
      (bob:User {name: "Bob"}),
      path = shortestPath(
        (alice)-[*]-(bob)
      )
RETURN path

// Create nodes and relationships
CREATE (alice:User {name: "Alice", age: 28})
CREATE (bob:User {name: "Bob", age: 30})
CREATE (alice)-[:FRIEND_OF {since: 2020}]->(bob)

Gremlin (Apache TinkerPop)

Gremlin is more functional/procedural, common in distributed systems:

// Traverse graph
g.V().hasLabel('User').has('name', 'Alice')
  .out('FRIEND_OF')
  .out('FRIEND_OF')
  .distinct()

// With filtering
g.V().hasLabel('User')
  .has('name', 'Alice')
  .out('FRIEND_OF')
  .has('location', 'Seattle')

SPARQL (RDF Stores)

SPARQL is XML-based, verbose but powerful for semantic queries:

SELECT ?foaf
WHERE {
  ?alice foaf:knows ?friend .
  ?friend foaf:knows ?foaf .
}

Graph Algorithms: Beyond Simple Traversal

Modern graph databases include or integrate with algorithms that work on entire graph structures:

Shortest Path (BFS / Dijkstra)

Find the minimum number of relationships between two entities. Use cases: Navigation networks, LinkedIn “how do you know this person,” fraud rings

MATCH path = shortestPath(
  (source:User)-[*..10]-(target:User)
)
WHERE source.name = "Alice" AND target.name = "Bob"
RETURN path

Complexity: O(V + E) for BFS (unweighted), O((V + E) log V) for Dijkstra (weighted)

PageRank

Identify high-influence nodes based on graph structure. Originally used by Google for web ranking. Use cases: Recommendation systems, fraud detection (suspicious account networks), finding authority figures in networks

Community Detection (Louvain)

Find tightly connected clusters in a graph. Use cases: Customer segmentation, fraud rings, identifying organizational clusters

Centrality Measures

• Degree Centrality: How many connections does a node have?
• Betweenness Centrality: How many shortest paths pass through this node? (bridge finder)
• Closeness Centrality: How close is this node to all others?

Popular Graph Databases Compared

Database	Model	Query Language	Scaling	Maturity	Best For
Neo4j	LPG	Cypher	Single-server or HA cluster	Very Mature	Social networks, reference data, knowledge graphs
Amazon Neptune	LPG + RDF	Gremlin, SPARQL, openCypher	Managed, automatic scaling	Mature	AWS-native apps, multi-model queries
JanusGraph	LPG	Gremlin	Excellent (requires external storage)	Mature	Large-scale graphs, distributed deployments
ArangoDB	Multi-model	AQL	Good	Mature	Mixed workloads, document + graph
Dgraph	LPG	GraphQL+	Excellent	Mature	API-first, GraphQL-friendly applications
TigerGraph	LPG	GSQL	Excellent	Maturing	Real-time analytics, algorithmic queries

Pro tip: Neo4j dominates mindshare and has the richest ecosystem, but it’s also proprietary and can be expensive at scale. If you need distributed scaling from day one, consider JanusGraph (open-source, pluggable storage) or Dgraph (GraphQL-native).

The Hard Problem: Scaling Graph Databases

Scaling a graph database is fundamentally harder than sharding relational tables.

The Partitioning Problem

Imagine partitioning a social network by user ID. User 1-1M goes to Shard A, User 1M-2M goes to Shard B. That works until User 1000 wants to traverse to their friends, who might live in Shard A, B, and C. You now have distributed traversals — network hops, latency, complexity.

Two main strategies:

• Vertex-Cut Partitioning: Shard by edge target (replicate popular nodes across shards).
• Edge-Cut Partitioning: Shard by node ID.

Write Performance vs Traversal Performance

• Single-node: Excellent write performance (ACID transactions, the whole graph in memory/disk)
• Distributed: Write consistency requires coordination across shards, reducing throughput

Real-World Applications

Friend Recommendations

// Recommend friends: users who are friends-of-friends but not already friends
MATCH (me:User {name: "Alice"})-[:FRIEND_OF]->(friend)-[:FRIEND_OF]->(foaf:User)
WHERE NOT (me)-[:FRIEND_OF]->(foaf)
  AND foaf.interests CONTAINS "hiking"
  AND distance(point({latitude: me.lat, longitude: me.lon}),
               point({latitude: foaf.lat, longitude: foaf.lon})) < 50
RETURN foaf.name, count(*) AS mutual_friends
ORDER BY mutual_friends DESC
LIMIT 10

Fraud Detection

// Find accounts that form a tight cluster (circular money transfers)
MATCH (account1:Account)
  -[:TRANSFERS_TO]->(account2:Account)
  -[:TRANSFERS_TO]->(account3:Account)
  -[:TRANSFERS_TO]->(account1)
WHERE account1.risk_score > 0.5
RETURN account1, account2, account3

Key Takeaways

• Graphs excel at relationships: Index-free adjacency means traversing relationships is O(1) per hop, not O(n) with joins
• Choose your model carefully: Labeled property graphs are most common; RDF is for semantic reasoning
• Scaling is hard: Partitioning graphs is fundamentally more complex than sharding relational data
• Query language matters: Cypher is intuitive, Gremlin is powerful, SPARQL is semantic—pick based on your use case
• Algorithms are built-in: Modern graph databases include PageRank, community detection, and shortest path

---

In the next chapter, we’ll shift to analytical queries: Data Warehouses vs Data Lakes.

// Cypher Query (Neo4j): Find Friends-of-Friends who like "Hiking"
MATCH (user:User {id: "USR_101"})-[:FRIEND_OF]->(f:User)-[:FRIEND_OF]->(fof:User)
WHERE NOT (user)-[:FRIEND_OF]->(fof) 
  AND fof.interests CONTAINS "hiking"
RETURN fof.name, COUNT(f) AS mutual_friends
ORDER BY mutual_friends DESC
LIMIT 10;

// ❌ Error: Anti-Pattern (Unbounded Multi-Hop Traversal on Dense Super-Nodes)
MATCH (u:User {id: "101"})-[*..15]-(connected:User) RETURN connected;
// Explodes into billions of paths! Crashes database server RAM memory!

// ✅ Safe: Idiomatic Pattern (Bound Traversal Depth & Specify Edge Types)
MATCH (u:User {id: "101"})-[:FRIEND_OF*1..3]->(connected:User) RETURN connected LIMIT 100;