2NF and 3NF

A relation schema $R$ with a set of functional dependencies $F$ is in First Normal Form if every attribute holds atomic values — the baseline assumed here. A candidate key of $R$ is a minimal set of attributes that functionally determines all attributes of $R$. An attribute is prime if it belongs to some candidate key; otherwise it is non-prime.

Second Normal Form (2NF). $R$ is in 2NF if it is in 1NF and every non-prime attribute is fully functionally dependent on every candidate key — meaning no non-prime attribute depends on a proper subset of a candidate key. This condition is vacuous whenever every candidate key has a single attribute, so 2NF violations arise only from composite candidate keys. The forbidden pattern is a partial dependency: $\alpha \to \beta$ where $\alpha$ is a proper subset of some candidate key $K$, and $\beta$ is a non-prime attribute not contained in $\alpha$.

Third Normal Form (3NF). $R$ is in 3NF if it is in 1NF and, for every nontrivial functional dependency $\alpha \to \beta$ in the closure $F^+$, at least one of the following holds: 1. $\alpha$ is a superkey of $R$ (contains a candidate key), or 2. every attribute in $\beta - \alpha$ is prime (belongs to some candidate key). Condition 2 is the clause that BCNF drops — it is precisely what makes 3NF strictly weaker than Boyce-Codd Normal Form but also what lets 3NF always be achieved without losing any functional dependency. The forbidden pattern that 3NF rules out (beyond what 2NF already rules out) is a transitive dependency: a chain $K \to A \to B$ where $K$ is a candidate key, $A$ is a non-prime attribute not in $K$, $B$ is a non-prime attribute not in $A$, and $A \not\to K$ (so the dependency is not simply a key rearrangement). Here $B$ depends on $K$ only through $A$, not directly. Every 3NF relation is automatically in 2NF, because a partial dependency $\alpha \to \beta$ (with $\alpha \subsetneq K$, $\beta$ non-prime) is itself a violation of 3NF's condition 2 (unless $\beta$ happens to be prime, contradicting non-primeness) — so 2NF is logically implied by 3NF. The two forms are presented separately because partial dependencies and transitive dependencies are diagnosed by different visual patterns in practice, and historically 2NF was formulated first as an intermediate stepping stone.

Both normal forms are checked and repaired by the same two-part recipe: (1) compute the candidate keys from $F$, then (2) scan $F$ for the forbidden dependency pattern and decompose whenever one is found. Decomposition means replacing $R$ with two or more smaller relations, each holding one determinant and everything it determines, so that the guilty dependency becomes a full (or non-transitive) dependency inside its new, smaller relation.

Step 1 — Find candidate keys. Compute the attribute closure $\alpha^+$ under $F$ for candidate subsets $\alpha$, starting from attributes that never appear on the right-hand side of any dependency (they must be in every candidate key), and search minimal supersets whose closure is all of $R$.

Step 2 — Test for 2NF. For each candidate key $K$, and for each proper nonempty subset $\alpha \subsetneq K$, compute $\alpha^+$. If $\alpha^+$ contains a non-prime attribute not in $\alpha$, that is a partial dependency: decompose $R$ into $R_1 = \alpha \cup \alpha^+$ (its own relation) and $R_2 = R - (\alpha^+ - \alpha)$ (the rest of $R$, still keyed by $K$).

Step 3 — Test for 3NF. For each dependency $\alpha \to \beta$ in a minimal cover of $F$, check whether $\alpha$ is a superkey or every attribute of $\beta$ is prime. If neither holds, decompose by projecting $R$ onto $\alpha \cup \beta$ (call it $R_\alpha$) and onto $(R - \beta) \cup \alpha$ (the remainder, still containing $\alpha$ as a bridge). In practice, rather than patching one violation at a time, designers use the 3NF synthesis algorithm, which builds a provably correct decomposition directly from a canonical cover in one pass, guaranteeing both properties every good decomposition needs:

• Lossless join: joining the decomposed relations back together, via natural join, reconstructs exactly the original relation — no spurious rows appear.
• Dependency preservation: every functional dependency in $F$ can be checked locally, within a single decomposed relation, without needing to join relations back together to verify it.

``` ALGORITHM Synthesize3NF(R, F):

# Step 1: compute a canonical (minimal) cover Fc of F Fc = MinimalCover(F)

# (a) split every RHS into single attributes: alpha -> {b1,...,bn}

# becomes alpha -> b1, ..., alpha -> bn

# (b) remove any extraneous attribute from each LHS

# (attribute a in alpha is extraneous if

# (alpha - a)+ still contains the RHS attribute)

# (c) remove any dependency alpha -> b that is implied by the rest,

# i.e. redundant if alpha+ (computed over Fc - {alpha->b}) contains b

# Step 2: group dependencies that share the same left-hand side group Fc by LHS: L1 -> {b11, b12, ...}, L2 -> {b21, ...}, ... for each group with LHS Li and RHS set Bi: create relation schema Ri = Li union Bi declare Li -> Bi as the FD(s) of Ri Li is a candidate key of Ri (by construction, minimal cover has no redundancy)

# Step 3: ensure a key of the original relation R is represented somewhere if no Ri's attribute set is a superkey of R: compute one candidate key K of R (via attribute closure search) add a new relation schema R_K = K with no non-key attributes

# Step 4: remove redundant relations for each Ri: if Ri's attributes are a subset of some Rj's attributes (i != j): discard Ri return { R1, R2, ..., Rm } # the 3NF decomposition ``` Two subroutines are used as black boxes above and deserve their own statement, since correctness of the whole algorithm rests on them. ``` FUNCTION AttributeClosure(alpha, F): result = alpha repeat: changed = false for each dependency (beta -> gamma) in F: if beta subset of result and gamma not subset of result: result = result union gamma changed = true until not changed return result FUNCTION MinimalCover(F): Fc = SplitRHS(F) # single attribute on each RHS for each dependency d = (alpha -> b) in Fc: for each attribute a in alpha: if b in AttributeClosure(alpha - a, Fc): alpha = alpha - a # a was extraneous; shrink LHS update d to (alpha -> b) for each dependency d = (alpha -> b) in Fc: if b in AttributeClosure(alpha, Fc - {d}): Fc = Fc - {d} # d is redundant given the rest return Fc ```

Computing attribute closure. `AttributeClosure(alpha, F)` runs in $O(|F| \cdot |R|)$ time in the naive form shown: each outer pass scans all dependencies, and the closure set grows by at least one attribute per productive pass, so there are at most $|R|$ passes, each costing $O(|F|)$ to scan. With better bookkeeping (a count of unsatisfied LHS attributes per dependency, decremented as attributes are added), this drops to $O(|F| \cdot |R|)$ worst case with a much smaller constant, or effectively linear in the total size of $F$ using standard graph-reachability tricks — the standard result used across normalization theory.

Computing a minimal cover. `MinimalCover` calls `AttributeClosure` $O(|F| \cdot |R|)$ times (once per attribute-removal test, and once per dependency-redundancy test), giving overall complexity polynomial in the size of the input dependency set — specifically $O(|F|^2 \cdot |R|^2)$ in the straightforward implementation. This is entirely tractable because real schemas have $F$ and $R$ of modest size (tens of dependencies, tens of attributes), never the exponential blow-up seen in candidate-key enumeration for pathological dependency sets.

Finding all candidate keys is, in the worst case, exponential in the number of attributes, since a relation can have an exponential number of minimal keys relative to $|R|$ in adversarially constructed dependency sets. In practice this is a non-issue: the synthesis algorithm above needs only one candidate key of the original $R$ (for Step 3), not the full set, and finding one key takes polynomial time by greedily removing attributes from $R$ while the closure remains $R$.

Correctness of 2NF decomposition. Suppose $\alpha \to \beta$ is a partial dependency with $\alpha \subsetneq K$ for candidate key $K$, and $\beta$ non-prime. Splitting into $R_1 = \alpha \cup \beta$ and $R_2 = R - \beta$ is lossless because $\alpha$ is a key of $R_1$ (by minimality of the dependency) and $\alpha \subseteq R_2$, so $R_1 \cap R_2 = \alpha \to R_1$ holds — satisfying the lossless-join test: a decomposition into $R_1, R_2$ is lossless iff $(R_1 \cap R_2) \to R_1$ or $(R_1 \cap R_2) \to R_2$ is in $F^+$. Here it holds with $R_1$, so no spurious tuples are introduced when the two projections are joined back via natural join.

Correctness of 3NF synthesis (sketch). The synthesis algorithm's guarantees rest on two facts, both provable from the construction:

• Dependency preservation holds because every dependency in the minimal cover $F_c$ appears, verbatim, inside exactly one synthesized relation $R_i = L_i \cup B_i$ — so checking $F$ never requires joining relations.
• Lossless join holds because Step 3 guarantees some relation's attributes form a superkey $K$ of the original $R$. A classical theorem states that if one relation of a decomposition contains a candidate key of the whole schema, and every dependency in $F$ is preserved somewhere in the decomposition, the join of all decomposed relations reconstructs $R$ exactly — extra tuples cannot appear because the key relation pins down, functionally, every other attribute value that must appear alongside it, and no dependency forces two different join results for the same key value.

Formally, the join-back proof proceeds by showing $r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie \cdots \bowtie \Pi_{R_m}(r)$ for any relation instance $r$ satisfying $F$: the $\subseteq$ direction is immediate (every tuple of $r$ projects into every $R_i$ and those projections rejoin to reproduce it), and the $\supseteq$ direction uses induction on the join order, at each step relying on the fact that the join attributes between the partially-joined relation and the next $R_i$ functionally determine one side (by construction of the synthesis), which is precisely the lossless-join test above applied repeatedly.

Tradeoffs. 3NF is always achievable while preserving both properties simultaneously — this is the celebrated guarantee that Boyce-Codd Normal Form cannot always offer, since eliminating every anomaly BCNF targets can sometimes force giving up dependency preservation. 3NF is therefore the practical "sweet spot" used by most production schemas: some redundancy from condition 2's exception can remain (a prime attribute may still be redundantly repeated), but every dependency stays locally checkable, which matters enormously for constraint enforcement via ordinary primary/foreign keys without triggers spanning multiple tables.

Consider an original, unnormalized order-tracking relation:

with functional dependency set $F$:

Step 1 — candidate key. OrderID and ProductID appear only on left-hand sides among the composite dependency, and $\{OrderID, ProductID\}^+ = \{OrderID, ProductID, CustName, CustCity, ProdName, ProdCategory, Qty\}$ = all attributes. Removing either attribute fails to reach CustName or ProdName respectively, so $K = \{OrderID, ProductID\}$ is the unique candidate key. All other six attributes are non-prime.

Step 2 — check 2NF. Test proper subsets of $K$:

Two partial dependencies exist, so OrderLine violates 2NF. Decompose:

Each is now checked: $R_3$'s only dependency, $\{OrderID,ProductID\} \to Qty$, is full (the key is the whole LHS), so $R_3$ is in 2NF (trivially, since it has no proper key subset smaller than the full key producing extra attributes). $R_1$ and $R_2$ have single-attribute keys, so 2NF is automatic for them.

Step 3 — check 3NF. Inspect $R_1(OrderID, CustName, CustCity)$ with key $\{OrderID\}$. Suppose business rules add the realistic dependency $CustCity \to$ (some sales-tax rate) — but here suppose instead a simpler, common real-world addition: $CustCity \to SalesRegion$. Extend $R_1$ to $R_1'(OrderID, CustName, CustCity, SalesRegion)$ with dependencies

Now test 3NF on $CustCity \to SalesRegion$: is $CustCity$ a superkey of $R_1'$? No — $\{CustCity\}^+ = \{CustCity, SalesRegion\} \ne R_1'$. Is $SalesRegion$ prime? No, the only candidate key is $\{OrderID\}$. Both 3NF escape clauses fail: this is a transitive dependency $OrderID \to CustCity \to SalesRegion$. Decompose:

Final 3NF schema:

Every dependency in the original $F$ (plus the added CustCity rule) is preserved locally in exactly one relation, and $R_3$ still carries a superkey of the original relation, so the join of all four relations losslessly reconstructs every valid instance of the original combined table — while now update, insertion, and deletion anomalies involving customer city or product category are impossible, because each fact lives in exactly one row of exactly one relation.

Every mainstream relational database system — PostgreSQL, MySQL, Oracle, SQL Server — is designed on the assumption that schemas fed to it will be normalized at least to 3NF for transactional (OLTP) workloads, and enforcement of foreign keys, unique constraints, and cascading deletes is built around the idea that each table owns exactly one determinant's worth of facts. Entity-Relationship modeling tools and ORM frameworks (Hibernate, Django ORM, ActiveRecord) generate schemas that are 3NF by default whenever relationships are declared with proper foreign keys, implicitly running a version of the synthesis logic in the tool's schema generator. Database design courses and certification exams (and real interview screens for backend engineering roles) routinely test the ability to spot partial and transitive dependencies in a proposed table, because the anomalies they cause — duplicate customer addresses scattered across order rows, orphaned product categories after the last product in that category is deleted — are among the most common data-quality bugs found in production systems. Data warehouse design deliberately reverses course with denormalized star schemas for read-heavy analytics, which only makes sense as a conscious tradeoff once the underlying 3NF-normalized operational schema is understood; and the entire theory here is the direct stepping stone to the stricter guarantees of Boyce-Codd Normal Form and the general machinery of Lossless-Join Decomposition used whenever a schema must be split correctly for any reason, normalization or otherwise.

Ask the tutor: How does the 3NF synthesis algorithm's guarantee break down if you skip computing a minimal cover first?