Appendices

Appendix G. Normalization Exercises and Solutions

Chapter 7's machinery as practice sets: state the FDs, find the keys, name the violations, decompose to the stated form, and check losslessness and dependency preservation. Attempt each before reading its solution; the forms and theorems are Chapter 7's, the method Chapter 28's (predict, then verify).

Exercise G1 — Course survey report

survey(course_id, course_title, dept_id, dept_name, instructor_id,
       section_id, semester, year, student_id, student_name, rating)
FDs:  course_id → course_title, dept_id
      dept_id → dept_name
      section_id → course_id, semester, year, instructor_id
      (student_id, section_id) → rating

Tasks: (a) the candidate key; (b) the highest normal form and every violated dependency; (c) the 3NF decomposition. Solutions: (a) the never-on-right-hand-side attributes are student_id and section_id; their closure is all attributes, so (student_id, section_id) is the only candidate key, and every other attribute is non-prime. (b) 1NF only — 2NF fails on partial dependencies: student_id → course_title, dept_name (student facts from half the key) and section_id → course_title, dept_name, semester, year, instructor_id (section facts from the other half); 3NF then fails transitively via course_id → dept_id → dept_name. (c) 2NF split: student(student_id, student_name), section_report(section_id, course_id, semester, year, instructor_id), rating(student_id, section_id, rating); 3NF split: course(course_id, course_title, dept_id), department(dept_id, dept_name) — leaving section(section_id, course_id, semester, year, instructor_id). Each split is lossless by the shared-key test (the shared attributes determine one whole side).

Exercise G2 — Employee parking

parking(emp_id, emp_name, lot_id, lot_name, lot_capacity,
        car_reg, car_color, sticker_no)
FDs:  emp_id → emp_name
      lot_id → lot_name, lot_capacity
      car_reg → car_color
      sticker_no → emp_id, lot_id
      emp_id → sticker_no        (one sticker per employee)

Tasks: (a) all candidate keys; (b) the form; (c) a dependency-preserving 3NF/BCNF decomposition. Solutions: (a) two candidate keys: (sticker_no, car_reg) — sticker_no determines emp_id, lot_id and their facts, car_reg brings car_color — and (emp_id, car_reg) — emp_id reaches sticker_no and thus the lot facts. Prime attributes: sticker_no, car_reg, emp_id; non-prime: emp_name, lot_id, lot_name, lot_capacity, car_color. (b) 1NF: the partial dependency sticker_no → lot_id, lot_name, lot_capacity places non-prime lot facts on a proper subset of the composite key. (c) 3NF synthesis by determinant: employee(emp_id, emp_name, sticker_no), lot(lot_id, lot_name, lot_capacity), car(car_reg, car_color), sticker(sticker_no, emp_id, lot_id), assignment(sticker_no, car_reg) — every FD lands in one table (dependency-preserving), each split passes the lossless shared-key test, and every table is in BCNF because each determinant is its own table's key.

Exercise G3 — The 4NF shape

service(instructor_id, student_id, committee)
MVDs: instructor_id ↠ student_id;  instructor_id ↠ committee
Rule: advising and committee service are independent.

Tasks: (a) the form and why; (b) the repair; (c) the spurious-tuple demonstration. Solutions: (a) BCNF (no non-trivial FDs) but not 4NF — the MVDs have non-superkey determinants; the table stores the cross product. (b) advisor(instructor_id, student_id) and committee_member(instructor_id, committee). (c) rejoining invents advisor-committee pairings the rule never asserted.

Exercise G4 — Retail orders (Chapter 7's set, extended)

order_report(order_no, order_date, customer_id, customer_name, city,
             product_id, product_name, unit_price, quantity)
FDs:  order_no → order_date, customer_id
      customer_id → customer_name, city
      product_id → product_name, unit_price
      (order_no, product_id) → quantity

Tasks: the key; the stepwise 1NF → 2NF → 3NF decomposition; the lossless test at each split; the one fact that is redundant by design in a real order system and its justification. Solutions: key = (order_no, product_id). 2NF: orders(order_no, order_date, customer_id), customer-attributes out of the key's way, product(product_id, product_name, unit_price), order_line(order_no, product_id, quantity). 3NF: customer(customer_id, customer_name, city) out of orders. Lossless: each split's shared attributes determine one side (order_no → orders; product_id → product). The deliberate redundancy: a real order_line stores unit_price at sale time (Chapter 29.5) — temporal correctness, with the FD (product_id → unit_price) deliberately not enforced on the line.

Exercise G5 — Two lossless-join proofs

For each split, prove lossless or show a spurious tuple on the canonical data:

(a) student(student_id, full_name, major_dept_id)
    department(dept_id, dept_name)          -- split at major_dept_id/dept_id
(b) e1(student_id, section_id)
    e2(student_id, grade)                   -- split of enrollment

Solutions: (a) the join attribute sets are {major_dept_id} and {dept_id} — a rename first (ρ), then the intersection dept_id → department (a key): lossless by Heath's theorem; rejoin equals the original. (b) student_id determines neither side; Nusrat (3 sections × 3 grades) produces 9 join rows, 6 spurious — the Chapter 7 demonstration.

Exercise G6 — The decomposition report (capstone rehearsal)

Take Exercise G1's survey table end to end: the closure of each key candidate, the canonical cover of the FD set, the 3NF-synthesis decomposition (Bernstein), the lossless and preservation checks, and the final DDL with named constraints. Solutions: the cover is G1's five FDs (already minimal); synthesis groups by determinant: student, section, course, department, instructor, rating(student_id, section_id); every FD lands in one table (preserved); each binary step is lossless by shared-key determination; the DDL is the canonical schema's shape — Chapter 7's throughline, reproduced as an exercise.