/    /  DBMS – BCNF  Decomposition Algorithm

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:

 

  1. α → β  is a trivial functional dependency. (β ⊆ α)
  2. α 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

BCNF  Decomposition Algorithm