Skip to content

Graph Databases#

Problem statement (interviewer prompt)

A social network must compute "people you may know" - friends-of-friends-of-friends, excluding existing friends, plus mutual count. In SQL this requires three self-joins on a 1B-row table. Design a storage and query model that makes this efficient.

A graph database stores entities as nodes (vertices) and relationships as first-class edges. Multi-hop traversals ((:Person)-[:KNOWS*1..3]->(:Person)) run in constant time per hop because edges are indexed by source.

flowchart LR
  A((Alice)) -->|KNOWS| B((Bob))
  A -->|KNOWS| C((Carol))
  B -->|KNOWS| D((David))
  C -->|KNOWS| D
  D -->|WORKS_AT| E((Acme))
  A -->|WORKS_AT| E

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class A,B,C,D,E client;
Directed acyclic graph example
Source: Wikimedia Commons. CC BY-SA / public domain.

Implementations: Neo4j, JanusGraph, ArangoDB, Amazon Neptune, TigerGraph, Dgraph, Memgraph. Property-graph model (Cypher) dominates; RDF/SPARQL is the alternative for semantic data.

A graph database represents data as nodes and edges, both with arbitrary properties. The killer use case: queries that traverse relationships dynamically (friend-of-friend, fraud rings, supply chain reachability).

Two models#

Property graph#

CREATE (a:Person {name: 'Alice'})-[:KNOWS {since: 2018}]->(b:Person {name: 'Bob'})
MATCH (a:Person {name: 'Alice'})-[:KNOWS*1..3]-(p:Person)
WHERE NOT (a)-[:KNOWS]-(p)
RETURN p, count(*) AS mutual ORDER BY mutual DESC LIMIT 10

Used by: Neo4j (Cypher), Memgraph, Amazon Neptune (Gremlin), TigerGraph (GSQL), JanusGraph.

RDF / triple store#

:Alice :knows :Bob .
:Alice :worksAt :Acme .
:Bob   :worksAt :Acme .

SELECT ?colleague WHERE {
  :Alice :worksAt ?company .
  ?colleague :worksAt ?company .
  FILTER (?colleague != :Alice)
}

Used by: GraphDB, Stardog, Amazon Neptune (also RDF), Apache Jena. Strong for semantic-web / ontology workloads.

Index-free adjacency#

A native graph database stores edges in a way that lets each node directly reach its neighbours - no index lookup per hop:

flowchart LR
  A[Alice<br/>edge ptr] --> E1[Edge A→Bob]
  E1 --> B[Bob]
  A --> E2[Edge A→Carol]
  E2 --> C[Carol]

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class A,B,C datastore;
    class E1,E2 edge;

A 3-hop traversal is O(N + E) in the traversed subgraph, not in the total graph size. In SQL, the same query is three self-joins, each O(N log N) over the whole table.

Where graph DBs shine#

Pattern Example
Multi-hop relationship traversal Friends of friends
Pattern matching Money laundering rings (cycles in transfers)
Path finding Shortest path in road network
Recommendation Collaborative filtering by graph proximity
Knowledge graphs Entity disambiguation, Q&A over ontologies
Authorization "Can Alice access doc X?" via permission chains

Where they hurt#

  • Aggregations across all nodes: column stores or warehouses win.
  • Heavy write throughput: native graphs struggle with millions of edge writes/sec.
  • Joins across tabular dimensions: SQL still cleaner.
  • Sharding: graph partitioning is NP-hard; cross-shard traversals are expensive.

Sharding strategy#

Cuts edges - any traversal crossing the cut costs an extra network hop.

flowchart LR
  subgraph S1[Shard 1]
    A((A))
    B((B))
    A --- B
  end
  subgraph S2[Shard 2]
    C((C))
    D((D))
    C --- D
  end
  B -. cross-shard edge .- C

Algorithms: METIS partitioning, label propagation. Neo4j Fabric and Amazon Neptune scale by sharding; TigerGraph and Dgraph are sharded-native.

Graph in SQL?#

Postgres + recursive CTEs handle small graphs:

WITH RECURSIVE foaf AS (
  SELECT friend_id, 1 AS depth FROM friends WHERE user_id = 'alice'
  UNION
  SELECT f.friend_id, depth+1 FROM friends f JOIN foaf ON f.user_id = foaf.friend_id
  WHERE depth < 3
)
SELECT friend_id, COUNT(*) FROM foaf GROUP BY friend_id;

Works for small graphs (< 1M edges) and shallow traversals. For deep, broad graphs, a dedicated graph DB wins.

ML on graphs#

Graph neural networks (GNNs) operate directly on graph structure. PyG, DGL, GraphSAGE. Often paired with vector databases for hybrid retrieval (similarity + graph proximity).

Where graph DBs fit#

flowchart TB
  GR((Graph DB))
  DBS[Database sharding<br/>partitioning is NP-hard]
  VEC[Vector databases<br/>often combined with graphs]
  REC[Recommendation system<br/>top consumer]
  SRCH[Search internals<br/>knowledge-graph augment]
  GR --> DBS
  GR -. hybrid .- VEC
  GR --> REC
  GR -. augments .- SRCH

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class GR service;
    class DBS,VEC,REC,SRCH datastore;

Glossary & fundamentals#

Tag Concept What it is Page
HLD Database sharding partitioning the graph database-sharding
HLD Vector databases semantic complement of graphs vector-databases
HLD Recommendation system top consumer of graph traversal recommendation-system
HLD Search internals knowledge graphs supplement search search-internals

Quick reference#

Two models#

  • Property graph (Cypher, Gremlin) - dominant
  • RDF / triples (SPARQL) - semantic web

Index-free adjacency#

Each node has direct pointers to its edges; k-hop = O(traversed subgraph), not O(N).

When graph wins#

  • Friends-of-friends
  • Fraud rings / cycles
  • Path finding
  • Permissions chains
  • Knowledge graphs

When graph loses#

  • Heavy aggregations across all nodes (use OLAP)
  • Million writes/sec (most native graphs struggle)
  • Cross-shard traversals expensive

Implementations#

DB Notes
Neo4j Cypher; market leader
Amazon Neptune Cypher + Gremlin + SPARQL
TigerGraph Sharded-native
Dgraph Distributed property graph
Memgraph In-memory
JanusGraph Embedded over Cassandra/HBase

Sharding#

NP-hard; minimise edge cuts via METIS / label propagation.

SQL alternative#

Recursive CTE for small graphs; doesn't scale to deep + broad traversals.

Refs#

  • Robinson, Webber, Eifrem - Graph Databases
  • Neo4j Cypher manual
  • Apache TinkerPop / Gremlin
  • GraphSAGE paper

FAQ#

What is a graph database?#

A graph database stores entities as nodes and relationships as first-class edges, so multi-hop traversals run in constant time per hop instead of needing joins.

Graph database vs relational database, when use which?#

Use a graph DB for traversal-heavy workloads like friends-of-friends, fraud rings, and reachability. Use SQL for aggregations and tabular reports.

What is the difference between property graph and RDF?#

Property graphs (Neo4j, Cypher) attach key-value properties to nodes and edges. RDF uses subject-predicate-object triples and SPARQL, common for semantic data.

Which graph database should I pick?#

Neo4j leads for general property graph workloads. JanusGraph and Dgraph scale horizontally. Amazon Neptune is a managed option that speaks both Cypher and SPARQL.

Why are friends-of-friends queries slow in SQL?#

A 3-hop traversal needs three self-joins on a huge edge table, each multiplying intermediate rows. Graph DBs follow edge indexes directly, in roughly O(k) hops.

Further reading#