Normalization for GATE CS

GATE normalization questions ask you to spot the highest normal form, find a violating FD, or choose a lossless decomposition. Definitions alone are not enough — work one small relation on paper every time.

Why normalize (anomalies)

On an unnormalized / poorly keyed table you get:

Insert anomaly — cannot store a course without inventing a student
Delete anomaly — deleting the last enrollment loses the course row’s only copy of course data
Update anomaly — course name stored in many rows; one update leaves inconsistency

Normalization splits relations so each fact lives in one place, using functional dependencies.

Functional dependencies

X → Y means each X-value determines at most one Y-value.

Example: SID → Name.

Useful vocabulary:

Trivial: Y ⊆ X
Partial: a proper subset of a composite key determines a non-prime attribute (kills 2NF)
Transitive: X → Y and Y → Z with Y non-prime (kills 3NF when X is a key)

Armstrong axioms (for closures): reflexivity, augmentation, transitivity. GATE may ask “which FD is implied?” — compute attribute closure X+ under F.

Normal forms (checklist)

Form	Extra rule (assuming lower forms hold)
1NF	Attributes atomic (no multi-valued cells)
2NF	No partial dependency of non-prime attrs on a composite key
3NF	No non-prime attribute transitively dependent on a key (equiv: for every FD X→A, X is superkey or A is prime)
BCNF	For every non-trivial FD X→A, X is a superkey

3NF vs BCNF: BCNF is stricter. A relation can be 3NF but not BCNF when a determinant is not a candidate key but the dependent is prime.

Worked: partial dependency (not 2NF)

Enrollment(SID, CID, Name, Grade)

Key: (SID, CID)

FD: SID → Name

Name depends on part of the key → not 2NF.

Split: Student(SID, Name), Enrollment(SID, CID, Grade).

Worked: transitive (not 3NF)

Student(SID, Name, Dept, DeptHead)

SID → Dept, Dept → DeptHead

DeptHead depends on Dept, not directly only on the key → not 3NF.

Split: Student(SID, Name, Dept), Department(Dept, DeptHead).

Worked: BCNF violation

R(SID, CID, Instructor)

(SID, CID) → Instructor, and CID → Instructor

Candidate key: (SID, CID). Determinant CID is not a key → not BCNF (may still be 3NF depending on primes).

Split toward: Course(CID, Instructor), Teaches(SID, CID).

Lossless join

Decompose R into R1, R2. Lossless if R1 ∩ R2 → R1 or R1 ∩ R2 → R2 (intersection is a key for one side). Dependency preservation is a separate ask — GATE sometimes wants both.

Exam habits

List candidate keys first, then classify each FD.
Do not claim BCNF just because you “removed transitive deps.”
For multi-choice, eliminate options that invent FDs not given.

Next: SQL Queries. Timed practice: GATE hub.

GATE CS - DATABASES (DBMS):Normalization