25 — Normalization & Data Modeling

-- Consider this unnormalized table (customer data stored with each order):
-- orders: order_id | customer_name | customer_city | amount
--         1        | Alice         | NYC            | 100
--         2        | Alice         | NYC            | 200
--         3        | Alice         | Boston         | 150   ← Alice moved, 2 rows stale

-- UPDATE ANOMALY: updating Alice's city in 2 of 3 rows → which is correct?
--   You must update ALL rows for Alice. Miss one → inconsistent data.
--   "How many rows do I need to update?" is the wrong question — the fact
--   should be in ONE place, so one update suffices.

-- INSERTION ANOMALY: can't insert a new customer until they place an order.
--   No order → no row → no customer record. Customer data is hostage to
--   having an order.

-- DELETION ANOMALY: deleting Alice's last order deletes Alice.
--   If Alice has one order and you delete it, the row is gone → Alice's
--   customer data is lost. Deleting one fact (the order) inadvertently
--   deletes another (the customer).

-- Normalization fixes all three: customer data in a `customers` table
-- (one row per customer), orders in an `orders` table (FK to customers).
-- One update to customers.city. Insert a customer without an order.
-- Delete an order without losing the customer.

-- ❌ Not 1NF: items column holds a comma-separated list
CREATE TABLE bad_orders (
  id SERIAL PRIMARY KEY,
  customer TEXT,
  items TEXT                           -- 'apple, banana, cherry' — one cell, multiple values
);
-- Can't index items for "which orders contain apple?" (LIKE '%apple%' →
-- full scan, false positives on 'pineapple'). Can't enforce integrity.
-- Can't add metadata (quantity, price per item).

-- ✅ 1NF: one row per item (normalize into a child table)
CREATE TABLE orders (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  customer TEXT NOT NULL
);
CREATE TABLE order_items (
  order_id BIGINT NOT NULL REFERENCES orders(id) ON DELETE CASCADE,
  item TEXT NOT NULL,
  quantity INTEGER NOT NULL DEFAULT 1,
  PRIMARY KEY (order_id, item)
);
-- Each cell is atomic. Can index item, enforce quantity > 0, add price.

-- ❌ Not 2NF: PK is (order_id, product_id), but product_name depends
-- only on product_id (not on order_id). If product 5's name changes,
-- you must update every order_items row for product 5.
CREATE TABLE bad_order_items (
  order_id BIGINT NOT NULL,
  product_id BIGINT NOT NULL,
  product_name TEXT NOT NULL,          -- depends on product_id ONLY, not order_id
  quantity INTEGER NOT NULL,
  PRIMARY KEY (order_id, product_id)
);
-- product_name is duplicated across all orders containing product 5.
-- Rename "Apple" to "Apple Inc." → update N rows. Miss one → inconsistency.

-- ✅ 2NF: move product_name to the products table
CREATE TABLE products (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  name TEXT NOT NULL                   -- depends on product_id (the PK of products)
);
CREATE TABLE order_items (
  order_id BIGINT NOT NULL REFERENCES orders(id),
  product_id BIGINT NOT NULL REFERENCES products(id),
  quantity INTEGER NOT NULL,
  PRIMARY KEY (order_id, product_id)   -- quantity depends on BOTH (which order, which product)
);
-- product_name lives in products (one place). Rename → one update.
-- quantity lives in order_items (depends on the full composite key).

-- ❌ Not 3NF: zip_code determines city, but city isn't the PK.
-- zip_code → city is a transitive dependency (id → zip_code → city).
CREATE TABLE bad_customers (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  name TEXT NOT NULL,
  zip_code TEXT NOT NULL,
  city TEXT NOT NULL                    -- derivable from zip_code, not from id directly
);
-- If zip_code 10001 maps to NYC, every customer with zip 10001 has city=NYC.
-- Duplicated. If the mapping changes (zip boundary redraw), update every row.

-- ✅ 3NF: zip → city in a separate table
CREATE TABLE zip_codes (
  zip TEXT PRIMARY KEY,
  city TEXT NOT NULL,
  state TEXT NOT NULL
);
CREATE TABLE customers (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  name TEXT NOT NULL,
  zip_code TEXT NOT NULL REFERENCES zip_codes(zip)
);
-- city lives in zip_codes (one place per zip). Join to get the city.
-- "The key, the whole key, and nothing but the key" — city depends on
-- the key (zip) of zip_codes, not on customers.id.

-- BCNF matters when you have overlapping candidate keys.
-- Example: a table of (student, course, instructor) where:
--   - Each course has one instructor
--   - Each instructor teaches one course
--   - A student can take multiple courses
-- Candidate keys: (student, course) and (student, instructor)
-- Dependencies: course → instructor AND instructor → course
-- This is 3NF (no transitive dependency on a non-key) but NOT BCNF
-- (course is a determinant but not a superkey in the (student, course) key).
-- Fix: split into (student, course) and (course, instructor).

-- In practice, BCNF violations are rare — most schemas that hit 3NF
-- are already BCNF. The difference matters in academic cases with
-- overlapping candidate keys.

-- Surrogate key: artificial, stable, simple. The default for most tables.
CREATE TABLE customers (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,  -- surrogate: no business meaning
  email TEXT NOT NULL UNIQUE                           -- natural key as a unique constraint
);
-- Pros: never changes, simple joins (single bigint), no cascade issues.
-- Cons: no business meaning (can't tell anything from id=42).

-- Natural key: meaningful, derived from the domain.
CREATE TABLE countries (
  iso_code CHAR(2) PRIMARY KEY,         -- 'US', 'GB', 'JP' — natural, stable, meaningful
  name TEXT NOT NULL
);
-- Pros: meaningful, no extra column, self-documenting.
-- Cons: mutable (email rename → cascade to every FK), may not be truly unique.

-- Rule of thumb:
-- - Use surrogate keys by default (BIGINT IDENTITY or UUID).
-- - Use natural keys only for genuinely stable, unique identifiers (country codes, ISBN).
-- - Keep natural keys as UNIQUE constraints, not PKs, if they might change.
-- - The PK choice affects every FK that references it — changing a PK type
--   is a massive migration. Choose wisely up front.

-- ── NORMALIZED (3NF) — for the transactional (OLTP) system ──────

-- users: one row per user. 1NF (atomic), 2NF (single-column PK, N/A),
-- 3NF (all columns depend on user id alone).
CREATE TABLE users (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  email TEXT NOT NULL UNIQUE,           -- natural key as unique constraint (not PK)
  name TEXT NOT NULL,
  created_at TIMESTAMPTZ NOT NULL DEFAULT now()
);

-- addresses: one user can have multiple addresses (1:N).
-- Separate table (not columns on users) because it's multi-valued (1NF).
-- zip_id FK to zip_codes (3NF: city derivable from zip, not stored here).
CREATE TABLE addresses (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  user_id BIGINT NOT NULL REFERENCES users(id) ON DELETE CASCADE,
  line1 TEXT NOT NULL,
  line2 TEXT,
  zip_id TEXT NOT NULL REFERENCES zip_codes(zip),
  label TEXT NOT NULL DEFAULT 'home',   -- 'home', 'work', 'shipping'
  created_at TIMESTAMPTZ NOT NULL DEFAULT now()
);

-- zip_codes: the 3NF fix — city/state derivable from zip, stored once.
CREATE TABLE zip_codes (
  zip TEXT PRIMARY KEY,
  city TEXT NOT NULL,
  state TEXT NOT NULL,
  country TEXT NOT NULL DEFAULT 'US'
);

-- categories: self-referencing for hierarchy (adjacency list).
-- parent_id is NULL for root categories.
CREATE TABLE categories (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  parent_id BIGINT REFERENCES categories(id) ON DELETE SET NULL,
  name TEXT NOT NULL,
  slug TEXT NOT NULL UNIQUE
);

-- products: name/price depend on product id (3NF).
-- category_id FK (not storing category name here — 2NF/3NF).
CREATE TABLE products (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  category_id BIGINT NOT NULL REFERENCES categories(id),
  name TEXT NOT NULL,
  price NUMERIC(10,2) NOT NULL CHECK (price >= 0),
  sku TEXT NOT NULL UNIQUE,
  created_at TIMESTAMPTZ NOT NULL DEFAULT now()
);

-- products_to_categories: many-to-many (a product can be in multiple categories).
-- Junction table with composite PK (no duplicate pairs).
CREATE TABLE products_to_categories (
  product_id BIGINT NOT NULL REFERENCES products(id) ON DELETE CASCADE,
  category_id BIGINT NOT NULL REFERENCES categories(id) ON DELETE CASCADE,
  PRIMARY KEY (product_id, category_id)
);

-- orders: one row per order. FK to user (not storing user name/email — 3NF).
-- shipping_address_id FK (not copying address fields — 3NF).
CREATE TABLE orders (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  user_id BIGINT NOT NULL REFERENCES users(id),
  shipping_address_id BIGINT NOT NULL REFERENCES addresses(id),
  status TEXT NOT NULL DEFAULT 'pending'
    CHECK (status IN ('pending','paid','shipped','delivered','cancelled')),
  total NUMERIC(10,2) NOT NULL CHECK (total >= 0),
  created_at TIMESTAMPTZ NOT NULL DEFAULT now()
);

-- order_items: the line items. Composite-relevant: quantity depends on
-- (order_id, product_id) — the whole composite key (2NF).
-- product_name is NOT here (it's in products — 2NF fix).
-- unit_price IS here (a snapshot of the price at order time — not a
-- 3NF violation because the current product.price may change, but the
-- historical order price shouldn't. This is a deliberate denormalization
-- for historical accuracy).
CREATE TABLE order_items (
  order_id BIGINT NOT NULL REFERENCES orders(id) ON DELETE CASCADE,
  product_id BIGINT NOT NULL REFERENCES products(id),
  quantity INTEGER NOT NULL CHECK (quantity > 0),
  unit_price NUMERIC(10,2) NOT NULL CHECK (unit_price >= 0),  -- price snapshot
  PRIMARY KEY (order_id, product_id)
);
-- The unit_price snapshot is a common pattern: store the price AT THE TIME
-- of the order, not a FK to a changing products.price. This is deliberate,
-- documented denormalization (historical accuracy > normalization purity).

-- ── DENORMALIZED (Star Schema) — for the analytics/OLAP system ──
-- The transactional schema is normalized (good for writes, integrity).
-- The analytics schema is denormalized (good for reads, aggregations).
-- They are SEPARATE databases (or schemas). Don't mix OLTP and OLAP
-- in the same schema — they have different access patterns.

-- Fact table: one row per order item (grain = line item).
-- Contains FKs to dimension tables + measures (quantity, amount).
CREATE TABLE fact_order_items (
  order_item_id BIGINT PRIMARY KEY,
  order_id BIGINT NOT NULL,
  order_date DATE NOT NULL,             -- denormalized from orders.created_at
  user_id BIGINT NOT NULL,
  user_email TEXT,                      -- denormalized from users (for grouping)
  user_city TEXT,                       -- denormalized from zip_codes via addresses
  product_id BIGINT NOT NULL,
  product_name TEXT,                    -- denormalized from products
  category_name TEXT,                   -- denormalized from categories
  category_parent_name TEXT,            -- denormalized (hierarchy flattened)
  quantity INTEGER NOT NULL,
  unit_price NUMERIC(10,2) NOT NULL,
  amount NUMERIC(10,2) NOT NULL,        -- quantity * unit_price (precomputed)
  order_status TEXT NOT NULL
);

-- Dimension tables (smaller, denormalized, for filtering/grouping):
CREATE TABLE dim_users (
  user_id BIGINT PRIMARY KEY,
  email TEXT,
  city TEXT,
  state TEXT,
  first_order_date DATE,
  total_orders INTEGER,
  total_spent NUMERIC(10,2)
);

CREATE TABLE dim_products (
  product_id BIGINT PRIMARY KEY,
  product_name TEXT,
  category_name TEXT,
  category_path TEXT,                   -- 'electronics > phones > accessories'
  current_price NUMERIC(10,2)
);

CREATE TABLE dim_dates (
  date DATE PRIMARY KEY,
  year INTEGER, month INTEGER, quarter INTEGER,
  day_of_week TEXT, is_weekend BOOLEAN,
  is_holiday BOOLEAN, holiday_name TEXT
);

-- Analytics query: total sales by city for Q3 2026 — ONE join, fast.
SELECT u.city, sum(f.amount) AS total
FROM fact_order_items f
JOIN dim_dates d ON d.date = f.order_date
JOIN dim_users u ON u.user_id = f.user_id
WHERE d.quarter = 3 AND d.year = 2026
GROUP BY u.city ORDER BY total DESC;
-- In the normalized schema, this would need 5+ joins (orders → users →
-- addresses → zip_codes, + order_items → products → categories). The
-- star schema pre-joins into the fact table for read performance.

-- Dimension data changes over time (a user moves cities, a product is
-- reclassified). How do you track history in the analytics schema?

-- SCD Type 1: overwrite (no history). Simple, loses the old value.
UPDATE dim_users SET city = 'Boston' WHERE user_id = 42;
-- Lost: the fact that user 42 used to live in NYC.

-- SCD Type 2: track history with validity dates (the standard approach).
CREATE TABLE dim_users_scd2 (
  user_sk BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,  -- surrogate key (not user_id)
  user_id BIGINT NOT NULL,                  -- natural key (business key)
  email TEXT,
  city TEXT,
  valid_from TIMESTAMPTZ NOT NULL DEFAULT now(),
  valid_to TIMESTAMPTZ,                     -- NULL = current version
  is_current BOOLEAN NOT NULL DEFAULT true
);
-- When user 42 moves from NYC to Boston:
UPDATE dim_users_scd2 SET valid_to = now(), is_current = false
WHERE user_id = 42 AND is_current;         -- close the old version
INSERT INTO dim_users_scd2 (user_id, email, city)
VALUES (42, 'alice@example.com', 'Boston'); -- open a new version
-- Fact table records use user_sk (the surrogate) so each fact points to
-- the correct version of the user at the time of the event.
-- Query "where did user 42 live when they placed order X?":
-- JOIN fact_order_items f ON f.user_sk = u.user_sk (point-in-time join).

-- Denormalize ONLY when you have a measured performance problem.
-- Each denormalization adds a consistency burden (how do you keep it in sync?).

-- 1. Precomputed aggregates (materialized views or trigger-maintained columns)
CREATE MATERIALIZED VIEW daily_sales AS
  SELECT date_trunc('day', created_at)::date AS sale_date,
         count(*) AS order_count,
         sum(total) AS revenue
  FROM orders GROUP BY 1;
-- Refresh periodically: REFRESH MATERIALIZED VIEW daily_sales;
-- Or use a trigger-maintained counter column on customers (order_count).

-- 2. Duplicate columns (with a sync mechanism)
ALTER TABLE orders ADD COLUMN customer_name TEXT;  -- denormalized from users
-- Sync via trigger (see chapter 21) or application code.
-- Cost: if users.name changes, orders.customer_name is stale until synced.

-- 3. JSONB for variable structure (deliberate denormalization)
CREATE TABLE products (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  name TEXT NOT NULL,
  attributes JSONB NOT NULL DEFAULT '{}'  -- variable key-value pairs
);
-- Better than EAV (see anti-patterns). Indexable with GIN, queryable with ->>.
CREATE INDEX products_attrs_idx ON products USING GIN (attributes);

-- 4. Summary tables (scheduled refresh)
CREATE TABLE monthly_revenue (
  month DATE PRIMARY KEY,
  revenue NUMERIC NOT NULL,
  updated_at TIMESTAMPTZ NOT NULL DEFAULT now()
);
-- Updated by a nightly job: INSERT ... ON CONFLICT (month) DO UPDATE ...

-- ❌ WRONG: denormalizing before you have a performance problem.
-- "Let's copy customer_name into orders to avoid a join" — before
-- measuring whether the join is actually slow.
-- Costs:
-- 1. Consistency burden: a trigger or app code must sync customer_name.
-- 2. Storage: duplicated data.
-- 3. Complexity: two sources of truth for the same fact.
-- 4. The join might be fast (indexed FK, small table) — the denormalization
--    added complexity for zero gain.

-- ✅ RIGHT: normalize first. Denormalize ONLY when you have a MEASURED
-- performance problem (EXPLAIN shows a slow join, profiling shows it's
-- the bottleneck). Then denormalize with a consistency mechanism.
-- Most "joins are slow" fears are unfounded — indexed FKs on small-ish
-- dimension tables are fast. Measure, don't guess.

-- ❌ WRONG: EAV — a "flexible" properties table
CREATE TABLE product_attributes (
  product_id BIGINT REFERENCES products(id),
  attribute_name TEXT,           -- 'color', 'weight', 'screen_size'
  attribute_value TEXT           -- 'red', '1.5kg', '15"'
);
-- Querying "all red products weighing < 2kg" requires 3+ self-joins:
SELECT p.* FROM products p
JOIN product_attributes a1 ON a1.product_id = p.id AND a1.attribute_name = 'color' AND a1.attribute_value = 'red'
JOIN product_attributes a2 ON a2.product_id = p.id AND a2.attribute_name = 'weight' AND a2.attribute_value::numeric < 2;
-- Problems: no typing (everything is TEXT), no indexes (can't index by
-- attribute_name+value efficiently), query complexity explodes, no
-- integrity (typos: 'Color' vs 'color'), can't enforce NOT NULL on
-- a specific attribute.

-- ✅ RIGHT: use JSONB for variable attributes (typed, indexable, queryable)
CREATE TABLE products (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  name TEXT NOT NULL,
  attributes JSONB NOT NULL DEFAULT '{}'
  -- {"color": "red", "weight_kg": 1.5, "screen_size": 15}
);
CREATE INDEX products_attrs_idx ON products USING GIN (attributes);
-- Query: all red products < 2kg
SELECT * FROM products
WHERE attributes->>'color' = 'red'
  AND (attributes->>'weight_kg')::numeric < 2;
-- Indexable (GIN), typed at query time, no self-joins. If attributes are
-- well-known and fixed, use real columns instead of JSONB (fully typed,
-- indexable by default, constraint-checkable).

-- ❌ WRONG: polymorphic association — commentable_type + commentable_id
CREATE TABLE comments (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  body TEXT NOT NULL,
  commentable_type TEXT NOT NULL,   -- 'post' or 'video' or 'product'
  commentable_id BIGINT NOT NULL    -- FK to... which table?
);
-- No FK possible — commentable_id could reference posts, videos, or products.
-- Referential integrity is NOT enforced. A deleted post leaves dangling comments.
-- Queries need dynamic SQL or CASE to join the right table.

-- ✅ RIGHT: separate tables per type, or nullable FKs with a CHECK constraint
-- Option 1: separate comment tables (simple, clear)
CREATE TABLE post_comments (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  post_id BIGINT NOT NULL REFERENCES posts(id) ON DELETE CASCADE,
  body TEXT NOT NULL
);

-- Option 2: nullable FKs with a CHECK (exactly one non-NULL)
CREATE TABLE comments (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  body TEXT NOT NULL,
  post_id BIGINT REFERENCES posts(id) ON DELETE CASCADE,
  video_id BIGINT REFERENCES videos(id) ON DELETE CASCADE,
  product_id BIGINT REFERENCES products(id) ON DELETE CASCADE,
  CHECK (num_nonnull(post_id, video_id, product_id) = 1)  -- exactly one target
);
-- FKs enforce integrity. CHECK ensures exactly one. No polymorphic magic.

-- One-to-Many: FK on the "many" side
CREATE TABLE customers (id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY, name TEXT);
CREATE TABLE orders (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  customer_id BIGINT NOT NULL REFERENCES customers(id),  -- FK on the many side
  amount NUMERIC NOT NULL
);

-- One-to-One: FK that's also the PK (UNIQUE + NOT NULL)
CREATE TABLE users (id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY, email TEXT UNIQUE);
CREATE TABLE user_profiles (
  user_id BIGINT PRIMARY KEY REFERENCES users(id),  -- PK → UNIQUE + NOT NULL → 1:1
  bio TEXT,
  avatar_url TEXT
);
-- Use 1:1 to: split wide tables, isolate sensitive columns (passwords),
-- model optional subclassing (users + admins).

-- Many-to-Many: junction table with composite PK
CREATE TABLE students (id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY, name TEXT);
CREATE TABLE courses  (id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY, title TEXT);
CREATE TABLE enrollments (
  student_id BIGINT NOT NULL REFERENCES students(id) ON DELETE CASCADE,
  course_id  BIGINT NOT NULL REFERENCES courses(id) ON DELETE CASCADE,
  enrolled_at TIMESTAMPTZ NOT NULL DEFAULT now(),
  grade TEXT,
  PRIMARY KEY (student_id, course_id)  -- prevents duplicate (student, course) pairs
);
-- The junction table can carry relationship attributes (enrolled_at, grade).

-- Adjacency list: each row has parent_id. Simple to maintain, query
-- subtrees with a recursive CTE (chapter 19).
CREATE TABLE categories (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  parent_id BIGINT REFERENCES categories(id),  -- NULL = root
  name TEXT NOT NULL
);
CREATE INDEX categories_parent_idx ON categories(parent_id);

-- Recursive CTE to get a subtree:
WITH RECURSIVE subtree AS (
  SELECT id, name, parent_id, 0 AS depth
  FROM categories WHERE id = 1                  -- start node
  UNION ALL
  SELECT c.id, c.name, c.parent_id, s.depth + 1
  FROM categories c
  JOIN subtree s ON c.parent_id = s.id          -- recurse up the tree
)
SELECT * FROM subtree ORDER BY depth, name;
-- Other options: path enumeration (/1/4/7/), nested sets (lft/rgt),
-- materialized path (ARRAY[1,4,7]). Adjacency list + recursive CTE
-- is the simplest and most flexible for most use cases.

CREATE TABLE products (
  id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  name TEXT NOT NULL,
  categories TEXT NOT NULL   -- 'electronics,tech,accessories'
);