Graph Databases

In the previous three families, the subject of the query was the record itself: if the key is known, the value arrives; if a field carries a condition, an index is built; if a range is wanted, the layout follows it. In the library data, though, some questions concern not the records but the links between them: the books also borrowed by people who borrowed this book, the shortest shared reading chain between two members. In the relational model this link is a join table, and every step is another join; the graph database makes the link a first-class object instead. This lesson builds the model with node, measures by depth the record count both models touch for the same question, and counts traversal’s cost when depth is not known in advance.

The Link Itself Is a Record

The model is a property graph: data consists of nodes and edges, and every node — and every edge — carries its own properties. In the library, the nodes are books and members; a loan is not a row but an edge, and the loan’s date and duration sit on that edge. Access is different too: a node’s neighbors are a list kept beside the node itself — the adjacency list. Walking from a node to its neighbors is traversal, the concept the Data Structures course covers for trees and graphs, applied here to nodes and edges.

NS3: the data is generated from 20,000 members, 5,000 books, and 2–12 loans per member; book selection follows a skewed distribution — a few books borrowed heavily, most very little. The generator is self-written, its seed visible in the code. NS4: the loan edge is undirected, walked the same way from either side.

// graph/model.mjs — property graph: nodes and edges, both carrying properties. The
// adjacency list is a real data structure; an edge property sits on the edge itself,
// not in a separate table. The generator is exported: the next blocks build the
// same set.
const SEED = 20240517, MEMBERS = 20_000, BOOKS = 5_000;
function* stream(t) { let x = t >>> 0; for (;;) { x = (Math.imul(x, 1103515245) + 12345) >>> 0; yield x / 4294967296; } }
export function loans() {                    // deterministic loan list, seed above
  const r = stream(SEED), list = [];
  for (let u = 1; u <= MEMBERS; u += 1) {
    const n = 2 + Math.floor(r.next().value * 11), seen = new Set();
    for (let j = 0; j < n; j += 1) {
      const p = r.next().value, book = 1 + Math.floor(BOOKS * p * p);   // skewed popularity
      if (seen.has(book)) continue; seen.add(book);
      list.push({ member: u, book, day: 1 + Math.floor(r.next().value * 364),
               duration: 3 + Math.floor(r.next().value * 40) });
    }
  }
  return list;
}

class PropertyGraph {
  #nodes = new Map(); #adjacency = new Map();
  node(id, properties) { this.#nodes.set(id, properties); this.#adjacency.set(id, []); }
  edge(a, b, properties) {                   // undirected: written to both adjacency lists
    this.#adjacency.get(a).push({ target: b, ...properties });
    this.#adjacency.get(b).push({ target: a, ...properties });
  }
  properties(id) { return this.#nodes.get(id); }
  neighbors(id, predicate) { const l = this.#adjacency.get(id) ?? []; return predicate ? l.filter(predicate) : l; }
  degree(id) { return (this.#adjacency.get(id) ?? []).length; }
}

if (import.meta.main) {                      // measurements print when run directly
  const g = new PropertyGraph(), TARGET = "book:2500", data = loans();
  for (let k = 1; k <= BOOKS; k += 1) g.node(`book:${k}`, { type: "book", title: `Book ${k}`, year: 1960 + (k % 65) });
  for (let u = 1; u <= MEMBERS; u += 1) g.node(`member:${u}`, { type: "member", name: `Member ${u}`, branch: 1 + (u % 9) });
  for (const o of data) g.edge(`member:${o.member}`, `book:${o.book}`, { type: "loan", day: o.day, duration: o.duration });

  let highest = null, e = 0, total = 0;
  for (let k = 1; k <= BOOKS; k += 1) { const d = g.degree(`book:${k}`); total += d;
    if (d > e) { e = d; highest = `book:${k}`; } }
  console.log(`${BOOKS + MEMBERS} nodes (${BOOKS} books + ${MEMBERS} members), ${data.length} edges (loans)`);
  console.log(`average degree: book ${(total / BOOKS).toFixed(1)}, member ${(data.length / MEMBERS).toFixed(1)}; ` +
    `highest ${highest} ${e}`);

  const all = g.neighbors(TARGET), long = g.neighbors(TARGET, (k) => k.duration > 21);
  console.log(`\n${TARGET} (${g.properties(TARGET).title}, ${g.properties(TARGET).year}): adjacency list ${all.length} edges, ` +
    `edges with duration>21 via the edge property ${long.length}`);
  console.log(`  first three edges: ${all.slice(0, 3).map((edge) => `${edge.target}(day ${edge.day}, duration ${edge.duration})`).join(", ")}`);
}

25000 nodes (5000 books + 20000 members), 139504 edges (loans)
average degree: book 27.9, member 7.0; highest book:1 1825

book:2500 (Book 2500, 1990): adjacency list 22 edges, edges with duration>21 via the edge property 11
  first three edges: member:202(day 157, duration 19), member:3845(day 73, duration 25), member:4394(day 21, duration 11)

The numbers are of the measurement class. The edge property lives on the edge itself, not in a side table: loans over 21 days drop from 22 edges to 11 with a single filter over the adjacency list — an edge, too, can carry a condition during traversal. The degree distribution is skewed: average degree on a book node is 27.9, while the highest is 1,825 — a number that returns at the end of the lesson.

There is no advantage here yet. Finding the borrowers of a book means reading 22 edges in the graph; in the relational model, the same job is an indexed search on book_id reading 22 rows. At the first degree, the two models do the same work. The difference begins at the second step.

The Same Question, Two Models

The question is this: the books also borrowed by the members who borrowed a given book — and deeper degrees of the same question. In the relational model this is the loan table joined against itself repeatedly, and every degree adds another join; in the graph, the same question is one more step through the adjacency list.

The measure on both sides is the interim record touched, and it is cumulative: the rows each layer produces in the join, the edges crossed in the traversal. NS5: the relational side is indexed on book_id and member_id; the join does not perform a full scan, so the measured difference does not come from a missing index.

// graph/two-models.mjs — the same question in two models: a join table on the
// relational side (node:sqlite, two indexes), traversal over the adjacency list on
// the graph side. Intermediate records touched are counted cumulatively on both
// sides. All numbers are independent of the run.
import { DatabaseSync } from "node:sqlite";
import { loans } from "./model.mjs";        // same data set, same seed
const TARGET = 2500, data = loans();

const db = new DatabaseSync(":memory:");
db.exec("CREATE TABLE loan(member_id INT, book_id INT, day INT, duration INT)");
const insert = db.prepare("INSERT INTO loan VALUES(?,?,?,?)");
db.exec("BEGIN"); for (const o of data) insert.run(o.member, o.book, o.day, o.duration); db.exec("COMMIT");
db.exec("CREATE INDEX i_book ON loan(book_id)"); db.exec("CREATE INDEX i_member ON loan(member_id)");

function join(d) {                          // d-layer join; COUNT(*) = number of d-step paths
  let sql = `SELECT COUNT(*) interim, COUNT(DISTINCT o${d}.${d % 2 ? "member_id" : "book_id"}) uniq FROM loan o1`;
  for (let i = 2; i <= d; i += 1)
    sql += i % 2 === 0 ? ` JOIN loan o${i} ON o${i}.member_id = o${i - 1}.member_id`
                       : ` JOIN loan o${i} ON o${i}.book_id = o${i - 1}.book_id`;
  return db.prepare(`${sql} WHERE o1.book_id = ?`).get(TARGET);
}

const adjacency = new Map();                 // adjacency list: node -> neighbor array
const link = (a, b) => { if (!adjacency.has(a)) adjacency.set(a, []); adjacency.get(a).push(b); };
for (const o of data) { link(`k:${o.book}`, `u:${o.member}`); link(`u:${o.member}`, `k:${o.book}`); }

function traverse(d) {                       // layer by layer; each layer is a set of unique nodes
  let layer = new Set([`k:${TARGET}`]), nodes = 0, edges = 0;
  for (let i = 1; i <= d; i += 1) { const next = new Set();
    for (const v of layer) { nodes += 1; for (const w of adjacency.get(v)) { edges += 1; next.add(w); } }
    layer = next; }
  return { nodes, edges, unique: layer.size };
}

console.log(`${data.length} loan records; start book:${TARGET}, degree ${adjacency.get(`k:${TARGET}`).length}\n`);
console.log("depth  join rows   nodes visited   edges traversed   unique result");
let cumulative = 0;
for (const d of [1, 2, 3, 4, 5]) {
  const b = join(d), c = traverse(d); cumulative += b.interim;
  if (b.uniq !== c.unique) throw new Error(`results diverged: ${b.uniq} != ${c.unique}`);
  console.log(String(d).padStart(5) + String(cumulative).padStart(19) + String(c.nodes).padStart(23) +
    String(c.edges).padStart(16) + String(c.unique).padStart(14));
}
let frontier = new Set([TARGET]), interimRows = 0;   // step-by-step deduplication on the relational side
for (let i = 1; i <= 5; i += 1) {
  const outField = i % 2 ? "member_id" : "book_id", inField = i % 2 ? "book_id" : "member_id";
  const r = db.prepare(`SELECT ${outField} a FROM loan WHERE ${inField} IN (${[...frontier].map(() => "?").join(",")})`).all(...frontier);
  interimRows += r.length; frontier = new Set(r.map((x) => x.a));
}
console.log(`\nstep-by-step deduplicated join: ${interimRows} rows, ${frontier.size} unique result, five separate statements`);

139504 loan records; start book:2500, degree 22

depth  join rows   nodes visited   edges traversed   unique result
    1                 22                      1              22            22
    2                218                     23             218           166
    3              13200                    189           11219          8295
    4             122105                   8484           78082          4996
    5           14190839                  13480          217544         20000

step-by-step deduplicated join: 217544 rows, 20000 unique result, five separate statements

The two models’ results are identical at every depth; the code checks this on every row and would throw if they diverged. What is not the same is the cost.

At the first and second degree, both sides touch the same number: 22 and 218. The divergence begins at the third degree (13,200 against 11,219), widens at the fourth (122,105 against 78,082), and jumps to a different scale at the fifth: 14,190,839 rows against 217,544 edges, sixty-five times. The reason fits in one sentence: a join layer counts paths, a traversal layer counts nodes. If a book is reached by a hundred different paths, the join produces its neighbors a hundred times; a traversal puts that book into the layer’s set once and looks at its neighbors once. The DISTINCT at the end cleans up only the last step; it does not spare the interim rows.

The last row shows where the boundary lies. The relational engine can imitate a traversal: deduplicating the interim result at every step and passing only the unique set forward reads 217,544 rows — exactly the edge count the traversal crosses. What is missing is not a way of storing data but a shape of query: the query stops being a single statement and splits into five, one more for every added degree. This is exactly what the graph store does; only the query author is spared the work. The Scaling the Data Layer course measured the same contrast by request count; the measure here is records touched.

The table’s last column is traversal’s own limit: at the fourth degree the result is 4,996 books, at the fifth it is 20,000 members — nearly the whole catalog and the whole member roll. The question loses its meaning before it gets expensive.

The Shortest Chain

In some questions, depth is not known in advance: how many steps is the shortest shared reading chain between two members? This question cannot be written with a fixed number of joins, because how many joins to write is the answer itself. Traversal has two forms: walking from one end, or walking from both ends and meeting in the middle.

// graph/shortest-chain.mjs — the shortest shared reading chain between two members:
// depth is not known in advance. Traversal runs one-ended and two-ended; nodes
// visited are counted.
import { loans } from "./model.mjs";        // same data set, same seed

const adjacency = new Map();
const link = (a, b) => { if (!adjacency.has(a)) adjacency.set(a, []); adjacency.get(a).push(b); };
for (const o of loans()) { link(`k:${o.book}`, `u:${o.member}`); link(`u:${o.member}`, `k:${o.book}`); }

function oneEnded(a, b) {                    // on a shortest path a node is never visited twice
  const distance = new Map([[a, 0]]); let layer = [a], nodes = 0, edges = 0, mostEdges = [null, 0];
  const stop = () => ({ length: distance.get(b), nodes, edges, mostEdges });
  while (layer.length) { const next = [];
    for (const v of layer) { nodes += 1; const d = adjacency.get(v).length;
      if (d > mostEdges[1]) mostEdges = [v, d];
      for (const w of adjacency.get(v)) { edges += 1;
        if (distance.has(w)) continue; distance.set(w, distance.get(v) + 1);
        if (w === b) return stop(); next.push(w); } }
    layer = next; }
  return null;
}
function twoEnded(a, b) {                    // each round the smaller frontier is expanded
  const distA = new Map([[a, 0]]), distB = new Map([[b, 0]]);
  let frontA = [a], frontB = [b], nodes = 0, edges = 0;
  while (frontA.length && frontB.length) {
    const forward = frontA.length <= frontB.length;
    const layer = forward ? frontA : frontB, mine = forward ? distA : distB, other = forward ? distB : distA, next = [];
    for (const v of layer) { nodes += 1;
      for (const w of adjacency.get(v)) { edges += 1;
        if (mine.has(w)) continue; mine.set(w, mine.get(v) + 1);
        if (other.has(w)) return { length: mine.get(w) + other.get(w), nodes, edges }; next.push(w); } }
    if (forward) frontA = next; else frontB = next; }
  return null;
}

console.log(`${"member pair".padEnd(29)}${"chain".padStart(7)}${"one-ended nodes".padStart(17)}${"two-ended nodes".padStart(17)}${"gain".padStart(8)}`);
for (const [a, b] of [[7, 19_842], [1_337, 15_004], [42, 9_999]]) {
  const t = oneEnded(`u:${a}`, `u:${b}`), i = twoEnded(`u:${a}`, `u:${b}`);
  if (t.length !== i.length) throw new Error(`lengths diverged: ${t.length} != ${i.length}`);
  console.log(`member:${a} — member:${b}`.padEnd(29) + String(t.length).padStart(7) +
    String(t.nodes).padStart(17) + String(i.nodes).padStart(17) +
    `${(t.nodes / i.nodes).toFixed(1)}x`.padStart(8));
}

const t7 = oneEnded("u:7", "u:19842");       // the node contributing the most edges to the search
const [node, degree] = t7.mostEdges;
console.log(`\nthe node contributing the most edges in the first search is ${node}, degree ${degree}: of the ` +
  `${t7.edges} edges traversed, ${(100 * degree / t7.edges).toFixed(1)}% passed through this node alone`);

member pair                    chain  one-ended nodes  two-ended nodes    gain
member:7 — member:19842            4              426               11   38.7x
member:1337 — member:15004         2                8                2    4.0x
member:42 — member:9999            4              227                7   32.4x

the node contributing the most edges in the first search is k:3, degree 611: of the 9477 edges traversed, 6.4% passed through this node alone

Both walks find the same length, and the code checks this on every pair. Nodes visited, though, are 426 against 11 and 227 against 7 for four-step chains — thirty to forty times. The reason is structural: each layer grows by roughly the average degree over the last one, so cost concentrates in the final layer. Walking from both ends turns four steps into two plus two, and two small layers sum to less than one large layer. When the chain is two steps, the gain drops to 4.0 times: there is no depth left to split.

The last row shows traversal’s own cost. The node contributing the most edges to the search is a book with degree 611, alone producing 6.4% of the 9,477 edges crossed. The skew of the degree distribution turns into cost here: access is cheap in this family, but every traversal through a high-degree node does work equal to that node’s degree — the catalog’s highest degree is 1,825, paid in a single step the moment that node is visited. The fix lies outside the model: filter on the edge’s type or property, or exclude that node from the traversal.

Summary

• In a property graph, data is nodes and edges, properties sit on both, and the adjacency list is a real data structure kept beside the node: a loan’s duration is an edge property, and 11 of 22 edges that exceed 21 days are separated with a single filter.
• At the first and second degree, both models touch the same number (22 and 218); the divergence begins at the third degree (13,200 against 11,219), becomes 122,105 against 78,082 at the fourth, and reaches 14,190,839 rows against 217,544 edges at the fifth — sixty-five times.
• The difference comes not from how the data is stored but from the shape of the query: a join layer counts paths, a traversal layer counts nodes. The same job drops to 217,544 rows on the relational side if deduplicated step by step, but the query stops being a single statement and becomes five separate ones.
• Questions whose depth is not known in advance cannot be written with a fixed number of joins. In the shortest chain, two-ended traversal visits 38.7 and 32.4 times fewer nodes than one-ended; when the chain is short, the gain drops to 4.0 times.
• The cost of traversal depends on the degree distribution: 6.4% of the 9,477 edges crossed pass through a single node of degree 611, while the highest degree in the catalog is 1,825.

Next Step

All four families so far share one thing: the data has an identity — a key, a document id, a row key, a node id — and every query starts from an identity or arrives at one. In the library’s operational data, though, there is a stream with no identity: shelf temperature measured every minute, an hourly door-crossing counter, a per-minute count of loan transactions. A single measurement is never asked for alone; questions run over ranges, data is only appended and never updated, and aging data is not kept at full resolution forever. The next lesson measures what this access pattern does to a store: the block a time-ordered layout reads for a range query, the space sorted measurements gain in compression, and which question a retention policy makes impossible to answer.