Skip to main content

Graph-Like Data Models

Adapted from: Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), Chapter 2 — rewritten and condensed for teaching.

Many-to-many relationships are the fault line that splits data models apart. If your application's data is mostly tree-shaped (one-to-many) or barely related at all, a document model fits comfortably. The relational model can handle simple many-to-many relationships too. But once the connections between your records become the interesting part of the data — not just an occasional join, but a dense web of relationships — it becomes natural to stop fighting the shape of the data and start modeling it as what it actually is: a graph.

What a Graph Actually Is​

A graph is built from exactly two kinds of objects:

  • Vertices (also called nodes or entities)
  • Edges (also called relationships or arcs)

A remarkable range of real-world data fits this shape:

DomainVerticesEdges
Social graphPeople"Knows each other"
The webWeb pagesHTML links
Road/rail networkJunctionsRoads or rail lines

Well-studied algorithms already exist for exactly this shape of data — car navigation finds shortest paths through a road network, and PageRank ranks web pages by analyzing the link graph between them.

Nothing about a graph requires every vertex to represent the same kind of thing, either. Facebook's graph famously mixes people, places, events, check-ins, and comments as vertices, with edges for friendships, "checked in at," "commented on," and "attended" all coexisting in one datastore. Homogeneous or not, a graph is just vertices and edges — the flexibility comes from what you choose to connect.

Throughout this lesson, we'll use one running example: two people, Lucy (from Idaho) and Alain (from Beaune, France), who are married and now live together in London. Modeling where they were born, where they live now, and how those places nest inside each other (a city within a state within a country within a continent) turns out to be exactly the kind of thing graphs handle gracefully and relational schemas handle awkwardly.

There are two closely related ways to structure and query graph data — the property graph model (Neo4j, and others) and the triple-store model (Datomic, AllegroGraph, and others). We'll look at both, plus three declarative query languages built for them: Cypher, SPARQL, and Datalog.

Property Graphs​

In the property graph model, every vertex carries:

  • a unique identifier,
  • a set of outgoing edges,
  • a set of incoming edges, and
  • a collection of properties (key-value pairs).

Every edge carries:

  • a unique identifier,
  • the vertex where it starts (the tail vertex),
  • the vertex where it ends (the head vertex),
  • a label describing the kind of relationship, and
  • its own collection of properties.

You can picture a property-graph store as nothing more exotic than two relational tables — one for vertices, one for edges:

CREATE TABLE vertices (
    vertex_id  integer PRIMARY KEY,
    properties json
);

CREATE TABLE edges (
    edge_id     integer PRIMARY KEY,
    tail_vertex integer REFERENCES vertices (vertex_id),
    head_vertex integer REFERENCES vertices (vertex_id),
    label       text,
    properties  json
);

CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);

Three properties of this layout matter enormously:

  1. No schema restricts which vertices can connect. Any vertex can have an edge to any other vertex — there's no fixed set of "allowed" relationship shapes to design around up front.
  2. Traversal works in both directions, efficiently. Given any vertex, the indexes on tail_vertex and head_vertex let you cheaply find both its outgoing and incoming edges — meaning you can walk a chain of relationships forward or backward.
  3. One graph, many kinds of relationships. Different edge labels let you layer several genuinely different kinds of information into a single graph without muddying the data model.

Together, these give graphs serious flexibility for modeling things a rigid relational schema struggles with — different administrative structures per country (France's départements and régions vs. the US's counties and states), a country nested inside another for historical reasons, or simply varying granularity (Lucy's current city is known precisely; her place of birth is only known down to the state). None of that requires redesigning a schema — you just add vertices and edges. That's also why graphs age well: as an application's requirements evolve, the graph extends to match without a disruptive migration.

Check: property graphs​

Quiz

The property graph model

1 / 3

What are the four components that make up a vertex in the property graph model?

Pick an answer to see if you are right.

The Cypher Query Language​

Cypher is a declarative query language for property graphs, created for the Neo4j database. Inserting part of our Lucy/Alain example looks like this — each vertex gets a symbolic name, and the arrow notation (a)-[:LABEL]->(b) creates a labeled edge from a to b:

CREATE
  (NAmerica:Location {name: 'North America', type: 'continent'}),
  (USA:Location {name: 'United States', type: 'country'}),
  (Idaho:Location {name: 'Idaho', type: 'state'}),
  (Lucy:Person {name: 'Lucy'}),
  (Idaho) -[:WITHIN]-> (USA) -[:WITHIN]-> (NAmerica),
  (Lucy) -[:BORN_IN]-> (Idaho)

With that graph populated, we can ask a genuinely interesting question: find everyone who was born in the United States and now lives in Europe. Concretely, we want every vertex with a BORN_IN path leading to a US location, and a LIVES_IN path leading to a European location:

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

Reading it out loud: find a vertex called person that has an outgoing BORN_IN edge, followed by zero or more WITHIN edges, landing on a Location named "United States" — and that same person has an outgoing LIVES_IN edge, followed by zero or more WITHIN edges, landing on a Location named "Europe." For every such person, return their name.

Note what you didn't have to specify: how many WITHIN hops to follow (a city could be one hop from its country, or three), or in what order to evaluate the two conditions. As with any declarative query language, the query optimizer picks an execution strategy — maybe scanning every person and checking their birthplace/residence, or maybe starting from the "United States" and "Europe" vertices and working backward through incoming edges — without you having to think about it while writing the query.

The Same Query in SQL​

We just said a property graph can live inside two ordinary relational tables — so can you query it with plain SQL? Yes, but it hurts. In a normal SQL query you know the joins you need in advance. Here, the number of WITHIN hops between a person's LIVES_IN edge and the location vertex you actually care about isn't fixed — a LIVES_IN edge might point straight at "Europe," or it might point at a street address three levels of nesting away.

SQL:1999 added recursive common table expressions (WITH RECURSIVE) precisely to express this kind of variable-length traversal. It works, but the contrast with Cypher's four-line query is stark — the SQL version needs several named recursive CTEs (one to walk up from "United States," one to walk up from "Europe," one to find everyone born within the first set, one to find everyone living within the second set) before a final join intersects the two.

A four-line query vs. a thirty-line query

If the same query takes 4 lines in one query language and roughly 30 in another, that's not a knock on SQL — it's a demonstration that different data models are built to make different kinds of questions cheap to ask. Graphs make "how are these two things connected, through however many hops" cheap; picking the right data model for your application is what makes queries like this pleasant instead of painful.

Activity: read the pattern

Given the Cypher pattern (person) -[:BORN_IN]-> () -[:WITHIN*0..]-> (loc:Location {name: 'Canada'}), describe in plain English what it matches — and what would change if *0.. were replaced with *1...

*0.. means "zero or more WITHIN hops," so it matches someone born directly in a Location named "Canada," or born somewhere nested inside Canada through any number of WITHIN edges. *1.. would require at least one WITHIN hop — excluding the case where the BORN_IN edge points straight at "Canada" itself.

Check: Cypher and SQL​

Quiz

Cypher queries and their SQL equivalent

1 / 3

In the Cypher pattern (Idaho) -[:WITHIN]-> (USA), what do "Idaho" and "USA" represent?

Pick an answer to see if you are right.

Triple-Stores and SPARQL​

The triple-store model is, under the hood, equivalent to the property graph model — it just describes the same ideas with different words. Every fact is stored as a three-part statement: (subject, predicate, object) — for example, (Jim, likes, bananas).

The subject is equivalent to a vertex. The object is one of two things:

  • A primitive value (a string, a number) — in which case the predicate and object together act like a property on the subject vertex. (Lucy, age, 33) is just Lucy with a property age: 33.
  • Another vertex — in which case the predicate is an edge label. (Lucy, marriedTo, Alain) connects two vertices with an edge labeled marriedTo.

Turtle is a common human-readable format for writing triples, and it gets noticeably more pleasant to read once you use semicolons to chain multiple facts about the same subject instead of repeating it:

@prefix : <urn:example:>.

_:lucy    a :Person;   :name "Lucy";          :bornIn _:idaho.
_:idaho   a :Location; :name "Idaho";         :type "state";   :within _:usa.
_:usa     a :Location; :name "United States"; :type "country"; :within _:namerica.
_:namerica a :Location; :name "North America"; :type "continent".
The semantic web, briefly

Triple-stores are frequently associated with the semantic web — the early-2000s vision of websites publishing machine-readable data (via the RDF format) so that data from different sites could be combined automatically into one giant web-wide database. The semantic web itself never really took off, and picked up a reputation for overhyped, overcomplicated standards along the way — but the triple-store model it popularized is genuinely useful as an internal application data model, with zero obligation to publish anything to the actual semantic web.

SPARQL is the query language built for RDF triple-stores, and it predates Cypher — in fact, Cypher's pattern-matching syntax was borrowed from it. The same emigration query looks like this in SPARQL:

PREFIX : <urn:example:>

SELECT ?personName WHERE {
  ?person :name ?personName.
  ?person :bornIn / :within* :name "United States".
  ?person :livesIn / :within* :name "Europe".
}

Since RDF doesn't distinguish "properties" from "edges" — both are just predicates — the exact same triple-matching syntax handles both jobs, which is part of why SPARQL reads even more compactly than Cypher for this kind of query.

Check: triple-stores and SPARQL​

Quiz

Triples, RDF, and SPARQL

1 / 2

In the triple (Lucy, bornIn, Idaho), what does the object (Idaho) represent, and how does this differ from (Lucy, age, 33)?

Pick an answer to see if you are right.

Datalog: The Foundation Underneath​

Datalog predates both SPARQL and Cypher by decades — it was studied extensively by academics in the 1980s, and while it's less familiar to most working programmers today, it's worth understanding because later graph query languages build on ideas it established first. Datomic uses it as its native query language.

Datalog's data model resembles the triple-store model, just written differently: instead of (subject, predicate, object), a fact is written predicate(subject, object):

name(namerica, 'North America').
type(namerica, continent).

name(usa, 'United States').
type(usa, country).
within(usa, namerica).

name(idaho, 'Idaho').
type(idaho, state).
within(idaho, usa).

name(lucy, 'Lucy').
born_in(lucy, idaho).

Where Cypher and SPARQL jump straight to a SELECT/MATCH, Datalog builds up a query as a small set of rules — new predicates derived from existing facts (or from other rules), the same way functions can call other functions:

within_recursive(Location, Name) :- name(Location, Name).
within_recursive(Location, Name) :- within(Location, Via),
                                     within_recursive(Via, Name).

migrated(Name, BornIn, LivingIn) :- name(Person, Name),
                                     born_in(Person, BornLoc),
                                     within_recursive(BornLoc, BornIn),
                                     lives_in(Person, LivingLoc),
                                     within_recursive(LivingLoc, LivingIn).

?- migrated(Who, 'United States', 'Europe').

Uppercase words are variables; a rule "fires" whenever the database can find a match for everything on the right-hand side of :-, at which point the left-hand side effectively becomes a new fact (with variables filled in). Tracing within_recursive for Idaho:

  1. name(namerica, 'North America') exists → rule 1 fires → within_recursive(namerica, 'North America').
  2. within(usa, namerica) exists, and step 1 just produced within_recursive(namerica, 'North America') → rule 2 fires → within_recursive(usa, 'North America').
  3. within(idaho, usa) exists, and step 2 just produced within_recursive(usa, 'North America') → rule 2 fires again → within_recursive(idaho, 'North America').

Repeated application of rules 1 and 2 eventually tells you every location contained within any given named region — and migrated then reuses that derived predicate twice (once for the birthplace chain, once for the residence chain) to answer the original question. This rule-reuse is Datalog's real advantage: rules compose like functions, so complex queries build up from small, independently reusable pieces — a real strength once your queries get complicated, even though it's noticeably less convenient than Cypher or SPARQL for a quick one-off question.

Activity: trace it yourself

Using the facts above, trace within_recursive for namerica directly (no intermediate steps). Which rule fires, and why does it terminate in exactly one step?

Rule 1 fires directly: name(namerica, 'North America') already exists as a base fact, so within_recursive(namerica, 'North America') is produced immediately — no within(namerica, ...) fact exists to feed rule 2, so there's nothing further to derive.

Check: Datalog​

Quiz

Datalog rules and recursion

1 / 2

In Datalog, what does it mean for a rule like within_recursive(Location, Name) :- within(Location, Via), within_recursive(Via, Name) to "fire"?

Pick an answer to see if you are right.

Graph Databases vs. the Old CODASYL Network Model​

It's tempting to look at a graph database and wonder if it's really just the CODASYL "network model" from the 1970s (the historical rival to the relational model, built to handle many-to-many relationships before relational databases could) wearing a new coat of paint. It isn't — a few concrete differences matter:

CODASYL network modelGraph database
SchemaFixed schema dictates which record types can nest inside which othersAny vertex can have an edge to any other vertex — no such restriction
AccessRecords reachable only by traversing a defined access pathAny vertex reachable directly by unique ID, or via an index
OrderingChildren of a record form an ordered set the database must maintainVertices/edges are unordered — you only sort at query time
QueriesImperative only, and brittle against schema changesUsually declarative (Cypher, SPARQL), though imperative traversal is possible too

The common thread: CODASYL locked in a rigid, imperative way of reaching your data; graph databases give you the same appetite for many-to-many relationships without that rigidity.

Key takeaways
  • A graph is just vertices and edges — an intentionally simple building block that models everything from social networks to road maps to a single application's tangled internal relationships.
  • The property graph model stores vertices and edges with properties and labels, and can even live inside two ordinary relational tables — but querying variable-depth relationships in plain SQL requires awkward recursive CTEs.
  • Cypher and SPARQL are declarative graph query languages that make "how are these two things connected, through however many hops" cheap and short to express — the query optimizer, not you, decides how to execute it.
  • The triple-store model (subject, predicate, object) is conceptually the same as a property graph in different clothing; Datalog goes further, letting you build queries out of small, reusable, composable rules.
  • Document, relational, and graph models are not competitors with one true winner — each is genuinely good at the relationships its shape naturally represents, and picking the right one for your application's actual data shape is the real skill.

Further Reading​