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 dass jedes relationale Schema, welches in BCNF transformiert wird, dann auch automatisch in dritter Normalform vorliegt.

Voraussetzung

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

Beispiel:

Der Synthesealgorithmus besteht dann aus vier Schritten:

  1. Reduktion von {\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 wird auch die Berechnung der kanonischen Überdeckung genannt.

1. Schritt: Linksreduktion

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

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

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

Lösung:

2. Schritt: Rechtsreduktion

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

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

An obigem Beispiel:

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

3. Schritt: Leere Klauseln

Eliminiere Klauseln der Form \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.

4. Schritt: Zusammenfassen

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

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

Neues Relationenschema

Aus allen Ψ \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:

Hinzufügen einer Relation

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

Formaler Algorithmus

Eingabe: universelles Schema R=(U,F)
Ausgabe: 3. Normalform D von R
B:=Reduktion(F)
R:={}
i:=0
for each Y\subseteq U mit (\exists A\in U):Y\rightarrow A\in B
   i := i+1
   X_{i}:=Y\cup \{A\in U|Y\rightarrow A\in B\}
   R_{i}:=(X_{i},\pi _{{X_{{i1}}}}(B))
   R:=R\cup \{R_{i}\}
if (\forall R_{i}\in R):X_{i}\rightarrow U\notin B^{+}
   i: = i+1
   R:=R\cup \{R_{i}\}
D:=(R,\{\ \})
Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 15.05. 2020