Engineering problem How does the choice of representation change what the data duplicates, and what that duplication costs?
A campus booking service stores rooms and the reservations made against them. The engineer chooses how to lay those facts out before any of the data exists, and that one choice decides how many copies of a room's facts the database holds — which decides both the footprint and the work a rename costs.
Background
A booking service holds two kinds of fact: what a room is — its name, its building, its capacity — and what has been booked against it. Those facts do not dictate how they are written down. The engineer chooses a representation: a layout of tables, or of documents, that the facts are stored into. Three layouts are compared here, and all three hold identical booking data.
The normalized relational layout keeps a ROOMS table with one row
per room and a RESERVATIONS table whose rows carry only a room identifier. The
denormalized relational layout has no rooms table at all: it copies the room's
facts onto every reservation row. The document layout stores one document per
room, with that room's reservations nested inside it.
Duplication means something precise here, and it is not “the same text appears
twice”. A fact has to be stored once; what counts as duplication is the excess.
Write a room's metadata onto each of its V reservations and one of those writes is
the fact while V − 1 are copies. So duplication is a property of
repetition: a room with a single reservation has no excess to pay for,
whichever layout stores it.
That makes the byte cost of duplication depend on two things an engineer can see — how many times the fact repeats, and how large the fact is. Doubling the reservations per room doubles the copies; doubling the room's metadata doubles what each copy costs.
Not duplicating is not free either. A normalized layout connects a reservation to its room with an identifier, and pays those identifier bytes once per occurrence: references instead of copies. The document layout avoids both, because containment is the reference, which is why it lands a little below the normalized tables rather than above them.
The second cost appears in no byte total. Rooms get renamed — a building is renumbered, a
hall takes a donor's name, a department reshuffles. Where the name is stored once, a rename is
one write and the database cannot hold two answers. Where it is stored V times,
all V copies have to change together, and a write that stops part-way leaves two
different names for one room. Duplication did not merely spend space; it created an obligation
to keep copies in agreement every time the fact changes.
The document representation is not the denormalized one. Nesting the reservations inside the room document stores the room's facts once, exactly as the normalized tables do. Its duplication profile matches the normalized case; only the denormalized table copies the room's facts onto every reservation. Database category and normalization are different dimensions, and this is where that separation becomes visible.
One qualification. Every figure on this page is arithmetic over the parameters you set, not a measurement of a running system. What the arithmetic settles is the direction and the shape of the trade; a figure for a particular engine has to be measured on that engine. The collapsed Model reference at the foot of the page states the formulas, the fixed constants and the exclusions in full.
Model
Table 1 — Model parameters
| Parameter | What it sets | Values | Default |
|---|---|---|---|
| Representation | The layout under study — how the same facts are written down | Normalized · Denormalized · Document | Normalized |
| Rooms R | Distinct rooms in the catalogue — the entity count | 10–10,000 | 100 |
| Reservations per room V | How many times each room's facts can repeat | 1–1000 | 20 |
| Room metadata size M | Bytes of room facts — what one duplicated copy costs | 50–2000 bytes | 200 |
Duplication is not in this table because it is not a control: it is produced by the representation and the repetition. Four further settings — reservation size, identifier size, the physical-overhead estimate and which room to rename — are in Further investigation, and the model's fixed constants are in the Model reference.
Table 2 — Observed quantities
| Quantity | What it counts | Unit |
|---|---|---|
| Logical storage | Unique facts, plus duplicated copies, plus the identifier bytes that connect records | bytes |
| Duplicated bytes | The excess only — the same fact stored again. Reported with a word for its band, not a colour alone | bytes |
| Records a rename touches | Stored records that have to be rewritten when one room's name changes. Not a storage figure | records |
The first two are what the representation costs to store. The third is what it costs to change, and it is the quantity the exercise exists to make visible.
Model assumptions
- Every figure is arithmetic over the parameters above. Nothing is measured and no database is contacted.
- Uniform sizes. Every room's metadata is the same size and every reservation is the same size, so the model has no distribution and no outliers.
- Reservations divide evenly among rooms, and every room has at least one.
- Indexes, page padding, compression and replication are outside the model unless the optional physical-overhead estimate is switched on, and that estimate is labelled an estimate wherever it appears.
The simulator estimates logical representation size, not actual disk consumption by PostgreSQL, MongoDB, or another engine. It claims no storage figure for any of them, or for any other product: nothing here was run.
Experiment
Three comparisons, in order. Each one names its baseline, the single parameter it changes and what it holds still, so a reading means something. Predict before you run — write the prediction down, then set the controls in the apparatus below and read the three reported quantities.
-
Representation against footprint
- Baseline
- 100 rooms, 20 reservations each, 200-byte room metadata, Normalized.
- Change
- Representation: Normalized → Denormalized → Document.
- Hold constant
- Rooms, reservations per room, room metadata size.
- Predict
- Which layout stores the most, and by roughly what factor? Which of the three duplicate nothing at all?
- Run & measure
- Logical storage and duplicated bytes, for each of the three.
- Explain
- The document layout is a different kind of database from the normalized tables, yet it duplicates the same amount — none. So what decides duplication: the kind of database, or the layout?
-
Repetition is what duplicates
- Baseline
- Denormalized at 100 rooms, 20 reservations each, 200-byte room metadata — Experiment 1's baseline with Denormalized selected.
- Change
- Reservations per room: 20 → 1.
- Hold constant
- Representation (Denormalized), rooms, room metadata size.
- Predict
- At one reservation per room, what happens to the duplicated bytes, and to the denormalized layout's multiple of the normalized footprint?
- Run & measure
- Duplicated bytes and the multiple reported beside the band word, at
V= 20 and atV= 1. - Explain
- Is denormalizing expensive, or is repeating expensive? Name a service where denormalizing would cost almost nothing.
-
What a rename obliges
- Baseline
- Denormalized, 100 rooms, 20 reservations each, 2,000-byte room metadata, renaming room 1.
- Change
- Representation: Denormalized → Normalized → Document, renaming the same room each time.
- Hold constant
- Rooms, reservations per room, room metadata size, the room renamed.
- Predict
- How many stored records does each layout have to rewrite for one rename? Does the answer depend on the room's metadata size?
- Run & measure
- Records a rename touches, for each layout, and the record lists in the rename comparison.
- Explain
- A rename costs no bytes. What does the denormalized count oblige the engineer to guarantee, and what is left behind if one of those writes does not land?
Interactive apparatus — controls
Results
no duplicated facts
All three layouts, the same data
The rename comparison
Each layout's records for the selected room, with every record holding a copy of the name marked. This is the part that matters more than the byte totals: it connects the representation to the obligation of keeping the data consistent while it is being changed.
Interpretation
- Two of the three layouts report the same duplicated bytes. Say which two, and say what they have in common that the third does not.
- The document layout lands below the normalized tables rather than above them. Which term in the model accounts for the difference, and which control changes it?
- At one reservation per room, denormalizing duplicates nothing. State the condition under which denormalizing is cheap, in terms of the parameters rather than the layouts.
- The rename count is not a storage figure. Say what it is a figure for, and what it would cost a running service to get it wrong.
- You are choosing a layout for this booking service. Recommend one, name the parameter whose value would change your recommendation, and say which way.
Further investigation
Optional. The apparatus above carries the four parameters the principal comparison needs; the model computes more than that, and the rest is here. None of it is required to answer the interpretation questions.
Additional parameters, and the optional physical-overhead estimate
Why physical storage is off by default. Logical storage follows from the representation: count the facts, count the copies, count the identifier bytes. It is exact arithmetic over the parameters in Table 1. Physical storage adds per-record headers and index entries, and those sizes are properties of a storage engine — so turning the estimate on changes the page's claim from a calculation into a model, and every figure it produces is labelled an estimate. The model's statement above holds either way: nothing here was run.
Further classroom configurations
Every quantity the model computes
- Unique facts
- —
- Duplicated facts
- —
- References and identifiers
- —
- Record overhead (estimated)
- —
- Field-name overhead (estimated)
- —
- Index overhead (estimated)
- —
- Stored records
- —
- Reservations in total
- —
The three stored shapes, as the controls set them
One data set — —. Three ways to write it down. The current choice is outlined.
Logical storage as the reservations per room grow
Model reference — the formulas, the layouts, the constants and the exclusions
Nothing on this page runs a database. There is no engine, no file, no page cache, and no measurement. Every figure comes from the formulas below applied to the controls, which is why the same controls always produce the same answer. The arithmetic is exact and there is no randomness anywhere in it, so a configuration is reproducible without needing a seed.
Two quantities, kept apart
S_logical = S_unique + S_duplicated + S_references
S_physical = S_logical + S_record_overhead + S_field_name_overhead + S_index_overhead
The first follows directly from the chosen representation: it counts the facts the representation stores, the copies it makes of them, and the identifier bytes it spends connecting records. The second requires assumptions about a storage engine — header layout, index structure, how field names are encoded — so it is labelled an estimate wherever it appears, and it is off until the reader asks for it.
The record layouts, and what each field costs
Write N = R × V for the total number of reservations. Identifier bytes are
charged per occurrence: a row's own key and a foreign key each cost I.
| Representation | Stored shape | Unique | Duplicated | References |
|---|---|---|---|---|
| Normalized relational | ROOMS(id, metadata)RESERVATIONS(id, room_id, payload) |
R·M + N·Z | 0 | R·I + 2N·I |
| Denormalized relational | RESERVATIONS(id, room_id, room_metadata, payload) |
R·M + N·Z | (N − R)·M | 2N·I |
| Document-oriented | { room_id, metadata, reservations: [ { id, payload }, … ] } |
R·M + N·Z | 0 | R·I + N·I |
Three modelling decisions worth arguing with, stated rather than buried.
First, the duplicated column is the excess: the denormalized table stores the room's
metadata V times, one of which is the fact and V − 1 of which
are copies, so the excess is (N − R)·M and the unique column is the
same in all three rows. Second, the denormalized representation has no ROOMS table
at all, which is what the lecture's diagram shows — and it means a room with no
reservations has nowhere to live. That is a fidelity cost of the shape, not only a storage one.
Third, a nested reservation carries no room_id: containment is the
reference, which is why the document representation spends N·I fewer
reference bytes than the normalized tables and lands a little below them.
A real document encoding stores its field names alongside the data, while a relational table keeps its column names once in the catalogue. That is a genuine cost, and it would push the document representation back above the normalized one — but it is a property of an encoding rather than of the representation, so it sits in the physical estimate below and not in the logical arithmetic.
Reservations per room
Every room holds exactly V reservations, so N = R × V and the
arithmetic stays closed-form at every scale the controls allow — ten million reservations
is a multiplication, not a loop. A real campus has a long tail of popular and unused rooms. The
uniform assumption changes the totals; it does not change which facts a representation
duplicates, which is what the exercise is about.
The physical estimate — assumptions, named
| Constant | Value | Assumption it encodes |
|---|---|---|
| Record header | — | Charged once per stored record: a relational row, a top-level document, and each nested sub-document. Stands for a length prefix, a visibility or version stamp, and a null bitmap. |
| Field-name bytes | — | Charged per document and per nested sub-document, in the document representation only. A schemaless encoding stores field names with every value; a relational table stores them once. |
| Index entry | — | 2I + 12 — a key, a row or document pointer, and per-entry tree bookkeeping. |
The index count is not a constant; it follows from which lookups each representation has to support. All three are charged for the same two capabilities: find a reservation by its own identifier, and find the reservations belonging to a room.
| Representation | Indexes assumed | Entries |
|---|---|---|
| Normalized relational | Primary key on ROOMS.id; primary key on RESERVATIONS.id; secondary index on RESERVATIONS.room_id |
R + 2N |
| Denormalized relational | Primary key on RESERVATIONS.id; secondary index on RESERVATIONS.room_id |
2N |
| Document-oriented | Primary key on room_id; one multi-key index over the nested reservations[].id. A room's reservations need no index at all — they arrive with the document. |
R + N |
What the estimate leaves out, stated so it is not mistaken for a measurement: no page or block granularity and therefore no internal fragmentation, no compression, no column-store encoding, no write-ahead log, no free-space map, no multi-version row copies, no replication factor, and no table or index bloat from the update history. A real engine has all of those, and the direction they push is not uniform — compression cuts the duplicated bytes hardest, while fragmentation and version copies add bytes the model never counts. Anyone who needs a number for a real system has to measure that system.
The rename, and what it costs
| Representation | Records touched | Why, and what it obliges |
|---|---|---|
| Normalized relational | 1 record | The room's name exists in one place. One write, and the database cannot hold two answers. |
| Denormalized relational | V records | Every reservation for that room carries a copy. All V have to change together: a write that stops halfway leaves the database holding two different names for one room. The duplication did not merely cost space — it created a consistency obligation. |
| Document-oriented | 1 document | The name lives once, in the room document. Its physical rewrite cost depends on the database engine: a document store may patch the field in place, or it may rewrite the whole document including every nested reservation. That is an engine property, so this page reports the logical count and names the uncertainty rather than estimating it away. |
The full parameter set
| Parameter | Meaning | Values | Default | What changing it does |
|---|---|---|---|---|
| Representation | How the same data is laid out | Normalized · Denormalized · Document | Normalized | Changes how many copies of a room's facts are stored |
| Rooms | Distinct rooms in the catalogue | 10–10,000 rooms | 100 | Scales the room-side cost in every layout |
| Reservations per room | Bookings held against each room | 1–1000 each | 20 | Scales the duplication the denormalized layout pays |
| Room metadata size | Bytes of room facts — name, building, capacity | 50–2000 bytes | 200 | Sets what one duplicated copy costs |
| Reservation size | Bytes of one booking's own fields | 50–1000 bytes | 100 | Scales the reservation side, identically in all three |
| Identifier size | Bytes of the key that joins a reservation to a room | 4–16 bytes | 8 | The price normalization pays for not duplicating |
| Physical-overhead estimate | Whether assumed engine overhead is added | Off · On | Off | Turns the reported figure from a calculation into an estimate |
| Room to rename | Which room the rename comparison follows | 1…R | 1 | Changes the name shown; the record counts are unaffected |
The model's self-tests
The engine is a pure module published as window.StorageCost with no browser
dependency, so the test suite under tests/ extracts it from this file and
exercises it directly. The tested text and the published text are the same bytes.