Normalisation: 3NF and BCNF
50 min · Advanced
Need help? Ask a tutor on WhatsApp (opens in a new tab)"Is this table in 3NF? What about BCNF?" is the classic follow-up once 2NF is done. The interviewer checks that you can test each FD against the rule and explain the one case where the two forms differ.
Transitive dependencies and 3NF
A table is in third normal form (3NF) when it is in 2NF and has no transitive dependency. Formally, for every non-trivial FD X → A, either X is a super key or A is a prime attribute.
In employee(emp_id, dept_id, dept_name), the department name repeats for every employee in that department. The program checks each FD against the 3NF rule.
Example 1 · Checking 3NF with a normal-form checker
from itertools import combinations
def closure(attrs, fds): result = set(attrs) changed = True while changed: changed = False for lhs, rhs in fds: if set(lhs) <= result and not set(rhs) <= result: result |= set(rhs) changed = True return result
def candidate_keys(attrs, fds): keys = [] for size in range(1, len(attrs) + 1): for subset in combinations(attrs, size): # A key determines every attribute, and no smaller key sits inside it. if closure(subset, fds) == set(attrs) and not any(set(k) <= set(subset) for k in keys): keys.append("".join(subset)) return keys
def highest_normal_form(attrs, fds): keys = candidate_keys(attrs, fds) prime = set("".join(keys)) # attributes that sit in some key is_2nf = is_3nf = is_bcnf = True for lhs, rhs in fds: for a in rhs: if a in lhs: # trivial dependency continue super_key = closure(lhs, fds) == set(attrs) if not super_key: is_bcnf = False if a not in prime: is_3nf = False if a not in prime and any(set(lhs) < set(k) for k in keys): is_2nf = False # part of a key decides a non-key attribute if is_bcnf: nf = "BCNF" elif is_3nf: nf = "3NF (not BCNF)" elif is_2nf: nf = "2NF (not 3NF)" else: nf = "1NF (not 2NF)" return f"keys {{{', '.join(keys)}}} -> {nf}"
def check(label, attrs, fds): print(f"{label}: {highest_normal_form(attrs, fds)}")
# E = emp_id, D = dept_id, N = dept_namecheck("employee(E, D, N)", "EDN", [("E", "D"), ("D", "N")])check("employee(E, D)", "ED", [("E", "D")])check("department(D, N)", "DN", [("D", "N")])employee(E, D, N): keys {E} -> 2NF (not 3NF)
employee(E, D): keys {E} -> BCNF
department(D, N): keys {D} -> BCNFWhat this code does
- The checker finds candidate keys with closures and tests every FD: D → N has a non-key left side and a non-prime right side, which is exactly a transitive dependency, so the table stops at 2NF.
- After splitting into employee(E, D) and department(D, N), each FD's left side is a key, so both pieces reach BCNF.
A transitive dependency is a chain key → X → A where X is not a key and A is non-prime: here emp_id → dept_id and dept_id → dept_name. The fix moves the tail of the chain into its own table: department(dept_id, dept_name), with dept_id kept as a foreign key in employee. Revise: Second and third normal form (opens in a new tab).
Predict the output
Test the 3NF rule
Check each FD against the rule and pick the answer.
Round 1 of 3
Which FD violates 3NF?
BCNF and how it differs from 3NF
Boyce-Codd normal form (BCNF) is the stricter rule: for every non-trivial FD X → A, X must be a super key. There is no exception for prime attributes. Every BCNF table is in 3NF, but not every 3NF table is in BCNF.
In teaches(student, course, instructor), each instructor teaches one course. The program tests this table: it passes 3NF but fails BCNF.
Example 2 · A table in 3NF but not in BCNF
from itertools import combinations
def closure(attrs, fds): result = set(attrs) changed = True while changed: changed = False for lhs, rhs in fds: if set(lhs) <= result and not set(rhs) <= result: result |= set(rhs) changed = True return result
def candidate_keys(attrs, fds): keys = [] for size in range(1, len(attrs) + 1): for subset in combinations(attrs, size): # A key determines every attribute, and no smaller key sits inside it. if closure(subset, fds) == set(attrs) and not any(set(k) <= set(subset) for k in keys): keys.append("".join(subset)) return keys
def highest_normal_form(attrs, fds): keys = candidate_keys(attrs, fds) prime = set("".join(keys)) # attributes that sit in some key is_2nf = is_3nf = is_bcnf = True for lhs, rhs in fds: for a in rhs: if a in lhs: # trivial dependency continue super_key = closure(lhs, fds) == set(attrs) if not super_key: is_bcnf = False if a not in prime: is_3nf = False if a not in prime and any(set(lhs) < set(k) for k in keys): is_2nf = False # part of a key decides a non-key attribute if is_bcnf: nf = "BCNF" elif is_3nf: nf = "3NF (not BCNF)" elif is_2nf: nf = "2NF (not 3NF)" else: nf = "1NF (not 2NF)" return f"keys {{{', '.join(keys)}}} -> {nf}"
def check(label, attrs, fds): print(f"{label}: {highest_normal_form(attrs, fds)}")
# S = student, C = course, I = instructorfds = [("SC", "I"), ("I", "C")]check("teaches(S, C, I)", "SCI", fds)check("after split: (I, C)", "IC", [("I", "C")])check("after split: (S, I)", "SI", [])teaches(S, C, I): keys {SC, SI} -> 3NF (not BCNF)
after split: (I, C): keys {I} -> BCNF
after split: (S, I): keys {SI} -> BCNFWhat this code does
- Keys are SC and SI, so C and I are both prime. I → C passes 3NF (C is prime) but fails BCNF (I is not a super key).
- Splitting into (I, C) and (S, I) reaches BCNF, but the FD SC → I now spans two tables, so it is no longer preserved.
The keys are (student, course) and (student, instructor). The FD instructor → course passes 3NF because course is prime, but fails BCNF because instructor is not a super key. Compare the two rules:
- 3NF: X is a super key, or A is prime.
- BCNF: X is a super key. Full stop.
- Gap: only possible with two or more overlapping composite candidate keys.
- Trade-off: BCNF may lose an FD; 3NF can always keep every FD.
Find the bug
Find the wrong claim
Each list has one wrong line. Tap it.
A learner analyses R(A, B, C) with FDs AB → C and C → B.
Round 1 of 2Lossless join and dependency preservation
A decomposition has the lossless-join property when joining the pieces gives back exactly the original table, with no missing and no extra (spurious) rows. For two pieces, the common attributes must be a key of at least one piece.
Splitting a table is only safe if you can rebuild the original. The program tests whether two pieces join back without losing or inventing rows.
Example 3 · Testing lossless join for two pieces
def closure(attrs, fds): result = set(attrs) changed = True while changed: changed = False for lhs, rhs in fds: if set(lhs) <= result and not set(rhs) <= result: result |= set(rhs) changed = True return result
def test(r1, r2, fds): common = [c for c in r1 if c in r2] cl = closure(common, fds) # Lossless if the common attributes determine all of one piece. lossless = set(r1) <= cl or set(r2) <= cl print(f"{r1} + {r2}: common {{{''.join(common)}}}, closure {{{''.join(sorted(cl))}}} -> " f"{'lossless' if lossless else 'LOSSY'}")
fds = [("A", "B"), ("B", "C")] # R(A, B, C)test("AB", "BC", fds)test("AC", "BC", fds)test("AB", "AC", fds)AB + BC: common {B}, closure {BC} -> lossless
AC + BC: common {C}, closure {C} -> LOSSY
AB + AC: common {A}, closure {ABC} -> losslessWhat this code does
- AB + BC: the common attribute B determines C, so B is a key of BC and the join cannot create extra rows.
- AC + BC: the common attribute C determines nothing else, so joining can pair rows wrongly and produce extra (spurious) rows.
Dependency preservation means every original FD can be checked inside a single piece, without a join; losing an FD means the database can no longer enforce it cheaply. A 3NF decomposition that is both lossless and dependency-preserving always exists. BCNF is always achievable losslessly, but sometimes only by giving up an FD, as in the teaches example.
Predict the output
Is the split lossless?
Check the common attributes and pick the answer.
Round 1 of 2
Is this split lossless?
Denormalisation and when it is used
Denormalisation is deliberately adding redundancy back to a normalised design, such as storing an order total or a customer name where it could be derived, to make frequent reads faster. It trades storage and upkeep for simpler, faster reads.
A dashboard shows each order with its customer name and total, thousands of times a minute. The example shows a denormalised report table and the cost of keeping it in sync.
Example 4 · A denormalised report table
Normalised (3NF): orders(order_id, customer_id, order_date) order_item(order_id, product_id, qty, unit_price) customer(customer_id, name, city)Dashboard query, run thousands of times a day: total per order + customer name + city -> 3-table join + SUM every timeDenormalised read table:
order_summary(order_id, order_date, customer_name, city, order_total)
Gains: one-table read, no join, no SUM at read time
Costs: name/city/total stored twice; must be updated when an item or
customer changes (in the same transaction, a trigger or a nightly job)
Rule: normalise first, denormalise only measured hot pathsWhat this code does
- The source of truth stays normalised; the summary table is a copy built for one frequent query.
- Interviewers want both sides: why it is faster, and what you must do to keep it correct.
Denormalisation is common in reporting tables, read-heavy dashboards, caches and NoSQL document stores. Make it a measured decision after normalising, kept consistent with transactions, triggers or batch jobs, not an excuse to skip design. Revise: When to denormalise (opens in a new tab).
Order of execution
Denormalise responsibly
Tap the steps in the order a careful team follows.
Worked decomposition example
The hostel table chains roll_no → room_no → block → warden. The program shows it before and after the split into three tables.
Example 5 · The hostel table, before and after
from itertools import combinations
def closure(attrs, fds): result = set(attrs) changed = True while changed: changed = False for lhs, rhs in fds: if set(lhs) <= result and not set(rhs) <= result: result |= set(rhs) changed = True return result
def candidate_keys(attrs, fds): keys = [] for size in range(1, len(attrs) + 1): for subset in combinations(attrs, size): # A key determines every attribute, and no smaller key sits inside it. if closure(subset, fds) == set(attrs) and not any(set(k) <= set(subset) for k in keys): keys.append("".join(subset)) return keys
def highest_normal_form(attrs, fds): keys = candidate_keys(attrs, fds) prime = set("".join(keys)) # attributes that sit in some key is_2nf = is_3nf = is_bcnf = True for lhs, rhs in fds: for a in rhs: if a in lhs: # trivial dependency continue super_key = closure(lhs, fds) == set(attrs) if not super_key: is_bcnf = False if a not in prime: is_3nf = False if a not in prime and any(set(lhs) < set(k) for k in keys): is_2nf = False # part of a key decides a non-key attribute if is_bcnf: nf = "BCNF" elif is_3nf: nf = "3NF (not BCNF)" elif is_2nf: nf = "2NF (not 3NF)" else: nf = "1NF (not 2NF)" return f"keys {{{', '.join(keys)}}} -> {nf}"
def check(label, attrs, fds): print(f"{label}: {highest_normal_form(attrs, fds)}")
# R = roll_no, N = name, M = room_no, B = block, W = wardencheck("hostel(R, N, M, B, W)", "RNMBW", [("R", "N"), ("R", "M"), ("M", "B"), ("B", "W")])check("student(R, N, M)", "RNM", [("R", "N"), ("R", "M")])check("room(M, B)", "MB", [("M", "B")])check("block(B, W)", "BW", [("B", "W")])hostel(R, N, M, B, W): keys {R} -> 2NF (not 3NF)
student(R, N, M): keys {R} -> BCNF
room(M, B): keys {M} -> BCNF
block(B, W): keys {B} -> BCNFWhat this code does
- The original table has one key, R, so it is in 2NF, but M → B and B → W are transitive dependencies, so it fails 3NF.
- Each of the three pieces has every FD starting at its key, so all are in BCNF; every original FD lives in one piece (dependency-preserving).
The only key is roll_no, so the table is in 2NF, but roll_no → room_no → block → warden are transitive dependencies, so it is not in 3NF. Decompose along the chain: student(roll_no, name, room_no), room(room_no, block), block(block, warden).
Each piece has one key and every FD's left side is that key, so all three are in BCNF. The common attributes (room_no, block) are keys of the second and third tables, so the decomposition is lossless, and every FD lives in one table.
Next step
Check your understanding
12 quick questions