Normalisation & Functional Dependencies

Why Normalise?

Analogy: Imagine a notebook where you write a student's name AND their department name AND their head of department's name all in one row. If the head changes, you must update 1000 rows!

Normalisation breaks this into smaller tables to avoid: 1. Update anomaly — change in one place means updating many rows 2. Insertion anomaly — cannot add data without other data (e.g., cannot add a dept without a student) 3. Deletion anomaly — deleting a row accidentally loses other data

---

Functional Dependencies — The Rules of Determination

FD X → Y means: "If two rows have the same X value, they MUST have the same Y value."

Real example: StudentID → StudentName (one student ID maps to exactly one name)

NOT a valid FD: Name → StudentID (two students can have the same name!)

Armstrong's Axioms (3 rules to derive new FDs):

1. Reflexivity:    Y ⊆ X  →  X → Y
   (X determines any subset of itself)
   Example: {ID, Name} → {Name}

2. Augmentation:   X → Y  →  XZ → YZ
   (Add same attributes to both sides)
   Example: ID → Name  →  {ID, Course} → {Name, Course}

3. Transitivity:   X → Y  and  Y → Z  →  X → Z
   (Chain of determination)
   Example: ID → DeptID  and  DeptID → DeptName  →  ID → DeptName

---

Attribute Closure (X+) — Finding What X Determines

Algorithm:

Start with: result = X
Repeat until no change:
  For each FD (A → B):
    If A ⊆ result: add B to result

X is a SUPERKEY if result = all attributes
X is a CANDIDATE KEY if it is a superkey AND removing any attribute from X breaks this

Worked Example:

Schema: R(A, B, C, D, E)
FDs: {A→B, BC→D, D→E, A→C}
Find closure of A (i.e., A+)

Start: result = {A}
A→B:  A ⊆ result → add B → result = {A,B}
A→C:  A ⊆ result → add C → result = {A,B,C}
BC→D: BC ⊆ result → add D → result = {A,B,C,D}
D→E:  D ⊆ result → add E → result = {A,B,C,D,E}

A+ = {A,B,C,D,E} = all attributes → A is a candidate key!

---

Normal Forms — The Ladder of Quality

Think of it as climbing steps. Higher = less redundancy.

1NF — No Lists in Cells

VIOLATES 1NF:
Student | Courses
101     | Math, Science, English  ← a LIST in one cell

FIX (1NF):
Student | Course
101     | Math
101     | Science
101     | English

2NF — No Partial Dependencies

Only relevant when PK is composite (multiple columns).

A partial dependency = non-key attribute depends on PART of the composite PK.

ENROLLMENT(StudentID, CourseID, CourseName, Grade)
PK = (StudentID, CourseID)

CourseName depends only on CourseID — not on the full PK!
This is a PARTIAL DEPENDENCY → not in 2NF

FIX: Split into:
ENROLLMENT(StudentID, CourseID, Grade)  ← full PK dependency
COURSE(CourseID, CourseName)            ← separate table

3NF — No Transitive Dependencies

A transitive dependency = non-key attribute determines another non-key attribute.

EMPLOYEE(EmpID, DeptID, DeptName)
PK = EmpID

EmpID → DeptID  (direct)
DeptID → DeptName  (DeptID is NOT a key!)
→ Transitive: EmpID → DeptID → DeptName

FIX: Split into:
EMPLOYEE(EmpID, DeptID)
DEPARTMENT(DeptID, DeptName)

BCNF — The Strict Version

For EVERY non-trivial FD X → Y: X must be a superkey.

BCNF is STRICTER than 3NF.
Every BCNF relation IS in 3NF.
A 3NF relation may NOT be in BCNF.

Classic example where 3NF ≠ BCNF:

TEACHING(Student, Course, Teacher)
FDs: {Student,Course} → Teacher  and  Teacher → Course
Candidate keys: {Student,Course} and {Student,Teacher}

FD Teacher → Course: Teacher is NOT a superkey
→ Violates BCNF, but is in 3NF (Course is prime attribute)

BCNF decomposition loses: {Student,Course} → Teacher

---

The Key Trade-off

┌─────────────────────────────────────────────────┐
│ Property              │ 3NF   │ BCNF             │
│─────────────────────────────────────────────────│
│ Lossless decomposition│  ✓    │  ✓               │
│ Preserves all FDs     │  ✓    │  ✗ (may lose)    │
│ No redundancy         │ Some  │  ✓               │
└─────────────────────────────────────────────────┘
Use 3NF when FD preservation is critical.
Use BCNF when no redundancy is more important.

---

Quick Check

Q1. FDs: A→B, B→C. Is AC → B a valid FD?

Compute (AC)+: A→B gives B; B→C gives C. (AC)+ = {A,B,C}
B ∈ (AC)+ → Yes, AC → B holds

Q2. R(A,B,C,D), FDs: AB→C, C→D, D→A. What are candidate keys?

Try AB: (AB)+ = AB → add C (AB→C) → add D (C→D) → add A (D→A) = {A,B,C,D} ✓
Try B alone: (B)+ = {B} ✗
B must appear in every CK (B not on RHS of any FD)
Try BC: (BC)+ = {B,C,D,A} ✓ but AB⊆BC? No, check minimality:
  Remove B: (C)+ = {C,D,A} — no B → not superkey → B needed
  Remove C: (B)+ = {B} — not superkey → C needed
So BC is also a candidate key.
Candidate keys: {AB, BC, BD}