3NF (transitive dependency + formal condition)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What does 2NF forbid? from Lesson 4.4.2
2. What is a minimal cover? from Lesson 4.2.5
3. Is {AC, BC} of R(A, B, C) with {AB → C, C → B} lossless? Preserving? from Lesson 4.3.2

1 · The Hook

STUDENT(roll, name, dept, hod) has key roll, so it is in 2NF. But dept → hod: the head of CS is repeated for every CS student. The non-key fact hod depends on the key only through another non-key attribute. Third normal form forbids this transitive dependency, and its formal rule is the one you will apply in almost every GATE NF question.

2 · Predict First

STUDENT(roll, name, dept, hod), FDs roll → name dept, dept → hod. Is it in 3NF? What should be split out?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

Not in 3NF: dept → hod, where dept is not a superkey and hod is not prime. Split DEPT(dept, hod) out, leaving STUDENT(roll, name, dept).

Transitive dependency

A → C is transitive if A → B and B → C hold, where B is not a superkey and C is non-prime (and B does not determine A). The key reaches C through a non-key attribute.

Third normal form (3NF): the formal condition

R is in 3NF if for every non-trivial FD X → A that holds on R, at least one of these is true:

1. X is a superkey of R, or
2. A is prime (A belongs to some candidate key).

Check it FD by FD (use single-attribute right sides). One FD failing both conditions → not in 3NF.

Why it covers 2NF too

A partial dependency (proper part of a key → non-prime A) fails both conditions, so 3NF ⊂ 2NF. And a transitive dependency (non-key → non-prime) fails both too.

Examples

• R(A, B, C, D), F = {AB → C, C → D, D → A}. Keys AB, BC, BD; all attributes prime. Every FD has a prime right side → 3NF. (Not BCNF: C → D has C not a superkey. Next lesson.)
• R(A, B, C, D), F = {A → B, B → C, C → D}. Key A. B → C: B not a superkey, C non-prime → not 3NF (2NF yes: single-attribute key).
• R(A, B, C, D, E), F = {AB → C, C → D, D → B, D → E}. Keys AB, AC, AD. D → E: D is not a superkey, E is non-prime → not 3NF (in fact not 2NF: D ⊂ AD).

Highest-NF procedure (so far)

1. Find all candidate keys; mark prime attributes.
2. For each FD X → A (single A, non-trivial):
   • X superkey → fine for every form.
   • A prime → fine for 3NF (bad for BCNF).
   • X ⊂ some key and A non-prime → violates 2NF.
   • otherwise (X not a superkey, not a proper part of a key, A non-prime) → violates 3NF but not 2NF.
3. The highest form is the highest whose conditions all FDs meet.

4 · Visual

For each FD  X -> A :

            X is a superkey?
              yes -> OK (BCNF-safe)
              no  -> A prime?
                       yes -> OK for 3NF  (BCNF violation)
                       no  -> X a proper part of a key?
                                yes -> 2NF violation
                                no  -> 3NF violation (transitive)

5 · Worked Examples

Example 1 Easy

R(A, B, C) with F = {A → B, B → C}. Highest normal form?

Solution

Key A. B → C: B not a superkey, C non-prime, B not part of a key → 2NF (not 3NF).

Example 2 Medium

R(A, B, C, D, E) with F = {A → BCDE, BC → A, D → E}. Highest normal form among 2NF and 3NF?

Solution

Keys: A, BC (BC⁺ = ABCDE). Prime: A, B, C. D → E: D not a superkey, E non-prime, D is not part of any key → 3NF violation, but 2NF holds → 2NF.

Example 3 GATE

R(A, B, C, D) with F = {AB → CD, D → A}. Is R in 3NF?

Solution

Keys: AB, and DB (DB⁺ = DBA → C). Prime: A, B, D. Check D → A: D not a superkey, but A is prime → allowed. AB → CD: AB superkey. Yes, 3NF.

8 · Connect the Dots

Lesson 4.4.2 banned dependence on part of a key; this lesson banned dependence on non-key attributes, with the formal "superkey or prime" test. Next: BCNF drops the "or prime" escape, and that small change has a big consequence for dependency preservation.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — 3NF

R(A, B, C) with F = {A → B, B → C}. The highest normal form is:

1. (A) BCNF
2. (B) 1NF
3. (C) 3NF
4. (D) 2NF

Q2 · MCQ · 2 mark(s) — 3NF

R(A, B, C, D) with F = {AB → C, C → D, D → A}. R is in:

1. (A) 2NF but not 3NF
2. (B) 3NF but not BCNF
3. (C) BCNF
4. (D) 1NF only

Q3 · MSQ · 2 mark(s) — Violations

R(A, B, C, D, E) with F = {A → B, A → C, C → D, D → E} and key A. Which FDs violate 3NF?

1. (A) D → E
2. (B) C → D
3. (C) A → C
4. (D) A → B

Q4 · MCQ · 2 mark(s) — Prime escape

R(A, B, C) with F = {AB → C, C → B}. Keys: AB, AC. Is R in 3NF?

1. (A) No, because C → B has a non-superkey left side
2. (B) Yes, because B is prime
3. (C) No, because it has two keys
4. (D) Yes, because it is in BCNF

Q5 · NAT · 2 mark(s) — Counting violations

R(A, B, C, D, E, F) with F = {AB → C, B → D, C → E, A → F}. How many of these four FDs violate 2NF?

Numerical answer: ________

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

transitive dependencythird normal form (3NF)3NF formal condition (superkey or prime)highest normal form procedure