Normalisation: 1NF, 2NF, 3NF and BCNF
Clear, exam-oriented notes on relational normalisation: definitions, laws (Armstrong's axioms), algorithms for finding keys and decomposing into 1NF, 2NF, 3NF and BCNF, with worked examples and common mistakes.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Database designers use normalisation to organise tables so that updates, inserts and deletes do not cause inconsistency and so storage is not wasted. Normal forms (1NF, 2NF, 3NF, BCNF) give precise rules using functional dependencies so engineers can decompose schemas into well-behaved relations during design and review.
Key ideas
Start with definitions and simple laws; build up to the normal forms and decomposition algorithms.
- Relation schema: a set of attributes (columns) that describe an entity type or relationship. Example: R(A, B, C).
- Instance: a set of tuples (rows) of a relation schema at a moment in time.
- Functional dependency (FD): For attributes X and Y (each a set of attributes) of relation R, the statement
X → Ymeans: for any two tuples t1 and t2 of any legal instance of R, if t1[X] = t2[X] then t1[Y] = t2[Y]. Boldly: X functionally determines Y. - Trivial FD:
X → Yis trivial ifY ⊆ X. - Superkey: a set of attributes X of R such that X → all attributes of R. A candidate key is a minimal superkey (no proper subset is a superkey). A primary key is a chosen candidate key.
- Prime attribute: an attribute that is part of some candidate key. Non-prime attribute: not part of any candidate key.
- Full functional dependency: attribute Y is fully dependent on X if
X → Yholds and for no proper subsetZ ⊂ XdoesZ → Yhold. If some proper subset determines Y, that is a partial dependency. - Transitive dependency: A non-prime attribute A is transitively dependent on key K if
K → BandB → Afor some attribute set B where B is not a key and A is non-prime (so A depends on K via B).
Armstrong's axioms (exact rules used to infer FDs):
- Reflexivity: if Y ⊆ X then
X → Y. - Augmentation: if
X → YthenXZ → YZfor any Z (concatenate attributes). - Transitivity: if
X → YandY → ZthenX → Z.
Common derived rules (often used in proofs):
- Union: if
X → YandX → ZthenX → YZ. - Decomposition: if
X → YZthenX → YandX → Z. - Pseudotransitivity: if
X → YandYZ → WthenXZ → W.
Key computations and algorithms students must know:
- Attribute closure X+: compute closure of X under a set F of FDs to test if
X → Aholds. Algorithmic steps: start with X+ = X; repeatedly, for any FDY → Zin F withY ⊆ X+, setX+ := X+ ∪ Z(i.e., add each attribute of Z to X+); continue until no further change. - Finding candidate keys: compute closures of attribute sets (start with all attributes that are not in RHS of any FD; augment until you find minimal sets whose closure is all attributes).
- Minimal cover (canonical cover) of F: (1) split RHS to single attributes, (2) remove extraneous attributes from LHS where possible, (3) remove redundant FDs. Minimal covers are used in the 3NF synthesis algorithm.
- BCNF decomposition algorithm (lossless-join, may not preserve dependencies): while there exists a non-trivial FD
X → Ythat violates BCNF in relation R, replace R with two relations R1 = X ∪ Y and R2 = R − (Y − X); repeat on any relation that still violates BCNF. - Lossless-join test for decomposition {R1, R2}: using table method (start with a row for attributes of R marked with row variables a1..an, set entries for R1 attributes equal for both rows, and apply FDs to see if you can make a row identical). A practical sufficient condition: if
(R1 ∩ R2) → R1or(R1 ∩ R2) → R2holds (i.e., intersection is a superkey for one component) then decomposition is lossless. Dependency preservation test: for a decomposition {R1,...,Rk}, compute the projection of F onto each Ri (Fi), then check whether the closure of ∪Fi implies all of F (e.g., via attribute closures or a chase); if yes, the decomposition preserves dependencies.
Precise definitions of normal forms:
- First normal form (1NF): A relation is in 1NF if all attribute domains are atomic (no repeating groups, no nested relations). Practically, each cell holds a single atomic value.
- Second normal form (2NF): A relation R is in 2NF if it is in 1NF and every non-prime attribute is fully functionally dependent on every candidate key (i.e., no partial dependency of a non-prime attribute on part of a candidate key).
- Third normal form (3NF) (commonly used formulation): A relation R is in 3NF if it is in 1NF and for every non-trivial FD
X → A(with A a single attribute), either (a) X is a superkey, or (b) A is a prime attribute. Equivalently, 3NF eliminates transitive dependencies of non-prime attributes on candidate keys. - Boyce–Codd normal form (BCNF): A relation R is in BCNF if for every non-trivial FD
X → Ythat holds in R, X is a superkey. BCNF is stricter than 3NF; every BCNF is 3NF but not vice versa.
Diagrams to draw in answers when asked (describe exactly):
- To show FDs: draw a box with attribute names inside (write attributes separated by commas). Draw arrows labelled with the left side mapping to right side; e.g. draw arrow from A to B labelled "A → B". For composite LHS, write attributes grouped and draw arrow from that group.
- For decomposition: draw original relation box R(A,B,C,...) and below it draw boxes R1(...), R2(...). Mark common attributes (intersection) with double border and label if it is a key for one component.
Formulas
X → Y : X functionally determines Y. (X, Y are attribute sets, no SI units; applies in relational schemas.)
X+ : closure of attribute set X under FD set F; the set of attributes functionally determined by X.
Reflexivity: if Y ⊆ X then X → Y : Armstrong axiom.
Augmentation: if X → Y then XZ → YZ : Armstrong axiom (Z arbitrary set).
Transitivity: if X → Y and Y → Z then X → Z : Armstrong axiom.
Decomposition: if X → YZ then X → Y and X → Z : derived rule.
Union: if X → Y and X → Z then X → YZ : derived rule.
BCNF condition: for every non-trivial X → Y, X is a superkey : applies when checking BCNF.
3NF condition: for every non-trivial X → A, X is a superkey OR A is prime : applies when checking 3NF.
Worked examples
Example 1 — Determine highest normal form Question: Given R(A, B, C) with F = {A → B, B → C}. Find candidate keys and highest NF. Answer (model steps):
- Compute closures: A+ = {A, B, C} because A → B and B → C ⇒ A → C by transitivity. So A is a candidate key.
- Any other key? B+ = {B, C} not all; C+ = {C}. So only candidate key is {A}.
- Prime attributes = {A}. Non-prime = {B, C}.
- 1NF: assume atomic domains ⇒ OK.
- 2NF: candidate key is single attribute A, so no partial dependency possible ⇒ relation is in 2NF.
- 3NF: check FDs: A → B: left is key ⇒ OK. B → C: left B is not a superkey and C is non-prime, so violates 3NF. Therefore relation is NOT in 3NF; highest NF = 2NF. Final: Highest normal form is 2NF. (Explain transitive dependency A → B → C causes violation of 3NF.)
Example 2 — Decompose to 3NF using synthesis Question: R(A,B,C,D) with F = {A → B, A → C, C → D}. Decompose to 3NF preserving dependencies. Answer:
- Compute minimal cover: RHS are singletons already. No extraneous LHS attributes. Minimal cover G = same as F.
- For each FD create relation schema: R1(A,B), R2(A,C), R3(C,D).
- Ensure a key: candidate keys? Compute A+ = {A,B,C,D} (using A→C and C→D) so A is a key; A appears in R1 and R2 so a relation containing a key exists (R1 or R2). So decomposition = {R1(A,B), R2(A,C), R3(C,D)}.
- Check lossless join: because R2 contains key A for original R, decomposition is lossless.
- All FDs are preserved by construction. Each relation is in BCNF or 3NF: R1 and R2 have key A so they are BCNF; R3: C → D with C key for R3 so BCNF. Therefore decomposition into BCNF actually also possible here. Final decomposition: R1(A,B), R2(A,C), R3(C,D).
Example 3 — BCNF decomposition that loses dependency preservation Question: R(A,B,C) with F = {A → B, B → A, B → C}. Here A and B are mutually determining. Answer:
- Find candidate keys: A ↔ B implies A+ = {A,B,C} so {A} and {B} are candidate keys; prime attributes {A,B}; C non-prime.
- Check BCNF: FD B → C left B is a key? Yes B is a key for whole R so OK. A → B left A is a key too. So R is already in BCNF (example instead to show loss of dependency preservation choose classic example: R(A,B,C) with F={A B → C, C → B}). Alternate classic example for loss of preservation: Use R(A,B,C) with F={AB → C, C → B}.
- Candidate key: AB determines C; AB+ = {A,B,C} so AB is a key.
- FD C → B violates BCNF because C is not a superkey. Decompose into R1(B,C) from C→B and R2(A,C) (projection). This decomposition is lossless (C is common and C→B makes the intersection a key for R1) but does not preserve AB → C. For example, R1 = {(b1,c1),(b1,c2)} and R2 = {(a1,c1),(a1,c2)} satisfy the projected dependencies, yet their join contains tuples (a1,b1,c1) and (a1,b1,c2), violating AB → C. The key teaching: BCNF decomposition may cause loss of dependency preservation; 3NF synthesis preserves dependencies but may not reach BCNF.
Common mistakes
- Forgetting to check for multiple candidate keys when deciding prime attributes.
- Incorrectly computing closures by forgetting to re-apply added attributes iteratively.
- Splitting RHS incorrectly when building minimal cover (always split to single attributes first).
For your exam
Question types you will see: definitions (FD, key, prime attribute), short notes (Armstrong's axioms, minimal cover), derivations (compute X+, find candidate keys), decomposition problems (convert to 2NF/3NF/BCNF showing steps), diagram questions (draw relation and FD arrows), and proofs (show lossless join or dependency preservation). What full-marks answers include:
- Clear statement of assumptions (1NF holds unless domains are non-atomic), explicit FDs used, step-by-step closure calculations with attribute sets shown, minimal cover steps listed, decomposition schemas listed, and a final statement about lossless join and dependency preservation with brief justification.
Quick check
- Define functional dependency in one sentence.
- State the BCNF condition in one line.
- If R(A,B,C) has F = {A → B, B → C}, is R in 3NF? (Yes/No and why.) Answers: 1. A functional dependency X → Y holds if equal X-values in any two tuples imply equal Y-values. 2. For every non-trivial FD X → Y, X must be a superkey. 3. No — A → B is from a key A, but B → C causes a transitive dependency so 3NF is violated because B is not a key and C is non-prime.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?