books / ddia / ch-02SHEET 2 / 11 · REV ASIGN IN
MODULE 2 · DESIGNING DATA-INTENSIVE APPLICATIONS CH 2

One Dataset, Three Shapes

A data model is a bet about the questions you'll ask later — so load one messy dataset into tables, documents, and triples, and feel each shape fight back.

The idea

The same facts — Priya worked at Initech, Priya endorses Marco, Marco works at Globex — can be stored as rows in tables, as one nested JSON blob per person, or as a pile of tiny three-word sentences. None of those is the truth. Each is a shape, and the shape you pick decides which questions are cheap, which are expensive, and which need a migration at 2am.

The relational move is to shred everything and join it back: every fact lives in one place, entities get IDs, and relationships get their own table. Updates touch one row, but reading a whole profile means stitching it together. The document move is the opposite — keep together what's read together. One person is one JSON tree, a profile is one read, and the object in the database finally looks like the object in your code. The bill arrives with many-to-many questions and with org names duplicated across a thousand files.

Schema is where this gets concrete. Tables check the shape on the way in, so you run one migration and every row conforms. Documents check on the way out, so you add a field by just writing it — and every reader grows an if-this-field-exists branch. Nothing is truly schemaless; the schema just moved from the database into your code.

When the relationships are the point — endorsement chains, who's within three introductions of me — both shapes strain. Store nothing but subject-predicate-object atoms and queries become patterns with holes: find every binding that makes all these sentences true. Filling those holes is called unification, and it's small enough to write yourself. That's the idea under Cypher, SPARQL, and Datalog, and it's why declarative queries win: because you never said how, the engine is free to reorder, index, and speed things up.

The bench — 4 exercises

EX 01

Shred It, Nest It, Atomize It

Load one deliberately messy resume-network dataset into three shapes — SQLite tables, per-person JSON files, and a flat triples file — so each model has to confront the same mess in its own way.

  1. Get or generate a messy JSONL dataset of people, orgs, jobs and endorsements: inconsistent field names, typo'd org names, one duplicated person, and at least one endorsement cycle.
  2. Write a SQL loader into resume.db with a real orgs table, foreign keys on, typo'd org names reconciled to one ID, and the duplicate person merged.
  3. Write a document loader producing docs/people/<id>.json with jobs and endorsements nested inside each person — and keep the org name inline as a string, duplication and all.
  4. Write a triples loader producing graph.nt, one tab-separated subject predicate object per line: person:12 works_at org:7, person:12 endorses person:31, plus name literals.
  5. Write a small census script that counts distinct people, orgs, employment facts and endorsements in each store.
hint

Resist fixing the document model's duplicated org names by adding an orgs collection — you'd be rebuilding the relational model in JSON, and the next exercise needs that wound open.

hint

PRAGMA foreign_key_check on resume.db should return nothing; grep graph.nt for IDs that never appear as a subject to find dangling refs.

DONE WHEN

· All three census counts match exactly, with the duplicate person merged and alias'd orgs counted once.

· Foreign key check is clean and no job row points at a nonexistent org.

· Pick 25 random people; each store returns the same profile once you sort keys and lists.

EX 02

Five Queries, Three Accents

Answer the same five questions in SQL and in hand-written document code, then evolve the schema and measure the blast radius in each model.

  1. Write down five queries in English: full profile of person P; everyone who worked at org X; everyone who worked at X and endorses someone at Y; everyone within 2 endorsement hops of P; everyone within N hops of P.
  2. Answer all five in SQL against resume.db — Q4 and Q5 will need WITH RECURSIVE, and that is meant to hurt a little.
  3. Answer all five with your own code walking the JSON files, with no SQLite anywhere on that side.
  4. Time Q3 in both models on a larger generated dataset and record the numbers.
  5. Produce a v2 dataset where every person gains a certifications list and org is renamed to company in new records; re-ingest, re-run all five, and count the files you had to touch in each model.
hint

For document Q3 you will end up writing a nested loop over every person, twice. Write it anyway — that loop is the chapter.

hint

The moment you start building an index-by-org dict to speed it up, notice: you're hand-rolling what the relational model gives you for free.

hint

For the recursive CTE, carry a depth column and a visited path to guard against the endorsement cycle.

DONE WHEN

· SQL and document answers agree for all five queries once canonicalized, checked at N = 1, 3 and 6.

· After the v2 load all five queries still pass in both models and Q1 now includes certifications.

· Notes file names the winning model per query and uses the words locality, join, recursion, and schema-on-read or schema-on-write.

EX 03

Build tsq — a Triple-Store Query Engine

Write a small Datalog-ish engine over graph.nt that answers pattern queries by unification, then add recursive rules so N-hop traversal becomes one line.

  1. Parse clauses of the form '?p works_at org:initech. ?p endorses ?q.' and evaluate by scanning triples, extending a bindings dict, and backtracking on failure.
  2. Support conjunction across any number of clauses plus literal patterns, so you can return names instead of IDs.
  3. Add recursive rules — reachable(?a,?b) from endorses, and reachable(?a,?c) from endorses plus reachable — evaluated by iterating to a fixpoint, with a 'within N' depth guard.
  4. Re-answer queries 2 through 5 in tsq and diff the results against your SQL and document answers.
  5. Count the lines each version of Q5 took in SQL, document code, and tsq.
hint

A binding is just a dict. Matching a pattern against a triple either extends the dict or fails; the whole evaluator is 'for each triple, try to extend, recurse on the remaining clauses'.

hint

Get stage one to about ten lines before adding anything clever.

hint

Fixpoint iteration (apply rules until no new facts appear) terminates on the endorsement cycle by construction; naive recursion loops forever.

hint

Keep the scope tight: conjunctive patterns and recursive rules only, no negation, aggregation or OR.

DONE WHEN

· Queries 2 through 5 via tsq return exactly the same answers as the SQL versions.

· A 'within 10' query through the endorsement cycle returns correct results in under five seconds.

· Q5 in tsq is at most three lines, against a recursive CTE and a hand-written BFS.

EX 04

Stretch: Teach Your Engine to Plan

Reorder clauses by selectivity before evaluating, and watch a deliberately worst-ordered query get dramatically faster without changing a single answer.

  1. Generate a large triples file (hundreds of thousands of lines) and write a pathological query with the broadest clause first and the most selective last.
  2. Add a pre-pass that counts matching triples per clause, then sort the conjunction most-selective-first before evaluation.
  3. Add an --explain flag that prints the chosen clause order and per-clause match counts.
  4. Time the pathological query with planning off and on, and re-run every earlier query to confirm the answers are untouched.
hint

Estimate selectivity cheaply — a single scan counting matches per clause is enough to beat the worst order badly.

hint

You are now a query optimizer; every declarative system you use does a grown-up version of this, which is exactly why declarative queries win.

DONE WHEN

· The pathological query runs at least 10x faster with planning enabled.

· Every earlier query returns byte-identical results with planning on and off.

· Notes name one thing a real planner has that yours doesn't — statistics, indexes, join algorithms, or a cost model.

Go deeper (after the bench)

Read DDIA Chapter 2 now — the relational-versus-document half lands differently once you've written all three loaders, and the graph/Datalog section reads like documentation for the engine you just built. If you want one more thing, do Learn Datalog Today (learndatalogtoday.org, free and interactive) right after tsq; every chapter reads as "oh, that's my engine plus one feature."