Notesdata-models🌱 seedling

Graph Model

Also: Graph Database · Property Graph · Labeled Property Graph · Triple Store

Data is vertices joined by typed edges, and both can carry properties. It is the natural model when many-to-many relationships are the point of the data and queries follow paths of unknown length.

Why it exists

Social networks, road maps, fraud rings, dependency graphs and knowledge graphs are mostly relationships. In tables each hop is another self-join, and "any number of hops" needs recursive SQL.

How it works

  • Property graph: each vertex has a label (Person) and properties; each edge has a type (KNOWS), a direction, properties, and a vertex at each end. Any vertex may link to any other, and edges are traversable both ways.
  • Triple store (RDF): every fact is subject–predicate–object, queried with SPARQL; common for linked open data.
  • Queries are patterns: (a)-[:KNOWS*1..3]-(b) matches paths of one to three hops, and the engine does the traversal.
  • Native storage (index-free adjacency) keeps direct pointers from each vertex to its edges, so a hop costs a pointer chase rather than an index lookup.
  • Standards: GQL (ISO/IEC 39075, April 2024) and SQL/PGQ (SQL:2023 Part 16), which defines graphs over ordinary tables.

Trade-offs

Gains Costs
variable-length paths are one clause bulk scans and aggregates are rarely its strength
schema grows by adding labels and edge types sharding a highly connected graph is hard: hops cross machines
traversal cost tracks the neighbourhood visited another system to run, unless graph queries run in your RDBMS

In practice

  • Facebook TAO serves the social graph as typed objects and associations on MySQL at about a billion reads per second.
  • LinkedIn LIquid answered around 2 million graph queries per second over some 270 billion edges in 2023.

Pitfalls

  • Choosing a graph database for data that is mostly tabular: the relationships must be the main access pattern.
  • Unbounded traversals over cyclic data. Bound the depth, in a graph language or in a recursive CTE.

Recall

These cards are also in your review deck, scheduled with spaced repetition.