Real-life analogy: The messy spreadsheet

Consider: (StudentID, StudentName, CourseID, CourseName, Instructor, InstructorPhone). Problems: (1) Changing InstructorPhone requires updating every row with that instructor — one missed row creates inconsistency (update anomaly). (2) Deleting a student removes course info (delete anomaly). (3) Cannot store a course with no students (insert anomaly). Normalization splits this into clean, anomaly-free tables.

Functional Dependencies and Armstrong axioms

FD X→Y: knowing the value of X uniquely determines Y. If two tuples have the same X values, they must have the same Y values. Example: StudentID→StudentName, CourseID→CourseName.

Armstrong axioms: (1) Reflexivity: Y⊆X implies X→Y. (2) Augmentation: X→Y implies XZ→YZ. (3) Transitivity: X→Y and Y→Z implies X→Z. Use these to compute X+ (closure of X — all attributes determined by X).

from itertools import combinations

def closure(X: set, FDs: list) -> set:
    result = set(X)
    changed = True
    while changed:
        changed = False
        for (lhs, rhs) in FDs:
            if lhs.issubset(result) and not rhs.issubset(result):
                result |= rhs
                changed = True
    return result

def candidate_keys(attrs: set, FDs: list) -> list:
    keys = []
    for size in range(1, len(attrs) + 1):
        for combo in combinations(attrs, size):
            s = set(combo)
            if closure(s, FDs) == attrs:
                if not any(set(k) < s for k in keys):
                    keys.append(frozenset(s))
    return [set(k) for k in keys]

# Example: R(A,B,C,D,E), FDs: A→B, BC→D, D→E
attrs = {'A','B','C','D','E'}
FDs   = [({'A'},{'B'}), ({'B','C'},{'D'}), ({'D'},{'E'})]

print("Closure of {A,C}:", closure({'A','C'}, FDs))  # {A,B,C,D,E}
print("Candidate keys:",   candidate_keys(attrs, FDs)) # [{A,C}]

Normal Forms — 1NF through BCNF

BCNF vs 3NF trade-off — GATE favorite: BCNF eliminates all redundancy but may lose some FDs (lossless but not always dependency-preserving). 3NF always preserves all FDs but allows slight redundancy. GATE pattern: "Is this in BCNF? In 3NF? Decompose it." Check: for every FD X→Y, is X a superkey (BCNF)? Or is X a superkey OR Y is prime (3NF)?

Worked example: decomposing to BCNF, step by step

R(StudentID, CourseID, Instructor)
FDs:  (StudentID, CourseID) → Instructor
      Instructor → CourseID          ← each instructor teaches ONE course

Step 1 — Find candidate keys.
  (StudentID, CourseID)+ = all ✓
  (StudentID, Instructor)+ = {S, I, C} = all ✓
  Candidate keys: {SID, CID} and {SID, Instructor}
  Prime attributes: StudentID, CourseID, Instructor (all three!)

Step 2 — Check BCNF for each FD.
  (SID, CID) → Instructor : LHS is a candidate key ✓
  Instructor → CID        : Instructor is NOT a superkey ✗ VIOLATION

Step 3 — Split on the violating FD (Instructor → CourseID).
  R1(Instructor, CourseID)      key: Instructor        — in BCNF ✓
  R2(StudentID, Instructor)     key: (SID, Instructor) — in BCNF ✓

Step 4 — Verify.
  Lossless? R1 ∩ R2 = {Instructor} → R1. YES ✓
  Dependency-preserving? (SID, CID) → Instructor is NOT
  enforceable in either table alone. NO ✗

This relation is the textbook proof that BCNF decomposition can
sacrifice dependency preservation — it was in 3NF all along
(Instructor → CID has prime CID on the right), so a designer
wanting to keep all FDs enforceable would stop at 3NF.

Minimal cover, lossless joins, and dependency preservation

A minimal (canonical) cover is the smallest FD set equivalent to the original — the cleaned-up input every decomposition algorithm expects. Three steps, in order: (1) make every right-hand side a single attribute; (2) remove extraneous LHS attributes — in AB → C, drop B if A⁺ (under the full FD set) already contains C; (3) remove redundant FDs — drop X → Y if Y ∈ X⁺ computed without that FD. The order matters; skipping step 2 before step 3 is the standard exam mistake.

GATE: the lossless-join test in 10 seconds: For a two-way split, intersect the attribute sets and compute the closure of the intersection. If it contains all attributes of either fragment, the join is lossless. Empty intersection = always lossy (the join becomes a Cartesian product). This one-line test answers a mark's worth of question in seconds.

Beyond BCNF — 4NF, 5NF, and when to denormalize

4NF targets multi-valued dependencies (MVDs): in Course ↠ Instructor | Textbook, instructors and textbooks vary independently, so one table storing both explodes into every combination. 4NF splits them into (Course, Instructor) and (Course, Textbook). 5NF handles join dependencies — relations only reconstructable by joining three or more projections. Both are rare in practice but regular in GATE theory questions.

In production systems, normalization is a starting point, not a religion. Denormalization — deliberately reintroducing redundancy — is standard where read performance beats write simplicity: data warehouses use star schemas with denormalized dimension tables; a product table may cache review_count rather than COUNT(*) on every page load. The discipline is to normalize first, measure, then denormalize knowingly, with triggers or application logic guarding the redundant copies.

Practice questions (GATE-style)

1. R(A,B,C,D). FDs: A→B, B→C, C→D, D→A. Find all candidate keys. (Answer: A→B→C→D→A is a cycle. Each single attribute determines all others. Candidate keys: {A}, {B}, {C}, {D}.)
2. R(SID,CID,InstructorID,InstructorPhone). PK=(SID,CID). FD: InstructorID→InstructorPhone. Which NF is violated? (Answer: 3NF violated — InstructorPhone transitively depends on PK via InstructorID (non-key→non-key).)
3. FD X→Y where X is not a superkey. R is definitely NOT in: (Answer: BCNF — BCNF requires every non-trivial FD LHS to be a superkey.)
4. What is a lossless join decomposition? (Answer: Decomposing R into R1, R2 such that R1 ⋈ R2 = R exactly. Guaranteed lossless if R1∩R2 → R1 or R1∩R2 → R2.)
5. Relation R(A,B,C). FDs: A→B, B→C, C→A. Is R in BCNF? (Answer: Yes — candidate keys are {A},{B},{C}. Every FD has a candidate key on the LHS, which is a superkey.)
6. R(A,B,C) decomposed into R1(A,B) and R2(B,C). FDs: A→B, B→C. Is the decomposition lossless? (Answer: Yes. R1 ∩ R2 = {B}, and B → C means B+ ⊇ {B,C} = all of R2. The shared attribute is a key of R2, so the join is lossless.)
7. Find the minimal cover of {A→BC, B→C, A→B, AB→C}. (Answer: Split RHS: A→B, A→C, B→C, AB→C. Drop extraneous B from AB→C (A→C already holds): duplicate of A→C. Remove redundant A→C (derivable via A→B, B→C). Minimal cover: {A→B, B→C}.)
8. Course ↠ Instructor and Course ↠ Textbook (independent MVDs) in one table causes what problem, and which NF fixes it? (Answer: Every (instructor × textbook) combination must be stored per course — insertion of one new textbook requires a row per instructor. 4NF fixes it by splitting into (Course, Instructor) and (Course, Textbook).)