3.1 Relational vs Document Models

1.1 History — and why it matters that the challengers all failed

The relational model: proposed by Edgar Codd in 1970. Data organized into relations (tables), each an unordered collection of tuples (rows).

It was originally a theoretical proposal, and many people doubted it could be implemented efficiently. By the mid-1980s RDBMSs and SQL had won for regularly structured data.

Meanwhile SQL absorbed each challenge in turn — XML support, JSON support, graph support.

Each competitor generated a lot of hype in its time, but none lasted. Instead, SQL grew to incorporate other types of data.

NoSQL was never a single technology — it was a loose set of ideas around new data models, schema flexibility, scalability, and open source licensing. NewSQL aimed at NoSQL scalability + relational data model and transactional guarantees. Both were very influential in design; as the principles became widely adopted, use of the terms faded.

The lasting effect of NoSQL: the document model (usually JSON), popularized by MongoDB and Couchbase — although most relational databases have now added JSON support too.

1.2 The object-relational impedance mismatch

If data is in relational tables and application code is object-oriented, an awkward translation layer is needed between objects and tables/rows/columns.

(The term is borrowed from electronics: every circuit has an impedance on its inputs and outputs; power transfer is maximized when output and input impedances match. A mismatch causes signal reflections and other troubles.)

ORM frameworks (ActiveRecord, Hibernate) reduce boilerplate but are widely criticized:

ORM advantages (the book is even-handed):

• For data well-suited to relational, some translation is inevitable — ORMs reduce the boilerplate for simple and repetitive cases (complex queries can still be handwritten)
• Some help with caching query results, reducing DB load
• Some help with schema migrations and other administrative activities

1.3 The document model for one-to-many

The LinkedIn-résumé example. first_name/last_name appear once per user → columns. But positions, education, and contact info are one-to-many → separate tables with foreign keys to users… or one JSON document:

{
  "user_id": 251, "first_name": "Barack", "last_name": "Obama",
  "headline": "Former President of the United States of America",
  "region_id": "us:91",
  "positions": [
    {"job_title": "President",        "organization": "United States of America"},
    {"job_title": "US Senator (D-IL)","organization": "United States Senate"}
  ],
  "education": [
    {"school_name": "Harvard University",  "start": 1988, "end": 1991},
    {"school_name": "Columbia University", "start": 1981, "end": 1983}
  ],
  "contact_info": {"website": "https://barackobama.com", "x": "https://x.com/barackobama"}
}

Advantages claimed for the document form:

• Reduced impedance mismatch with application code
• Lack of schema (discussed below)
• Better locality: fetching the relational profile needs multiple queries or a messy multiway join; in JSON all the relevant information is in one place, making the query both faster and simpler
• The tree structure is made explicit

The important caveat: a one-to-many relationship is sometimes called one-to-few — a résumé has a small number of positions. If you have a genuinely large number of related items — e.g. thousands of comments on a celebrity's post — embedding them all in the same document may be too unwieldy, so the relational approach is preferable.

1.4 Normalization, denormalization, and joins

Why is region_id an ID rather than the string "Washington, DC, United States"? If the UI has a free-text field, a string is fine. But a standardized list with a drop-down gives:

• Consistent style and spelling across profiles
• Disambiguation — "Washington" alone: the DC or the state?
• Ease of updating — the name is stored once, so a city rename propagates everywhere
• Localization — the standardized list can be translated, so the region displays in the viewer's language
• Better search — the region list can encode that Washington is on the US East Coast, which the raw string doesn't reveal

Definition: storing an ID = more normalized (human-meaningful information stored in exactly one place; everything referring to it uses an ID that has meaning only within the database). Storing the text = denormalized (duplicating human-meaningful information in every record).

The core argument for IDs: because an ID has no meaning to humans, it never needs to change. The ID stays the same even when the information it identifies changes. Anything meaningful to humans may need to change — and if it's duplicated, all redundant copies must be updated, requiring more code, more writes, more disk space, and risking inconsistency when some copies are updated and others aren't.

Downside of normalization: every display of a record containing an ID needs an extra lookup — a join.

SELECT users.*, regions.region_name
FROM users JOIN regions ON users.region_id = regions.id
WHERE users.id = 251;

Document databases can store both normalized and denormalized data, but they're associated with denormalization because (a) JSON makes it easy to add denormalized fields, and (b) weak join support in many document databases makes normalization inconvenient. Some don't support joins at all → you join in application code (fetch a document with an ID, then a second query to resolve it). MongoDB offers $lookup in an aggregation pipeline:

db.users.aggregate([
  { $match: { _id: 251 } },
  { $lookup: { from: "regions", localField: "region_id",
               foreignField: "_id", as: "region" } }
])

The trade-off, stated crisply:

View denormalization as a form of derived data — you need a process for updating the redundant copies.

And beyond the cost of the updates: what about consistency if a process crashes halfway through? Databases with atomic transactions make consistency easier, but not all databases offer atomicity across multiple documents. Consistency can also be maintained via stream processing (Ch 12).

Where each fits:

• Normalization → better for OLTP, where both reads and updates must be fast
• Denormalization → often better for analytics, where updates are bulk and read-only query performance dominates
• Small-to-moderate scale → normalized is often best: no multi-copy consistency worries, and join cost is acceptable
• Very large scale → the cost of joins can become problematic

1.5 The X/Twitter timeline: a masterclass in partial denormalization

Recall Ch 2's materialized timeline. It's the cache of the result of the expensive posts ⋈ follows join, and fan-out is how the denormalized copy is kept consistent.

But the crucial detail: X's materialized timeline does NOT store the post text. Each entry stores only:

• the post ID
• the ID of the user who posted it
• a little extra info to identify reposts and replies

i.e., it's the precomputed result of:

SELECT posts.id, posts.sender_id FROM posts
  JOIN follows ON posts.sender_id = follows.followee_id
  WHERE follows.follower_id = current_user
  ORDER BY posts.timestamp DESC LIMIT 1000

So reading a timeline still performs two joins, in application code:

1. Look up post IDs → fetch actual post content plus statistics like like/reply counts
2. Look up sender IDs → fetch username, profile picture, other details

This is called hydrating the IDs.

Why store only IDs? Because the data they refer to is fast-changing:

• Like and reply counts may change multiple times per second on a popular post
• Users regularly change their username or profile photo
• The timeline must show the latest counts and picture when viewed
• Denormalizing them would also significantly increase storage cost

This example shows that having to perform joins when reading data is NOT, as sometimes claimed, an impediment to creating high-performance, scalable services. Hydration scales easily because it parallelizes well, and the cost doesn't depend on how many accounts you follow or how many followers you have.

The generalizable rule: the most scalable approach denormalizes some things and leaves others normalized. Decide per-field by asking:

1. How often does this information change? (fast-changing → keep normalized, hydrate on read)
2. What is the cost of reads vs writes — which may be dominated by outliers (users with many follows/followers)

Normalization and denormalization are not inherently good or bad — they are trade-offs in read/write performance and implementation effort.

1.6 Many-to-one and many-to-many

In the relational model a many-to-many is an associative table (join table): each position row associates one user ID with one organization ID.

Many-to-one and many-to-many relationships do not easily fit within one self-contained JSON document; they lend themselves to a normalized representation.

In a document model you'd reference by ID:

{ "user_id": 251, "first_name": "Barack", "last_name": "Obama",
  "positions": [
    {"start": 2009, "end": 2017, "job_title": "President",         "org_id": 513},
    {"start": 2005, "end": 2008, "job_title": "US Senator (D-IL)", "org_id": 514}
  ] }

Querying many-to-many "in both directions" — all organizations a person worked for, and all people who worked at an organization. Two options:

Many document databases and relational databases with JSON support can create indexes on values inside a document — this is what makes the normalized document approach viable.

1.7 Star and snowflake schemas (analytics)

Data warehouses are usually relational, with conventions optimized for business analysts: star schema, snowflake schema, dimensional modeling, and one big table (OBT). ETL translates operational data into the chosen schema.

Fact table — each row is an event that occurred at a particular time (a customer's purchase of a product; or, for web analytics, a page view or click).

Facts are usually captured as individual events, because this allows maximum flexibility of analysis later. This means the fact table can become extremely large — a big enterprise may have many petabytes of transaction history, mostly fact tables.

Fact table columns are either:

• Attributes — e.g. the price at which the product was sold and the cost from the supplier (so profit margin can be computed)
• Foreign keys to dimension tables — the who, what, where, when, how, and why of the event

Even date and time get a dimension table, because it lets you encode extra facts about dates (public holidays), enabling queries that differentiate holiday from non-holiday sales.

The name star schema comes from the visual: fact table in the middle, dimension tables around it like rays.

Snowflake schema = dimensions further broken into subdimensions (separate brand and category tables referenced by FK from dim_product rather than stored as strings). More normalized than star schemas — but star schemas are often preferred because they're simpler for analysts to work with.

Tables are wide: fact tables frequently have over a hundred columns, sometimes several hundred. Dimension tables are wide too — dim_store might include which services each store offers, whether it has an in-store bakery, square footage, opening date, last remodel date, and distance to the nearest highway.

Relationship shape: star/snowflake schemas consist mostly of many-to-one relationships. Other types could exist in principle but are often denormalized to simplify queries — e.g. a multi-item transaction is not represented explicitly; the fact table just has a separate row per product purchased, and those rows happen to share the same customer ID, store ID, and timestamp.

One big table (OBT) takes denormalization further: drop the dimension tables entirely and fold their information into denormalized columns on the fact table — essentially precomputing the fact↔dimension joins. More storage, sometimes faster queries.

Why aggressive denormalization is safe here: the data is a log of historical data that is not going to change (except to correct errors). The consistency and write-overhead problems of OLTP denormalization are not as pressing in analytics.

1.8 When to use which model

Arguments for document: schema flexibility · better performance due to locality · closer to the application's object model. Arguments for relational: better support for joins, many-to-one, and many-to-many.

If your data has a document-like structure — a tree of one-to-many relationships where the entire tree is typically loaded at once — a document model is probably a good idea. The relational technique of shredding (splitting a document-like structure across multiple tables) can lead to cumbersome schemas and unnecessarily complicated application code.

Document model limitations:

• You cannot refer directly to a nested item. You must say "the second item in the list of positions for user 251." If you need to reference nested items, relational works better — any item is directly addressable by its ID.
• Conversely, ordered/reorderable lists favor documents. A to-do list or issue tracker where users drag-and-drop to reorder: in a document, items (or their IDs) sit in a JSON array that is the order. Relational databases have no standard way of representing reorderable lists — the workarounds are sorting by an integer column (requiring renumbering when inserting into the middle), maintaining a linked list of IDs, or fractional indexing.

1.9 Schema-on-read vs schema-on-write

Most document databases (and JSON support in relational databases) do not enforce any schema. (XML support in relational databases usually does offer optional schema validation.) No schema = arbitrary keys and values can be added, and readers have no guarantees about what fields exist.

"Schemaless" is misleading — the code reading the data usually assumes some structure. There is an implicit schema; it's just not enforced by the database.

Just as the static/dynamic typing debate has no clear winner, neither does this one.

The difference is most visible when changing the data format. Say you store a user's full name in one field and now want first and last name separately.

Document (schema-on-read): just start writing new documents with the new fields, and handle old ones in application code:

if (user && user.name && !user.first_name) {
    // Documents written before Dec 8, 2023 don't have first_name
    user.first_name = user.name.split(" ")[0];
}

Downside: every part of your application that reads from the database must now handle old formats, possibly written long ago.

Relational (schema-on-write): migrate.

ALTER TABLE users ADD COLUMN first_name text DEFAULT NULL;
UPDATE users SET first_name = split_part(name, ' ', 1);        -- PostgreSQL
UPDATE users SET first_name = substring_index(name, ' ', 1);   -- MySQL

Adding a column with a default is fast and unproblematic even on large tables. But the UPDATE is likely slow on a large table since every row is rewritten, and other schema operations (e.g. changing a column's datatype) typically require copying the entire table.

Tools exist for background, no-downtime schema change, but migrations on large databases remain operationally challenging. And the clever escape hatch: add the column with a NULL default (fast) and fill it in at read time — exactly as you would with a document database.

Schema-on-read is advantageous when the data is heterogeneous:

• Many types of objects, and it isn't practicable to put each type in its own table
• The structure is determined by external systems you don't control and that may change at any time

But when all records are expected to have the same structure, schemas are a useful mechanism for documenting and enforcing that structure.

1.10 Data locality for reads and writes

A document is usually stored as a single continuous string — JSON, XML, or a binary variant like MongoDB's BSON. If the app often needs the entire document (to render a page), this storage locality has a performance advantage; splitting across tables requires multiple index lookups, which may mean more disk seeks and more time.

The locality advantage applies ONLY if you need large parts of the document at the same time. The database typically loads the entire document, which is wasteful if you need only a small part of a large one. And on updates, the entire document usually needs to be rewritten.

Therefore: keep documents fairly small and avoid frequent small updates.

Locality is not exclusive to the document model:

1.11 Query languages for documents

Relational → SQL. Document databases vary widely: key-value access by primary key only / secondary indexes into document values / rich query languages.

• XML: XQuery and XPath — complex queries, including joins across multiple documents, results formatted as XML
• JSON: JSON Pointer and JSONPath are the XPath equivalents
• MongoDB aggregation pipeline — a query language for collections of JSON documents

Aggregation example — sharks sighted per month:

-- PostgreSQL
SELECT date_trunc('month', observation_timestamp) AS observation_month,
       sum(num_animals) AS total_animals
FROM observations
WHERE family = 'Sharks'
GROUP BY observation_month;

// MongoDB aggregation pipeline — same query
db.observations.aggregate([
    { $match: { family: "Sharks" } },
    { $group: {
        _id: { year:  { $year:  "$observationTimestamp" },
               month: { $month: "$observationTimestamp" } },
        totalAnimals: { $sum: "$numAnimals" }
    } }
]);

The aggregation pipeline is similar in expressiveness to a subset of SQL, with a JSON-based syntax rather than SQL's English-sentence style. The difference is perhaps a matter of taste.

1.12 Convergence

Document and relational databases started as very different approaches and have grown more similar over time.

• Relational added JSON types and query operators, and indexing of properties inside documents
• Document (MongoDB, Couchbase, RethinkDB) added joins, secondary indexes, and declarative query languages

This is good news, because the two models work best when combined in the same database. Many document databases need relational-style references; many relational databases have sections where schema flexibility helps. Relational–document hybrids are a powerful combination.

Historical footnote worth knowing: Codd's original 1970 relational model allowed something like JSON — he called them nonsimple domains: a value in a row need not be a primitive; it can be a nested relation, giving arbitrarily nested trees. That's comparable to the JSON/XML support added to SQL over 30 years later.