Hamish Burke | 2025-05-29

Related to: #databases

BCNF Decomposition Algorithm

Goal is to decompose a relation schema into BCNF while preserving lossless join (though not dependency preservation)

Steps

First check if not already BCNF
Find a violation (where FD $X \to A$ , $X$ is not a Superkey of $R$ )
Decompose
1. Replace $R$ with two new schemas
  1. $R_{1} = X \cup A$
  2. $R_{2} = R - A \cup X$
2. Compute $F_{1} = F + projected onto R_{1}$
3. Compute $F_{2} = F + projected onto R_{2}$
Repeat until all schemas are BCNF

Example

$R = {A, B, C}$

$F = {A \to B, B \to C}$

$A \to B$ : $A$ is a superkey ( $A ⋆ = A B C$ )
$B \to C$ : $B$ is not a superkey ( $B ⋆ = B C$ )
1. $R_{1} = {B, C}$
  1. $F_{1} = {B \to C}$
2. $R_{2} = {A, B}$
  1. $F_{2} = {A \to B}$
$R_{1}, R_{2}$ both result in BCNF (with their FD $X \to A$ , $X ⋆$ being a superkey)
Done