← Back to the section

When choosing between the relational and document models the rule is simple: a tree that's always read whole is a document; connected entities you have to join are tables. But there's a third case people remember less often: data where there are more many-to-many relationships than entities. People know people, work at companies, attend events; products relate to products ("bought together"); accounts transfer money to accounts. This is a graph — and the question is what to store it in and how to walk it.

How to tell your data is a graph

Two signs, and both are about queries, not about how the data sits:

  • Queries "N steps deep," where N isn't known in advance. "All subcategories of a category at 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 ordinary SQL the number of JOINs is fixed when you write the query; here it depends on the data itself.
  • The relationships are of different kinds and live their own lives. In a social-network graph, the edges "is friends with," "works at," "commented on" connect vertices of different types, and the edges themselves have properties (since what year they've been friends, in what role they work). When the relationships are like that, the relationship table stops being a boring technical detail and becomes the main content of the database.

If you have only the first sign and one or two hierarchies — you don't need a graph, recursive SQL is enough. If both, plus queries over the relationships are the core of the product, read on.

A hierarchy in PostgreSQL: adjacency list + WITH RECURSIVE

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

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

You can't fetch a whole branch with an ordinary JOIN — the depth isn't known ahead of time. For that SQL has a recursive query (a recursive common table expression, CTE):

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 recursion step
)
SELECT * FROM subtree;

It reads like this: the starting part (before UNION ALL) puts the root into the result; the recursive part attaches children to what's already been found — and repeats as long as new rows keep turning up. The same trick handles an org chart ("all reports down the chain" — the same table, just manager_id instead of parent_id), threaded comments, and a bill of materials.

Two practical details. First — cycle protection: if the data suddenly has a loop (A is B's parent, and B is A's parent), the query will loop forever; the safeguard is either to accumulate the traversed path into an array and check id <> ALL(path), or simply cap depth. Second — performance: a recursive query is fast only when an index fires on each step (CREATE INDEX ON categories (parent_id)); without it, each step turns into a full table scan.

PostgreSQL has other tools for hierarchies too — a materialized path on ltree, a closure table — but "adjacency list + WITH RECURSIVE" covers the vast majority of tasks and requires no denormalization.

Where recursive SQL hits its limit

A general graph is stored in a relational database with 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);

Storing it works beautifully. The trouble starts in the queries. "Find people born in the US and living in Europe," where the birthplace is recorded at different levels of detail (city → state → country → continent), is a traversal of "located in" edges to an arbitrary depth and in two directions at once. In recursive SQL such a query takes nearly thirty lines across four CTEs; in the graph 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

Here *0.. means "zero or more edges" — like * in regular expressions, only for relationships. When queries of this kind are everyday work, the "thirty lines versus four" difference becomes a difference in the whole team's speed of thought.

When it's more honest to reach for a graph database

Graph databases (Neo4j and others) implement the property graph model: every vertex and every edge has an identifier and a set of properties, edges are typed, and the schema doesn't restrict what can connect to what. The model's main strength is evolvability: a new kind of relationship is just new edges with a new label, with no migrations and no reshaping of tables. (Curiously, the similar CODASYL network model was the relational model's main rival back in the 1970s and lost; but graph databases aren't its reincarnation: they have index access to any vertex and declarative queries instead of manual pointer navigation.)

Practical guideposts for the fork:

  • One or two hierarchies (categories, an org chart, comments) — PostgreSQL + WITH RECURSIVE. Standing up a separate database for a tree is unnecessary infrastructure.
  • There are graph queries, but they're 5% of the load — also PostgreSQL: two tables, recursive CTEs, indexes on both ends of the edge. Slower than Cypher in expressiveness, but without a second database to operate.
  • Traversing relationships is the core of the product (recommendations, fraud detection over transfer chains, social features, a knowledge graph) — here a graph database is justified: both the query language and the storage are tuned for traversal, and there are many such queries.

A separate database is always a separate cost: replication, backups, monitoring, one more system in the team's head — the same considerations as in any polyglot architecture. It's worth paying that cost for the core of the product, not for a single feature.

Where this applies

The fork shows up not at the moment you pick a database, but later — when the first hierarchy or the first "down the chain" query appears in a live project. The right first move is almost always the same: WITH RECURSIVE in the database you already have. And moving to a graph database is a product-level decision, worth making by the numbers: how many traversal queries, at what depth, what share of the load.

Where beginners stumble:

  • Hacking depth with crutches — five self-joins "just in case," or dumping the whole table into memory and traversing it in code. WITH RECURSIVE handles this properly.
  • Forgetting about cycles — a recursive query over data with a loop hangs; a path check or a depth limit is mandatory for general graphs.
  • Reaching for a graph database for one hierarchy — a second database to operate 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 relationships between documents turn into manual joins in application code.

What to read next: PostgreSQL or MongoDB — the neighboring fork about the data model; composite indexes — so the recursion step runs on an index; document modeling in MongoDB — embed versus reference.