← Back to the section

For the choice between the relational and document models the rule is simple: a tree read as a whole is a document; linked entities with joins are tables. But there is a third case people remember less often: data where many-to-many relationships outnumber the entities themselves. People know people, work at companies, attend events; products relate to products ("bought together"); accounts transfer money to accounts. That is a graph — and the question is what to store and traverse it with.

How to tell your data is a graph

Two signs, both about queries rather than storage:

  • Queries "N steps deep" where N is not known in advance. "All subcategories of a category — to any depth," "everyone under this manager down the chain," "is there a path from account A to account B through a chain of transfers." In plain SQL the number of JOINs is fixed when the query is written; here it depends on the data.
  • Relationships are heterogeneous and live lives of their own. In a social graph the edges "friends with," "works at," "commented on" connect vertices of different types, and the edges themselves carry properties (friends since which year, employed in which role). When relationships behave like that, the link table stops being a boring technical detail and becomes the main content of the database.

If you only have the first sign and one or two hierarchies — you do not need a graph, recursive SQL will do. If you have both and relationship queries are the core of the product, read to the end.

A hierarchy in PostgreSQL: adjacency list + WITH RECURSIVE

The classic way to store a tree is an adjacency list: each row references its parent.

CREATE TABLE categories (
    id        bigint PRIMARY KEY,
    parent_id bigint REFERENCES categories (id),
    name      text NOT NULL
);

A plain JOIN cannot fetch a whole branch — the depth is unknown. That is what a recursive common table expression is for:

WITH RECURSIVE subtree AS (
    SELECT id, parent_id, name, 1 AS depth
    FROM categories
    WHERE id = 42                          -- the branch root

    UNION ALL

    SELECT c.id, c.parent_id, c.name, s.depth + 1
    FROM categories c
    JOIN subtree s ON c.parent_id = s.id   -- the recursive step
)
SELECT * FROM subtree;

Read it like this: the seed part (before UNION ALL) puts the root into the result; the recursive part joins children to what has already been found — and repeats while new rows keep appearing. The same technique handles an org chart ("all reports down the chain" — same table, manager_id instead of parent_id), nested comment threads, and bill-of-materials explosion.

Two practical details. First, cycle protection: if the data contains a loop (A is B's parent, B is A's parent), the query spins forever; the safeguard is either accumulating the path into an array and checking id <> ALL(path), or capping depth. Second, performance: a recursive CTE is efficient when every step hits an index (CREATE INDEX ON categories (parent_id)); without one, every step is a full scan.

PostgreSQL has other tools for hierarchies — materialized path with ltree, closure tables — but adjacency list + WITH RECURSIVE covers the vast majority of cases and requires no denormalization.

Where recursive SQL hits its limit

A general graph in a relational database is stored as two tables — vertices and edges:

CREATE TABLE vertices (
    id         bigint PRIMARY KEY,
    kind       text  NOT NULL,   -- person, company, event…
    properties jsonb NOT NULL
);
CREATE TABLE edges (
    from_id    bigint NOT NULL REFERENCES vertices (id),
    to_id      bigint NOT NULL REFERENCES vertices (id),
    label      text   NOT NULL,  -- friend_of, works_at…
    properties jsonb  NOT NULL
);
CREATE INDEX ON edges (from_id);
CREATE INDEX ON edges (to_id);

Storage is the easy part. The trouble starts with queries. "Find people born in the US who live in Europe," where birthplaces come at different granularity (city → state → country → continent), is a traversal of "located in" edges to arbitrary depth in two directions at once. In recursive SQL that query runs to about thirty lines across four CTEs; in the graph query language Cypher — four:

MATCH
  (p:Person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (:Location {name:'United States'}),
  (p)        -[:LIVES_IN]-> () -[:WITHIN*0..]-> (:Location {name:'Europe'})
RETURN p.name

*0.. means "zero or more edges" — like * in regular expressions, but for relationships. When queries of this kind are everyday work, the difference of thirty lines versus four becomes a difference in how fast the team can think.

When a graph database is the honest choice

Graph databases (Neo4j and others) implement the property graph model: a vertex and an edge each have an identifier and a set of properties, edges are typed, and no schema restricts what can be connected to what. The model's strength is evolvability: a new kind of relationship is just new edges with a new label — no migrations, no reshaping of tables. Curiously, a similar idea — the CODASYL network model — was the relational model's main rival back in the 1970s and lost; graph databases are not its reincarnation: any vertex is reachable through an index, and queries are declarative instead of manual pointer navigation.

Practical guideposts for the fork:

  • One or two hierarchies (categories, org chart, comments) — PostgreSQL + WITH RECURSIVE. A separate database for the sake of a tree is extra infrastructure.
  • Graph queries exist but make up 5% of the load — still PostgreSQL: two tables, recursive CTEs, indexes on both ends of the edge. Less expressive than Cypher, but no second database to operate.
  • Traversal is the core of the product (recommendations, fraud detection over transfer chains, social features, a knowledge graph) — a graph database earns its keep: the query language and the storage are both built for traversal, and there is a lot of it.

A separate database has a separate price: replication, backups, monitoring, one more system in the team's heads — the same considerations as in any polyglot persistence setup. Pay it for the core of the product, not for a single feature.

Where this applies

The fork shows up not when you pick a database but later — when a live project grows its first hierarchy or its first "down the chain" query. The right first move is almost always the same: WITH RECURSIVE in the database you already run. Moving to a graph database is a product-level decision, and it should be made on numbers: how many traversal queries, how deep, what share of the load.

Where beginners stumble:

  • Faking depth with workarounds — five self-joins "just in case," or loading the whole table into memory and traversing in code. WITH RECURSIVE solves this properly.
  • Forgetting about cycles — a recursive query over data with a loop hangs; a path check or a depth cap is mandatory for general graphs.
  • Bringing in a graph database for a single hierarchy — a second database in operation costs more than thirty lines of SQL.
  • Modeling a graph in a document database — nesting expresses a one-to-many tree well, but many-to-many links between documents turn into joins emulated in application code.

What to read next: PostgreSQL or MongoDB — the neighboring fork about the data model; composite indexes — so the recursive step runs on an index; document modeling in MongoDB — embed vs reference. The primary source is Martin Kleppmann, "Designing Data-Intensive Applications," chapter 2.