Normalization

Complete Exam Study Guide

Based on Lecture 13 (Chapter 6) — Coronel & Morris, Database Systems: Design, Implementation,
and Management, 13th ed.

Contents: (1) Core Concepts (2) The Methods (3) Worked Examples (4) Practice Exercises (5)
Answer Key (6) Cheat Sheet & Likely Exam Questions

Part 1 — Core Concepts

1.1 What is Normalization?
Normalization is a systematic technique of organizing data in a database by decomposing tables to:
• Eliminate data redundancy (duplicate data)
• Eliminate anomalies (Insertion, Update, Deletion)
• Ensure data dependencies make sense (data is stored logically)
It is a multi-step process that puts data into tabular form by removing duplicated data and ensuring
each piece of data is logically stored.

1.2 The Three Purposes of Normalization

1. Eliminating database anomalies
2. Eliminating redundant data
3. Ensuring data dependencies make sense (logical storage)

1.3 Problems WITHOUT Normalization — The Three Anomalies

Memorize these with the Student-table example — it is a classic exam question.

Anomaly What it means Example (Student table)

The same fact is stored in many rows; to To change a student's address who appears
Update Anomaly change it you must update every row, or in multiple rows, you must change
data becomes inconsistent S_Address in all their rows
A new student who has not chosen a
You cannot insert a record because some
Insertion Anomaly subject — you'd have to insert NULL for
other (unrelated) data is missing
Subject_opted (which is NOT NULL)
If a student has only one subject and drops
Deleting one fact accidentally deletes
Deletion Anomaly it, deleting that row deletes the entire
other useful facts
student record

1.4 Functional Dependency (FD)

Attribute B has a functional dependency on attribute A (written A → B) if, for any two records with
the same value of A, they must have the same value of B.
• Example: EmpNum → EmpEmail (each employee number determines exactly one email).
 • Read A → B as: "A determines B" or "B is functionally dependent on A".
Determinant: the attribute on the left-hand side of an FD. In EmpNum → EmpEmail, EmpNum is the
determinant.

1.5 Transitive Dependency

Given A → B and B → C, then by transitivity A → C. We say C is transitively dependent on A
through B.
• Example: EmpNum → DeptNum and DeptNum → DeptName, therefore EmpNum →
DeptName is transitive.
• A transitive dependency = a non-key attribute determined by another non-key attribute.

1.6 Partial Dependency

A partial dependency exists when a non-key attribute depends on only PART of a composite (multi-
attribute) primary key, not the whole key.
• Can only happen when the primary key is composite (2+ columns).
• Example: Key = {InvNum, LineNum}, but InvNum → InvDate. Since InvDate depends on
only part of the key, it's a partial dependency.

1.7 The Hierarchy of Normal Forms

Strength (weakest → strongest): 1NF → 2NF → 3NF → BCNF → 4NF.
Every BCNF relation is in 3NF; every 3NF is in 2NF; every 2NF is in 1NF.

Form Requirement (previous form PLUS...)

1NF Atomic values (single value per cell), no repeating groups, each row identified by a primary key
2NF In 1NF and no partial dependencies (no non-key attribute depends on part of a composite key)
In 2NF and no transitive dependencies (no non-key attribute depends on another non-key
3NF
attribute)
BCNF In 3NF and every determinant is a candidate key (every X in X→Y is a superkey)
4NF In BCNF and no multivalued dependencies (each MVD in its own relation)

1.8 Definitions to Quote Verbatim

• 1NF: Each column value is atomic (single); no repeating groups; every row has a primary key.
• 2NF: In 1NF and contains no partial dependencies. (A 2NF table can still have transitive
dependencies.)
• 3NF: In 2NF and contains no transitive dependencies.
• BCNF: Every determinant is a candidate key. If a table has only one candidate key, 3NF and
BCNF are equivalent.

1.9 Multivalued Dependency (MVD) and 4NF

A multivalued dependency occurs when one determinant is matched with a set of independent
values.
 • Example: Employee →→ Degree and Employee →→ Sibling (several degrees and
several siblings, unrelated to each other).
• The determinant of an MVD can never be a primary key.
• 4NF rule: Put each multivalued dependency into its own separate relation.

1.10 Lossless vs Lossy Decomposition

• Lossless (lossless-join): Natural join of the decomposed pieces reproduces exactly the
original relation — no lost data, no spurious rows. This is what we want.
• Lossy: Joining the pieces does NOT reproduce the original (information lost or spurious rows).
Often happens when pieces don't share a common key. This is bad.

1.11 Denormalization
Denormalization = deliberately introducing redundancy back into a normalized design (e.g., for faster
reporting/queries).
• Example: EVALDATA is the normalized master table; FACHIST is a denormalized table built via
queries to produce a desired report quickly.
Part 2 — The Methods (How to Actually Solve Problems)
2.1 General Normalization Procedure (1NF → 2NF → 3NF)
Step 0 — Identify the primary key (often composite).
Step 1 — Convert to 1NF: Remove repeating groups / multi-valued cells (e.g., split "Biology, Maths"
into separate rows). Make every value atomic; give the table a PK.
Step 2 — Convert to 2NF (remove partial dependencies): For each part of the composite key that
determines attributes by itself, move those attributes into a new table keyed on that part.
Step 3 — Convert to 3NF (remove transitive dependencies): Find any non-key attribute that
determines another non-key attribute; move that determinant + dependent(s) into a new table.
Slide trick — write each key component on its own line, the full key on the last line, then each
attribute under the key it depends on:

PROJECT (PROJ_NUM, PROJ_NAME)

EMPLOYEE (EMP_NUM, EMP_NAME, JOB_CLASS, CHG_HOUR)
ASSIGN (PROJ_NUM, EMP_NUM, HOURS)

2.2 How to Read a Dependency Diagram (exam favorite)

• PK components: bold, underlined, shaded.
• Arrows ABOVE the boxes: desirable dependencies (everything depends on the PK).
• Arrows BELOW the boxes: the problems — partial dependencies (from part of the key) and
transitive dependencies (from a non-key attribute).
• Your job: list the partial + transitive deps, then split the table to remove them.

2.3 Computing an Attribute Closure (X+) — needed for BCNF

The closure of X (written X+) = all attributes you can determine starting from X using the FDs.
1. Start: X+ = X (the attributes in X itself).
2. Repeat: if some FD A → B has its left side A fully inside X+, add B to X+.
3. Stop when nothing new can be added.
4. If X+ = all attributes of the relation → X is a superkey (SK).

2.4 Testing for BCNF

A relation is in BCNF if and only if for every FD X → Y, X is a superkey (X+ = all attributes).
• Take each determinant, compute its closure.
• If every determinant's closure = all attributes → BCNF.
• If even one determinant is not a superkey → NOT BCNF; decompose on that FD.
Decomposition when X → Y violates BCNF: split R into R1 = X+ (closure of the bad determinant)
and R2 = (R − X+) ∪ X (everything else plus X, to keep the join lossless).
2.5 The Lossless-Join Test (the Y/N matrix / tableau method)
1. Build a matrix: rows = sub-relations (R1, R2, …); columns = all attributes.
2. Fill it: put Y if the attribute is present in that sub-relation, N otherwise.
3. For each FD LHS → RHS: find rows that have all Y across the LHS columns; for those
matching rows, if any RHS column is Y in one row, set the others to Y too.
4. Repeat applying all FDs until no more changes.
5. Result: if any single row becomes all Y, the decomposition is LOSSLESS. Otherwise it is
LOSSY.
Part 3 — Worked Examples from the Slides
3.1 The Running Construction-Company Example (Figure 5.1)
Original un-normalized table: (PROJ_NUM, PROJ_NAME, EMP_NUM, EMP_NAME, JOB_CLASS,
CHG_HOUR, HOURS)
Problems: PROJ_NUM (intended PK) contains nulls; massive redundancy → update, insertion,
deletion anomalies.
Dependencies (1NF):
• Desirable (full key {PROJ_NUM, EMP_NUM}): → HOURS
• Partial: PROJ_NUM → PROJ_NAME; EMP_NUM → EMP_NAME, JOB_CLASS, CHG_HOUR
• Transitive: JOB_CLASS → CHG_HOUR
After 2NF (remove partial deps):

PROJECT (PROJ_NUM, PROJ_NAME)

EMPLOYEE (EMP_NUM, EMP_NAME, JOB_CLASS, CHG_HOUR)
ASSIGN (PROJ_NUM, EMP_NUM, HOURS)

Still has transitive dep JOB_CLASS → CHG_HOUR. After 3NF (remove it):

PROJECT (PROJ_NUM, PROJ_NAME)

ASSIGN (PROJ_NUM, EMP_NUM, HOURS)
EMPLOYEE (EMP_NUM, EMP_NAME, JOB_CLASS)
JOB (JOB_CLASS, CHG_HOUR)

Benefit: less data duplication, data integrity achieved.

3.2 Student / Subject 1NF → 2NF Example

Not in 1NF (multi-valued cell): Waseem | 15 | Biology, Maths
1NF — split the cell into rows; PK = {Student, Subject}:

Student Age Subject

Waseem 15 Biology
Waseem 15 Maths
Ahmed 14 Maths
Sajid 17 Maths
Problem: Age depends only on Student (part of key) → partial dependency → not 2NF. 2NF fix:

STUDENT (Student, Age) -- PK: Student

SUBJECT (Student, Subject) -- Student is FK; PK: {Student, Subject}

3.3 Transitive-Dependency 3NF Example (EMP table)

EMP (EMPNO, ENAME, DEPTNO, DNAME, LOC) — PK = EMPNO. DEPTNO → DNAME, LOC
and EMPNO → DEPTNO, so DNAME, LOC are transitively dependent on EMPNO. 3NF fix:
 EMP (EMPNO, ENAME, DEPTNO)
DEPT (DEPTNO, DNAME, LOC)

3.4 BCNF Closure Example — R(A, B, C, D)

FDs: A → BCD, BC → AD, D → B. Candidate keys: A and BC. Test each determinant:
• A+ = {A,B,C,D} → superkey ✓
• BC+ = {B,C,A,D} → superkey ✓
• D+ = {D,B} → NOT all attributes → NOT a superkey ✗
Since D → B has a non-superkey determinant, R is NOT in BCNF. Decompose on D → B:

R1 (A, C, D) -- the rest + D

R2 (D, B) -- the violating FD

3.5 BCNF Example — R(A, B, C), FDs {A→B, B→C, C→A}

Closures: A+ = B+ = C+ = {A,B,C}. Every single attribute determines everything → every
determinant (A, B, C) is a candidate key → the relation IS in BCNF.

3.6 Lossless-Join Worked Example — R(A,B,C,D,E)

Decomposition: R1(A,C), R2(A,B,D), R3(D,E); FDs: A→C, AB→D, D→E. Initial matrix:

A B C D E

R1 Y N Y N N
R2 Y Y N Y N
R3 N N N Y Y
• Apply A→C: R1,R2 both Y in A; R1 has C=Y → set R2's C=Y.
• Apply AB→D: only R2 has Y in both A and B → no other row matches → no change.
• Apply D→E: R2,R3 both Y in D; R3 has E=Y → set R2's E=Y.
Result: R2 row becomes Y Y Y Y Y (all Y) → decomposition is LOSSLESS. ✓
Part 4 — Practice Exercises (the exact tasks from the PPT)
Do these on paper, then check Part 5.

Exercise 1 — Dependency Diagram (attributes A–G)

A relation with attributes A, B, C, D, E, F, G has composite primary key {A, B}. Undesirable
dependencies below the line:
• B → C (partial)
• A → D (partial)
• E → G (transitive)
Task: Identify the partial and transitive dependencies, then decompose to 2NF and then 3NF.

Exercise 2 — Dependency Diagram (Skills / Members)

Attributes: Member Code, Skill Code, Skill Type, Title, Name, Last Name, Age, Group Code, City
Code, Post Code. Composite PK = {Member Code, Skill Code}. Undesirable deps:
• Skill Code → Skill Type (partial)
• Member Code → Title, Name, Last Name, Age, Group Code, City Code,
Post Code (partial)
• City Code → Post Code (transitive)
Task: Normalize to 3NF.

Exercise 3 — "Expertise" Expert System

Un-normalized table (sample data):

Expert Expertise Expertise

Name Last Name Dept Code Dept Name Location
Code Code Name

21 113 System Alice Adams 55 Brown NYC

35 113 System Tom Hank 32 Green LA
50 179 Database Robert Cody 40 Yellow Mexico
77 148 Web Lisa Baker 52 Black Hawaii
Task: Analyze and prepare a normalized database with the least redundancy (to 3NF).

Exercise 4 — Student Registration System

Un-normalized table (sample data):

Code Term Subj Code Subject Name Subj Cat Category Name Cr Hrs Grade

4501 1/45 A01 Mathematics 02 Natural Science 3 F

4501 1/45 A03 Urdu Language 01 Basic Studies 3 C
4501 2/45 A01 Mathematics 02 Natural Science 3 D
4502 1/45 A04 English 1 01 Basic Studies 3 C
4502 2/45 A02 Database System 03 Computer Science 3 B
Task: Analyze and prepare a normalized Student Registration system with the least redundancy (to
3NF).

Exercise 5 — PVFC Customer Invoice → 3NF

A customer invoice with Customer ID, Customer Name, Address; Order ID, Order Date; and line
items (Product ID, Product Description, Finish, Quantity, Unit Price, Extended Price).
Task: Convert the invoice into a set of 3NF relations.

Exercise 6 — "Stereos To Go" Invoice → 3NF

An invoice with Order No., Date, Account No., Customer, Address (City/State/Zip), Date Shipped,
and line items (Item Number, Product Code, Product Description/Manufacturer, Qty, Price), plus
Subtotal/Shipping/Tax/Total.
Task: Normalize the invoice to 3NF.

Exercise 7 — Mountain View Community Hospital Patient Bill → 3NF

A hospital invoice with Patient Name, Patient #, Account Number, Invoice/Due Date, Date
Admitted/Discharged, and charge lines (Code, Description, Total Charge), plus Total Charges Due.
Task: Normalize the patient bill to 3NF.

Exercise 8 — PART SUPPLIER (Table 4-3)

Part No Description Vendor Name Address Unit Cost

1234 Logic chip Fast Chips Cupertino 10.00

1234 Logic chip Smart Chips Phoenix 8.00
5678 Memory chip Fast Chips Cupertino 3.00
5678 Memory chip Quality Chips Austin 2.00
5678 Memory chip Smart Chips Phoenix 5.00
Given: part numbers uniquely identify parts; vendor names uniquely identify vendors.
Tasks:
1. Convert this table to a relation named PART SUPPLIER in 1NF (show sample data).
2. List the functional dependencies in PART SUPPLIER and identify a candidate key.
3. Develop a set of 3NF relations from PART SUPPLIER.

Exercise 9 — GRADE REPORT (Table 4-4)

Campus Instructo Instr Grad
StudentID Name Major CourseID Course Title
Addr r Loc e

168300458 Williams 208 Brooks IS IS 350 Database Mgt Codd B 104 A

Systems
168300458 Williams 208 Brooks IS IS 465 Parsons B 317 B
Analysis
543291073 Baker 104 Phillips Acctg IS 350 Database Mgt Codd B 104 C
543291073 Baker 104 Phillips Acctg Acct 201 Fund Acctg Miller H 310 B
 Campus Instructo Instr Grad
StudentID Name Major CourseID Course Title
Addr r Loc e

543291073 Baker 104 Phillips Acctg Mkgt 300 Intro Mktg Bennett B 212 A
Tasks:
1. In what normal form is this relation currently?
2. Decompose GRADE REPORT into a set of 3NF relations.

BCNF Activity (from the slides)

Convert this table into BCNF:

S_Num T_Code Offering# Review Date

123599 FIT104 01764 2nd March

123599 PIT305 01765 12th April
123599 PIT107 01789 2nd May
346700 FIT104 01764 3rd March
346700 PIT305 01765 7th May
Hint: Offering# → T_Code, and {S_Num, Offering#} → Review Date.
Part 5 — Answer Key (check your work)
Exercise 1
• Partial deps: A → D, B → C. Transitive: E → G.
2NF:

R1(A, D)
R2(B, C)
R3(A, B, E, F, G)

3NF (remove E → G from R3):

R1(A, D)
R2(B, C)
R3(A, B, E, F)
R4(E, G)

Exercise 2 (3NF)
MEMBER (Member Code, Title, Name, Last Name, Age, Group Code, City Code)
CITY (City Code, Post Code) -- removes City Code -> Post Code
(transitive)
SKILL (Skill Code, Skill Type) -- removes Skill Code -> Skill Type
(partial)
MEMBER_SKILL (Member Code, Skill Code) -- M:N link; PK = {Member Code, Skill
Code}

Exercise 3 (3NF)
FDs: ExpertCode → Name, LastName, DeptCode; DeptCode → DeptName, Location;
ExpertiseCode → ExpertiseName.

EXPERT (ExpertCode, Name, LastName, DeptCode)

DEPARTMENT (DeptCode, DeptName, Location)
EXPERTISE (ExpertiseCode, ExpertiseName)
EXPERT_EXPERTISE (ExpertCode, ExpertiseCode) -- M:N link

Exercise 4 (3NF)
FDs: SubjectCode → SubjectName, SubjectCategory, CreditHours; SubjectCategory →
CategoryName; {Code, Term, SubjectCode} → Grade.

SUBJECT (SubjectCode, SubjectName, SubjectCategory, CreditHours)

CATEGORY (SubjectCategory, CategoryName)
REGISTRATION (StudentCode, Term, SubjectCode, Grade)
STUDENT (StudentCode, ...) -- any student-only attributes

Exercise 5 (PVFC Invoice, 3NF)

CUSTOMER (CustomerID, CustomerName, CustomerAddress)
 ORDER (OrderID, OrderDate, CustomerID)
PRODUCT (ProductID, ProductDescription, Finish, UnitPrice)
ORDER_LINE (OrderID, ProductID, Quantity)

Extended Price = Quantity × Unit Price is derived, so it is NOT stored.

Exercise 6 (Stereos To Go, 3NF)

CUSTOMER (AccountNo, Customer, Address, City, State, ZipCode)
ORDER (OrderNo, Date, DateShipped, AccountNo)
PRODUCT (ProductCode, ProductDescription, Manufacturer, Price)
ORDER_LINE (OrderNo, ProductCode, Qty)

Exercise 7 (Hospital Bill, 3NF)

PATIENT (PatientNo, PatientName, PatientAddress)
INVOICE (AccountNumber, InvoiceDate, DueDate, DateAdmitted, DateDischarged,
PatientNo)
CHARGE (Code, Description) -- Code -> Description
BILL_ITEM (AccountNumber, Code, TotalCharge) -- charges on this bill

Exercise 8 (PART SUPPLIER)

(a) 1NF: PART SUPPLIER (PartNo, Description, VendorName, Address, UnitCost) — PK = {PartNo,
VendorName} (same 5 sample rows, one relation).
(b) FDs: PartNo → Description; VendorName → Address; {PartNo, VendorName} → UnitCost.
Candidate key = {PartNo, VendorName}.
(c) 3NF:

PART (PartNo, Description)

VENDOR (VendorName, Address)
SUPPLIES (PartNo, VendorName, UnitCost)

Exercise 9 (GRADE REPORT)

(a) Currently in 1NF (atomic, no repeating groups). Not 2NF — partial deps such as StudentID →
StudentName, CampusAddress, Major and CourseID → CourseTitle, InstructorName. Also a
transitive dep InstructorName → InstructorLocation.
(b) 3NF:

STUDENT (StudentID, StudentName, CampusAddress, Major)

COURSE (CourseID, CourseTitle, InstructorName)
INSTRUCTOR (InstructorName, InstructorLocation) -- removes transitive dep
REGISTRATION (StudentID, CourseID, Grade)

BCNF Activity
FDs: {S_Num, Offering#} → Review Date, Offering# → T_Code. Candidate key = {S_Num,
Offering#}. The determinant Offering# is not a candidate key → violates BCNF. Decompose:
StudentReview (S_Num, Offering#, Review Date) -- PK {S_Num, Offering#}
OfferingTeacher (Offering#, T_Code) -- PK Offering#
Part 6 — Cheat Sheet & Likely Exam Questions
One-Line Memory Hooks
• 1NF = atomic values, no repeating groups.
• 2NF = 1NF + no partial dependency (kills "depends on part of the key").
• 3NF = 2NF + no transitive dependency (kills "non-key depends on non-key").
• BCNF = every determinant is a candidate key.
• 4NF = BCNF + each multivalued dependency in its own table.
• Partial ⇒ only possible with a composite key. Transitive ⇒ non-key → non-key.
• Determinant = left side of an FD. Lossless = join rebuilds original (one all-Y matrix row).
• Single candidate key ⇒ 3NF = BCNF.

Question Types You're Likely to Get

1. Define + give example of the 3 anomalies (use the Student table).
2. Define FD / partial / transitive / determinant.
3. "Which normal form is this table in?" — check atomic (1NF), partial deps (2NF), transitive deps
(3NF), determinant=candidate key (BCNF). Justify each step.
4. "Normalize this table/invoice to 3NF" — identify PK & FDs, split partial deps, split transitive
deps, write final relations.
5. BCNF via closures — compute X+ for each determinant; if any determinant isn't a superkey,
decompose R into X+ and (R−X+)∪X.
6. Lossless vs lossy — build the Y/N matrix, apply FDs, check for an all-Y row.
7. Read a dependency diagram — list partial (below, from part of key) and transitive (below, from
non-key) dependencies.

How to Show Working (so you don't lose marks)

1. State the primary/candidate key first.
2. List all functional dependencies.
3. Classify each FD as full / partial / transitive.
4. Decompose one normal form at a time (1NF → 2NF → 3NF), writing relations after each step.
5. Underline primary keys; mark foreign keys.
6. Note removed derived columns (e.g., Extended Price, Total) — don't store calculated values.

Good luck — you've got this.