Property graph versus RDF, and what graph forbids

What does modelling data as triples cost, and what can graph processing never give you?

Property graph versus RDF

Both model the same thing. They differ in where structure is bound: early (decided when data is written) or late (decided when data is read). This is the cleanest example of early versus late binding across the platform.

A property graph attaches a bag of key-value properties to vertices and edges. A vertex with twelve properties is one record.
An RDF triple store decomposes everything into (subject, predicate, object) with no other structure. The same vertex with twelve properties is twelve triples.

Triples are maximal normalization. Everything is self-describing, the schema is data, adding a property is inserting a row, and merging two independently designed datasets needs no migration. This is valuable when you do not control the sources and cannot agree a schema in advance. That is the real, defensible case for RDF, and it is an organizational argument rather than a technical one. RDF is the right model when schema agreement is more expensive than query cost.

The price is exactly what denormalization (storing related data together to avoid joins) exists to avoid. Rebuilding one entity is a multi-way self-join over the triple table. Query cost rises. Cardinality estimation becomes much harder, because every join is over the same table with different constants for the predicate. The single predicate column is also catastrophically skewed: a few predicates dominate. Triple stores respond by keeping multiple sorted permutations of the same triples (SPO, POS, OSP, ...) so that any access pattern has a matching sort order. That is the directional-index rule taken to its conclusion: with three columns and no fixed direction, you store the data several ways. Index-per-direction, paid in full.

Property graphs bind structure earlier. They get cheaper reads and better statistics, and they pay when the schema must change or two graphs must be merged. It is the same trade as schema-on-write versus schema-on-read, with the same deciding question: where does the failure surface, at write time or at read time?

One line: triples are maximal normalization. Schema becomes data, and the cost is a self-join per property plus an index per access direction.

What graph forbids

You cannot prune a traversal by inspecting values, because reachability is not a predicate over stored data.
You cannot cost-estimate a traversal from summary statistics, because the cost depends on degrees not yet visited.
You cannot balance-partition a power-law graph without cutting most edges.
You cannot have a deep traversal that is not, in effect, a full scan.

The escapes and their prices

Escape	Price
Materialized adjacency (CSR) removes an index descent per hop	immutability, plus a reverse copy
BSP converts random access into a shuffle	a barrier and a straggler tax per hop
Vertex-cut replication balances skew	replica reconciliation
Bidirectional search halves the exponent	only for point-to-point queries
Incremental maintenance avoids global recomputation	the usual delta-tracking machinery
Truncated iteration bounds the cost	only where the answer is approximable
Multiple sorted permutations make any access direction cheap	linear growth in copies

Case, resolvedConstructed case · Amara at Haatly

Friends of friends that never finishes

A three-hop friends-of-friends query took about 3 seconds and never finished for users near accounts with 2 million followers, and more database servers did not help. Where it started: Graph →

The three-hop query. Amara looks at the numbers. The average Haatly user follows about 100 accounts, so three hops mean about 100³ = 1,000,000 candidate vertices before deduplication. Each hop in PostgreSQL is a self-join with one B-tree descent per frontier row. That is why the typical page takes 3 seconds. She does three things:

She builds a CSR (and a reverse CSR, because the product also asks "who follows me?") in a nightly analytical job, and keeps the PostgreSQL edge table as the source of truth. The online path reads the CSR for the shallow lookup and joins the result with "who bought this item", which is a small set. She starts from the buyers side (few seeds) and walks outwards two hops, instead of from the viewer, and meets in the middle: this is bidirectional search, so the cost is about 2·100^1.5 = 2,000 instead of 1,000,000.
For the handful of hubs with 2 million followers, she stops expanding past a hub in the online path and uses a precomputed, capped list for it. The real cost of those queries was never the average degree. It was one hub.
For the big offline question ("which communities exist on Haatly?"), she uses a BSP job with vertex-cut partitioning, combiners, and a threshold to decide convergence. Adding servers did not help the original query because one query was one dependency chain. Adding servers helps the offline job only because it is organized in rounds.