3.2 Graph-Like Data Models

The decision rule: mostly one-to-many (tree-structured) with few other relationships → document. Many-to-many relationships very common, connections increasingly complex → graph.

A graph has vertices (nodes, entities) and edges (relationships, arcs).

Well-known algorithms operate on them: shortest path for map navigation; PageRank on the web graph for page popularity and search ranking.

Two representations:

Graphs are not limited to homogeneous data — an equally powerful use is storing completely different types of objects in a single database:

• Facebook maintains a single graph with many vertex and edge types: vertices are people, locations, events, check-ins, and comments; edges say who is friends with whom, which check-in happened at which location, who commented on which post, who attended which event.
• Search engines use knowledge graphs to record facts about entities common in queries — organizations, people, places — obtained by crawling and analyzing website text. Some sites (Wikidata) publish graph data in structured form directly.

Running example (Figure 3-6): Lucy from Idaho and Alain from Saint-Lô, France; married, living in London. Each person and location is a vertex; relationships are edges.

2.1 Property graphs

Implemented by Neo4j, Memgraph, KùzuDB, and others.

Each vertex has: a unique identifier · a label (string) describing the type of object · a set of outgoing edges · a set of incoming edges · a collection of properties (key-value pairs).

Each edge has: a unique identifier · the tail vertex (where it starts) · the head vertex (where it ends) · a label describing the kind of relationship · a collection of properties.

You can think of a graph store as two relational tables:

CREATE TABLE vertices (
    vertex_id   integer PRIMARY KEY,
    label       text,
    properties  jsonb
);
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  jsonb
);
CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);

Three important aspects:

1. Any vertex can have an edge connecting it with any other vertex. There is no schema restricting which kinds of things can be associated.
2. Given any vertex, you can efficiently find both its incoming and outgoing edges, and thus traverse the graph both forward and backward — that's exactly why there are indexes on both tail_vertex and head_vertex.
3. Different labels for different kinds of vertices and relationships let you store several kinds of information in a single graph while keeping a clean data model.

The edges table is the many-to-many join table, generalized to allow many types of relationship in the same table. There may also be indexes on labels and properties.

A real limitation: an edge associates only two vertices, whereas a relational join table can represent three-way or higher-degree relationships via multiple FK references on one row. Workarounds: create an extra vertex per join-table row with edges to/from it, or use a hypergraph.

Why graphs are good for evolvability — the example is subtle and worth keeping:

• Different regional structures in different countries (France has départements and régions; the US has counties and states)
• Quirks of history such as a country within a country
• Varying granularity of data — Lucy's current residence is a city, but her birthplace is specified only at the level of a state

All three are difficult in a traditional relational schema, and trivial in a graph. Then: add food allergies (a vertex per allergen, an edge person→allergen), link allergens to foods containing them, and query what's safe for each person to eat. As you add features, a graph easily extends to accommodate changes in the application's data structures.

2.2 Cypher

Query language for property graphs, originally from Neo4j, now the open standard openCypher. Supported by Neo4j, Memgraph, KùzuDB, Amazon Neptune, Apache AGE (storage in PostgreSQL). (Named after the character in The Matrix; unrelated to cryptographic ciphers.)

Insert:

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)

Symbolic names (usa, idaho) are not stored — they exist only within the query to wire up edges.

Query — people who emigrated from the US to Europe:

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

Read as: find any vertex person where (1) it has an outgoing BORN_IN edge to a vertex from which you can follow a chain of outgoing WITHIN edges until reaching a Location named United States; and (2) the same vertex has an outgoing LIVES_IN edge from which a chain of WITHIN edges reaches a Location named Europe.

*0.. means "follow this edge zero or more times" — like the * operator in a regular expression. This is the essential capability, and the thing SQL struggles with.

Two possible execution strategies (the optimizer chooses — this is declarative):

• Forward: scan all people, examine each person's birthplace and residence, filter.
• Backward: if there's an index on name, efficiently find the US and Europe vertices, follow incoming WITHIN edges to enumerate all locations inside each, then look for people via incoming BORN_IN/LIVES_IN edges at those locations.

2.3 The same query in SQL — why the model matters

Every edge you traverse in a graph query is effectively a join with the edges table. In a relational database you usually know in advance which joins you need. In a graph query, you may traverse a VARIABLE number of edges — the number of joins is not fixed in advance.

A person's LIVES_IN may point to a street, city, district, region, or state; a city is WITHIN a region, a region WITHIN a state, a state WITHIN a country. The target may be directly adjacent or several levels away.

SQL's tool for this is the recursive common table expression (WITH RECURSIVE):

WITH RECURSIVE
  -- in_usa: vertex IDs of all locations within the United States
  in_usa(vertex_id) AS (
      SELECT vertex_id FROM vertices
        WHERE label = 'Location' AND properties->>'name' = 'United States'
    UNION
      SELECT edges.tail_vertex FROM edges
        JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
        WHERE edges.label = 'within'
  ),
  -- in_europe: same, starting from Europe
  in_europe(vertex_id) AS (
      SELECT vertex_id FROM vertices
        WHERE label = 'location' AND properties->>'name' = 'Europe'
    UNION
      SELECT edges.tail_vertex FROM edges
        JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
        WHERE edges.label = 'within'
  ),
  -- born_in_usa: people born somewhere within the US
  born_in_usa(vertex_id) AS (
    SELECT edges.tail_vertex FROM edges
      JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
      WHERE edges.label = 'born_in'
  ),
  -- lives_in_europe: people living somewhere within Europe
  lives_in_europe(vertex_id) AS (
    SELECT edges.tail_vertex FROM edges
      JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
      WHERE edges.label = 'lives_in'
  )
SELECT vertices.properties->>'name'
FROM vertices
JOIN born_in_usa     ON vertices.vertex_id = born_in_usa.vertex_id
JOIN lives_in_europe ON vertices.vertex_id = lives_in_europe.vertex_id;

A 4-line Cypher query requires 31 lines in SQL. That's how much difference the right choice of data model and query language makes.

And that's just the beginning — there are further details around handling cycles and choosing breadth-first vs depth-first traversal.

Other options: Oracle's hierarchical SQL extension, TigerGraph's GSQL, PGQL. The ISO GQL standard (2024), based on Cypher, is published but not yet widely adopted — hopefully leading to greater uniformity.

2.4 Triple stores and RDF

Mostly equivalent to the property graph model, using different words for the same ideas. Worth knowing because the tools and languages are valuable additions to your toolbox.

All information is stored as three-part statements: (subject, predicate, object). In (Jim, likes, bananas): Jim = subject, likes = predicate (verb), bananas = object.

Precision note: real systems store extra metadata. AWS Neptune uses quads (adds a graph ID); Datomic uses 5-tuples (adds a transaction ID and a Boolean indicating deletion). They keep the subject-predicate-object core, so the book still calls them triple stores.

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

Turtle (a subset of Notation3) is the readable encoding:

@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".

_:someName names a vertex; the name means nothing outside the file — it exists only so we know which triples refer to the same vertex. Semicolons let you say multiple things about one subject.

The Semantic Web. Triple stores were motivated by the early-2000s effort to publish data in standardized machine-readable form for internet-wide exchange. The Semantic Web as originally envisioned did not succeed, but its legacy lives on in: JSON-LD, biomedical ontologies, Facebook's Open Graph protocol (used for link unfurling), knowledge graphs like Wikidata, and Schema.org vocabularies. Even with no interest in the Semantic Web, triples can be a good internal data model for applications.

RDF is the underlying data model (Turtle is one encoding; RDF/XML is another, more verbose one; Apache Jena converts between them).

RDF's quirk: because it's designed for internet-wide data exchange, subject/predicate/object are often URIs — <http://my-company.com/namespace#within> rather than plain WITHIN. The reasoning: you should be able to combine your data with someone else's, and if they attach a different meaning to within, you won't get a conflict, because their predicate is actually <http://other.org/foo#within>. The URL need not resolve to anything — it's just a namespace. Declare the prefix once at the top and forget it.

2.5 SPARQL

Query language for RDF triple stores. (Recursive acronym: SPARQL Protocol and RDF Query Language; pronounced "sparkle.") It predates Cypher — and Cypher's pattern matching is borrowed from SPARQL, which is why they look similar.

PREFIX : <urn:example:>
SELECT ?personName WHERE {
  ?person :name ?personName.
  ?person :bornIn  / :within* / :name "United States".
  ?person :livesIn / :within* / :name "Europe".
}

Equivalences (SPARQL variables start with ?):

Because RDF doesn't distinguish between properties and edges — it just uses predicates for both — you can use the SAME syntax for matching properties and for traversing edges. That's a genuine elegance advantage over property graphs.

Supported by Amazon Neptune, AllegroGraph, Blazegraph, OpenLink Virtuoso, Apache Jena.

2.6 Datalog

Much older than SPARQL or Cypher — from 1980s academic research. Less well known among software engineers and not widely supported in mainstream databases, but it ought to be better known: very expressive, especially powerful for complex queries. Used by Datomic, LogicBlox, CozoDB, and LinkedIn's LIquid. It's based on a relational data model, not a graph — but recursive queries on graphs are a particular strength.

Contents are facts, each corresponding to a row in a relational table. location(2, "United States", "country") means the location table has a row with those column values.

location(1, "North America", "continent").
location(2, "United States", "country").
location(3, "Idaho", "state").
within(2, 1).    /* US is in North America */
within(3, 2).    /* Idaho is in the US     */
person(100, "Lucy").
born_in(100, 3). /* Lucy was born in Idaho */

Edges (within, born_in, lives_in) are two-column join tables.

within_recursive(LocID, PlaceName) :- location(LocID, PlaceName, _). /* Rule 1 */
within_recursive(LocID, PlaceName) :- within(LocID, ViaID),          /* Rule 2 */
                                      within_recursive(ViaID, PlaceName).
migrated(PName, BornIn, LivingIn)  :- person(PersonID, PName),       /* Rule 3 */
                                      born_in(PersonID, BornID),
                                      within_recursive(BornID, BornIn),
                                      lives_in(PersonID, LivingID),
                                      within_recursive(LivingID, LivingIn).
us_to_europe(Person) :- migrated(Person, "United States", "Europe"). /* Rule 4 */

Cypher and SPARQL jump in right away with SELECT; Datalog takes a small step at a time.

How it works: rules derive new virtual tables from underlying facts. These derived tables are like virtual SQL views — not stored, but queryable like stored tables. The name and columns come from the part before :-; the content from the pattern-matching after :-. A rule applies if the system can find a match for all patterns on the right-hand side; when it applies, it's as though the left-hand side was added to the database (variables replaced by matched values).

Trace of the recursion:

1. location(1, "North America", "continent") exists → rule 1 fires → within_recursive(1, "North America")
2. within(2, 1) exists and within_recursive(1, "North America") exists → rule 2 fires → within_recursive(2, "North America")
3. within(3, 2) exists and within_recursive(2, "North America") exists → rule 2 fires → within_recursive(3, "North America") — Idaho is in North America

By repeated application of rules 1 and 2, within_recursive yields all locations contained in any other location. Rule 3 finds people with a birthplace and residence; rule 4 pins those to United States and Europe.

Datalog requires a different kind of thinking: complex queries are built up rule by rule, with one rule referring to others — like breaking code into functions that call each other. And just as functions can be recursive, Datalog rules can invoke themselves (rule 2), which is what enables graph traversals.

2.7 GraphQL — deliberately the least powerful

By design much more restrictive than the others. Intended for OLTP queries; its purpose is to let client software on a user's device (mobile app, JS frontend) request a JSON document with a particular structure containing exactly the fields needed to render its UI.

The benefit: developers can rapidly change queries in client code without changing server-side APIs.

The costs:

• Organizations adopting GraphQL often need tooling to convert queries into requests to internal services, which commonly use REST or gRPC (Ch 5)
• Authorization, rate limiting, and performance are additional concerns

The language is intentionally limited BECAUSE GraphQL queries come from untrusted sources. It does not allow anything expensive to execute, since otherwise users could (perhaps unintentionally) cause a denial-of-service by running lots of expensive queries. Specifically:

• No recursive queries (unlike Cypher, SPARQL, SQL, Datalog)
• No arbitrary search conditions — you can't ask "find people born in the US now living in Europe" unless the service owners explicitly choose to offer that search functionality

Example — a Slack/Discord-style chat app:

query ChatApp {
  channels {
    name
    recentMessages(latest: 50) {
      timestamp
      content
      sender   { fullName imageUrl }
      replyTo  { content sender { fullName } }
    }
  }
}

The response mirrors the query structure exactly — those attributes, no more and no less.

{ "data": { "channels": [ { "name": "#general", "recentMessages": [
  { "timestamp": 1693143014, "content": "Hey! How are y'all doing?",
    "sender": {"fullName": "Aaliyah", "imageUrl": "https://..."}, "replyTo": null },
  { "timestamp": 1693143024, "content": "Great! And you?",
    "sender": {"fullName": "Caleb", "imageUrl": "https://..."},
    "replyTo": { "content": "Hey! How are y'all doing?",
                 "sender": {"fullName": "Aaliyah"} } } ] } ] } }

The advantage: the server does not need to know which attributes the client requires to render its UI — the client simply requests what it needs. If the UI changes to show the replyTo sender's profile picture, the client adds imageUrl to the query with no server-side changes.

Two deliberate duplication choices, both justified the same way:

• The sender's name and image are embedded in each message, so if one user sends multiple messages, the info repeats. In principle this could be reduced, but GraphQL accepts a larger response to make it simpler to render the UI.
• replyTo duplicates the replied-to content and sender name. Returning just an ID would force an additional client→server request if that ID isn't among the 50 messages returned. Duplicating makes it much simpler to work with the data.

Server-side: the database can store data more normalized and perform the joins to answer the query (store a message with the sender's user ID and the replied-to message ID, then resolve). But only joins explicitly declared in the GraphQL schema can be requested by the client — that's the DoS guardrail.

Despite the name and the JSON-shaped response, GraphQL can be implemented on top of ANY type of database — relational, document, or graph.