Unit 4: Normalization

Scenario: A university stores everything in one table:

UNF Table
student_id | name | dept | dept_hod | course_id | course_name | instructor | credits | grade | hostel | room

FDs:

student_id → name, dept, hostel, room
dept → dept_hod
course_id → course_name, instructor, credits
{student_id, course_id} → grade
hostel → warden  (each hostel has one warden)

Task: Normalize step-by-step from UNF → 1NF → 2NF → 3NF → BCNF. Show each table at each stage.

💡 Complete Solution

Step-by-step Normalization
1NF: Already 1NF (atomic values, no repeating groups assumed)

2NF: Remove partial dependencies from PK = {student_id, course_id}
  Partial FDs:
    student_id → name, dept, hostel, room    (depends on PART of PK)
    course_id → course_name, instructor, credits  (depends on PART of PK)
  
  Decompose:
    students(student_id, name, dept, hostel, room)  PK: student_id
    courses(course_id, course_name, instructor, credits)  PK: course_id
    enrollments(student_id, course_id, grade)  PK: {student_id, course_id}

3NF: Remove transitive dependencies
  In students: student_id → dept → dept_hod (transitive — but dept_hod 
    isn't in students anymore if we didn't include it. Let's assume 
    the original had dept_hod in students table)
    
    students(student_id, name, dept, hostel, room) — dept_hod removed
    departments(dept, dept_hod)  PK: dept
    
  In students: student_id → hostel → warden (transitive if warden exists)
    students(student_id, name, dept, hostel, room)
    hostels(hostel, warden)  PK: hostel

BCNF: Check — is every determinant a superkey?
  students: student_id → all. student_id is PK. ✓
  departments: dept → dept_hod. dept is PK. ✓
  courses: course_id → all. course_id is PK. ✓
  enrollments: {student_id, course_id} → grade. Composite PK. ✓
  hostels: hostel → warden. hostel is PK. ✓
  All in BCNF! ✓

SQL — Final Normalized Schema
CREATE TABLE departments (
    dept       VARCHAR2(10)  PRIMARY KEY,
    dept_hod   VARCHAR2(50)
);
CREATE TABLE hostels (
    hostel     VARCHAR2(20)  PRIMARY KEY,
    warden     VARCHAR2(50)
);
CREATE TABLE students (
    student_id NUMBER(10)    PRIMARY KEY,
    name       VARCHAR2(50)  NOT NULL,
    dept       VARCHAR2(10)  REFERENCES departments(dept),
    hostel     VARCHAR2(20)  REFERENCES hostels(hostel),
    room       VARCHAR2(10)
);
CREATE TABLE courses (
    course_id  VARCHAR2(10)  PRIMARY KEY,
    course_name VARCHAR2(50) NOT NULL,
    instructor VARCHAR2(50),
    credits    NUMBER(1)     CHECK (credits BETWEEN 1 AND 5)
);
CREATE TABLE enrollments (
    student_id NUMBER(10)    REFERENCES students(student_id),
    course_id  VARCHAR2(10)  REFERENCES courses(course_id),
    grade      CHAR(2),
    PRIMARY KEY (student_id, course_id)
);

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

💡 Complete Solution

Solution
Step 1: Attribute analysis
  B appears ONLY on LEFT side → B must be in every candidate key.

Step 2: Find closures starting with B + each other attribute
  {A, B}⁺: AB→C ⇒ {A,B,C}. C→D ⇒ {A,B,C,D}. D→E ⇒ {A,B,C,D,E} ✓ ALL!
  {B, C}⁺: C→D ⇒ {B,C,D}. D→E ⇒ {B,C,D,E}. E→A ⇒ {A,B,C,D,E} ✓ ALL!
  {B, D}⁺: D→E ⇒ {B,D,E}. E→A ⇒ {A,B,D,E}. AB→C ⇒ {A,B,C,D,E} ✓ ALL!
  {B, E}⁺: E→A ⇒ {A,B,E}. AB→C ⇒ {A,B,C,E}. C→D ⇒ {A,B,C,D,E} ✓ ALL!

  All are superkeys. Check minimality:
  B⁺ = {B} — NOT all. So B alone is not a key.
  ∴ All of {AB, BC, BD, BE} are CANDIDATE KEYS (minimal).

Step 3: Prime and non-prime attributes
  Prime: A, B, C, D, E — ALL are prime! (every attribute is in some CK)
  Non-prime: NONE

Step 4: Check normal forms
  1NF: ✓ (assumed atomic)
  2NF: Check partial dependencies on composite CKs.
    AB→C: full (C depends on all of AB) ✓
    But C→D: C is part of CK {BC}. D depends on just C, not full BC.
    However, D is a prime attribute — 2NF only restricts NON-prime partials.
    Since ALL attributes are prime, 2NF is satisfied. ✓
  3NF: For each FD, check: is LHS a superkey OR is RHS prime?
    AB→C: AB is superkey ✓
    C→D: C is NOT a superkey. But D IS prime. ✓ (3NF exception)
    D→E: D is NOT a superkey. But E IS prime. ✓
    E→A: E is NOT a superkey. But A IS prime. ✓
    ∴ 3NF satisfied. ✓
  BCNF: For each FD, is LHS a superkey?
    C→D: C is NOT a superkey (C⁺ = {C,D,E,A} ≠ all, missing B). ✗
    ∴ NOT in BCNF. ✗

Answer: Candidate Keys = {AB, BC, BD, BE}. Highest NF = 3NF (not BCNF).

Scenario: Flipkart's normalized product catalog (5 tables: products, categories, sellers, images, reviews) takes 200ms for a JOIN query. The homepage needs <50ms response time. Design a denormalization strategy.

💡 Solution

SQL — Denormalized Read Table
-- Normalized source tables (OLTP — source of truth)
-- products, categories, sellers, product_images, reviews

-- Denormalized materialized view (for read performance)
CREATE MATERIALIZED VIEW mv_product_listing
BUILD IMMEDIATE REFRESH COMPLETE ON DEMAND AS
SELECT
    p.product_id, p.product_name, p.price,
    c.category_name,
    s.seller_name,
    (SELECT image_url FROM product_images pi 
     WHERE pi.product_id = p.product_id AND pi.is_primary = 1
     AND ROWNUM = 1) AS primary_image,
    (SELECT ROUND(AVG(rating),1) FROM reviews r 
     WHERE r.product_id = p.product_id) AS avg_rating,
    (SELECT COUNT(*) FROM reviews r 
     WHERE r.product_id = p.product_id) AS review_count
FROM products p
JOIN categories c ON p.category_id = c.category_id
JOIN sellers s ON p.seller_id = s.seller_id;

-- Refresh every 15 minutes via scheduled job
-- Homepage queries hit mv_product_listing (single table, no JOINs)
-- Write operations (new product, review) go to normalized tables

Architecture: Writes → Normalized OLTP tables (3NF). Reads → Denormalized materialized view. This is the standard CQRS (Command Query Responsibility Segregation) pattern used by Flipkart, Amazon, and Swiggy.