Graph Data Models

Property graphs, RDF triples and graphs stored in SQL tables: how each works, how you query paths of unknown length, and when a graph database is worth it.

Overview

Some data is mostly about connections. Who follows whom, which account shared a card with which device, which package depends on which. When the links are what you query, and a question can follow them several steps deep, a graph is the natural model: vertices (also called nodes) are the things, and edges (relationships) are the links between them.

Tables can hold a graph too, so the real question is how easy the model makes path questions and what it costs to answer them. This chapter covers the three common ways to store a graph and how each one asks for a path.

When connections are the data

A tree is a graph where each item has one parent. Documents handle trees well. Once items share neighbors in many directions, and the depth of a question is not fixed ('anyone within three follows of Ana'), a graph model keeps both the data and the queries simple.

Social network — People — Follows, friends — Friends of friends not yet connected
Fraud detection — Accounts, cards, devices, addresses — Used, shares — Accounts linked through shared devices
Package manager — Packages and versions — Depends on — Everything a package pulls in, transitively
Access control — Users, groups, resources — Member of, can read — Can this user reach this file through any group?

Property graphs

In a property graph, each vertex and each edge has a label (its type) and any number of key-value properties. Edges have a direction and can carry data of their own, such as when a follow started. Neo4j uses this model, and Amazon Neptune supports it alongside RDF.

You query a property graph with a pattern language. In Cypher (Neo4j's language, also offered as openCypher by Neptune) you draw the pattern with parentheses for vertices and arrows for edges, and the database finds every match. A quantifier after an edge, such as {1,3}, matches a path of one to three hops, so a question of unknown depth is one line.

Older Cypher writes the same hop range as -[:FOLLOWS*1..3]->. Neo4j still accepts it but notes it is not GQL conformant.

Graph query languages now have an ISO standard. GQL (ISO/IEC 39075) was published in April 2024, the first new ISO database query language since SQL (first published in 1987). It shares its pattern syntax, which comes from Cypher, with SQL/PGQ (ISO/IEC 9075-16:2023), an extension that lets SQL query tables as a read-only property graph.

Triple stores and RDF

The RDF model, a W3C standard, breaks every fact into a triple: subject, predicate, object. The subject is an IRI (a global identifier) or a blank node; the predicate is an IRI; the object is an IRI, a blank node or a literal value such as a string. A set of triples is a graph: subjects and objects are the vertices, predicates are the edges.

ex:ana — ex:follows — ex:raj
ex:ana — ex:name — "Ana"
ex:ana — ex:worksAt — ex:acme
ex:acme — ex:locatedIn — ex:lisbon

A property and a link look the same: 'Ana's name is Ana' and 'Ana follows Raj' are both triples, and only the object differs (a literal or another resource). Because identifiers are global IRIs, triples from different organizations can be merged into one graph, which is why RDF is used for linked data and knowledge graphs.

SPARQL is RDF's query language. SPARQL 1.1 (a W3C Recommendation since 2013) has property paths, so ex:follows+ matches a chain of one or more follows.

Unit of data — Vertex or edge with properties — One subject, predicate, object
Properties on edges — Built in — Needs extra triples
Identifiers — Local to the database — Global IRIs, easy to merge
Query language — Cypher, Gremlin, GQL — SPARQL

A graph in SQL tables

A relational database stores a graph as an edge table: one row per edge, with the source and target ids. One hop is a join. A path of unknown length needs a recursive query (WITH RECURSIVE), which repeats a join until no new rows appear. PostgreSQL 14 added a CYCLE clause that marks paths that come back to a vertex they already visited, so a loop in the data cannot make the query run forever.

raj — 1
kim — 2
li — 2
sam — 3

It works, and for shallow questions on modest data it is often enough. It is longer to write than the one-line Cypher pattern, and the planner treats each step as a join like any other.

Why a hop can cost less in a native graph store

In an edge table, each hop looks up the next rows through an index on src: a B-tree search whose cost grows slowly with the size of the table. Neo4j describes its storage as index-free adjacency: each vertex holds direct references to its neighbors, so following an edge is a pointer lookup, and a query's cost depends on how much of the graph it touches rather than on the total size of the data.

Two things do not change with the model. First, the work grows with the number of paths: if each person follows 200 others, three hops can touch 200 × 200 × 200 = 8 million paths in any database, so limit depth and remove duplicates early. Second, splitting a graph across machines is hard, because edges cross partitions and each crossing is a network round trip.

Neighbors of the graph model

Datalog is an older logic language in which you state facts and rules, and rules can build on each other to express paths. Datomic uses Datalog for queries and can also query the database as of a past point in time.
Graph processing systems are different from graph databases. Google's Pregel (2010) runs batch algorithms such as PageRank over a very large graph in rounds called supersteps, where each vertex computes and sends messages to its neighbors. A graph database answers many small queries with low latency; a processing system runs one big computation over the whole graph.

What you will be able to do

Describe a property graph and an RDF triple store, and say how they differ.
Write a path query of unknown depth in Cypher and in SQL with WITH RECURSIVE.
Explain index-free adjacency and what it does and does not speed up.
Decide when a graph database is worth adding to a design, and when an edge table is enough.

Key concepts

Vertex and edge: A vertex (node) is a thing; an edge (relationship) is a directed link between two vertices. Both can have a label and properties in a property graph.
Property graph: A graph model where vertices and edges carry a label and key-value properties. Used by Neo4j and supported by Amazon Neptune.
RDF triple: One fact written as subject, predicate, object. A set of triples forms a graph. Defined by the W3C.
Cypher: A declarative pattern language for property graphs, from Neo4j and offered as openCypher by other databases. Paths of variable length are written with a quantifier such as {1,3}.
SPARQL: The W3C query language for RDF. Property paths such as follows+ match chains of any length.
GQL: The ISO graph query language standard (ISO/IEC 39075), published in April 2024. Its pattern syntax is shared with SQL/PGQ.
Recursive CTE: A SQL query written WITH RECURSIVE that repeats a join until no new rows appear. How a relational database follows paths of unknown length.
Index-free adjacency: A storage design where each vertex holds direct references to its neighbors, so a hop is a pointer lookup instead of an index search.

When to use it

Designing a social graph, a recommendation feature or a fraud-ring detector
Modeling permissions that flow through nested groups
Explaining why deep path questions are awkward in plain SQL
Choosing between a graph database and an edge table in PostgreSQL
Separating an online graph database from an offline graph processing job

Interview questions

When would you choose a graph database over a relational one?
How do a property graph and an RDF triple store differ?
How would you find everyone within three hops of a user in SQL?
What is the difference between a graph database and a graph processing framework?