Normalization — 1NF, 2NF, 3NF, BCNF — anomalies each resolves: Exercises

Before we start, one shared vocabulary reminder — every problem below leans on these, so pin them down:

Definition The words you must never confuse

A functional dependency $X \to A$ means "same $X$ forces same $A$ ". See Functional Dependencies.
A candidate key is a minimal set of columns that determines every other column. See Candidate Keys and Superkeys.
A superkey is any set that determines everything (a candidate key plus optional extra columns). Every candidate key is a superkey; not every superkey is minimal.
A prime attribute is an attribute that appears in at least one candidate key. If it appears in no candidate key, it is non-prime. (This distinction is the whole point of 2NF and 3NF, so learn it now.)
An FD $X \to A$ is trivial when $A$ is already inside $X$ (e.g. ${A, B} \to A$ ) — it says nothing new and is never a violation of anything. An FD is non-trivial when $A$ is not fully contained in $X$ . All the "offending" FDs below are non-trivial ones.

Figure — Normalization — 1NF, 2NF, 3NF, BCNF — anomalies each resolves

Level 1 — Recognition

Goal: name the form / spot the violation by inspection.

Problem 1.1 (L1)

A table cell contains Skills = "Java; SQL; Python". Which normal form is violated, and why?

Recall Solution 1.1

WHAT: The cell holds a list, not a single value. WHICH form: 1NF is violated (atomicity). This is step 1 of the map figure — before any FD reasoning, cells must be atomic. WHY it hurts: you cannot ask "who knows SQL?" without string-searching, cannot index the skill, cannot delete just one skill. Fix: EmpSkill(EmpID, Skill) — one skill per row.

Problem 1.2 (L1)

Enroll(StudentID, CourseID, Grade, StudentName) with candidate key {StudentID, CourseID}. The FD StudentID → StudentName exists. Name the type of dependency and the highest form the table already satisfies.

Recall Solution 1.2

StudentID is a proper subset of the key {StudentID, CourseID}. StudentName appears in no candidate key, so it is non-prime. So StudentID → StudentName is a partial dependency. The table is in 1NF (all values atomic) but not 2NF. Highest form satisfied = 1NF.

Problem 1.3 (L1)

Match each label to its offending FD pattern (determinant $X$ , dependent $A$ ): (a) partial · (b) transitive · (c) BCNF violation.

Recall Solution 1.3

First, a precondition for all three: the FD $X \to A$ must be non-trivial ( $A$ not already inside $X$ ). A trivial FD like ${A, B} \to A$ violates nothing — no normal form ever forbids it — so we only ever classify non-trivial FDs.

(a) partial: $X$ is a proper part of a candidate key, and $A$ is non-prime (appears in no candidate key).
(b) transitive: the structure is a chain $key \to X \to A$ where the middle attribute $X$ is itself non-prime (not a superkey) and $A$ is also non-prime. The key reaches $A$ only through the non-key middleman $X$ — that indirect, two-hop route is exactly what "transitive" means (as in "if key→X and X→A then key→A"). Because $A$ really depends on $X$ , not on the key directly, $A$ gets duplicated once per repeated $X$ -value.
(c) BCNF violation: the FD is non-trivial and $X$ is not a superkey — full stop, even if $A$ is prime. (Trivial FDs never count, which is why ${A, B} \to A$ is fine even though ${A, B}$ might not be a superkey.)

Level 2 — Application

Goal: given FDs, decompose to the requested form.

Problem 2.1 (L2)

Emp(EmpID, DeptID, DeptCity), key = EmpID, FDs EmpID → DeptID and DeptID → DeptCity. Decompose to 3NF.

Recall Solution 2.1

WHAT: EmpID → DeptID → DeptCity, so EmpID → DeptCity holds through the non-key middleman DeptID → a transitive dependency (the key reaches DeptCity only via the non-prime middle attribute DeptID). WHY split: DeptCity repeats for every employee of a department (update anomaly); the last employee leaving deletes the city (delete anomaly). Decomposition: Emp(EmpID, DeptID) + Dept(DeptID, DeptCity). Check lossless (see Decomposition — Lossless Join and Dependency Preservation): the shared column DeptID is a key of Dept, so the join reconstructs the original — lossless. ✔

Problem 2.2 (L2)

Enroll(StudentID, CourseID, Grade, StudentName, CourseName), key {StudentID, CourseID}, FDs StudentID → StudentName, CourseID → CourseName. Decompose to 2NF and verify the decomposition is lossless and dependency-preserving.

Recall Solution 2.2

WHAT: two partial dependencies — each non-prime attribute hangs off half the key. Split each partial FD into its own table:

Student(StudentID, StudentName)
Course(CourseID, CourseName)
Enroll(StudentID, CourseID, Grade) WHY three tables: StudentName now stored once per student, CourseName once per course; Enroll keeps only what genuinely needs both halves of the key (the grade). Lossless-join check (see Decomposition — Lossless Join and Dependency Preservation): re-join Enroll with Student on the shared column StudentID; that column is the key of Student, so each Enroll row matches exactly one Student row — no spurious rows. Re-join the result with Course on CourseID, again the key of Course. Since each pairwise join is on a key of one side, the whole reconstruction is lossless. ✔ Dependency-preservation check: StudentID → StudentName lives entirely inside Student ✔; CourseID → CourseName lives entirely inside Course ✔; the key FD {StudentID, CourseID} → Grade lives inside Enroll ✔. Every original FD sits inside some single table, so all constraints are still locally enforceable → dependency-preserving. ✔

Problem 2.3 (L2)

Is Product(SKU, Price) with key SKU already in 3NF? Justify.

Recall Solution 2.3

Single-column key → no proper subset exists → cannot have a partial dependency → automatically 2NF. Only FD is SKU → Price; SKU is the key (a superkey), so no transitive dependency either → 3NF. In fact also BCNF.

Level 3 — Analysis

Goal: find the candidate keys yourself, then classify the highest form.

Problem 3.1 (L3)

R(A, B, C, D) with FDs AB → C, C → D, D → A. Find all candidate keys and the highest normal form.

Recall Solution 3.1

This is step 2 (find keys) and step 3 (test each determinant) of the map figure, done with closures. Note first: B never appears on any FD's right side, so B can be produced by nothing — every candidate key must contain B. We only need to test sets containing B. Superkey {A,B}: $A B^{+}$ : AB → C, then C → D, then D → A ⇒ ${A, B, C, D}$ = all → superkey. Is {A,B} minimal? Drop A: $B^{+} = {B}$ (no FD has left side inside ${B}$ ) → misses everything → fails. Drop B: $A^{+} = {A}$ (no FD fires on ${A}$ alone) → fails. Both proper subsets fail → {A,B} is a candidate key (minimal). ✔ Superkey {B,C}: $B C^{+}$ : C → D, D → A, then having A,B fires AB → C (already have C) ⇒ ${B, C, D, A}$ = all → superkey. Minimal? Drop C: $B^{+} = {B}$ fails. Drop B: $C^{+} = {C, D, A}$ misses B (again, B is unproducible) → fails. → {B,C} is a candidate key. ✔ Superkey {B,D}: $B D^{+}$ : D → A, then A,B fire AB → C, then C → D (have it) ⇒ ${B, D, A, C}$ = all → superkey. Minimal? Drop D: $B^{+} = {B}$ fails. Drop B: $D^{+} = {D, A}$ misses B,C → fails. → {B,D} is a candidate key. ✔ Any others? All candidate keys contain B plus one attribute that (with B) reaches everything; A, C, D each work, and no single-attribute set works (each misses B). So the candidate keys are exactly {A,B}, {B,C}, {B,D}. Prime attributes (appear in some candidate key): A✔ B✔ C✔ D✔ — all four are prime. Highest form: Since every attribute is prime, no FD has a non-prime dependent → every FD satisfies 3NF. BCNF? C → D (non-trivial): is C a superkey? $C^{+} = {C, D, A}$ , missing B → not a superkey → violates BCNF. Highest form = 3NF, not BCNF.

Problem 3.2 (L3)

Teach(Student, Subject, Teacher): {Student, Subject} → Teacher and Teacher → Subject. List candidate keys, prime attributes, and prove it is in 3NF but not BCNF.

Recall Solution 3.2

Superkey {Student, Subject}: ${S t u d e n t, S u bj ec t}^{+}$ : {Student,Subject} → Teacher ⇒ all three → superkey. Minimal? Drop Subject: $S t u d e n t^{+} = {S t u d e n t}$ (no FD fires on Student alone — every FD's left side needs Subject or Teacher) → fails. Drop Student: $S u bj ec t^{+} = {S u bj ec t}$ (no FD fires on Subject alone) → fails. Both proper subsets fail → candidate key. ✔ Superkey {Student, Teacher}: ${S t u d e n t, T e a c h er}^{+}$ : Teacher → Subject, now we hold {Student, Subject, Teacher} = all → superkey. Minimal? Drop Teacher: $S t u d e n t^{+} = {S t u d e n t}$ → fails. Drop Student: $T e a c h e r^{+} = {T e a c h er, S u bj ec t}$ misses Student (nothing produces Student) → fails. Both fail → candidate key. ✔ Note Student is unproducible (never a right-hand side), so it must be in every key — that is why no key omits it, and why there are exactly these two candidate keys: {Student, Subject} and {Student, Teacher}. Prime attributes: Student, Subject, Teacher each appear in some candidate key → all three prime; none is non-prime. 3NF check of Teacher → Subject (non-trivial): Teacher is not a superkey ( $T e a c h e r^{+} = {T e a c h er, S u bj ec t}$ , missing Student), but Subject is prime → the 3NF escape hatch ("or $A$ is prime") is satisfied → 3NF holds. ✔ BCNF check of Teacher → Subject: Teacher is not a superkey, and BCNF has no prime exception → BCNF fails. ✔ Anomaly it causes: you cannot record "Teacher X teaches Subject Y" until some student enrolls (insert anomaly). Fix: TeacherSubject(Teacher, Subject) + StudentTeacher(Student, Teacher).

Level 4 — Synthesis

Goal: decompose fully, then judge lossless-join and dependency-preservation trade-offs.

Problem 4.1 (L4)

Take Teach(Student, Subject, Teacher) from 3.2. Decompose to BCNF. Is the decomposition lossless? Is it dependency-preserving? If not, what is lost?

Recall Solution 4.1

BCNF decomposition: the offending FD is Teacher → Subject. Split on it:

R1(Teacher, Subject) (holds Teacher → Subject)
R2(Student, Teacher) Lossless? Shared column Teacher is a key of R1 — its closure within R1 is ${T e a c h er}^{+} = {T e a c h er, S u bj ec t}$ = all of R1. The lossless rule: the common attributes must be a key of at least one piece — satisfied → lossless. ✔ Dependency-preserving? Original FDs: Teacher → Subject (lives in R1 ✔) and {Student, Subject} → Teacher. The second FD spans Student (in R2) and Subject (in R1) — no single table holds both → it is NOT preserved in either piece. What is lost: you can no longer enforce "(Student, Subject) determines a unique Teacher" with a local key/constraint; a student could appear paired with two teachers of the same subject and no single table would catch it. Conclusion: classic BCNF trade-off — we gained BCNF (no bad FD) but sacrificed dependency preservation. Sometimes staying at 3NF is the correct engineering choice. See Decomposition — Lossless Join and Dependency Preservation.

Problem 4.2 (L4)

Sales(OrderID, ProductID, Qty, ProductName, UnitPrice), key {OrderID, ProductID}, FDs {OrderID, ProductID} → Qty, ProductID → ProductName, ProductID → UnitPrice. Fully normalize to BCNF and count the resulting tables.

Recall Solution 4.2

Step 1 — 1NF: all values atomic ✔. Step 2 — 2NF: ProductID → ProductName and ProductID → UnitPrice are partial (ProductID is half the key, and ProductName/UnitPrice are non-prime — they appear in no candidate key). Split:

Product(ProductID, ProductName, UnitPrice)
Sales(OrderID, ProductID, Qty) Step 3 — 3NF: In Product, only determinant is ProductID (the key) → no transitive dependency. In Sales, only FD is the full key → clean. Already 3NF. Step 4 — BCNF: every determinant (ProductID in Product, {OrderID, ProductID} in Sales) is a superkey of its table → BCNF. ✔ Result: 2 tables, both BCNF, decomposition lossless (shared ProductID is key of Product) and dependency-preserving (all three FDs recoverable). A clean case where BCNF costs nothing.

Level 5 — Mastery

Goal: reason about the whole design, edge cases, and trade-offs end to end.

Problem 5.1 (L5)

R(A, B, C) with FDs A → B and B → A and B → C. Determine all candidate keys, and the highest normal form. Then decide: is BCNF decomposition even needed, and would it preserve dependencies?

Recall Solution 5.1

Keys (via closure, with minimality): $A^{+} = {A, B, C}$ (via A→B, B→C) = all → A is a single-attribute superkey, so it is trivially minimal → candidate key {A}. $B^{+} = {B, A, C}$ (via B→A, B→C) = all → single attribute, minimal → candidate key {B}. $C^{+} = {C}$ (no FD fires on C) → C is not even a superkey, so no key involves only C. So candidate keys = {A} and {B}. Prime = {A, B}; non-prime = {C}. BCNF check — every non-trivial FD's left side must be a superkey: A → B (A is a key ✔), B → A (B is a key ✔), B → C (B is a key ✔). Every determinant is a superkey → already BCNF. Decomposition needed? No — it is BCNF as-is. Being BCNF, it's automatically 3NF/2NF/1NF. Nothing to split, nothing to lose; dependency preservation is trivially intact (all FDs stay in the single table). Lesson: having two candidate keys is fine; BCNF only cares that each determinant is some superkey, not that there's exactly one key.

Problem 5.2 (L5)

A junior dev proposes decomposing every table until each has exactly two columns "to be maximally normalized." Give a rigorous critique: name (a) a correctness risk and (b) a performance risk, referencing the correct vault concepts, and state the recommended stopping point.

Recall Solution 5.2

(a) Correctness risk — lost dependency preservation & lossy joins. Splitting blindly can (i) break FDs so no single table can enforce a business rule (exactly what happened in 4.1, where {Student, Subject} → Teacher became unenforceable), and (ii) produce a lossy decomposition where re-joining invents spurious rows if the shared columns are not a key of at least one piece. Over-splitting therefore increases, not decreases, the risk of silent data corruption. See Decomposition — Lossless Join and Dependency Preservation. (b) Performance risk — join explosion. Every query that needs several facts together must now JOIN many tiny tables. Reads slow down, index maintenance multiplies (see Indexes and Joins), and the query planner faces exponentially more join orderings to consider. This is precisely the situation where engineers apply Denormalization for Performance — deliberately storing controlled redundancy to speed up read-heavy paths. Recommended stopping point: target 3NF as the default sweet-spot (it removes partial and transitive anomalies while almost always staying lossless and dependency-preserving); advance to BCNF only when the decomposition remains both lossless and dependency-preserving; and denormalize consciously and locally where profiling proves a read path needs it. "Normalize to death" is an anti-pattern, not a virtue.

Problem 5.3 (L5)

Degenerate/edge check: A relation R(A) with a single column. Which normal forms does it satisfy? Justify each.

Recall Solution 5.3

1NF: if the single value is atomic (one value, no list) → ✔.
2NF: key is {A} (single column) → no proper subset → no partial dependency possible → ✔.
3NF: the only possible FD is the trivial A → A; no non-prime attribute exists to depend transitively → ✔.
BCNF: BCNF only constrains non-trivial FDs, and the single-column relation has none (the only FD A → A is trivial) → vacuously ✔. Conclusion: a single-attribute relation is in BCNF (hence all lower forms). Degenerate cases pass trivially because the "offending" structures (composite keys, non-key middlemen, non-trivial non-superkey determinants) simply cannot exist.

Recall One-paragraph Feynman recap

Every exercise here reduced to the same move: write the FDs, find the determinant that isn't allowed, split it out. 1NF wants atomic cells; 2NF forbids depending on part of a key; 3NF forbids depending on a non-key middleman; BCNF forbids any non-trivial non-superkey determinant. The only judgement calls are (1) whether a BCNF split stays lossless and dependency-preserving, and (2) whether performance justifies deliberate denormalization. Structure over eyeballs, dependencies over duplication.