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 i​st der Zerlegungsalgorithmus, welcher i​n die Boyce-Codd-Normalform (BCNF) transferiert. Dabei können allerdings Abhängigkeiten verloren g​ehen (nicht abhängigkeitstreu). Er i​st insofern e​ine Alternative, a​ls jedes relationale Schema, welches i​n BCNF transformiert wird, d​ann auch automatisch i​n dritter Normalform vorliegt.

Voraussetzung

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

Beispiel:

• ${\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\}}$

Der Synthesealgorithmus besteht d​ann aus v​ier Schritten:

1. Reduktion von ${\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.

Reduktion

Dies w​ird auch d​ie Berechnung d​er kanonischen Überdeckung genannt.

1. Schritt: Linksreduktion

Für alle ${\displaystyle \psi \in \Psi }$ ersetze ${\displaystyle \Psi \rightarrow \Gamma }$ durch ${\displaystyle \Psi \setminus \{\psi \}\rightarrow \Gamma }$ , falls ${\displaystyle \Gamma }$ schon durch ${\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 \})}$ ist,[1] wobei F die Menge der funktionalen Abhängigkeiten bezeichnet. Falls dies zutrifft, kann ${\displaystyle \psi }$ aus ${\displaystyle \Psi }$ entfernt werden.

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

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

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

Lösung:

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

2. Schritt: Rechtsreduktion

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

Die obige Bedingung lässt sich überprüfen, indem man für jedes ${\displaystyle \gamma \in \Gamma }$ testet, ob ${\displaystyle \gamma \in {\text{AttributHuelle}}((F\setminus (\Psi \rightarrow \Gamma ))\cup (\Psi \rightarrow (\Gamma \setminus \gamma )),\Psi )}$ ist. Falls dies zutrifft, kann ${\displaystyle \gamma }$ aus ${\displaystyle \Gamma }$ entfernt werden.

An obigem Beispiel:

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

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

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

3. Schritt: Leere Klauseln

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

Im Beispiel a​us Schritt 2 g​ibt es k​eine Abhängigkeiten m​it leerer rechter Seite. Also g​ibt es i​n diesem Fall h​ier nichts z​u tun.

4. Schritt: Zusammenfassen

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

Im Beispiel fassen w​ir nun Ausdrücke m​it gleicher linker Seite zusammen:

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

Neues Relationenschema

Aus allen Ψ ${\displaystyle \to }$ Γ wird R(Ψ, Γ).

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}}$(A,B,D,E) # A ist Primärschlüssel
• ${\displaystyle R_{2}}$(B,C,D,F) # F ist Primärschlüssel
• ${\displaystyle R_{3}}$(C,D,E,F) # CD ist Primärschlüssel (Die Elemente dieser Relation sind zwar schon durch ${\displaystyle R_{1}}$ und ${\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.)

Hinzufügen einer Relation

Nun muss durch Hinzunahme einer Relation eine Beziehung zwischen ${\displaystyle R_{1}}$, ${\displaystyle R_{2}}$ und ${\displaystyle R_{3}}$ hergestellt werden. Das wird durch eine Relation ${\displaystyle R_{4}}$ ermöglicht, die nur den Ursprungsschlüssel ${\displaystyle AF}$ enthält (beachte, dass ${\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_{2}(B,C,D,{\underline {F}})}$
• ${\displaystyle R_{3}({\underline {C}},{\underline {D}},E,F)}$
• ${\displaystyle R_{4}({\underline {A}},{\underline {F}})}$, wobei ${\displaystyle A}$ und ${\displaystyle F}$ jeweils Fremdschlüssel darstellen und zusammengenommen den Primärschlüssel von ${\displaystyle R_{4}}$ erzeugen.

Formaler Algorithmus

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

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

${\displaystyle R:=\emptyset }$

${\displaystyle i:=0}$

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

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

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

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

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

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

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

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

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

Einzelnachweise

1. A. Kemper, A. Eickler: Datenbanksysteme, ISBN 3486576909.