Boyce-Codd Normal Form

Schema $R$ is in BCNF with respect to a set of functional dependencies $F$ if and only if whenever $(X\to Y)\in F^{+}$ where $XY\subseteq R$ then at least one of the following hold:

1. $X\to Y$ is trivial ($Y\in X$)
2. $X$ is a superkey of $R$

Database schema $⟨p=\{R_1,\dots ,R_n\},F⟩$ is in BCNF if each relation schema $R_i$ is in BCNF with respect to $F$

Algorithm

function computeBCNF(R, F)
begin
    Result := {R};
    while some Ri ∈ Result and (X -> Y) ∈ F+
            violate the BCNF condition do begin
        Replace Ri by Ri - (Y - X);
        Add X ∪ Y to Result;
    end;
    return Result;
end

Correctness Theorem for ComputeBCNF

Function ComputeBCNF(R,F) returns a lossless-join decomposition of $R$ for which each table in the decomposition is in BCNF with respect to $F$