Database Normalization from 1NF to BCNF: Solved Step-by-Step with TU Board Question Tables

Author: Bhuban Subedi | Subject: Database Management Systems (CACS255) | Semester: Fourth Semester

When designing relational database schemas, storing all data in a single large unnormalized table leads to catastrophic data redundancy, wasted disk space, and operational data corruption.

Normalization is the systematic mathematical technique of decomposing relation schemas to minimize data redundancy and prevent Insert, Update, and Delete Anomalies.

In the Tribhuvan University (TU) BCA Fourth Semester DBMS (CACS255) board examination, a comprehensive normalization numerical question carrying 10 full marks is virtually guaranteed in every exam cycle.

In this guide, we will analyze data anomalies, define functional dependencies, and walk step-by-step through normalizing an unnormalized university dataset from 1NF all the way to BCNF.

1. The Three Evil Database Anomalies

Consider a poorly designed single flat table:
$$\text{STUDENT_COURSE}(\underline{\text{StudentID, CourseID}}, \text{StudentName, Major, CourseName, Instructor, InstructorRoom})$$

+-----------+----------+-------------+-------+------------+------------+----------------+
| StudentID | CourseID | StudentName | Major | CourseName | Instructor | InstructorRoom |
+-----------+----------+-------------+-------+------------+------------+----------------+
| 101       | CS101    | Sagar KC    | BCA   | C-Prog     | Prof. Giri | Block-B 201    |
| 101       | CS201    | Sagar KC    | BCA   | DSA        | Dr. Sharma | Block-A 105    |
| 102       | CS101    | Ritu Rana   | BCA   | C-Prog     | Prof. Giri | Block-B 201    |
+-----------+----------+-------------+-------+------------+------------+----------------+

1. Insertion Anomaly: You cannot add a newly hired instructor or a new course unless at least one student enrolls in it, because StudentID is part of the composite primary key and cannot be NULL (Entity Integrity Rule).
2. Deletion Anomaly: If student 102 drops out and we delete their record, we accidentally lose all information about course CS101 and Professor Giri if they were the only student enrolled in that section.
3. Update / Modification Anomaly: If Professor Giri moves to Block-C 304, we must locate and update thousands of individual student enrollment rows. Missing a single row causes inconsistent data.

2. Functional Dependencies Explained

A Functional Dependency (FD) $X \to Y$ means that the value of attribute set $X$ uniquely determines the value of attribute set $Y$.

+------------------------------------+------------------------------------+
| Dependency Type                    | Meaning & Definition               |
+------------------------------------+------------------------------------+
| **Full Functional Dependency**     | An attribute $Y$ depends on the    |
|                                    | entire composite key $X$, not on   |
|                                    | any proper subset of $X$.          |
+------------------------------------+------------------------------------+
| **Partial Dependency**             | A non-prime attribute depends on a |
|                                    | *part* of a composite primary key. |
+------------------------------------+------------------------------------+
| **Transitive Dependency**          | $X \to Y$ and $Y \to Z \implies X \to Z$ |
|                                    | (Non-prime attribute determines    |
|                                    | another non-prime attribute).      |
+------------------------------------+------------------------------------+

3. The Normal Forms Hierarchy

       +---------------------------------------------+
       | BCNF (Boyce-Codd Normal Form)               |
       | Strictly Every Determinant is a Super Key   |
       +---------------------------------------------+
       | 3NF (Third Normal Form)                     |
       | No Transitive Dependencies                  |
       +---------------------------------------------+
       | 2NF (Second Normal Form)                    |
       | No Partial Dependencies                     |
       +---------------------------------------------+
       | 1NF (First Normal Form)                     |
       | Atomic Attributes (No multi-values/repeats) |
       +---------------------------------------------+

4. Step-by-Step Normalization: Solved TU Board Question

The Problem:

“Given the unnormalized relation $R(A, B, C, D, E, F)$ with Candidate Key $AB$ and the set of Functional Dependencies:
– $AB \to C$
– $AB \to D$
– $A \to E$
– $C \to F$

Decompose the relation into 1NF, 2NF, 3NF, and BCNF, clearly showing keys and justifications at each step.” (TU BCA 10 Marks)

Step 1: First Normal Form (1NF)

Rule: A relation is in 1NF if and only if all attribute values are atomic (single-valued) and there are no repeating groups.

• Assuming table $R$ contains atomic scalar values, $R(A, B, C, D, E, F)$ with Composite Primary Key $(\underline{A, B})$ is in 1NF.

Step 2: Second Normal Form (2NF)

Rule: A relation is in 2NF if it is in 1NF and no non-prime attribute is partially dependent on any proper subset of any candidate key.

• Candidate Key: $AB$
• Prime Attributes (part of key): $A, B$
• Non-prime Attributes: $C, D, E, F$

Identify Partial Dependencies:
– Look at $A \to E$: Attribute $E$ depends solely on $A$ (which is only a part of the composite key $AB$). This is a Partial Dependency that violates 2NF!

Decomposition into 2NF:
1. Split out the partial dependency:
$$\mathbf{R_1(\underline{A}, E)} \quad [\text{with Key } A]$$
2. Retain the remaining attributes with the full composite key:
$$\mathbf{R_2(\underline{A, B}, C, D, F)} \quad [\text{with Key } AB]$$

Step 3: Third Normal Form (3NF)

Rule: A relation is in 3NF if it is in 2NF and no non-prime attribute is transitively dependent on the primary key (i.e., for every $X \to Y$, either $X$ is a Super Key or $Y$ is a Prime Attribute).

• Inspect $R_1(\underline{A}, E)$: $A \to E$ ($A$ is a Super Key). $R_1$ is already in 3NF.
• Inspect $R_2(\underline{A, B}, C, D, F)$:
• $AB \to C$ ($AB$ is Super Key $\checkmark$)
• $AB \to D$ ($AB$ is Super Key $\checkmark$)
• $C \to F$ ($C$ is NOT a super key, and $F$ is NOT a prime attribute! This is a Transitive Dependency violating 3NF).

Decomposition into 3NF:
1. Split out the transitive dependency:
$$\mathbf{R_{2a}(\underline{C}, F)} \quad [\text{with Key } C]$$
2. Replace with foreign key link in the main table:
$$\mathbf{R_{2b}(\underline{A, B}, C, D)} \quad [\text{with Key } AB]$$

Final 3NF Relations:
$$\mathbf{R_1(\underline{A}, E)},\quad \mathbf{R_{2a}(\underline{C}, F)},\quad \mathbf{R_{2b}(\underline{A, B}, C, D)}$$

Step 4: Boyce-Codd Normal Form (BCNF)

Rule: A relation is in BCNF (Strict 3NF) if and only if for every non-trivial functional dependency $X \to Y$, $X$ must be a Super Key.

Let’s verify all our 3NF decomposed tables:
1. In $R_1(\underline{A}, E)$: FD is $A \to E$. $A$ is the primary key (Super Key). $\implies$ In BCNF $\checkmark$
2. In $R_{2a}(\underline{C}, F)$: FD is $C \to F$. $C$ is the primary key (Super Key). $\implies$ In BCNF $\checkmark$
3. In $R_{2b}(\underline{A, B}, C, D)$: FDs are $AB \to C, AB \to D$. $AB$ is the composite primary key (Super Key). $\implies$ In BCNF $\checkmark$

$$\mathbf{Final\ BCNF\ Schemas:}\ R_1(\underline{A}, E),\ R_{2a}(\underline{C}, F),\ R_{2b}(\underline{A, B}, C, D)$$

Frequently Asked Questions (FAQ)

Q1: What is the difference between 3NF and BCNF?

In 3NF, for a dependency $X \to Y$, if $X$ is not a super key, the dependency is still permitted as long as $Y$ is a prime attribute (part of a candidate key). In BCNF, this exception is strictly removed: $X$ MUST be a super key, with zero exceptions.

Q2: What is Lossless Join Decomposition?

A decomposition of relation $R$ into $R_1$ and $R_2$ is lossless if joining them back using natural join yields the exact original relation without creating spurious phantom tuples:
$$R_1 \bowtie R_2 = R \iff (R_1 \cap R_2) \to R_1 \text{ or } (R_1 \cap R_2) \to R_2$$