Part 2: Normalization & Dependencies

1. What is Normalization & Why Do We Do It?

Normalization organizes tables to minimize redundancy and dependency problems — the goal being to avoid the three anomalies:

• Insertion anomaly: can’t insert a fact because another fact is missing (a customer can’t get a row until they place an order).
• Update anomaly: changing one fact requires updating many rows (a lecturer’s phone number repeated across every course they teach).
• Deletion anomaly: deleting one thing accidentally deletes another (deleting the last course a lecturer teaches deletes the lecturer).

The ladder: 1NF → 2NF → 3NF → BCNF → 4NF. Each step removes one class of problem, at the cost of more joins.

2. Functional Dependencies

A functional dependency X → Y means: given a value of X, there is exactly one value of Y. X is the determinant, Y is dependent.

• Trivial FD: X → Y where Y ⊆ X (e.g. {name, age} → {age}) — always true, tells you nothing.
• Non-trivial FD: Y has at least one attribute not in X — the ones that matter for normalization.
• Full FD: Y depends on the whole X, not a subset — the key concept behind 2NF.
• Transitive FD: X → Y → Z, so X determines Z “through” Y — the key concept behind 3NF.

3. The Normal Forms

• 1NF — every column holds a single atomic value; no repeating groups / no arrays or comma-separated lists.
• 2NF — 1NF + every non-key attribute is fully dependent on the whole primary key. Kills partial dependencies (relevant only for composite keys).
  • Example: Order(OrderID, ProductID, ProductName) — ProductName depends only on ProductID, not the whole key. Split it out.
• 3NF — 2NF + no transitive dependency: a non-key attribute must not depend on another non-key attribute.
  • Example: Employee(EmpID, DeptID, DeptName) — DeptName depends on DeptID, not on EmpID. Split Dept out.
• BCNF — 3NF + every determinant must be a candidate key (stricter than 3NF).
• 4NF — BCNF + no multivalued dependencies (no independent repeating facts in one table). Splits into two tables.

Normal form	Adds over previous	Removes
1NF	Atomic values	Repeating groups
2NF	Full key dependency	Partial dependency
3NF	No transitive dependency	Transitive dependency
BCNF	Every determinant is a key	Non-key determinants
4NF	No multivalued dependency	Independent repetitions

Rule of thumb: every BCNF is 3NF, every 3NF is 2NF, every 2NF is 1NF.

4. Worked Example — BCNF Decomposition

The classic that always appears: R(Student, Subject, Teacher)

FDs: (Student, Subject) → Teacher
     Teacher → Subject          ← Teacher is NOT a super key

A teacher teaches only one subject, so Teacher → Subject, but Teacher isn’t a key. This violates BCNF (yet satisfies 3NF, since Subject is a prime attribute). Redundancy: every student taking that teacher’s subject repeats the subject.

Fix: decompose into R1(Student, Teacher) and R2(Teacher, Subject).

R1: (Student, Teacher)
R2: (Teacher, Subject)

Now every determinant is a key. Lossless — joining R1 and R2 on Teacher recovers the original data. Note: 3NF is sometimes kept because BCNF is not always dependency-preserving.

5. Worked Example — Lossless-Join Decomposition

A decomposition is lossless if joining the parts recovers the original rows exactly (no spurious rows).

Given: R(A, B, C) decomposed into R1(A, B) and R2(B, C).

• Condition for lossless: the shared attribute(s) must be a super key in at least one of the decomposed relations, or R1 ∩ R2 → R1 (or → R2) holds.
• Here B is shared; if B → C (B is a key in R2), the join R1 ⨝ R2 on B reproduces R exactly.

Counter-example (lossy): decomposing R(A,B,C) into R1(A,B) and R2(A,C) when B and C are independent — joining produces spurious rows that never existed.

• Interview answer format: state the candidate keys, check each FD, note which normal form is violated, then split on the violating FD and verify the shared key.

6. Normalization vs. Denormalization (Storage vs. Speed)

• Normalization is ideal for OLTP (transactional systems) — data integrity is the highest priority; you accept more joins.
• Denormalization intentionally reintroduces redundancy by merging tables (or adding precomputed columns) to reduce expensive JOINs.
• Ideal for: OLAP (analytical/reporting systems) where you query massive historical data fast.

OLTP vs OLAP (quick sheet):

	OLTP	OLAP
Purpose	Daily transactions	Analytics / reporting
Workload	Many small writes	Large reads
Normalization	Normalized	Denormalized (star schema)
Users	Customers	Analysts