Core CS · DBMS

Where 3NF stops and BCNF keeps going

Q: State 3NF the way you would write it on a whiteboard.

For every non-trivial X → Y , either X is a superkey, or every attribute of Y not already in X is prime. The classical wording is equivalent: the relation is in 2NF and no non-prime attribute is transitively dependent on any candidate key. Interviewers usually ask for the second and then push on the first, and the first is the one you can actually run down a list of arrows without arguing about what “transitively” covers.

Q: What is BCNF, and how exactly does it differ from 3NF?

For every non-trivial X → Y , X must be a superkey. There is no second clause. 3NF is the same rule plus one exemption for arrows whose right-hand side is entirely prime, so every relation in BCNF is in 3NF, and the gap between the forms is exactly the set of arrows taking that exemption. Some textbooks say “every determinant is a candidate key”; strictly it is superkey, and a determinant that is a candidate key with a spare column bolted on still passes.

Q: Give me a relation that is in 3NF but not in BCNF.

ZONE(Street, City, PIN) , with Street, City → PIN because a street lies in one postal zone within a city, and PIN → City because a zone lies in one city. The candidate keys are {Street, City} and {Street, PIN} , so every column is prime. PIN → City has a left-hand side that closes to only two of the three columns, which fails BCNF, but City is prime, so 3NF forgives it. The relation is still not free of repetition, and that is the honest cost of stopping there.

Q: What is 4NF?

For every non-trivial multivalued dependency X ↠ Y , X must be a superkey. A multivalued dependency says the set of Y values attached to an X value does not depend on the rest of the row. 4NF sits above BCNF, so every 4NF relation is in BCNF, and a relation can pass BCNF with no functional dependency left to fix and still be forced to store every pairing of two unrelated sets.

The two forms ask every dependency the same question and disagree about exactly one answer. You will build the relation where they disagree, watch each definition rule on it, and see what the stricter form charges you for the privilege.

Run one relation past both definitions →

PIN → City is a pass under one definition and a violation under the other. Nothing about the data changes between those two readings. Only the clause you are allowed to invoke changes.

01 The idea

One clause apart

Every normal form after 1NF is a test you run on arrows, not on rows. An arrow, or functional dependency, written X → Y, says any two rows agreeing on X must agree on Y. The left-hand side of a non-trivial arrow is called its determinant. Once the arrows are written down, 3NF and BCNF are two one-line tests over the same list, and neither of them ever looks at your data again.

BCNF is the short one. For every non-trivial X → Y, X must be a superkey. That is the entire rule and nothing is exempt. 3NF is that same rule with one escape clause bolted on: X is allowed to fail the superkey test, provided every attribute it determines that it does not already contain is prime. So every relation in BCNF is automatically in 3NF, and the relations that sit between the two forms are exactly the ones holding an arrow that takes the escape.

The classical wording of 3NF sounds like a different rule and is not. “No non-prime attribute is transitively dependent on any candidate key” bans precisely the arrows the escape clause fails to save, because an arrow with a non-superkey determinant pointing at a non-prime attribute is a non-prime attribute reaching the key through something that is not the key. Learn both sentences. Interviewers ask for the second and then push on the first, and the first is the one you can actually run down a list.

For every non-trivial X → Y, both forms ask whether X is a superkey. 3NF forgives a no when everything on the right is already part of some candidate key. BCNF never forgives it. That single clause is the whole of the difference, and every trade-off in this lesson is a consequence of it.

SuperkeyAny set of columns whose closure is every column of the relation. A candidate key is a superkey you cannot remove a column from, and every superkey has a candidate key sitting inside it.

Prime attributeA column belonging to at least one candidate key. Not the primary key you happened to declare: if a relation has two candidate keys, every column of either one is prime.

Transitive dependencyThe key determines X, X determines Y, and X does not determine the key back. Y then reaches the key only through X, so it is rewritten once for every row that repeats that X value.

02 Worked example

One allotment table, and the arrow 3NF lets through

An exam board allots five candidates to four centres and records the centre’s address on the same row. Four business rules govern it, and they are rules about every legal row, not observations about these five. Two arrows that people expect to hold do not, and they do different jobs. One is why the third rule needs both of its columns. The other is why PIN can never identify a row on its own, and that is the fact the whole second half of this lesson runs on.

-- the four rules, as the board states themRoll         -> Centre          -- a candidate sits at exactly one centreCentre       -> Street, City    -- a centre has one addressStreet, City -> PIN             -- within a city, a street lies in one postal zonePIN          -> City            -- a postal zone lies in exactly one city -- two arrows that do NOT hold, and each one does a different jobStreet       -> PIN             -- MG Road is 560001 in Bengaluru, 600002 in Chennai: line 4 needs CityPIN          -> Street          -- 560001 covers MG Road and Church St: PIN alone is never a key -- Roll sits on no right-hand side, and Roll+ reaches every columncandidate key {Roll}, and only that.  prime: Roll.  non-prime: Centre, Street, City, PIN.

Here is the table itself. Amber marks a cell that restates a fact an earlier row already stated, working down the arrows one at a time.

Roll	Centre	Street	City	PIN
R1	VH	MG Road	Bengaluru	560001
R2	VH	`MG Road`	`Bengaluru`	`560001`
R3	SH	Park St	Bengaluru	560038
R4	KH	MG Road	Chennai	600002
R5	TH	Church St	`Bengaluru`	560001

Four amber cells out of twenty-five, which looks like almost nothing, and that is the trap this table is set for. Five candidates is a teaching size. A real allotment puts three hundred candidates in VH, and then MG Road, Bengaluru is written three hundred times and any two of those rows are free to disagree. The redundancy is not measured by the amber count. It is measured by how many rows repeat a determinant, and that number is set by the data, not by the schema.

Follow one fact. 560001 is in Bengaluru is recorded on rows 1, 2 and 5, three times in a five-row table, and nothing in the schema knows those three cells are one fact.

1 · One tableCENTRE_ALLOT, five rows, one candidate key {Roll}, four non-prime columns

→

2 · Roll → Centre → StreetStreet reaches the key only through Centre, and Centre is not a key here

→

3 · The 3NF splitALLOT, CENTRE, ZONE. Every one of the four arrows now sits inside a single table

→

4 · ZONE still repeatsPIN → City writes the same city on every street row of a zone, and 3NF permits it

→

5 · The BCNF splitthe repeat goes, and Street, City → PIN can no longer be checked in any one table

Node 4 is the node the whole lesson turns on, and it is the one most revision notes skip straight past. After the 3NF split the schema is genuinely in 3NF, every arrow is checkable without a join, and one of the three tables still writes the same fact on many rows. 3NF is not failing to notice. 3NF has looked at that arrow and passed it, on purpose, using the escape clause. Node 5 is what removing it costs.

03 Mechanics

Every arrow, tested against both definitions

Two tables. The first is the pair of definitions side by side, because most of what gets recited about 3NF and BCNF is a garbled memory of one row of it. The second runs every non-trivial arrow in the story past both definitions and marks each one, which is the only way to say a relation is in a form and mean it.

	3NF	BCNF
The test, for every non-trivial X → Y	`X is a superkey, OR every attribute of Y not in X is prime`	`X is a superkey`
The escape clause	`a wholly prime right-hand side`	`none`
Classical wording	2NF, and no non-prime attribute transitively dependent on any candidate key	every determinant is a candidate key, though superkey is the accurate word
A decomposition always exists that is	`lossless and dependency preserving`	`lossless only`
What it can still leave behind	`one fact rewritten on every row that repeats a non-superkey determinant`	nothing that a functional dependency can explain

One shortcut before the second table, because otherwise the job looks infinite. You are told a handful of arrows, but the relation obeys every arrow those imply, and there are a lot of those. You do not have to test them. If a derived arrow X → A has a non-superkey left-hand side, then somewhere in the closure computation that put A into X⁺ there was a given arrow with a non-superkey left-hand side of its own, and that given arrow already fails whatever X → A fails. Deriving new arrows cannot manufacture a violation the given ones do not already show, for either form. Test the list you were handed and stop. That holds for the relation as it was handed to you. After a split you work out afresh which arrows live inside each piece, which is why one row of the table below is marked derived: Street, PIN → City is not one of the four stated rules, and it is listed because it is where ZONE’s second candidate key comes from.

Relation	Non-trivial arrow	Left side a superkey?	Right side all prime?	3NF	BCNF
CENTRE_ALLOT key {Roll}	Roll → Centre	`yes, Roll is the key`	not consulted	`pass`	`pass`
	Centre → Street, City	`no, closure misses Roll`	`no, neither is prime`	`fail`	`fail`
	Street, City → PIN	`no, closure misses Roll and Centre`	`no, PIN is not prime`	`fail`	`fail`
	PIN → City	`no, closure is {PIN, City}`	`no, City is not prime`	`fail`	`fail`
ALLOT key {Roll}	Roll → Centre	`yes`	not consulted	`pass`	`pass`
CENTRE key {Centre}	Centre → Street, City	`yes`	not consulted	`pass`	`pass`
ZONE keys {Street, City} and {Street, PIN}	Street, City → PIN	`yes, it is a candidate key`	not consulted	`pass`	`pass`
	Street, PIN → City (derived)	`yes, the other candidate key`	not consulted	`pass`	`pass`
	PIN → City	`no, closure is {PIN, City}`	`yes, City is in {Street, City}`	`pass`	`fail`
ZONE_CITY key {PIN}	PIN → City	`yes`	not consulted	`pass`	`pass`
ZONE_ST key {Street, PIN}	none exists	—	—	`pass`	`pass`

The ninth row is the whole lesson. PIN closes to {PIN, City}, which is two of ZONE’s three columns, so it is not a superkey and the first clause fails for both forms. Then 3NF asks its second question, finds City sitting inside the candidate key {Street, City}, and passes the arrow. BCNF has no second question. Same relation, same arrow, same closure, two verdicts.

Notice how ZONE got two candidate keys. {Street, City} is a key by rule three. {Street, PIN} is a key because PIN hands you City by rule four, and Street with City then hands you everything. Neither can lose a column: Street alone determines nothing, City alone determines nothing, and PIN alone stops at City. Two keys, and they share Street.

-- after the 3NF decomposition: every arrow lives inside one relationALLOT (Roll*, Centre)                  -- Roll -> CentreCENTRE(Centre*, Street, City)         -- Centre -> Street, CityZONE  (Street, City, PIN)             -- Street,City -> PIN  and  PIN -> City        keys {Street, City} and {Street, PIN} -- after splitting ZONE on the one arrow BCNF rejectsZONE_CITY(PIN*, City)                  -- PIN -> City, and PIN is the keyZONE_ST  (Street*, PIN*)                -- no non-trivial arrow at all        lost: Street,City -> PIN now spans two tables and lives in neither        25 cells -> 34 after 3NF -> 36 after BCNF -- this was never about space

The 3NF decomposition on lines 2 to 4 is not guesswork. Take a canonical cover, make one relation from each group of arrows that share a determinant, drop any relation wholly contained in another, and add one holding a candidate key if none of them already does. Here that yields {Roll, Centre}, {Centre, Street, City}, {Street, City, PIN} and {PIN, City}, and the last is contained in the third, so it goes. ALLOT holds the candidate key, so nothing extra is needed. That last check is not book-keeping. It is what makes the synthesis lossless: once a candidate key sits whole inside one of the pieces the algorithm builds, joining the pieces gives back the original rows and nothing else. Every arrow ends up inside one relation, which is what dependency preserving means, and this construction works for any relation you will ever be handed. That is the guarantee 3NF has and BCNF does not.

Line 10 is the price of line 8. Split ZONE and no table holds Street, City and PIN together any more, so there is nowhere to write the rule down. Project the arrows onto the pieces and you get PIN → City in ZONE_CITY and, in ZONE_ST, nothing at all. Close {Street, City} under what survives and you reach {Street, City}. It does not reach PIN. The rule is gone, not relocated.

Both splits are lossless, and that part is free: put the determinant and everything it determines in one piece, leave the determinant behind in the other, and the join returns exactly the rows you started with. Dependency preservation is not free. After the BCNF split you can hold (MG Road, 560001) and (MG Road, 560038) in ZONE_ST while ZONE_CITY puts both zones in Bengaluru. Neither table is violated. Neither holds a duplicate. Join them and one street in one city carries two postal codes, which is the rule you gave up, broken.

One form further, in a paragraph, because it is asked as a follow-up. A multivalued dependency X ↠ Y says the set of Y values attached to an X value does not depend on the rest of the row, and 4NF demands that every non-trivial one has a superkey on the left. It matters because a relation can pass BCNF and still repeat itself. Give a centre a set of invigilators and, independently, a set of subjects, and CENTRE_STAFF(Centre, Invigilator, Subject) has no non-trivial functional dependency anywhere in it, so its only key is all three columns and BCNF passes it without comment. Three invigilators and two subjects still force it to store all six pairings. Split it into (Centre, Invigilator) and (Centre, Subject) and the same information sits in five rows, and a fourth invigilator costs one row instead of two. Functional dependencies never saw that redundancy, because no column was determining another.

05 Cheat sheet

Four forms, four tests, and what each one still allows

Read the right-hand column, not the middle one. Anyone can recite a test. The follow-up is always what the form does not protect you from, and that is where a recited answer runs out.

Form	The test to apply	What it still allows
2NF	`no non-prime attribute depends on only part of a candidate key` There is nothing to test unless some candidate key has more than one column.	`a non-key column determining another non-key column`
3NF	`every non-trivial X → Y has X a superkey, or Y minus X all prime`	`one fact rewritten on every row that repeats a non-superkey determinant`
BCNF	`every non-trivial X → Y has X a superkey`	repetition that no functional dependency explains, and a rule you can no longer check in one table
4NF	`every non-trivial X ↠ Y has X a superkey`	read cost. It says nothing about how many tables a query now joins

Lossless is free, dependency preserving is notSplit on X → Y so that X becomes the key of one piece and stays behind in the other, and the join always returns exactly the original rows. That holds for both forms and for every step. Dependency preservation does not: every relation has a 3NF decomposition that keeps every arrow inside a single table, and there are relations, ZONE among them, for which no BCNF decomposition manages it.

Prime is about candidate keys, not your PRIMARY KEYThe single most common way to report the wrong normal form is to take the key you would have declared, call everything else non-prime, and then find a violation that is not there or miss one that is. Find every candidate key first. In ZONE there are two, and they make all three columns prime, which is the only reason PIN → City survives 3NF.

3NF is where most production schemas stopNot out of laziness. The last step trades a rule you can enforce in one line of DDL for a repeat you can often live with, and that trade only pays when the repeat is large or the rule can be re-enforced some other way. Say that out loud in an interview and you have given a better answer than “always normalise to BCNF”.

06 Where & why

Where the lost dependency goes to live

The trade-off is not a diagram. Before the split, Street, City → PIN is one line of DDL, because {Street, City} is a candidate key of ZONE and UNIQUE (street, city) enforces it on every write. After the split no table holds those three columns, so that line has nowhere to go. Every mainstream engine has an answer, all four answers are different, and none of them is one line.

PostgreSQL

A trigger, or a view you have to remember to refresh

A CHECK constraint may not contain a subquery and may not look at another table, so the rule becomes a trigger on both tables, or a materialised view over the join with a unique index on it. PostgreSQL refreshes a materialised view only when you run REFRESH MATERIALIZED VIEW, so that route detects the violation later rather than rejecting it.

Oracle

Refresh on commit turns a view into a constraint

Oracle can define a materialised view with REFRESH ON COMMIT and put a unique constraint on it, so the check runs as the transaction commits rather than at the next manual refresh. That is the closest any mainstream product gets to the standard’s CREATE ASSERTION, which none of them implement. You pay for it on every write to the base tables.

SQL Server

An indexed view is maintained inside your transaction

A SCHEMABINDING view over the two tables with a UNIQUE CLUSTERED INDEX is updated in the same transaction as the base-table write, so the offending insert fails immediately with a duplicate-key error. It is the cleanest reconstruction of the lost rule and the most restricted: indexed views carry a long list of rules about what the view is allowed to contain.

MySQL

No materialised views, so it is triggers or nothing

MySQL has no materialised views at all, and CHECK constraints were only parsed and ignored before 8.0.16 and still may not contain a subquery. A rule spanning two tables becomes a BEFORE INSERT and BEFORE UPDATE trigger on each of them, or it slides into application code where a batch import walks past it. That gap is a large part of why teams here stop at 3NF.

Denormalisation is this lesson’s trade run backwards, and it takes the same discipline. Copying City back onto every street row to kill a join re-creates the exact repeat BCNF removed, so name the arrow you are re-introducing a copy of, name the table that stays authoritative, say what refreshes the copy and how stale it may get. A schema that stops at 3NF has made one such trade knowingly. A schema that copies a column because a join looked slow has made the same trade without measuring, and finds out when the two copies disagree.

07 Interview questions

What they actually ask

Expect to be handed a small relation and a list of arrows and asked for the key, then the normal form, then a decomposition, in that order. The questions below escalate the same way, and the ones near the end are where prepared answers usually stop.

What is a transitive dependency?

The key determines one column, that column determines a second, and it does not determine the key back, so the second column reaches the key only through the first. In CENTRE_ALLOT, Roll → Centre and Centre → Street, and Centre does not give you back Roll, so Street is transitively dependent on Roll. The cost is that the centre’s street is rewritten once for every candidate allotted there, and any two of those rows are then free to disagree.

State 3NF the way you would write it on a whiteboard.

For every non-trivial X → Y, either X is a superkey, or every attribute of Y not already in X is prime. The classical wording is equivalent: the relation is in 2NF and no non-prime attribute is transitively dependent on any candidate key. Interviewers usually ask for the second and then push on the first, and the first is the one you can actually run down a list of arrows without arguing about what “transitively” covers.

What is a prime attribute?

A column that belongs to at least one candidate key, not only the one you would have declared as the primary key. In ZONE(Street, City, PIN) the candidate keys are {Street, City} and {Street, PIN}, so all three columns are prime. Taking your chosen primary key and calling everything else non-prime is the most common way a candidate reports the wrong normal form.

What is BCNF, and how exactly does it differ from 3NF?

For every non-trivial X → Y, X must be a superkey. There is no second clause. 3NF is the same rule plus one exemption for arrows whose right-hand side is entirely prime, so every relation in BCNF is in 3NF, and the gap between the forms is exactly the set of arrows taking that exemption. Some textbooks say “every determinant is a candidate key”; strictly it is superkey, and a determinant that is a candidate key with a spare column bolted on still passes.

Give me a relation that is in 3NF but not in BCNF.

ZONE(Street, City, PIN), with Street, City → PIN because a street lies in one postal zone within a city, and PIN → City because a zone lies in one city. The candidate keys are {Street, City} and {Street, PIN}, so every column is prime. PIN → City has a left-hand side that closes to only two of the three columns, which fails BCNF, but City is prime, so 3NF forgives it. The relation is still not free of repetition, and that is the honest cost of stopping there.

How do you decompose a relation into BCNF?

Find a non-trivial X → Y whose left-hand side is not a superkey. Replace the relation with one holding X and everything it determines, and one holding everything else with X left behind in it. Repeat until no violation is left. X becomes the key of the first piece and survives in the second, which is exactly what makes every step lossless.

Which decomposition is guaranteed to preserve every dependency?

3NF, always. Take a canonical cover, build one relation from each group of arrows sharing a determinant, drop any relation wholly contained in another, and add one holding a candidate key if none already does. Every arrow ends up inside a single relation, so every arrow stays checkable without a join. BCNF is only guaranteed lossless; there are relations for which no BCNF decomposition preserves every dependency, and ZONE is one of them.

You lost a dependency. What actually goes wrong?

Nothing at all, until two rows that are each perfectly legal on their own get joined. After the ZONE split you can hold (MG Road, 560001) and (MG Road, 560038) in one table while the other says both zones are in Bengaluru. Neither table is violated and neither holds a duplicate, yet the join shows one street in one city under two postal codes. Catching it means looking at both tables at once, which no CHECK or UNIQUE on a single table can do.

What is 4NF?

For every non-trivial multivalued dependency X ↠ Y, X must be a superkey. A multivalued dependency says the set of Y values attached to an X value does not depend on the rest of the row. 4NF sits above BCNF, so every 4NF relation is in BCNF, and a relation can pass BCNF with no functional dependency left to fix and still be forced to store every pairing of two unrelated sets.

Does going past 3NF ever make things worse?

Hard

Show that a relation in 3NF with exactly one candidate key is always in BCNF, then state what must therefore be true of the candidate keys of any relation that is in 3NF and not in BCNF.

Follow-up

No example can settle this, because the claim is about every relation, so it has to come out of the two definitions alone. The argument is four lines long and turns on one fact about superkeys that this lesson states in passing.

Show the hint

Start from an arrow X → A that fails BCNF, work out what 3NF then forces A to be, and look for a superkey you can assemble out of X and part of the candidate key.