Zerlegungsalgorithmus Normalform

Der Zerlegungsalgorithmus Normalform überführt einen Datenbankentwurf in ein Relationenschema der Boyce-Codd-Normalform (BCNF). Dabei können allerdings funktionale Abhängigkeiten verloren gehen.

Eingabe: universelles Schema R=(U,F)
Ausgabe: verbundstreue ("lossless-join") BCNF-Zerlegung D=(R,.)
  
 1  $R:=\{R\}$
 2  done:=false
 3  while not done
 4     if $(\exists R_{i}\in R):R_{i}$ not in BCNF and insb. $(\exists Y\rightarrow Z\in F_{i}^{+},Z\cap Y=\varnothing ):Y\rightarrow X_{i}\notin F_{i}^{+}$
 5        $X_{i,1}=YZ$
 6        $X_{i,2}=X_{i}-Z$
 7        $R_{i,1}=(X_{i,1},\pi _{x_{i,1}}(F_{i}^{+}))$
 8        $R_{i,2}=(X_{i,2},\pi _{x_{i,2}}(F_{i}^{+}))$
 9        $R:=R-\{R_{i}\}\cup \{R_{i,1},R_{i,2}\}$
10     else
11        done:=true

In einfachen Worten:

1. Die Menge R wird so lange bearbeitet, bis alle Elemente in BCNF sind.
2. Wenn ein $R_{i}$ noch nicht in BCNF ist, dann wird dieses wie folgt in zwei Teile zerlegt

Erweiterung für 4. Normalform

Durch minimale Anpassungen kann der Algorithmus auch für die 4. Normalform (siehe Normalisierung) verwendet werden.

1. Fasse funktionale Abhängigkeiten $FD$ und mehrwertige Abhängigkeiten $MVD$ zu einer Menge $D$ zusammen
2. Verwende an Stelle von $F^{+}$ die durch $D$ implizierte Menge $D^{+}$

Oben stehender Algorithmus ist sodann analog anwendbar:

1 $R:=\{R\}$
2 done:=false
3 while not done
4    if $(\exists R_{i}\in R):R_{i}$ not in 4NF and insb. $(\exists Y\rightarrow \rightarrow Z\in D_{i}^{+},Z\cap Y=\varnothing ):Y\rightarrow R_{i}\notin D^{+}$
5       $R:=R-\{R_{i}\}\cup \{(R_{i}-Z)\}\cup \{(Y,Z)\}$
6    else
7       done:=true