Schema Design, Normalisation and NoSQL

How you model data decides what is easy, what is slow and what is impossible later. Interviewers ask you to design a schema for a product (a library, a ride-sharing app, a social feed) and then to defend your choice of database. This chapter covers relational modelling and normalisation, when to denormalise, the main NoSQL families, and a decision framework.

1. Relational modelling

Start from entities (things), attributes (facts about them) and relationships:

• One-to-many: a foreign key on the "many" side (orders.customer_id).
• Many-to-many: a join table holding two foreign keys (student_course(student_id, course_id)), often with its own attributes (grade, enrolled_on).
• One-to-one: a foreign key with a unique constraint, or merge the tables.

Choose primary keys deliberately. Natural keys (an email, a national ID) can change or collide; surrogate keys (an auto-increment integer, a UUID) are stable. Auto-increment integers are compact and index-friendly but guessable and awkward to generate across shards; random UUIDv4 are unguessable but scatter inserts across the index; time-ordered IDs (UUIDv7, ULID, Snowflake IDs) give uniqueness plus locality.

Always declare constraints (NOT NULL, UNIQUE, CHECK, FOREIGN KEY). They make impossible data impossible, which is cheaper than finding bugs later.

2. Normalisation

Normalisation removes redundancy so each fact is stored once, preventing update, insert and delete anomalies.

The mnemonic: every non-key attribute depends on the key, the whole key, and nothing but the key.

An anomaly, concretely

A single wide table repeats the department name for every employee. Renaming a department requires updating many rows, and a missed row leaves inconsistent data.

CREATE TABLE emp_wide (id INTEGER PRIMARY KEY, name TEXT, dept_id INTEGER, dept_name TEXT);
INSERT INTO emp_wide VALUES (1,'Asha',10,'Engineering'),(2,'Ravi',10,'Engineering'),(3,'Meera',20,'Sales');

CREATE TABLE dept (id INTEGER PRIMARY KEY, name TEXT NOT NULL UNIQUE);
CREATE TABLE emp  (id INTEGER PRIMARY KEY, name TEXT NOT NULL, dept_id INTEGER NOT NULL REFERENCES dept(id));
INSERT INTO dept VALUES (10,'Engineering'),(20,'Sales');
INSERT INTO emp  VALUES (1,'Asha',10),(2,'Ravi',10),(3,'Meera',20);

# wide table: renaming touches every row, and a partial update leaves contradictions
q("UPDATE emp_wide SET dept_name = 'Platform' WHERE id = 1")
assert len({r[0] for r in q("SELECT dept_name FROM emp_wide WHERE dept_id = 10")}) == 2       # the same department has two names

# normalised: one fact, one place
q("UPDATE dept SET name = 'Platform' WHERE id = 10")
names = q("SELECT DISTINCT d.name FROM emp e JOIN dept d ON d.id = e.dept_id WHERE e.dept_id = 10")
assert names == [("Platform",)]

3. When to denormalise

Normalised schemas are right for correctness and writes. Joins cost time at scale, so denormalise deliberately, for a measured read bottleneck:

• Store a derived value (an order_total, a like_count) and keep it in sync with a trigger, application code, or an async job.
• Copy a column that rarely changes (the product name on an order line, so history is preserved even if the product is renamed; this is also a correctness feature, an immutable snapshot).
• Materialised views and summary tables for reporting, refreshed on a schedule.
• Embed related data in a document (NoSQL).

The price is possible inconsistency and more write logic. Say what you would do to keep the copies consistent and what error you can tolerate.

q("CREATE TABLE posts(id INTEGER PRIMARY KEY, likes INTEGER NOT NULL DEFAULT 0)")
q("CREATE TABLE likes(post_id INTEGER, user_id INTEGER, PRIMARY KEY (post_id, user_id))")
q("INSERT INTO posts(id) VALUES (1)")

def like(post_id, user_id):
    try:
        db.execute("INSERT INTO likes VALUES (?, ?)", (post_id, user_id))           # the primary key rejects a duplicate like
    except Exception:
        db.rollback(); return False
    db.execute("UPDATE posts SET likes = likes + 1 WHERE id = ?", (post_id,))      # the denormalised counter, kept in the same transaction
    db.commit(); return True

assert like(1, 7) and like(1, 8) and not like(1, 7)
assert q("SELECT likes FROM posts") == [(2,)]
assert q("SELECT COUNT(*) FROM likes WHERE post_id = 1") == [(2,)]                   # the counter agrees with the source of truth

4. Modelling patterns

• Soft delete: a deleted_at column instead of removing rows; remember to filter it everywhere and to handle unique constraints (partial unique indexes help).
• Audit and history: an append-only history table, or temporal columns (valid_from, valid_to) when you need "what was true on that date".
• Hierarchies: adjacency list (parent_id, simple, recursive queries to traverse), materialised path (/1/4/9/), nested sets, closure table.
• Polymorphic data: a table per type, a single table with a type column, or JSON for the variable part. Avoid a generic "entity-attribute-value" table unless you accept slow, unvalidated queries.
• Money: store as an integer in the smallest unit (paise) or DECIMAL, never as floating point; store the currency.
• Time: store UTC timestamps with time zone awareness; convert at the edges.
• Enumerations: a lookup table or a check constraint, not free text.

assert 0.1 + 0.2 != 0.3                       # binary floating point cannot represent these exactly
assert 10 + 20 == 30                          # integer paise are exact
from decimal import Decimal
assert Decimal("0.10") + Decimal("0.20") == Decimal("0.30")

A hierarchy with a recursive query

CREATE TABLE category (id INTEGER PRIMARY KEY, name TEXT, parent_id INTEGER REFERENCES category(id));
INSERT INTO category VALUES (1,'Electronics',NULL),(2,'Phones',1),(3,'Android',2),(4,'Laptops',1);

tree = q("""WITH RECURSIVE sub(id, name, depth) AS (
              SELECT id, name, 0 FROM category WHERE id = 1
              UNION ALL
              SELECT c.id, c.name, s.depth + 1 FROM category c JOIN sub s ON c.parent_id = s.id)
            SELECT name, depth FROM sub ORDER BY depth, name""")
assert tree == [("Electronics", 0), ("Laptops", 1), ("Phones", 1), ("Android", 2)]

5. Worked schema: a booking system

Requirements: users book seats for shows; a seat can be booked once per show; payments may fail.

CREATE TABLE shows  (id INTEGER PRIMARY KEY, title TEXT NOT NULL, starts_at TEXT NOT NULL);
CREATE TABLE seats  (id INTEGER PRIMARY KEY, label TEXT NOT NULL);
CREATE TABLE bookings (
  id INTEGER PRIMARY KEY,
  show_id INTEGER NOT NULL REFERENCES shows(id),
  seat_id INTEGER NOT NULL REFERENCES seats(id),
  user_id INTEGER NOT NULL,
  status TEXT NOT NULL CHECK (status IN ('held','confirmed','cancelled')),
  UNIQUE (show_id, seat_id)               -- the database itself prevents a double booking
);
INSERT INTO shows VALUES (1,'Concert','2025-01-01T19:00');
INSERT INTO seats VALUES (1,'A1'),(2,'A2');

db.execute("INSERT INTO bookings(show_id, seat_id, user_id, status) VALUES (1, 1, 100, 'confirmed')")
try:
    db.execute("INSERT INTO bookings(show_id, seat_id, user_id, status) VALUES (1, 1, 200, 'confirmed')")
    raise AssertionError("double booking was allowed")
except Exception as e:
    assert "UNIQUE" in str(e)                          # two users racing for the same seat: one insert fails

The key move: enforce the invariant (one booking per seat per show) with a unique constraint, not with an "is it free?" check in application code that two requests can pass at the same time. A cancelled booking would need either deletion, a partial unique index (WHERE status <> 'cancelled') or a separate history table.

6. NoSQL families

"NoSQL" covers several models. Choose by access pattern.

Modelling in NoSQL: query first

In relational design you model the data, then write queries. In key-value, wide-column and (often) document stores you model the queries, then shape the data to serve them, duplicating data as needed.

Embed or reference (documents): embed when the child belongs to the parent, is read with it and is bounded in size (order lines inside an order); reference when the child is shared, large or unbounded (a user's thousands of posts).

order_doc = {
    "_id": "o-1001",
    "customer": {"id": "c7", "name": "Asha"},                       # a snapshot, copied at order time
    "lines": [{"sku": "A", "qty": 2, "price": 100}, {"sku": "B", "qty": 1, "price": 250}],
    "status": "paid",
}
total = sum(l["qty"] * l["price"] for l in order_doc["lines"])
assert total == 450                                                  # one read returns everything the order page needs

Wide-column partition design: the partition key decides which node stores a row and bounds query efficiency; a clustering key orders rows within a partition. A good key spreads load evenly (avoid hot partitions, such as one key for all today's events) and keeps partition size bounded (add a time bucket to the key).

def partition_key(device_id, ts_seconds):
    return f"{device_id}#{ts_seconds // 86400}"                      # one partition per device per day
assert partition_key("d1", 86400 * 3 + 5) == "d1#3"
assert partition_key("d1", 86400 * 3 + 80000) == "d1#3"
assert partition_key("d1", 86400 * 4) == "d1#4"

7. Consistency and the CAP theorem

In a distributed store, when the network partitions you must choose between consistency (every read sees the latest write, possibly by refusing some requests) and availability (every request gets an answer, possibly stale). Partitions cannot be ruled out, so the real choice is made during a partition. Without a partition, the trade-off is latency versus consistency. The more precise framing is PACELC: if Partition, choose A or C; Else, choose Latency or Consistency.

def quorum_overlaps(n, r, w):
    return r + w > n                              # any read set and write set must intersect
assert quorum_overlaps(3, 2, 2) is True           # the common configuration: survives one node failure and reads see the newest write
assert quorum_overlaps(3, 1, 1) is False         # fast, but a read can miss the latest write
assert quorum_overlaps(5, 3, 3) is True

8. Scaling data: replication, partitioning, sharding

• Replication copies data to several nodes for availability and read scaling. Leader-follower replication sends writes to the leader and replicates asynchronously (replicas may lag, so reads from followers can be stale); synchronous replication costs write latency. Multi-leader and leaderless designs allow writes in several places and need conflict resolution.
• Partitioning (sharding) splits data across nodes by a key. Range partitioning keeps ordering but risks hotspots; hash partitioning spreads evenly but loses range scans; consistent hashing moves little data when nodes join or leave.
• Cross-shard operations (joins, transactions, global unique constraints) become expensive; choose the shard key to keep related data together, and avoid it until a single node truly cannot cope. Vertical scaling, read replicas, caching and archiving come first.

import hashlib

def shard_for(key, n_shards):
    return int(hashlib.md5(key.encode()).hexdigest(), 16) % n_shards

keys = [f"user-{i}" for i in range(10000)]
counts = [0] * 4
for k in keys:
    counts[shard_for(k, 4)] += 1
assert max(counts) - min(counts) < 300                     # a hash spreads keys evenly across shards

# naive modulo resharding moves most keys; this is the problem consistent hashing solves
moved = sum(1 for k in keys if shard_for(k, 4) != shard_for(k, 5))
assert moved > 0.7 * len(keys)

9. Choosing a datastore

1. Start with a relational database (PostgreSQL or MySQL) unless you have a specific reason not to. It gives transactions, constraints, flexible queries and a mature ecosystem, and it scales much further than people expect.
2. Add specialised stores for specific needs: Redis for caching and rate limiting, a search engine for full-text, a time-series store for metrics, object storage for files, a warehouse for analytics.
3. Pick NoSQL for access patterns: a known set of key lookups at huge scale (key-value, wide-column), self-contained aggregates (document), relationship traversal (graph).
4. Do not use polyglot persistence casually. Each extra datastore adds operations, consistency problems and cost.

10. Common mistakes

• Choosing NoSQL "for scale" before any scale problem exists, then reinventing joins and transactions.
• Over-normalising a read-heavy path with no measurement, or denormalising everything with no consistency plan.
• Enforcing invariants only in application code, where concurrent requests break them.
• Floating-point money and local-time timestamps.
• A hot partition key (a sequential ID or a single popular value).
• Unbounded arrays inside documents.
• Ignoring migrations and evolution of the schema.
• Guessing instead of listing access patterns.

11. Practice questions

1. Design a schema for a library: books, copies, members, loans, holds. State the constraints.
2. Explain 1NF, 2NF and 3NF with an example of each violation.
3. When would you denormalise? How do you keep the copy consistent?
4. How do you model a many-to-many relationship with attributes on the relationship?
5. Embed or reference in a document store? Give an example of each.
6. Explain CAP and PACELC. What does $R+W>N$ guarantee?
7. How do you choose a shard key? What goes wrong with a poor one?
8. Pick a datastore for: a shopping cart, a chat history, product search, sensor metrics, a social graph.