BCNF Decomposition Algorithm
Definition: Let there be a relation R.
Let F be the set of Functional Dependencies applicable on R.
Let F+ be a closure set of F.
Here, R is said to be in BCNF, if for every FD of the form α → β (α ⊆ R and β ⊆ R.) in F+ satisfies one of the following two conditions:
- α → β is a trivial functional dependency. (β ⊆ α)
- α is a super key of R.
Algorithm: The following is the algorithm for BCNF composition.
Result = {R} ;
done = false ;
compute F+ ;
while (not done) do
if (there is a schema Ri in result that is not in BCNF)
then begin
Let α → β be a non-trivial FD that holds
on Ri such that α → Ri is not in F+
And α ∩ β = ∅
Result= ( result – Ri) U ( Ri – β ) U ( α, β ) ;
end
else done = true ;
Note: The above algorithm is developed based on the BCNF definition.
Reference Link