The Cost of Storing Information

The same reservations, stored three ways. What gets duplicated is a property of the representation, not of the database category.

Teach with MAGE
ECE 30861 · Act III
Data Management

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

Figure 1: the same booking data in three representations Three panels hold the same two rooms and four reservations. Panel A, normalized, shows two tables: a rooms table with one row per room carrying that room's name and metadata of M bytes, and a reservations table whose rows carry only a room identifier. Nothing is duplicated, each room's facts are stored once, and a rename touches one row. Panel B, denormalized, shows one wide reservations table and no rooms table; every row repeats the room's name and metadata, drawn shaded and outlined in the failure colour and labelled repeated on every row. Two of its four stored copies are excess, duplication grows with the reservations per room, and a rename touches every row. Panel C, document, shows two room documents, each storing its room's facts once and nesting that room's reservations inside it; nothing is duplicated, containment is the reference, and a rename touches one document. The marked quantities R, V and M are defined in Table 1. A · Normalized B · Denormalized C · Document rooms R = 2 rooms R1 metadata = M B R2 metadata = M B reservations V = 2 each room_id R1 · when room_id R1 · when room_id R2 · when room_id R2 · when 0 bytes duplicated each room's facts stored once a rename touches 1 row reservations no rooms table metadata = M B · when metadata = M B · when metadata = M B · when metadata = M B · when Repeated on every row 2 of 4 copies are excess duplication grows with V a rename touches every row room R1 metadata = M B reservation · when reservation · when room R2 metadata = M B reservation · when reservation · when 0 bytes duplicated containment is the reference a rename touches 1 document
Figure 1. Two rooms, two reservations each, three layouts. Only the denormalized table copies the room's facts onto every reservation row — which is both the extra bytes and the extra rows a rename has to visit.

Table 1 — Model parameters

Table 1 — the parameters you adjust in the apparatus
ParameterWhat it sets ValuesDefault
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,000100
Reservations per room V How many times each room's facts can repeat 1–100020
Room metadata size M Bytes of room facts — what one duplicated copy costs 50–2000 bytes200

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

Table 2 — the quantities the apparatus reports
QuantityWhat 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.

  1. 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?

  2. 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 at V = 1.
    Explain
    Is denormalizing expensive, or is repeating expensive? Name a service where denormalizing would cost almost nothing.

  3. 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

Which layout the reported figures describe.
Distinct rooms in the catalogue. Scales every layout alike.
How many times a room's facts repeat in the denormalized layout.
Bytes of room facts. Sets what one duplicated copy costs.
Download HTML

Results

Logical storage — for the layout selected above
Duplicated bytes — —
Records a rename touches — —

no duplicated facts

All three layouts, the same data

Unique facts — stored once Duplicated facts — the same fact stored again References and identifiers Estimated storage overhead (hatched)

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

  1. 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.
  2. 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?
  3. 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.
  4. 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.
  5. 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
Scales the reservation side identically in all three layouts, so it moves the totals without moving the comparison.
The price the normalized layout pays for not duplicating.
Adds assumed engine overhead, labelled an estimate everywhere it appears.
Which room the rename comparison follows.

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
Physical storage — estimate — turn the optional control on
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

Normalized relational Denormalized relational Document-oriented

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.

RepresentationStored shapeUniqueDuplicatedReferences
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

ConstantValueAssumption 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.

RepresentationIndexes assumedEntries
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

RepresentationRecords touchedWhy, and what it obliges
Normalized relational1 record The room's name exists in one place. One write, and the database cannot hold two answers.
Denormalized relationalV 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-oriented1 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

Every parameter the model exposes, with its range, default and effect
ParameterMeaning ValuesDefault 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 rooms100 Scales the room-side cost in every layout
Reservations per room Bookings held against each room 1–1000 each20 Scales the duplication the denormalized layout pays
Room metadata size Bytes of room facts — name, building, capacity 50–2000 bytes200 Sets what one duplicated copy costs
Reservation size Bytes of one booking's own fields 50–1000 bytes100 Scales the reservation side, identically in all three
Identifier size Bytes of the key that joins a reservation to a room 4–16 bytes8 The price normalization pays for not duplicating
Physical-overhead estimate Whether assumed engine overhead is added Off · OnOff Turns the reported figure from a calculation into an estimate
Room to rename Which room the rename comparison follows 1…R1 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.