DBMS — Level 2: Normalization¶
1. What is Normalization?¶
Normalization is the process of organizing data in relational databases to:
- Reduce unnecessary data redundancy
- Prevent insertion, update, and deletion anomalies
- Improve data consistency
- Represent independent facts in appropriate relations
The central idea is:
Store each fact in the appropriate place, rather than repeatedly storing the same fact.
Example¶
Suppose we have:
| Student_ID | Student_Name | Course_ID | Course_Name | Instructor | Grade |
|---|---|---|---|---|---|
| 101 | Rahul | C01 | DBMS | Prof A | A |
| 102 | Aman | C01 | DBMS | Prof A | B |
| 103 | Priya | C01 | DBMS | Prof A | A |
The course information:
C01 → DBMS
C01 → Prof A
is repeated for every student.
If the instructor changes, multiple rows must be updated.
Normalization separates these independent facts.
2. Problems Caused by Poorly Designed Relations¶
There are three classic anomalies.
2.1 Update Anomaly¶
The same fact appears in multiple rows, so updating it requires multiple changes.
Example:
| Student | Course | Instructor |
|---|---|---|
| S1 | DBMS | Prof A |
| S2 | DBMS | Prof A |
| S3 | DBMS | Prof A |
If Prof A changes to Prof B, all three rows need updating.
If one row is missed, the database becomes inconsistent.
2.2 Insertion Anomaly¶
A fact cannot be inserted without another unrelated fact.
Example:
COURSE_ENROLLMENT(
Student_ID,
Student_Name,
Course_ID,
Course_Name
)
Suppose we want to add a new course:
C05 → Computer Networks
but no student has enrolled yet.
If the table requires a student for every row, we cannot store the course independently.
2.3 Deletion Anomaly¶
Deleting one fact unintentionally deletes another unrelated fact.
Example:
| Student | Course | Instructor |
|---|---|---|
| S1 | DBMS | Prof A |
| S2 | DBMS | Prof A |
If S1 and S2 are both deleted, we may also lose:
DBMS → Prof A
even though the course itself still exists.
3. Functional Dependency (FD)¶
Functional dependency is the foundation of normalization.
A functional dependency is written as:
X → Y
and means:
If two tuples have the same value for X, they must have the same value for Y.
Formally:
If t1[X] = t2[X]
then t1[Y] = t2[Y]
3.1 Example¶
Suppose:
Student_ID → Student_Name
This means:
A Student_ID uniquely determines a Student_Name.
If:
101 → Rahul
then two rows with:
Student_ID = 101
cannot have different student names under the stated business rule.
3.2 Important: FD is a rule, not an observation¶
Suppose the current data is:
| Employee_ID | Name |
|---|---|
| 1 | Rahul |
| 2 | Aman |
| 3 | Priya |
You should NOT automatically conclude:
Name → Employee_ID
just because all current names happen to be different.
An FD is based on a business/domain rule, not accidental uniqueness in the current dataset.
If the business rule says names are unique, then it can be an FD.
4. Determinant¶
In:
X → Y
X is called the determinant.
Example:
Student_ID → Student_Name
Therefore:
Student_ID = determinant
Student_Name = dependent attribute
A major BCNF rule later will be:
Every determinant must be a superkey.
5. Types of Functional Dependencies¶
5.1 Trivial FD¶
An FD is trivial when:
Y ⊆ X
Example:
(Student_ID, Course_ID) → Student_ID
This is always true because Student_ID is already present on the left.
5.2 Non-trivial FD¶
An FD is non-trivial when:
Y ⊄ X
Example:
Student_ID → Student_Name
Student_Name is not part of Student_ID.
5.3 Completely Non-trivial FD¶
If:
X ∩ Y = ∅
then the FD is completely non-trivial.
Example:
Student_ID → Student_Name
6. Composite Determinant¶
A determinant can contain multiple attributes.
Example:
(Student_ID, Course_ID) → Grade
The determinant is:
(Student_ID, Course_ID)
This is a composite determinant.
This is common when a relationship between two entities has its own attribute.
For example:
Student + Course → Grade
because a student's grade depends on which course they took.
7. Partial Dependency¶
Partial dependency is particularly important for 2NF.
Suppose:
Candidate Key = (A, B)
and:
A → C
where C is a non-prime attribute.
C depends only on part of the composite key.
Therefore:
(A, B) → C
is a partial dependency.
Example¶
Consider:
ENROLLMENT(
Student_ID,
Course_ID,
Student_Name,
Course_Name,
Grade
)
Candidate key:
(Student_ID, Course_ID)
FDs:
Student_ID → Student_Name
Course_ID → Course_Name
(Student_ID, Course_ID) → Grade
Here:
Student_ID → Student_Name
depends on only part of:
(Student_ID, Course_ID)
Similarly:
Course_ID → Course_Name
depends on only part of the key.
These are partial dependencies.
8. Transitive Dependency¶
A transitive dependency occurs when:
A → B
B → C
therefore:
A → C
Example:
Student_ID → Dept_ID
Dept_ID → Dept_Name
Therefore:
Student_ID → Dept_Name
through:
Student_ID → Dept_ID → Dept_Name
This is a transitive dependency.
It is the major dependency issue addressed by 3NF.
9. Armstrong's Axioms¶
Armstrong's axioms are inference rules used to derive functional dependencies.
There are three fundamental axioms.
9.1 Reflexivity¶
If:
Y ⊆ X
then:
X → Y
Example:
(A, B) → A
9.2 Augmentation¶
If:
X → Y
then:
XZ → YZ
Example:
If:
A → B
then:
AC → BC
9.3 Transitivity¶
If:
X → Y
Y → Z
then:
X → Z
Example:
Student_ID → Dept_ID
Dept_ID → Dept_Name
therefore:
Student_ID → Dept_Name
10. Derived Rules¶
The Armstrong axioms allow several useful derived rules.
Union¶
If:
X → Y
X → Z
then:
X → YZ
Example:
Student_ID → Student_Name
Student_ID → Branch
therefore:
Student_ID → Student_Name, Branch
Decomposition¶
If:
X → YZ
then:
X → Y
X → Z
Pseudotransitivity¶
If:
X → Y
WY → Z
then:
WX → Z
These become particularly useful when solving candidate-key and closure problems.
11. Attribute Closure¶
Attribute closure is one of the most important tools for normalization problems.
The closure of X, written:
X+
means:
The complete set of attributes that can be functionally determined by X.
Example¶
Consider:
R(A, B, C, D)
with:
A → B
B → C
C → D
Start:
A+ = {A}
Using:
A → B
we get:
A+ = {A, B}
Using:
B → C
we get:
A+ = {A, B, C}
Using:
C → D
we get:
A+ = {A, B, C, D}
Therefore:
A+ = {A, B, C, D}
Since the closure contains all attributes of R:
A
is a superkey.
If no proper subset of A can determine all attributes, it is a candidate key.
12. Candidate Key Using Closure¶
A set of attributes X is a candidate key if:
X+contains all attributes of the relation.- X is minimal.
Example:
R(A, B, C, D)
FDs:
A → B
B → C
AC → D
Calculate:
A+
Start:
{A}
A → B:
{A, B}
B → C:
{A, B, C}
Now we have A and C, so:
AC → D
Therefore:
A+ = {A, B, C, D}
Hence A is a superkey.
Since A itself is a single attribute, it is minimal.
Therefore:
A = candidate key
13. Prime and Non-Prime Attributes¶
An attribute is prime if it belongs to at least one candidate key.
An attribute is non-prime if it belongs to no candidate key.
Example:
Candidate Key = (A, B)
Then:
A → prime
B → prime
C → non-prime
D → non-prime
This distinction is especially important for the formal definition of 3NF.
14. First Normal Form — 1NF¶
A relation is in 1NF when values are atomic and there are no repeating groups/multivalued cells.
Core idea:
One cell → one value.
Example — violation¶
| Student_ID | Name | Phone |
|---|---|---|
| 101 | Rahul | 9876, 9123 |
| 102 | Aman | 8888 |
The Phone cell for Rahul contains multiple values.
This violates the standard 1NF design principle.
Correct design¶
STUDENT¶
STUDENT(
Student_ID,
Name
)
STUDENT_PHONE¶
STUDENT_PHONE(
Student_ID,
Phone
)
Data:
| Student_ID | Phone |
|---|---|
| 101 | 9876 |
| 101 | 9123 |
| 102 | 8888 |
Now each cell contains one value.
15. Atomicity — Important Interview Nuance¶
"Atomic" does not simply mean:
"A value cannot physically be split."
It means that the value is treated as one meaningful value according to the domain/application.
For example:
Address = "Noida, Uttar Pradesh, India"
may be acceptable as one value if the application treats it as a single address.
But if the application needs to query:
City
State
Country
PIN
then these should generally be modeled separately.
For placement questions:
If an attribute contains multiple independent values, suspect a 1NF violation.
16. 1NF and Multivalued Attributes¶
An ER model may have:
Student
├── Student_ID
├── Name
└── {Phone}
The {Phone} is a multivalued attribute.
Mapping it to relations gives:
STUDENT(
Student_ID,
Name
)
STUDENT_PHONE(
Student_ID,
Phone
)
This naturally produces a 1NF relational representation.
17. Second Normal Form — 2NF¶
A relation is in 2NF if:
- It is in 1NF.
- Every non-prime attribute is fully functionally dependent on every candidate key.
The common interview interpretation:
2NF removes partial dependencies.
17.1 Partial dependency¶
Suppose:
Candidate Key = (A, B)
and:
A → C
where C is non-prime.
C depends on only part of the key.
Therefore:
Partial dependency exists.
So the relation violates 2NF.
18. Classic 2NF Example¶
Consider:
ENROLLMENT(
Student_ID,
Course_ID,
Student_Name,
Course_Name,
Instructor,
Grade
)
Candidate key:
(Student_ID, Course_ID)
FDs:
Student_ID → Student_Name
Course_ID → Course_Name
Course_ID → Instructor
(Student_ID, Course_ID) → Grade
The first three dependencies are partial dependencies.
Therefore:
ENROLLMENT
is not in 2NF.
19. Decomposition to 2NF¶
Create:
STUDENT¶
STUDENT(
Student_ID PK,
Student_Name
)
COURSE¶
COURSE(
Course_ID PK,
Course_Name,
Instructor
)
ENROLLMENT¶
ENROLLMENT(
Student_ID FK,
Course_ID FK,
Grade,
PRIMARY KEY(Student_ID, Course_ID)
)
Now each non-key fact is stored with the attributes it actually depends on.
20. Important 2NF Shortcut¶
If every candidate key is a single attribute, a 1NF relation is automatically in 2NF.
Why?
Partial dependency requires a proper subset of a composite key.
A single attribute key has no proper non-empty subset that can act as part of the key.
Therefore:
1NF + only single-attribute candidate keys
↓
automatically 2NF
21. Third Normal Form — 3NF¶
A relation is in 3NF if it is in 2NF and has no problematic transitive dependency.
The common interview version:
3NF removes transitive dependencies.
21.1 Example¶
Consider:
STUDENT(
Student_ID,
Student_Name,
Dept_ID,
Dept_Name
)
FDs:
Student_ID → Student_Name
Student_ID → Dept_ID
Dept_ID → Dept_Name
Therefore:
Student_ID → Dept_Name
through:
Student_ID → Dept_ID → Dept_Name
This is a transitive dependency.
22. Decomposition to 3NF¶
Create:
STUDENT¶
STUDENT(
Student_ID PK,
Student_Name,
Dept_ID FK
)
DEPARTMENT¶
DEPARTMENT(
Dept_ID PK,
Dept_Name
)
Now department information is stored only once.
23. Formal Definition of 3NF¶
For every non-trivial functional dependency:
X → A
at least one of the following must be true:
Condition 1¶
X is a superkey
OR:
Condition 2¶
A is a prime attribute
Therefore:
3NF:
X → A
X = superkey
OR
A = prime attribute
This formal definition is important because:
"3NF means simply no transitive dependency"
is useful intuition but not the complete mathematical definition.
24. BCNF — Boyce-Codd Normal Form¶
BCNF is stricter than 3NF.
Definition:
For every non-trivial FD
X → Y, X must be a superkey.
In other words:
Every determinant must be a superkey.
Compare:
3NF¶
X → A
X is superkey
OR
A is prime
BCNF¶
X → A
X MUST be superkey
Therefore:
BCNF ⟹ 3NF
but:
3NF ⇏ BCNF
25. Classic 3NF but Not BCNF Example¶
Consider:
TEACHING(
Student,
Course,
Instructor
)
Assume:
- A student can take multiple courses.
- Each instructor teaches only one course.
- A course can have multiple instructors.
FDs:
(Student, Course) → Instructor
Instructor → Course
Candidate keys are:
(Student, Course)
(Student, Instructor)
Therefore all three attributes are prime.
Now consider:
Instructor → Course
Instructor is not a superkey because it does not identify a student.
But Course is prime.
Therefore the FD satisfies 3NF.
However, BCNF requires the determinant itself to be a superkey.
Instructor is not.
Therefore:
3NF ✅
BCNF ❌
This is the classic distinction between 3NF and BCNF.
26. BCNF Decomposition¶
Original:
TEACHING(
Student,
Course,
Instructor
)
with:
Instructor → Course
Decompose into:
INSTRUCTOR_COURSE¶
INSTRUCTOR_COURSE(
Instructor,
Course
)
STUDENT_INSTRUCTOR¶
STUDENT_INSTRUCTOR(
Student,
Instructor
)
The problematic dependency now has its determinant as a key in the relevant relation.
27. How to Check BCNF¶
Given:
A → B
BC → D
D → E
Do not just look at the relation visually.
Use this procedure:
Step 1¶
Find all candidate keys.
Step 2¶
List all non-trivial FDs.
Step 3¶
For each FD:
X → Y
check:
Is X a superkey?
If even one non-trivial FD has:
X = not a superkey
then:
❌ Not BCNF
28. Multivalued Dependency — MVD¶
A multivalued dependency is represented as:
X →→ Y
It describes a situation where the values of Y are independently associated with X, regardless of the remaining attributes.
The key intuition:
MVD represents an independent set of multiple values.
29. MVD Example¶
Consider:
STUDENT(
Student,
Hobby,
Language
)
Suppose Rahul has:
Hobbies:
Cricket
Music
and:
Languages:
English
Hindi
and the hobbies and languages are independent.
The table may become:
| Student | Hobby | Language |
|---|---|---|
| Rahul | Cricket | English |
| Rahul | Cricket | Hindi |
| Rahul | Music | English |
| Rahul | Music | Hindi |
There are:
2 hobbies × 2 languages = 4 rows
The combinations are generated because the two multivalued facts are independent.
30. Meaning of Student →→ Hobby¶
It means:
For a given Student, the set of Hobby values is independent of the values of the other attributes.
Similarly:
Student →→ Language
under the same independence assumption.
31. MVD vs FD¶
This distinction is important.
Functional Dependency¶
Student → Department
Means:
One Student has exactly one Department under the business rule.
Multivalued Dependency¶
Student →→ Hobby
Means:
One Student can have multiple Hobby values independently of another attribute set.
Simplified memory aid:
FD → one determined value
MVD → independently determined set of values
32. Fourth Normal Form — 4NF¶
4NF handles multivalued dependencies.
Definition:
A relation is in 4NF if for every non-trivial MVD
X →→ Y, X is a superkey.
Compare:
BCNF → handles problematic FDs
4NF → handles problematic MVDs
33. 4NF Example¶
Consider:
STUDENT(
Student,
Hobby,
Language
)
with:
Student →→ Hobby
If Student is not a superkey of the original relation, this violates 4NF.
Decompose into:
STUDENT_HOBBY¶
STUDENT_HOBBY(
Student,
Hobby
)
STUDENT_LANGUAGE¶
STUDENT_LANGUAGE(
Student,
Language
)
Now the independent multivalued facts are stored separately.
34. Normalization Hierarchy¶
The overall sequence:
Functional Dependencies
↓
Candidate Keys
↓
1NF
↓
2NF
↓
3NF
↓
BCNF
↓
4NF
The main issue addressed by each:
| Normal Form | Main Problem |
|---|---|
| 1NF | Non-atomic / repeating values |
| 2NF | Partial dependency |
| 3NF | Transitive dependency |
| BCNF | Non-superkey determinant |
| 4NF | Multivalued dependency |
35. Denormalization¶
Normalization isn't always taken to the theoretical maximum.
Denormalization means:
Intentionally introducing controlled redundancy to improve performance or simplify read-heavy workloads.
Why denormalize?¶
1. Faster reads¶
Fewer joins may be required.
2. Reporting/analytics¶
Frequently accessed data can be stored in a read-optimized form.
3. Read-heavy systems¶
If data is:
read millions of times
updated very rarely
some redundancy may be worthwhile.
4. Distributed architectures¶
Sometimes joining data across services/databases is expensive or undesirable.
36. Cost of Denormalization¶
Denormalization introduces:
- More storage
- Duplicate data
- More complicated updates
- Greater consistency risk
- Potential synchronization logic
Example:
If:
Customer_Name = Rahul
is duplicated across 10,000 order records, changing Rahul's name may require updating many records or maintaining a separate synchronization mechanism.
37. Normalization vs Denormalization¶
| Normalization | Denormalization |
|---|---|
| Reduces redundancy | Intentionally adds redundancy |
| Improves consistency | Can increase consistency complexity |
| Reduces anomalies | Can reintroduce redundancy/anomalies |
| More joins may be required | Fewer joins may be required |
| Good default design approach | Usually workload-driven |
| Often write-friendly | Can be read-performance-oriented |
A strong interview answer:
Start with a normalized design for correctness and maintainability. Denormalize selectively when measured workload requirements justify the additional redundancy and consistency cost.
38. Normalization Decision Process¶
When given a normalization problem in an interview/exam, follow this exact process.
Step 1 — Identify all attributes¶
Write:
R(A, B, C, D, E)
Step 2 — Identify functional dependencies¶
Example:
A → B
C → D
AC → E
Step 3 — Find candidate keys¶
Use attribute closure.
For example:
A+
and:
AC+
Determine which sets determine all attributes.
Step 4 — Identify prime/non-prime attributes¶
Prime:
Part of at least one candidate key.
Non-prime:
Part of no candidate key.
Step 5 — Check 1NF¶
Ask:
Are values atomic?
Are there repeating groups?
Are multiple independent values stored in one cell?
Step 6 — Check 2NF¶
Ask:
Is there a non-prime attribute
dependent on only part of a composite candidate key?
If yes:
❌ Not 2NF
Step 7 — Check 3NF¶
For each non-trivial FD:
X → A
check:
X is superkey?
OR
A is prime?
If neither:
❌ Not 3NF
Step 8 — Check BCNF¶
For every non-trivial FD:
X → Y
ask:
Is X a superkey?
If not:
❌ Not BCNF
Step 9 — Check MVDs / 4NF¶
Look for:
X →→ Y
where Y is independently multivalued.
Then check:
Is X a superkey?
If not:
❌ Not 4NF
39. Most Important Interview Traps¶
Trap 1 — "Primary key" instead of "candidate key"¶
Normalization definitions are generally based on candidate keys, not merely the declared primary key.
Trap 2 — 2NF matters only with composite candidate keys¶
If all candidate keys are single attributes:
1NF ⇒ 2NF
Trap 3 — 3NF is not simply "no transitive dependency"¶
The formal definition is:
For every non-trivial X → A:
X is superkey
OR
A is prime
Trap 4 — BCNF is not the same as 3NF¶
Remember:
BCNF ⟹ 3NF
3NF ⇏ BCNF
Trap 5 — Every determinant must be a superkey only in BCNF¶
For BCNF:
X → Y
requires:
X = superkey
Trap 6 — FD is not based on current data accidentally¶
Don't infer:
Name → Employee_ID
just because names are currently unique.
It must be a domain/business rule.
Trap 7 — Composite key ≠ candidate key¶
"Composite" describes the number of attributes.
"Candidate" describes minimality and uniqueness.
A candidate key can be:
A
or:
(A, B)
Trap 8 — MVD and FD are different¶
X → Y
means a functional determination.
X →→ Y
means an independent multivalued relationship.
Trap 9 — Denormalization is not bad database design by definition¶
Denormalization can be legitimate when there is a clear performance/workload reason.
The key is:
Controlled, intentional redundancy.
40. Quick Comparison Table¶
| Concept | Meaning |
|---|---|
| Super Key | Uniquely identifies a tuple |
| Candidate Key | Minimal superkey |
| Prime Attribute | Part of a candidate key |
| FD | X determines Y |
| MVD | X determines an independent set of Y values |
| 1NF | Atomic values |
| 2NF | No partial dependency |
| 3NF | X superkey OR RHS prime for every non-trivial FD |
| BCNF | X must be superkey for every non-trivial FD |
| 4NF | X must be superkey for every non-trivial MVD |
| Denormalization | Deliberate redundancy for a justified benefit |
41. One-Page Revision Summary¶
NORMALIZATION
│
├── Goal
│ ├── Reduce redundancy
│ ├── Avoid anomalies
│ └── Improve consistency
│
├── Functional Dependency
│ └── X → Y
│ Same X ⇒ same Y
│
├── Attribute Closure
│ └── X+ = all attributes determined by X
│
├── Candidate Key
│ └── Minimal X such that X+ = all attributes
│
├── 1NF
│ └── Atomic values
│
├── 2NF
│ ├── Must be 1NF
│ └── No partial dependency
│
├── 3NF
│ ├── Must be 2NF
│ └── For every non-trivial X → A:
│ X is superkey OR A is prime
│
├── BCNF
│ └── For every non-trivial X → Y:
│ X must be superkey
│
├── MVD
│ └── X →→ Y
│ Independent multivalued relationship
│
├── 4NF
│ └── For every non-trivial MVD:
│ X must be superkey
│
└── Denormalization
└── Controlled redundancy for performance
42. Final Placement Mental Model¶
When you see a normalization question, think:
GIVEN RELATION
│
↓
Find Functional Dependencies
│
↓
Find Candidate Keys
│
↓
┌─────────────────────┐
│ Is it in 1NF? │
└──────────┬──────────┘
↓
┌─────────────────────┐
│ Partial dependency? │
└──────────┬──────────┘
↓
2NF
↓
┌─────────────────────┐
│ Transitive / 3NF? │
└──────────┬──────────┘
↓
3NF
↓
┌─────────────────────┐
│ Every determinant │
│ is a superkey? │
└──────────┬──────────┘
↓
BCNF
↓
┌─────────────────────┐
│ Any problematic MVD?│
└──────────┬──────────┘
↓
4NF
The four phrases worth memorizing¶
1NF → Atomicity
2NF → No partial dependency
3NF → No problematic transitive dependency
BCNF → Every determinant is a superkey
4NF → Every non-trivial MVD has a superkey determinant
And the most important relationship:
BCNF ⟹ 3NF ⟹ 2NF ⟹ 1NF
but the reverse implications do not generally hold.