Third Normal Form

Schema $R$ is in 3NF with respect to a set of functional dependencies $F$ if and only if whenever $(X→Y)\in F^+) and $X Y \subseteq R$ then one of the following holds:

$X \to Y$ is trivial
$X$ is a superkey of $R$
Each attribute of $Y - X$ is contained in a candidate key of $R$

Database schema $⟨ p = {R_{1}, \dots, R_{n}}, F ⟩$ is in 3NF if each relation schema $R_{i}$ is in 3NF with respect to $F$

BCNF implies 3NF

$R = {A, B, C}$ is in 3NF with respect to $F = {A B \to C, C \to B}$

Lossless-Join and Dependency Preserving decomposition into 3NF relation schemata always exists

Compute 3NF Decomposition

Assume $R$ is a set of Attributes and $F$ a set of FDs over $R$

We will need the minimal cover

function Compute3NF(R, F)
begin
    Result := ∅;
    G := minimal cover for F;
    for each (X -> Y) ∈ G do
        Result := Result ∪ {XY};
    if there is no Ri ∈ Result such that
        Ri contains a candidate key for R then begin
            compute a candidate key K for R;
            Result := Result ∪ {K};
    end;
    return Result;
end

Add all FDs in minimal cover as decompositions
Then add a candidate key decomposition if there doesn’t exists one

Correctness Theorem

Compute3NF( $R, F$ ) returns a lossless-join decomposition of $R$ that is also dependency preserving and for which each table in the decomposition is in 3NF with respect to $F$