Normal Forms: 1NF, 2NF, 3NF and BCNF: short notes (Database Management Systems)

Introduction

A relation that stores two independent facts in one row repeats one of them, and repetition causes anomalies. In STUDENT_DEPT(roll, name, dept, hod), the head of department is stored once per student: changing the head means updating many rows (update anomaly), a department with no student cannot record its head (insertion anomaly), and deleting the last student of a department loses its head (deletion anomaly).

After 1NF's atomic-domain condition, the 2NF, 3NF and BCNF conditions here are FD-based and progressively stronger, ruling out the corresponding redundancies. The definitions, a reliable test procedure, how to find the highest normal form of a relation from its FDs, and which decomposition reaches a target form are the standard facts.

Prerequisites

Functional Dependencies, Closure and Canonical Cover: attribute closure, candidate keys and prime attributes.

Core concepts

Let $R$ have FD set $F$ . An FD $X \to A$ is nontrivial if $A \notin X$ . An attribute is prime if it belongs to some candidate key.

Normal form	Condition
1NF	every attribute value is atomic (no sets, lists or nested relations)
2NF	1NF, and no non-prime attribute is functionally dependent on a proper subset of any candidate key (no partial dependency)
3NF	for every nontrivial $X \to A$ in $F^+$ : $X$ is a superkey or $A$ is prime
BCNF	for every nontrivial $X \to A$ in $F^+$ : $X$ is a superkey

Equivalent form of 3NF. $R$ is in 3NF iff no non-prime attribute is transitively dependent on a candidate key, that is, there is no chain key $\to X \to A$ with $X$ not a superkey, $A$ non-prime, and $A\notin X$ (the last FD must be nontrivial).

Inclusions. BCNF $\subset$ 3NF $\subset$ 2NF $\subset$ 1NF, and each inclusion is strict.

Four nested regions: 1NF outermost, then 2NF, 3NF and BCNF innermost, each labelled with its condition and an example relation that is in that form but not the next — Figure 1. The normal forms as nested classes, with one relation in each band: $R(A, B, C, D)$ with $AB \to CD$ , $B \to C$ is only in 1NF; with $A \to B$ , $B \to C$ , $C \to D$ it is in 2NF; $R(A, B, C)$ with $AB \to C$ , $C \to B$ is in 3NF; with $A \to BC$ it is in BCNF.

How it works: finding the highest normal form

Find all candidate keys and the prime attributes.
BCNF: for every FD $X \to Y$ of the given $F$ (nontrivial part only), check that $X^+ = R$ . If all pass, the relation is in BCNF.
3NF: for every FD $X \to A$ of $F$ (split right sides) that failed step 2, check whether $A$ is prime. If every failure has a prime $A$ , the relation is in 3NF.
2NF: for every candidate key $K$ and every proper subset $S \subset K$ , check whether $S^+$ contains a non-prime attribute not in $S$ . If none does, the relation is in 2NF.
Otherwise it is in 1NF (assuming atomic values).

Testing with $F$ instead of $F^+$ . For the relation $R$ itself, steps 2 and 3 may use the given $F$ : if some FD of $F^+$ violates BCNF or 3NF, some FD of $F$ does too. This shortcut is not valid for a sub-relation $R_i$ of a decomposition: there the FDs that hold are the projection of $F^+$ onto $R_i$ , which can contain FDs that appear in no member of $F$ . The next note shows an instance.

Algorithms and pseudocode

Text

HIGHEST-NF(R, F)
  K <- CANDIDATE-KEYS(R, F); P <- union of the keys     // prime attributes
  bcnf <- true; third <- true
  for each X -> A in F with A not in X
      if CLOSURE(X, F) != R then
          bcnf <- false
          if A not in P then third <- false
  if bcnf then return "BCNF"
  if third then return "3NF"
  for each key k in K, for each proper subset S of k
      if (CLOSURE(S, F) - S) contains an attribute not in P then return "1NF"
  return "2NF"

Cost is dominated by finding candidate keys, exponential in the worst case; each closure is polynomial.

Mathematical explanation

Why the inclusions hold. BCNF implies 3NF because its condition is the first disjunct of the 3NF condition. 3NF implies 2NF: a partial dependency $S \to A$ with $S \subset K$ and $A$ non-prime is a nontrivial FD whose left side $S$ is not a superkey (a proper subset of a candidate key cannot be a superkey, by minimality) and whose right side is non-prime, so it violates 3NF.

Useful sufficient conditions. The singleton-key and two-attribute shortcuts below, including their repetitions in examples, traps and the summary, assume no nontrivial empty-determinant (constant) dependencies. Without that assumption, test the empty subset too using the general definitions.

Assuming no nontrivial empty-determinant FDs, if every candidate key is a single attribute, the relation is in 2NF (a single attribute has no non-empty proper subset).
If every attribute is prime, the relation is in 3NF (the second disjunct always holds).
With no nontrivial empty-determinant FDs, every relation with exactly two attributes is in BCNF: any nontrivial FD is $A \to B$ or $B \to A$ , and then its left side determines both attributes.

Why 3NF exists alongside BCNF. Some relations have no BCNF decomposition that preserves all dependencies (the relation $R(A, B, C)$ with $AB \to C$ , $C \to B$ is the standard case), while a dependency-preserving, lossless 3NF decomposition always exists. 3NF is the compromise that tolerates a little redundancy to keep every FD checkable in one table.

Worked examples

#	Relation and FDs	Candidate keys	Highest form	Reason
1	$R(A, B, C, D)$ ; $AB \to CD$ , $B \to C$	$AB$	1NF	$B \to C$ is partial ( $C$ non-prime)
2	$R(A, B, C, D)$ ; $A \to B$ , $B \to C$ , $C \to D$	$A$	2NF	single-attribute key; $B \to C$ transitive
3	$R(A, B, C, D)$ ; $AB \to C$ , $C \to D$	$AB$	2NF	no partial FD; $C \to D$ transitive
4	$R(A, B, C)$ ; $AB \to C$ , $C \to B$	$AB$ , $AC$	3NF	$C$ not a superkey but $B$ prime
5	$R(A, B, C, D, E)$ ; $A \to B$ , $BC \to E$ , $ED \to A$	$ACD$ , $BCD$ , $CDE$	3NF	all attributes prime; $A \to B$ breaks BCNF
6	$R(A, B, C, D, E, G)$ ; $BE \to G$ , $D \to E$ , $AB \to C$ , $C \to D$ , $G \to A$	$AB$ , $BC$ , $BD$ , $BE$ , $BG$	3NF	all prime; $D \to E$ breaks BCNF
7	$R(A, B, C)$ ; $A \to BC$	$A$	BCNF	the only left side is a key

Example 8: the anomaly relation. STUDENT_DEPT(roll, name, dept, hod) with roll $\to$ name, dept and dept $\to$ hod. Key: roll. Single-attribute key, so 2NF; dept $\to$ hod has a non-superkey left side and non-prime right side, so not 3NF. Splitting into (roll, name, dept) and (dept, hod) gives two BCNF relations and removes all three anomalies.

Example 9: a partial dependency on a prime attribute is allowed in 2NF. In Example 4, $C \to B$ has left side $C$ , a proper subset of key $AC$ , but $B$ is prime, so it is not a 2NF violation (and the relation is even in 3NF).

Example 10: three overlapping keys. $R(A, B, C, D)$ with $AB \to C$ , $C \to D$ , $D \to A$ .

$B$ is on no right side, so it is in every key. $B^+ = B$ .
$(AB)^+ = ABCD$ , $(BC)^+ = BCDA$ , $(BD)^+ = ABCD$ . So $AB$ , $BC$ , $BD$ are keys, and every attribute is prime.
3NF holds because every right side is prime. BCNF fails: $C^+ = ACD$ , so $C \to D$ has a non-superkey left side.
The three keys pairwise share $B$ : 3NF without BCNF happens only when candidate keys overlap.

Example 11: the chosen primary key hides a partial dependency. $R(A, B, C, D, E)$ with $A \to BCDE$ , $BC \to A$ , $C \to D$ .

$A^+ = ABCDE$ , so $A$ is a key. $(BC)^+ = ABCDE$ , and neither $B^+ = B$ nor $C^+ = CD$ is $R$ , so $BC$ is also a key. Candidate keys: $A$ , $BC$ . Prime attributes: $A$ , $B$ , $C$ .
$C \to D$ : $C$ is a proper subset of the candidate key $BC$ and $D$ is non-prime. That is a partial dependency, so the relation is not in 2NF; the highest form is 1NF.
If only the primary key $A$ is examined, the relation looks like 2NF because $A$ has no proper subset. The 2NF test runs over every candidate key.

Important properties and observations

Only non-prime attributes matter for 2NF and 3NF; BCNF ignores primality.
Two-attribute relations are always in BCNF.
A relation whose only key is all its attributes (no nontrivial FD) is in BCNF.
Check all candidate keys, not only the primary key, when deciding primality and partial dependency.
Test on $F$ for the whole relation; on the projection of $F^+$ for a sub-relation.
Normal form is a property of the schema with its FDs, not of one instance.

Related material. Fourth normal form (4NF) uses multivalued dependencies $X \twoheadrightarrow Y$ : a relation is in 4NF if every nontrivial MVD has a superkey on the left. It removes redundancy that FDs cannot describe, such as an employee's independent sets of skills and languages stored in one table. 5NF uses join dependencies.

Common misconceptions.

"3NF means no transitive dependency at all." Only no transitive dependency of a non-prime attribute.
"If the primary key is a single attribute, the relation is in 3NF." Not even 2NF is guaranteed: 2NF needs every candidate key to be a single attribute (or no partial dependency on a composite one), as Example 11 shows. With no constant dependencies, every candidate key being a singleton guarantees 2NF, but not 3NF; otherwise test empty subsets too.
"BCNF and 3NF differ only when there are composite keys." They differ when a non-superkey determines a prime attribute, which needs overlapping candidate keys.

GATE examination perspective

Highest normal form. Keys first, then BCNF, 3NF, 2NF tests in that order.
Prime attributes from overlapping keys. Relations where every attribute is prime are at least 3NF.
Partial versus transitive dependency. Classify a given FD as the cause of a 2NF or 3NF violation.
Which FD set makes the relation BCNF. Pick the option where every nontrivial FD has a superkey on its left side.
Anomalies. Recognise which anomaly a given redundancy causes.

Summary

Functional Dependencies, Closure and Canonical Cover: prerequisite; closure, keys and primality.
Lossless-Join and Dependency-Preserving Decomposition: dependent; how to reach 3NF and BCNF by splitting relations.

Normal Forms: 1NF, 2NF, 3NF and BCNF

Introduction

Prerequisites

Core concepts

How it works: finding the highest normal form

Algorithms and pseudocode

Mathematical explanation

Worked examples

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

How it works: finding the highest normal form

Algorithms and pseudocode

Mathematical explanation

Worked examples

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps