Synthesealgorithmus

Der Synthesealgorithmus beschreibt, wie aus einem relationalen Datenbankschema ein Relationenschema der dritten Normalform wird. Das besondere an diesem Algorithmus ist, dass er im Gegensatz zu der intuitiven Zerlegung des Schemas in die dritte Normalform die Abhängigkeitserhaltung in jedem Fall garantiert.

Ein alternativer Algorithmus ist der Zerlegungsalgorithmus, welcher in die Boyce-Codd-Normalform (BCNF) transferiert. Dabei können allerdings Abhängigkeiten verloren gehen (nicht abhängigkeitstreu). Er ist insofern eine Alternative, als jedes relationale Schema, welches in BCNF transformiert wird, dann auch automatisch in dritter Normalform vorliegt.

Es müssen alle funktionalen Abhängigkeiten ${\displaystyle {\mathcal {F}}}${\displaystyle {\mathcal {F}}} der zu zerlegenden Relation ${\displaystyle R}${\displaystyle R} unter den Attributen bekannt sein.

Beispiel:

• ${\displaystyle R=\operatorname {Relation} (A,B,C,D,E,F)}${\displaystyle R=\operatorname {Relation} (A,B,C,D,E,F)}
• ${\displaystyle {\mathcal {F}}=\left\{\left\{A\right\}\to \left\{B,E\right\},\left\{A,E\right\}\to \left\{B,D\right\},\left\{F\right\}\to \left\{C,D\right\},\left\{C,D\right\}\to \left\{B,E,F\right\},\left\{C,F\right\}\to \left\{B\right\}\right\}}${\displaystyle {\mathcal {F}}=\left\{\left\{A\right\}\to \left\{B,E\right\},\left\{A,E\right\}\to \left\{B,D\right\},\left\{F\right\}\to \left\{C,D\right\},\left\{C,D\right\}\to \left\{B,E,F\right\},\left\{C,F\right\}\to \left\{B\right\}\right\}}

Der Synthesealgorithmus besteht dann aus vier Schritten:

1. Reduktion von ${\displaystyle {\mathcal {F}}}${\displaystyle {\mathcal {F}}}, d. h. die Bestimmung der kanonischen Überdeckung.
2. Erzeugen der neuen Relationenschemata aus der kanonischen Überdeckung.
3. Ggf. die Hinzunahme einer Relation, die nur den Ursprungsschlüssel enthält.
4. Elimination der Schemata, die in einem anderen Schema enthalten sind.

Dies wird auch die Berechnung der kanonischen Überdeckung genannt.

Für alle ${\displaystyle \psi \in \Psi }${\displaystyle \psi \in \Psi } ersetze ${\displaystyle \Psi \rightarrow \Gamma }${\displaystyle \Psi \rightarrow \Gamma } durch ${\displaystyle \Psi \setminus \{\psi \}\rightarrow \Gamma }${\displaystyle \Psi \setminus \{\psi \}\rightarrow \Gamma } , falls ${\displaystyle \Gamma }${\displaystyle \Gamma } schon durch ${\displaystyle \Psi \setminus \{\psi \}\rightarrow \Gamma }${\displaystyle \Psi \setminus \{\psi \}\rightarrow \Gamma } determiniert ist.

Die obige Bedingung lässt sich testen, indem man überprüft, ob ${\displaystyle \Gamma \subseteq \mathop {\mathrm {AttributH{\ddot {u}}lle} } (F,\Psi \setminus \{\psi \})}${\displaystyle \Gamma \subseteq \mathop {\mathrm {AttributH{\ddot {u}}lle} } (F,\Psi \setminus \{\psi \})} ist,^[1] wobei F die Menge der funktionalen Abhängigkeiten bezeichnet. Falls dies zutrifft, kann ${\displaystyle \psi }${\displaystyle \psi } aus ${\displaystyle \Psi }${\displaystyle \Psi } entfernt werden.

Beispiel: ${\displaystyle \mathop {\mathrm {Relation} } \left(A,B,C,D,E,F\right)}${\displaystyle \mathop {\mathrm {Relation} } \left(A,B,C,D,E,F\right)}

• ${\displaystyle A\rightarrow B,E}${\displaystyle A\rightarrow B,E}
• ${\displaystyle A{\underline {E}}\rightarrow B,D}${\displaystyle A{\underline {E}}\rightarrow B,D}
• ${\displaystyle F\rightarrow C,D}${\displaystyle F\rightarrow C,D}
• ${\displaystyle CD\rightarrow B,E,F}${\displaystyle CD\rightarrow B,E,F}
• ${\displaystyle {\underline {C}}F\rightarrow B}${\displaystyle {\underline {C}}F\rightarrow B}

In der zweiten funktionalen Abhängigkeit fällt E weg, da sich B und D in der Attributhülle von A (${\displaystyle A^{+}=\{A,{\underline {B,D}},E\}}${\displaystyle A^{+}=\{A,{\underline {B,D}},E\}}) befinden. In der letzten funktionalen Abhängigkeit fällt C weg, wegen ${\displaystyle F^{+}=\{{\underline {B}},C,D,E,F\}}${\displaystyle F^{+}=\{{\underline {B}},C,D,E,F\}}. Man kann es auch so formulieren: E wird in ${\displaystyle AE\rightarrow B,D}${\displaystyle AE\rightarrow B,D} nicht benötigt, um ${\displaystyle B,D}${\displaystyle B,D} zu erreichen.

Lösung:

• ${\displaystyle A\rightarrow B,E}${\displaystyle A\rightarrow B,E}
• ${\displaystyle A\rightarrow B,D}${\displaystyle A\rightarrow B,D}
• ${\displaystyle F\rightarrow C,D}${\displaystyle F\rightarrow C,D}
• ${\displaystyle CD\rightarrow B,E,F}${\displaystyle CD\rightarrow B,E,F}
• ${\displaystyle F\rightarrow B}${\displaystyle F\rightarrow B}

Für alle ${\displaystyle \gamma \in \Gamma }${\displaystyle \gamma \in \Gamma } ersetze ${\displaystyle \Psi \rightarrow \Gamma }${\displaystyle \Psi \rightarrow \Gamma } durch ${\displaystyle \Psi \rightarrow \Gamma \setminus \{\gamma \}}${\displaystyle \Psi \rightarrow \Gamma \setminus \{\gamma \}}, falls ${\displaystyle \gamma }${\displaystyle \gamma } schon transitiv durch ${\displaystyle \Psi }${\displaystyle \Psi } bestimmt ist.

Die obige Bedingung lässt sich überprüfen, indem man für jedes ${\displaystyle \gamma \in \Gamma }${\displaystyle \gamma \in \Gamma } testet, ob ${\displaystyle \gamma \in {\text{AttributHuelle}}((F\setminus (\Psi \rightarrow \Gamma ))\cup (\Psi \rightarrow (\Gamma \setminus \{\gamma \})),\Psi )}${\displaystyle \gamma \in {\text{AttributHuelle}}((F\setminus (\Psi \rightarrow \Gamma ))\cup (\Psi \rightarrow (\Gamma \setminus \{\gamma \})),\Psi )} ist. Falls dies zutrifft, kann ${\displaystyle \gamma }${\displaystyle \gamma } aus ${\displaystyle \Gamma }${\displaystyle \Gamma } entfernt werden. Hierbei handelt es sich um ein iteratives Verfahren, d. h. ${\displaystyle F}${\displaystyle F} enthält in jedem Schritt die bereits in vorherigen Schritten aktualisierten Abhängigkeiten.

An obigem Beispiel:

• ${\displaystyle A\rightarrow {\underline {B}},E}${\displaystyle A\rightarrow {\underline {B}},E}
• ${\displaystyle A\rightarrow B,D}${\displaystyle A\rightarrow B,D}
• ${\displaystyle F\rightarrow C,D}${\displaystyle F\rightarrow C,D}
• ${\displaystyle CD\rightarrow {\underline {B}},E,F}${\displaystyle CD\rightarrow {\underline {B}},E,F}
• ${\displaystyle F\rightarrow B}${\displaystyle F\rightarrow B}

In der ersten funktionalen Abhängigkeit fällt B weg, da ${\displaystyle A_{F'}^{+}=\{A,{\underline {B}},D,E\}}${\displaystyle A_{F'}^{+}=\{A,{\underline {B}},D,E\}}. In der vierten funktionalen Abhängigkeit fällt ebenfalls das B weg, wegen ${\displaystyle CD_{F'}^{+}=\{{\underline {B}},C,D,E,F\}}${\displaystyle CD_{F'}^{+}=\{{\underline {B}},C,D,E,F\}}.

• ${\displaystyle A\rightarrow E}${\displaystyle A\rightarrow E}
• ${\displaystyle A\rightarrow B,D}${\displaystyle A\rightarrow B,D}
• ${\displaystyle F\rightarrow C,D}${\displaystyle F\rightarrow C,D}
• ${\displaystyle CD\rightarrow E,F}${\displaystyle CD\rightarrow E,F}
• ${\displaystyle F\rightarrow B}${\displaystyle F\rightarrow B}

Eliminiere Klauseln der Form ${\displaystyle \Psi \rightarrow \varnothing }${\displaystyle \Psi \rightarrow \varnothing }

Im Beispiel aus Schritt 2 gibt es keine Abhängigkeiten mit leerer rechter Seite. Also gibt es in diesem Fall hier nichts zu tun.

Fasse Formeln ${\displaystyle a\rightarrow b_{0},a\rightarrow b_{1}\dots }${\displaystyle a\rightarrow b_{0},a\rightarrow b_{1}\dots } zu ${\displaystyle a\rightarrow b_{0}\cup b_{1}\dots }${\displaystyle a\rightarrow b_{0}\cup b_{1}\dots } zusammen.

Im Beispiel fassen wir nun Ausdrücke mit gleicher linker Seite zusammen:

• ${\displaystyle A\rightarrow E,B,D}${\displaystyle A\rightarrow E,B,D}
• ${\displaystyle F\rightarrow C,D,B}${\displaystyle F\rightarrow C,D,B}
• ${\displaystyle CD\rightarrow E,F}${\displaystyle CD\rightarrow E,F}

Aus allen ${\displaystyle \Psi \to \Gamma }${\displaystyle \Psi \to \Gamma } wird ${\displaystyle R(\Psi ,\Gamma )}${\displaystyle R(\Psi ,\Gamma )}.

Zusätzlich muss ein neuer Schlüssel gefunden werden. Gegebenenfalls muss eine neue Relation erzeugt werden. Überflüssige Relationen können gestrichen werden, wenn diese in anderen enthalten sind.

Am Beispiel:

• ${\displaystyle R_{1}({\underline {A}},B,D,E)}${\displaystyle R_{1}({\underline {A}},B,D,E)} # ${\displaystyle A}${\displaystyle A} ist Primärschlüssel
• ${\displaystyle R_{2}(B,C,D,{\underline {F}})}${\displaystyle R_{2}(B,C,D,{\underline {F}})} # ${\displaystyle F}${\displaystyle F} ist Primärschlüssel
• ${\displaystyle R_{3}({\underline {C,D}},E,F)}${\displaystyle R_{3}({\underline {C,D}},E,F)} # ${\displaystyle CD}${\displaystyle CD} ist Primärschlüssel (Die Elemente dieser Relation sind zwar schon durch ${\displaystyle R_{1}}${\displaystyle R_{1}} und ${\displaystyle R_{2}}${\displaystyle R_{2}} gegeben, jedoch muss zur Abhängigkeitserhaltung diese weiterhin aufgeführt werden, es dürfte nur entfernt werden, wenn eine Relation vollends in einer anderen enthalten wäre. Dies ist jedoch nicht möglich, da diese Fälle vorher durch die Links- und Rechtsreduktion entfernt wurden.)

Nun muss durch Hinzunahme einer Relation eine Beziehung zwischen ${\displaystyle R_{1}}${\displaystyle R_{1}}, ${\displaystyle R_{2}}${\displaystyle R_{2}} und ${\displaystyle R_{3}}${\displaystyle R_{3}} hergestellt werden. Das wird durch eine Relation ${\displaystyle R_{4}}${\displaystyle R_{4}} ermöglicht, die nur den Ursprungsschlüssel ${\displaystyle AF}${\displaystyle AF} enthält (beachte, dass ${\displaystyle AF^{+}=\{A,B,C,D,E,F\}}${\displaystyle AF^{+}=\{A,B,C,D,E,F\}} ist). Wir erhalten ein Schema in der 3. Normalform wie folgt:

• ${\displaystyle R_{1}({\underline {A}},B,D,E)}${\displaystyle R_{1}({\underline {A}},B,D,E)}
• ${\displaystyle R_{2}(B,C,D,{\underline {F}})}${\displaystyle R_{2}(B,C,D,{\underline {F}})}
• ${\displaystyle R_{3}({\underline {C}},{\underline {D}},E,F)}${\displaystyle R_{3}({\underline {C}},{\underline {D}},E,F)}
• ${\displaystyle R_{4}({\underline {A}},{\underline {F}})}${\displaystyle R_{4}({\underline {A}},{\underline {F}})}, wobei ${\displaystyle A}${\displaystyle A} und ${\displaystyle F}${\displaystyle F} jeweils Fremdschlüssel darstellen und zusammengenommen den Primärschlüssel von ${\displaystyle R_{4}}${\displaystyle R_{4}} erzeugen.

Eingabe: universelles Schema ${\displaystyle R=(U,F)}${\displaystyle R=(U,F)}
Ausgabe: 3. Normalform ${\displaystyle D}${\displaystyle D} von ${\displaystyle R}${\displaystyle R}

${\displaystyle B:=\operatorname {reduction} (F)}${\displaystyle B:=\operatorname {reduction} (F)}

${\displaystyle R:=\emptyset }${\displaystyle R:=\emptyset }

${\displaystyle i:=0}${\displaystyle i:=0}

${\displaystyle \mathbf {for,円each} \;Y\subseteq U\;\mathbf {where} \;\exists A\in U.(Y\rightarrow A)\in B}${\displaystyle \mathbf {for,円each} \;Y\subseteq U\;\mathbf {where} \;\exists A\in U.(Y\rightarrow A)\in B}

${\displaystyle i:=i+1}${\displaystyle i:=i+1}

${\displaystyle X_{i}:=Y\cup \{,円A\in U,円|,円(Y\rightarrow A)\in B,円\}}${\displaystyle X_{i}:=Y\cup \{,円A\in U,円|,円(Y\rightarrow A)\in B,円\}}

${\displaystyle R_{i}:=(X_{i},\Pi _{X_{i}}(B))}${\displaystyle R_{i}:=(X_{i},\Pi _{X_{i}}(B))}

${\displaystyle R:=R\cup \{R_{i}\}}${\displaystyle R:=R\cup \{R_{i}\}}

${\displaystyle \mathbf {if} \;\forall R_{i}\in R.(X_{i}\rightarrow U)\notin B^{+}}${\displaystyle \mathbf {if} \;\forall R_{i}\in R.(X_{i}\rightarrow U)\notin B^{+}}

${\displaystyle i:=i+1}${\displaystyle i:=i+1}

${\displaystyle R:=R\cup \{R_{i}\}}${\displaystyle R:=R\cup \{R_{i}\}}

${\displaystyle D:=(R,\emptyset )}${\displaystyle D:=(R,\emptyset )}

1. ↑ A. Kemper, A. Eickler: Datenbanksysteme, ISBN 3-486-57690-9.

• Datenbankmodellierung