BCNF vs 3NF: 6 Solved Problems on Decomposition and Dependency Preservation
A relation is in BCNF if, for every non-trivial dependency X -> Y, X is a superkey. It is in 3NF if, for every such dependency, X is a superkey or every attribute of Y is a prime attribute (part of some candidate key). So BCNF is the stricter rule. 3NF allows one extra case, and that case is where most exam questions hide.
This worksheet has six original solved problems on checking normal forms, decomposing into BCNF, building a 3NF design, and testing lossless join and dependency preservation. Self-tests with answers are at the end. If candidate keys are new to you, first do the candidate keys and attribute closure worksheet. More DBMS sets are the SQL output questions and the serializability worksheet. All are on the Exam Numericals Hub.
1. Rules you need
- Closure X+: all attributes you can reach from X using the dependencies. X is a superkey if X+ is every attribute of R.
- Prime attribute: belongs to at least one candidate key.
- 3NF test: for each X -> A, either X is a superkey or A is prime.
- BCNF test: for each X -> A, X must be a superkey. No exception.
- BCNF decomposition: if X -> Y violates BCNF, split R into (X+) and (R - X+ + X). Repeat on each part.
- Lossless join (two parts R1, R2): lossless if (R1 intersect R2) -> R1 or (R1 intersect R2) -> R2 holds. For more parts use the chase table.
- Dependency preserving: every original dependency can be derived from the dependencies that sit inside the separate tables.
Choose a design: constraints first
Assume 1NF and exactly the stated functional dependencies throughout. A normal form is a schema property under those dependencies, not a conclusion from a few sample rows. A candidate key is a minimal superkey; a prime attribute belongs to any candidate key, not just the chosen primary key.
For a non-trivial X -> A | +-- X is a superkey? -- yes --> BCNF accepts | 3NF accepts no | +-- A is prime? ------ yes --> 3NF accepts | BCNF rejects no v 3NF and BCNF reject After EVERY decomposition: 1. Lossless? No spurious joined rows 2. Preserved? Enforce F via local tables
| Property | BCNF decomposition | 3NF synthesis |
|---|---|---|
| Normal-form guarantee | BCNF (also 3NF) | 3NF; may also be BCNF |
| Lossless guarantee | Yes, recursive FD splits | Yes, with key-table step |
| Dependency preservation | Not guaranteed | Guaranteed with minimal cover |
| Required work | Project F+ onto each part | Minimal cover; remove contained tables; include a key |
Two properties, two separate questions
Problem 2/3: R(A,B,C), AB -> C, C -> B
split on C -> B
+-----+
R1(C,B) R2(A,C)
C is key AC is key
shared C determines R1: LOSSLESS
local AB+ stays AB: NOT PRESERVEDLosslessness asks whether projecting a legal relation and joining the projections recovers exactly that relation. Preservation asks whether local constraints imply all original dependencies without joining tables. One does not prove the other.
2. Six solved problems
Problem 1: Find the highest normal form
R(A, B, C, D) with F = {AB -> C, C -> D}.
Keys: AB+ = {A, B, C, D}, so AB is a key. A+ = {A} and B+ = {B}, so nothing smaller works. The only candidate key is AB. Prime attributes: A, B. Non-prime: C, D.
Check AB -> C: AB is a superkey, fine. Check C -> D: C+ = {C, D} is not everything, so C is not a superkey. D is not prime. This breaks 3NF and BCNF. It is not a partial dependency (C is not part of a key), so 2NF holds.
Fix with BCNF: take C -> D. C+ = {C, D}. Split into R1(C, D) and R2(A, B, C). Common attribute C, and C -> D holds in R1, so the join is lossless. Both dependencies stay inside a table (C -> D in R1, AB -> C in R2), so it is dependency preserving too.
Problem 2: In 3NF but not in BCNF
R(A, B, C) with F = {AB -> C, C -> B}.
AB+ = {A, B, C}. AC+ = {A, C, B} (C -> B gives B). A+ = {A}. So the candidate keys are AB and AC. Prime attributes: A, B, C (every attribute).
C -> B: C is not a superkey (C+ = {C, B}). But B is prime, so 3NF allows it. BCNF does not, because C is not a superkey.
Problem 3: Decompose into BCNF, and test the result
Decompose the relation of Problem 2 into BCNF. Is it lossless? Is it dependency preserving?
Violating dependency: C -> B. C+ = {C, B}. Split into R1(C, B) and R2(A, C) (R minus C+ is A, plus C).
Lossless? R1 intersect R2 = {C}. C -> B and R1 = {C, B}, so C determines all of R1. Yes, lossless.
Dependency preserving? C -> B sits in R1. But AB -> C needs A, B and C together, and no table has A and B. Test it with the closure method: start with Z = {A, B}. In R1 = {C, B}: the part of Z in R1 is {B}, B+ = {B}, nothing new. In R2 = {A, C}: the part of Z in R2 is {A}, A+ = {A}, nothing new. Z stays {A, B}, C is never reached.
Problem 4: A longer BCNF decomposition
R(A, B, C, D, E) with F = {A -> B, B -> C, D -> E}. Find the key and decompose into BCNF.
A+ = {A, B, C}. D+ = {D, E}. AD+ = {A, B, C, D, E}. The only candidate key is AD. Both A -> B and the others have left sides that are not superkeys, so R is not in BCNF.
Step 1: use A -> B. A+ = {A, B, C}. Split into R1(A, B, C) and R2(A, D, E).
Step 2: in R1, B -> C violates BCNF (key of R1 is A). B+ = {B, C}. Split R1 into (B, C) and (A, B).
Step 3: in R2(A, D, E), D -> E violates (key is AD). D+ = {D, E}. Split into (D, E) and (A, D).
Problem 5: 3NF synthesis, and a lossless check with the chase
R(A, B, C, D, E) with F = {AB -> C, C -> D, D -> E}. Give a lossless, dependency preserving 3NF design.
F is already minimal. The only key is AB (AB+ = A, B, C, D, E). Make one table for each dependency: R1(A, B, C), R2(C, D), R3(D, E). A candidate key (AB) is inside R1, so no extra table is needed.
Check each table: R1 has key AB. R2 has C -> D, C is its key. R3 has D -> E, D is its key. All are in 3NF (also BCNF here).
Now check the join with the chase. Rows: R1 = (a, b, c, d1, e1), R2 = (a2, b2, c, d, e2), R3 = (a3, b3, c3, d, e). Here small letters with a number are unknown values and a, b, c, d, e are the real ones. Use C -> D: rows R1 and R2 share c, so R1 gets d. Use D -> E: rows R1, R2 and R3 now share d, so R1 gets e. Row R1 becomes (a, b, c, d, e), all real values.
Problem 6: Lossless but not dependency preserving, and the reverse
(a) R(A, B, C, D) with F = {B -> C, C -> D} is split into AB, BC, CD. Is it lossless?
Chase rows: AB = (a, b, c1, d1), BC = (a2, b, c, d2), CD = (a3, b3, c, d). B -> C: rows AB and BC share b, so AB gets c. C -> D: rows AB, BC and CD share c, so all three get d. Row AB is (a, b, c, d), all real values. Lossless.
(b) R(A, B, C, D) with F = {A -> B, C -> D} is split into AB and CD. Is it lossless?
AB and CD share no attribute. The common part is empty, and nothing is determined by it. No row can become all real values. Not lossless. The join of AB and CD is a cross product and creates extra rows. But A -> B is in AB and C -> D is in CD, so the split does preserve dependencies.
Read a chase table without guessing
Use one distinguished symbol per column (aA, aB, ...). Each missing cell starts with its own b symbol. For each X -> Y, rows matching on X must match on Y. Replace symbols everywhere, preferring a distinguished symbol in its column. Repeat until nothing changes. Any all-distinguished row proves losslessness.
| Problem 5 row | A | B | C | D | E |
|---|---|---|---|---|---|
| ABC start | aA | aB | aC | b1D | b1E |
| CD start | b2A | b2B | aC | aD | b2E |
| DE start | b3A | b3B | b3C | aD | aE |
| ABC after C -> D | aA | aB | aC | aD | b1E |
| ABC after D -> E | aA | aB | aC | aD | aE |
For Test C, legal original rows (a1,b,c1) and (a2,b,c2) satisfy A -> B. Joining AB with BC also produces (a1,b,c2) and (a2,b,c1). These are concrete spurious rows, so the split is lossy even though A -> B stays enforceable in AB.
3. Common mistakes
- Skipping implied dependencies when decomposing. For each new table, use the projection of F+ onto that table, not merely the written dependencies whose attributes fit. A cover of F is enough to test the original relation, but projected covers must be found for its parts.
- Saying a relation is in BCNF because it is in 3NF. BCNF is stricter.
- Forgetting the 3NF exception: X -> A is allowed if A is prime, even when X is not a superkey.
- Testing dependency preservation by looking only at whether each attribute appears in a table. Use the closure method inside the tables.
- Calling a split lossless because the tables share some attribute. The shared attributes must determine one of the two tables.
- Skipping the key-table step in 3NF synthesis. After using a minimal cover, combine equal determinants if desired and remove contained tables. Add a table containing a candidate key only if no retained table already contains one; a key-only table is valid and may be necessary.
4. Self-tests
Test A. R(A, B, C) with F = {A -> B, B -> C}. Which is the highest normal form? Decompose it.
Test B. R(A, B, C) with F = {A -> B, A -> C}. Is it in BCNF?
Test C. R(A, B, C) with F = {A -> B} is split into AB and BC. Is it lossless?
Answers. A: key is A (A+ = A, B, C). B -> C has a non-superkey left side and C is not prime, so it is in 2NF but not 3NF. BCNF split on B -> C: (B, C) and (A, B). Lossless and dependency preserving. B: A+ = {A, B, C}, so A is a key and every dependency has a superkey on the left. Yes, it is in BCNF. C: the shared attribute is B. B+ = {B}, which is neither AB nor BC. Not lossless, the join can create false rows.
Run the checks yourself
Python 3, no packages. This small-schema verifier enumerates subsets to find minimal keys and projected dependencies, tests normal forms, checks preservation through local closures, and chases each decomposition. Exhaustive enumeration is useful for these four- and five-attribute exercises, not a scalable production schema tool.
from itertools import combinations
def subsets(attrs):
attrs = sorted(attrs)
for size in range(len(attrs) + 1):
for group in combinations(attrs, size):
yield frozenset(group)
def closure(x, fds):
out = set(x)
while True:
old = out.copy()
for left, right in fds:
if set(left) <= out:
out.update(right)
if old == out:
return out
def keys(attrs, fds):
found = []
for x in subsets(attrs):
if not any(k <= x for k in found) and set(attrs) <= closure(x, fds):
found.append(x)
return found
def project(attrs, fds):
# Include implied dependencies, not just the written ones.
return [(x, {a}) for x in subsets(attrs)
for a in sorted((closure(x, fds) & set(attrs)) - x)]
def normal_form(attrs, fds):
ks = keys(attrs, fds)
prime = set().union(*ks)
deps = project(attrs, fds)
bcnf = all(set(attrs) <= closure(x, fds) for x, y in deps)
third = all(set(attrs) <= closure(x, fds) or y <= prime for x, y in deps)
second = not any(x < k and y - prime for k in ks for x, y in deps)
return 'BCNF' if bcnf else '3NF' if third else '2NF' if second else '1NF'
def preserved(parts, fds):
local = [fd for part in parts for fd in project(part, fds)]
return all(set(y) <= closure(x, local) for x, y in fds)
def lossless(attrs, parts, fds):
# Chase: each absent cell gets a unique symbol; a column's
# distinguished symbol wins whenever two symbols are equated.
attrs = sorted(attrs)
rows = [[f'a{j}' if a in part else f'b{i}_{j}'
for j, a in enumerate(attrs)] for i, part in enumerate(parts)]
while True:
before = [row[:] for row in rows]
for left, right in fds:
li = [attrs.index(a) for a in left]
ri = [attrs.index(a) for a in right]
for i, j in combinations(range(len(rows)), 2):
if all(rows[i][k] == rows[j][k] for k in li):
for k in ri:
u, v = rows[i][k], rows[j][k]
keep = f'a{k}' if f'a{k}' in (u,v) else min(u,v)
for row in rows:
row[:] = [keep if value in (u,v) else value for value in row]
if rows == before:
break
return any(row == [f'a{j}' for j in range(len(attrs))] for row in rows)
def show(label, attrs, fds, parts=None):
name = lambda x: ''.join(sorted(x))
print(label + ': keys=' + ','.join(map(name, keys(attrs,fds)))
+ '; form=' + normal_form(attrs,fds))
if parts:
print(' parts=' + ','.join(map(name, parts))
+ '; lossless=' + str(lossless(attrs,parts,fds))
+ '; preserved=' + str(preserved(parts,fds)))
print(' part forms=' + ','.join(normal_form(p, project(p,fds)) for p in parts))
f1 = [('AB','C'), ('C','D')]
f2 = [('AB','C'), ('C','B')]
f4 = [('A','B'), ('B','C'), ('D','E')]
f5 = [('AB','C'), ('C','D'), ('D','E')]
show('P1', 'ABCD', f1, ['CD','ABC'])
show('P2/P3', 'ABC', f2, ['CB','AC'])
assert keys('ABC',f2) == [frozenset('AB'),frozenset('AC')]
assert not preserved(['CB','AC'],f2)
print(' AB+ under projected dependencies:', ''.join(sorted(closure('AB', project('CB',f2)+project('AC',f2)))))
show('P4', 'ABCDE', f4, ['BC','AB','DE','AD'])
show('P5', 'ABCDE', f5, ['ABC','CD','DE'])
show('P6a', 'ABCD', [('B','C'),('C','D')], ['AB','BC','CD'])
show('P6b', 'ABCD', [('A','B'),('C','D')], ['AB','CD'])
show('Test A', 'ABC', [('A','B'),('B','C')], ['BC','AB'])
show('Test B', 'ABC', [('A','B'),('A','C')])
show('Test C', 'ABC', [('A','B')], ['AB','BC'])
# Concrete lossy-join witness for Test C.
original = {('a1','b','c1'), ('a2','b','c2')}
ab = {(a,b) for a,b,c in original}
bc = {(b,c) for a,b,c in original}
joined = {(a,b,c) for a,b in ab for b2,c in bc if b == b2}
print('Test C spurious rows:', sorted(joined-original))
assert len(joined-original) == 2Actual output
P1: keys=AB; form=2NF
parts=CD,ABC; lossless=True; preserved=True
part forms=BCNF,BCNF
P2/P3: keys=AB,AC; form=3NF
parts=BC,AC; lossless=True; preserved=False
part forms=BCNF,BCNF
AB+ under projected dependencies: AB
P4: keys=AD; form=1NF
parts=BC,AB,DE,AD; lossless=True; preserved=True
part forms=BCNF,BCNF,BCNF,BCNF
P5: keys=AB; form=2NF
parts=ABC,CD,DE; lossless=True; preserved=True
part forms=BCNF,BCNF,BCNF
P6a: keys=AB; form=1NF
parts=AB,BC,CD; lossless=True; preserved=True
part forms=BCNF,BCNF,BCNF
P6b: keys=AC; form=1NF
parts=AB,CD; lossless=False; preserved=True
part forms=BCNF,BCNF
Test A: keys=A; form=2NF
parts=BC,AB; lossless=True; preserved=True
part forms=BCNF,BCNF
Test B: keys=A; form=BCNF
Test C: keys=AC; form=1NF
parts=AB,BC; lossless=False; preserved=True
part forms=BCNF,BCNF
Test C spurious rows: [('a1', 'b', 'c2'), ('a2', 'b', 'c1')]Exam and interview quick answers
- Is prime the same as a key? No. Prime describes membership in a candidate key; a superkey must determine every attribute.
- Does BCNF imply dependency preservation? No. Problem 3 loses AB -> C after splitting into CB and AC.
- Does preserving every FD make the join lossless? No. Problem 6(b) preserves both FDs but the join can create extra rows.
- Can a key-only table be necessary? Yes. With R(A,B,C,D) and A -> B, C -> D, synthesis needs AC alongside AB and CD. Without AC the decomposition is lossy.
- Can two lossless BCNF designs differ? Yes. Different violating dependencies can produce different decompositions. Recheck each part and preservation rather than assuming one unique answer.
- Can I inspect only written FDs inside a part? No. An implied FD can survive projection even when its derivation uses attributes outside that part.
- When does a two-table split pass the lossless test? When the common attributes determine either whole part under F+. A nonempty intersection alone is insufficient.
- Is 3NF always the right practical choice? No. 3NF synthesis guarantees preservation; BCNF removes more FD-based redundancy. Decide which constraints need local enforcement, then verify the design.
Sources checked
The definitions of BCNF, 3NF synthesis, lossless join and dependency preservation were checked against the lecture notes RPI CSCI 4380: BCNF and 3NF decompositions. Every answer here was recomputed with a program: closures, keys, normal-form tests, the BCNF splits, dependency preservation, and the chase tables.
Comments
Post a Comment