Which of the following are true about decomposition into normal forms?

Every relation in BCNF is in 3NF

A dependency-preserving decomposition into BCNF always exists

Every relation in BCNF is in 3NF

A table `emp(eid, mgr)` declares `mgr` as a foreign key referencing `emp(eid)`. A row is inserted with `mgr` set to NULL. What happens?

The insert succeeds — a null foreign key satisfies referential integrity

The insert is rejected — a foreign key must match an existing row

The insert succeeds — a null foreign key satisfies referential integrity

The insert succeeds only if the table is empty

The null is silently replaced by the smallest existing eid

Functional Dependencies, Normal Forms and Integrity Constraints

This is the section that rewards a mechanical habit over insight, because every question reduces to the same three-step procedure: compute closures, read off the candidate keys, then test each dependency against the key structure. A functional dependency X → Y says that fixing X fixes Y, and the closure X⁺ is everything X determines — computed by starting with X and repeatedly adding the right-hand side of any dependency whose left-hand side you already hold, until nothing changes. A set is a superkey when its closure is the whole relation, and a candidate key when it is a superkey with no proper subset that is one. Everything after that is definitions applied carefully. An attribute is prime if it appears in some candidate key, and the normal-form ladder is a sequence of restrictions on the dependencies you are allowed to keep: 2NF forbids a non-prime attribute depending on part of a key, 3NF forbids it depending on anything that is not a superkey, and BCNF drops the escape clause and demands the left side of every non-trivial dependency be a superkey, full stop. The single most useful consequence: if every attribute of a relation is prime, the relation is automatically in 3NF no matter how tangled its dependencies look — and the chapter’s central example is one where all three dependencies violate BCNF while 3NF holds for exactly that reason. Then decomposition, where two properties pull against each other and the trade is the examinable content: a lossless 3NF decomposition preserving every dependency always exists, while BCNF may cost you dependency preservation.

Closures First, Keys Second, Everything Else Third

Take R(A, B, C, D, E) with F = {A → B, BC → E, ED → A}. Compute closures by hand and the key structure falls out. A⁺ = AB and stops, so A alone is far from a key. CD⁺ = CD — neither dependency fires, because you have no A and no B to pair with C. But ACD⁺: A gives B, so you hold ABCD; BC now gives E, so ABCDE. That is the whole relation, so ACD is a superkey, and since CD⁺ = CD and AC⁺ = ABCE and AD⁺ = ABD, no proper subset of it is — ACD is a candidate key. The same walk gives BCD⁺ = ABCDE (BC gives E, ED gives A) and CDE⁺ = ABCDE (ED gives A, A gives B), so BCD and CDE are candidate keys too. Three candidate keys, and between them they use every attribute of the relation — which is a fact with consequences.

R(ABCDE), F = {A → B, BC → E, ED → A} — closures, computed
Attribute set X	X⁺	Verdict
A	AB	Not a superkey
CD	CD	Nothing fires at all
AC	ABCE	D is missing — not a superkey
ACD	ABCDE	Candidate key
BCD	ABCDE	Candidate key
CDE	ABCDE	Candidate key

🧠 Counting superkeys without listing them

A superkey is any set whose closure is everything, so every superset of a candidate key is a superkey — which turns the count into a counting problem rather than a search. The clean case first: in R(A, B, C, D) with F = {A → B, B → C, C → D, D → A} the dependencies form a cycle, so each single attribute determines all four and all four singletons are candidate keys. Then every non-empty subset of the four attributes contains a candidate key, so the superkey count is 2⁴ − 1 = 15 and the relation is in BCNF — every left side is a superkey by definition. Where the candidate keys overlap, inclusion–exclusion is needed and brute force is often faster: for R(ABCDE) with keys ACD, BCD and CDE the answer is 7, and the shape of that is worth noting — CD is in all three keys, so every superkey contains CD, and the count is the number of subsets of {A, B, E} that make one of the keys complete: ACD, BCD, CDE, ABCD, ACDE, BCDE, ABCDE. Seven, and CDE itself is why {A, B, E} alone does not multiply cleanly.

The Ladder, and the Rung Where Prime Attributes Save You

What each normal form forbids, for a non-trivial X → Y
Form	Requirement	The escape clause
1NF	Every attribute holds a single atomic value	None — a multivalued attribute needs its own table
2NF	No non-prime attribute depends on a proper part of a candidate key	Automatic when every candidate key is a single attribute
3NF	X is a superkey or every attribute of Y − X is prime	The prime escape — this is the rung that gets used
BCNF	X is a superkey. Nothing else.	None — 3NF’s escape clause is exactly what BCNF removes

🎯 All three dependencies violate BCNF, and the relation is still in 3NF

Return to R(ABCDE) with F = {A → B, BC → E, ED → A} and candidate keys ACD, BCD, CDE. Check BCNF: is A a superkey? A⁺ = AB, so no. Is BC? BC⁺ = BCE, no. Is ED? ED⁺ = ABDE, no. Every one of the three dependencies violates BCNF. Now check 3NF, which allows the violation when the determined attribute is prime. The candidate keys are ACD, BCD and CDE, and between them they contain A, B, C, D and E — so every attribute is prime. A → B determines B, prime. BC → E determines E, prime. ED → A determines A, prime. The relation is in 3NF. This is the single most useful shortcut in the topic: if every attribute is prime, 3NF holds automatically, whatever the dependencies look like, because 3NF’s escape clause can never fail. So the honest procedure is to find the candidate keys, take their union, and if it covers the relation stop worrying about 3NF and go straight to testing BCNF. It also explains why so many exam relations sit exactly at 3NF-but-not-BCNF: that is what a relation with overlapping candidate keys usually is.

Three worked relations, each landing on a different rung
Relation and dependencies	Candidate keys	Highest form	What decides it
R(ABCD), A→B, B→C, C→D, D→A	A, B, C, D	BCNF	Every left side is a whole candidate key
R(ABC), AB→C, C→A	AB, BC	3NF	C→A breaks BCNF, but A is prime, so 3NF survives
R(ABCDE), AB→C, C→D, D→E	AB only	2NF	C→D and D→E are transitive; D and E are non-prime

⚠️ 2NF fails on partial dependencies, 3NF on transitive ones — check which

In R(ABCDE) with AB → C, C → D, D → E the only candidate key is AB, so C, D and E are all non-prime. Now look at what fails and what does not. Is there a partial dependency — a non-prime attribute determined by part of AB? No: neither A nor B alone determines anything. So 2NF holds. Are there transitive dependencies — a non-prime attribute determined by a non-superkey? Yes, twice: C → D and D → E, with C and D not superkeys and D and E not prime. So 3NF fails and the relation is exactly in 2NF. The mistake to avoid is jumping from "there are bad dependencies" to "it is only in 1NF". The ladder is checked rung by rung and the two failures have different shapes: 2NF is about the left side being a proper part of a key, 3NF is about the left side not being a superkey at all. A relation can pass 2NF and fail 3NF, as here; the reverse is impossible, because every 3NF relation is in 2NF.

Lossless Join, Dependency Preservation, and Which You Give Up

A decomposition of R into R1 and R2 is lossless when joining them back gives exactly R — no spurious tuples. The test for two-way decomposition is one line: let X be the attributes common to R1 and R2; the decomposition is lossless iff X is a superkey of R1 or of R2, equivalently iff X⁺ contains one of the halves. On R(ABCDE) with F = {A → B, BC → E, ED → A}: decomposing into (AB, ACDE) shares A, and A⁺ = AB which covers AB, so it is lossless. Decomposing into (ABC, CDE) shares C, and C⁺ = C, which covers neither ABC nor CDE, so it is lossy — joining those two back produces tuples that were never in R. And (AB, CDE) shares nothing, which is always lossy, because the join degenerates to a cross product.

🎯 The one trade: 3NF keeps both properties, BCNF may not

Two properties matter in a decomposition and they are not equally available. Lossless join means you can reconstruct R. Dependency preservation means every dependency in F can still be checked inside a single fragment, without a join — which matters because a constraint you can only verify by joining is a constraint the database will not enforce cheaply. The theorem worth carrying: a lossless, dependency-preserving decomposition into 3NF always exists for any relation, and a lossless decomposition into BCNF always exists, but a dependency-preserving one may not. The standard witness is R(A, B, C) with AB → C and C → B. Candidate keys are AB and AC, so B and C are prime and the relation is in 3NF; C → B violates BCNF because C⁺ = CB is not everything. Any BCNF decomposition has to split B away from C or from A, and whichever way you cut it, AB → C ends up spanning two fragments and can no longer be checked locally. So BCNF is not simply "better than 3NF": it removes redundancy more completely and can cost you enforceable constraints, which is why real schemas often stop at 3NF deliberately.

Integrity Constraints: What the Database Refuses to Store

The named constraints, and what each one forbids
Constraint	What it forbids
Domain integrity	A value outside the column’s declared type or `CHECK` condition
Entity integrity	A null in any part of the primary key, and duplicate key values
Referential integrity	A non-null foreign key with no matching row in the referenced table
Key (`UNIQUE`)	Duplicate values — but nulls are permitted, unlike a primary key

ℹ️ A foreign key may be null, and that is not a violation

Referential integrity says a foreign key value must match an existing primary key, and a null does not have a value to match — so a null foreign key satisfies the constraint. That is exactly how a partial relationship is represented after ER mapping: an employee with no manager carries a null in mgr, and the database is content. It is also, not coincidentally, how the NOT IN trap of the previous chapter gets into a real schema. Two further distinctions get examined. A primary key may not be null in any component and there is at most one per table; a UNIQUE constraint forbids duplicates but permits nulls and may be declared several times. And when a referenced row is deleted, the action is declared, not inferred: ON DELETE CASCADE removes the dependent rows, ON DELETE SET NULL blanks the foreign key, and the default NO ACTION (or RESTRICT) refuses the delete — so the outcome of deleting a parent row is a schema decision that a question must state before it can have an answer.

Key takeaways

Compute closures first, read candidate keys off them, and test dependencies only after that.
On R(ABCDE) with A→B, BC→E, ED→A the candidate keys are ACD, BCD and CDE — three of them.
If every attribute is prime, 3NF holds automatically, whatever the dependencies look like.
2NF fails on a partial dependency; 3NF on a transitive one. Check the rungs separately.
BCNF demands every left side be a superkey and has no escape clause.
Two-way decomposition is lossless iff the common attributes are a superkey of one half.
A lossless dependency-preserving 3NF decomposition always exists; for BCNF it may not.
Every superset of a candidate key is a superkey — count, do not search.
A null foreign key satisfies referential integrity; a null in a primary key never does.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

For the relation R(A, B, C, D, E) with functional dependencies F = {A → B, BC → E, ED → A}, the number of candidate keys is ______
Numerical answer — type the value.
Show answer
Answer: 3
3 — ACD, BCD and CDE. Start from what must be in every key: C and D appear on no right-hand side, so nothing determines them and every candidate key must contain both. And CD⁺ = CD, so CD alone is not enough. Now test CD plus one more attribute. ACD⁺: A gives B, then BC gives E, reaching ABCDE ✓. BCD⁺: BC gives E, then ED gives A, reaching ABCDE ✓. CDE⁺: ED gives A, then A gives B, reaching ABCDE ✓. All three work, none has a proper subset that does (since CD alone fails), so all three are candidate keys and there are no others — a fourth would need a fourth attribute to add to CD, and only A, B, E exist. Two useful by-products: the three keys between them contain every attribute, so every attribute is prime and the relation is in 3NF; and the superkey count is 7, being those three plus ABCD, ACDE, BCDE and ABCDE.
R(A, B, C, D, E) has F = {A → B, BC → E, ED → A} with candidate keys ACD, BCD and CDE. The highest normal form R satisfies is:
1. 2NF
2. 3NF
3. BCNF
4. 1NF only
Show answer
Answer: B — 3NF
3NF, and not BCNF. Test BCNF first, since it is the stricter condition: it needs every left-hand side to be a superkey. A⁺ = AB, BC⁺ = BCE, ED⁺ = ABDE — none of the three is a superkey, so all three dependencies violate BCNF and option C is out. Now 3NF, which permits a non-superkey left side provided the attributes it determines are prime. The three candidate keys ACD, BCD and CDE together contain A, B, C, D and E, so every attribute of R is prime. A → B determines a prime attribute, BC → E likewise, ED → A likewise, so 3NF holds — and it holds for a reason that cannot fail, which is the shortcut worth carrying: once the union of the candidate keys covers the relation, 3NF is automatic. Option A understates it: 2NF would require a partial dependency to be the worst problem, and there is no dependency here whose left side is a proper subset of a candidate key. Option D is the reflex of assuming that three BCNF violations must mean a low form.
R(A, B, C, D, E) has F = {AB → C, C → D, D → E} and AB as its only candidate key. The highest normal form R satisfies is:
1. 1NF
2. 2NF
3. 3NF
4. BCNF
Show answer
Answer: B — 2NF
Exactly 2NF. With AB the only candidate key, the prime attributes are A and B, so C, D and E are all non-prime. 2NF asks about partial dependencies — a non-prime attribute determined by a proper part of a candidate key. Neither A nor B alone determines anything here, so there is no partial dependency and 2NF holds. 3NF asks about transitive dependencies — a non-prime attribute determined by something that is not a superkey. There are two: C → D and D → E, with C⁺ = CDE and D⁺ = DE, neither a superkey, and D and E non-prime. So 3NF fails, and BCNF fails with it. The mistake option A represents is jumping from "there are violations" straight to the bottom rung; the ladder has to be climbed one step at a time, and a relation can satisfy 2NF while failing 3NF exactly as here. Note the useful contrast with the previous question: there, non-superkey left sides were harmless because every attribute was prime; here the same shape of violation is fatal to 3NF because D and E are not.
R(A, B, C, D, E) has F = {A → B, BC → E, ED → A}. Which decomposition is lossless?
1. (ABC, CDE)
2. (AB, ACDE)
3. (AB, CDE)
4. (ABE, CDE)
Show answer
Answer: B — (AB, ACDE)
(AB, ACDE). Apply the two-way test: the decomposition is lossless iff the common attributes form a superkey of one of the halves. Here the halves share A, and A⁺ = AB, which contains all of AB — so A is a key of the fragment AB and the join reconstructs R exactly. Option A shares only C, and C⁺ = C: C determines nothing, so it is a key of neither ABC nor CDE, and rejoining invents tuples that were never in R. Option C shares nothing at all, which is always lossy — with no common attribute the natural join degenerates into a cross product. Option D shares E, and E⁺ = E, so it fails for the same reason as A. The habit worth building: identify the common attributes, take their closure, and check it against each half. Two attributes in common is not better than one; what matters is whether the closure swallows a fragment.
Which of the following are true about decomposition into normal forms?
1. A lossless, dependency-preserving decomposition into 3NF always exists
2. A lossless decomposition into BCNF always exists
3. A dependency-preserving decomposition into BCNF always exists
4. Every relation in BCNF is in 3NF
Show answer
Answer: A — A lossless, dependency-preserving decomposition into 3NF always exists; B — A lossless decomposition into BCNF always exists; D — Every relation in BCNF is in 3NF
A, B and D. A and B are the two existence theorems, and the asymmetry between them is the examinable content. C is false, and the standard witness is R(A, B, C) with AB → C and C → B: its candidate keys are AB and AC, so B and C are prime and the relation is already in 3NF, while C → B violates BCNF because C⁺ = CB is not the whole relation. Any BCNF decomposition must separate B from A, and then AB → C spans two fragments and can no longer be checked without a join — so dependency preservation is lost whichever way you cut. D is immediate from the definitions: BCNF requires every left side to be a superkey, which is 3NF’s first alternative, so BCNF is the strictly stronger condition and implies 3NF. The practical reading of A against C is why real schemas often stop at 3NF on purpose: BCNF removes more redundancy but can cost you a constraint the database could otherwise enforce cheaply.
R(A, B, C, D) has F = {A → B, B → C, C → D, D → A}. The number of superkeys of R is ______
Numerical answer — type the value.
Show answer
Answer: 15
15. The dependencies form a cycle, so each single attribute reaches all the others: A⁺ = ABCD (A gives B, B gives C, C gives D), and by symmetry B⁺ = C⁺ = D⁺ = ABCD. So all four singletons are candidate keys. A superkey is any set whose closure is everything, and since every non-empty subset of {A, B, C, D} contains at least one singleton, every non-empty subset is a superkey: 2⁴ − 1 = 15. The −1 is the empty set, whose closure is empty. Two things worth taking from this. First, the relation is in BCNF: every left-hand side is a whole candidate key, so there is nothing to violate. Second, the counting method generalises only when the candidate keys are disjoint or singletons — with overlapping multi-attribute keys, inclusion–exclusion is needed, and for R(ABCDE) with keys ACD, BCD, CDE the answer is 7, not a clean power of two.
R(A, B, C) has F = {AB → C, C → A}. Which statement is correct?
1. R is in BCNF
2. R is in 3NF but not BCNF
3. R is in 2NF but not 3NF
4. R is only in 1NF
Show answer
Answer: B — R is in 3NF but not BCNF
3NF but not BCNF — the canonical example of that gap. First the keys: AB⁺ = ABC ✓ and BC⁺ = ABC (C gives A) ✓, while A⁺ = A, B⁺ = B, C⁺ = CA, so the candidate keys are AB and BC, and every attribute appears in one of them — A, B, C are all prime. Now BCNF: C → A has C⁺ = CA, not the whole relation, so C is not a superkey and BCNF fails. Now 3NF: the attribute C determines is A, which is prime, so the escape clause applies and 3NF holds. Option C would need a non-prime attribute determined by part of a key; there are no non-prime attributes at all here, so nothing can violate 2NF or 3NF. This relation is also the standard witness that a dependency-preserving BCNF decomposition need not exist: splitting to satisfy BCNF separates A from B, and then AB → C spans two fragments and can no longer be enforced locally.
A table emp(eid, mgr) declares mgr as a foreign key referencing emp(eid). A row is inserted with mgr set to NULL. What happens?
1. The insert is rejected — a foreign key must match an existing row
2. The insert succeeds — a null foreign key satisfies referential integrity
3. The insert succeeds only if the table is empty
4. The null is silently replaced by the smallest existing eid
Show answer
Answer: B — The insert succeeds — a null foreign key satisfies referential integrity
The insert succeeds. Referential integrity requires that a foreign key value match some existing primary key, and a null has no value to match — the constraint is stated over non-null values and is vacuously satisfied. That is exactly how ER mapping represents partial participation: an employee with no manager carries a null, and this is the intended design rather than a loophole. Contrast a primary key, which may not be null in any component — that is entity integrity, a different constraint, and conflating the two is what makes option A tempting. Option D describes something no SQL database does; constraints reject or accept, they do not silently substitute values. Worth connecting to the previous chapter: this legitimate null is precisely how a real schema acquires the NOT IN hazard, since eid NOT IN (SELECT mgr FROM emp) will then return no rows at all.