~2026-23594-56: /* Hinzufügen einer Relation */

2026-04-17T15:28:39Z

Hinzufügen einer Relation

Neue Seite

Der '''Synthesealgorithmus''' beschreibt, wie aus einem relationalen [[Datenbank]]schema
ein [[Relationenschema]] der [[Normalisierung (Datenbank)#Dritte Normalform (3NF)|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 Normalform|Zerlegungsalgorithmus]], welcher in die [[Normalisierung (Datenbank)#Boyce-Codd-Normalform (BCNF)|Boyce-Codd-Normalform]] (BCNF) transferiert. Dabei können allerdings Abhängigkeiten verloren gehen (nicht [[Abhängigkeitstreue|abhängigkeitstreu]]). Er ist insofern eine Alternative, als jedes relationale Schema, welches in BCNF transformiert wird, dann auch automatisch in dritter Normalform vorliegt.

== Voraussetzung ==
Es müssen alle [[Funktionale Abhängigkeit|funktionalen Abhängigkeiten]] <math>\mathcal F</math> der zu zerlegenden Relation <math>R</math> unter den [[Attribut (Relationale Algebra)|Attributen]] bekannt sein.

Beispiel:
* <math>R = \operatorname{Relation}(A,B,C,D,E,F)</math>
* <math>\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\}</math>

Der Synthesealgorithmus besteht dann aus vier Schritten:
# Reduktion von <math>\mathcal F</math>, d. h. die Bestimmung der kanonischen Überdeckung.
# Erzeugen der neuen Relationenschemata aus der kanonischen Überdeckung.
# Ggf. die Hinzunahme einer Relation, die nur den Ursprungsschlüssel enthält.
# Elimination der Schemata, die in einem anderen Schema enthalten sind.

== Reduktion ==
Dies wird auch die Berechnung der [[Kanonische Überdeckung|kanonischen Überdeckung]] genannt.

=== 1. Schritt: Linksreduktion ===
Für alle <math>\psi \in \Psi</math> ersetze <math>\Psi \rightarrow \Gamma</math> durch <math>\Psi \setminus \{\psi\} \rightarrow \Gamma</math> , falls <math>\Gamma</math> schon durch <math> \Psi \setminus \{\psi\} \rightarrow \Gamma</math> determiniert ist.

Die obige Bedingung lässt sich testen, indem man überprüft, ob <math>\Gamma \subseteq \mathop{\mathrm{AttributH\ddot ulle}}(F, \Psi \setminus \{\psi\})</math> ist,<ref>A. Kemper, A. Eickler: ''Datenbanksysteme'', ISBN 3-486-57690-9.</ref> wobei F die Menge der funktionalen Abhängigkeiten bezeichnet. Falls dies zutrifft, kann <math>\psi</math> aus <math>\Psi</math> entfernt werden.

Beispiel: <math>\mathop{\mathrm{Relation}}\left(A,B,C,D,E,F\right)</math>
* <math>A \rightarrow B,E</math>
* <math>A\underline{E} \rightarrow B,D</math>
* <math>F \rightarrow C,D</math>
* <math>CD \rightarrow B,E,F</math>
* <math>\underline{C}F \rightarrow B</math>

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

Lösung:
* <math>A \rightarrow B,E</math>
* <math>A \rightarrow B,D</math>
* <math>F \rightarrow C,D</math>
* <math>CD \rightarrow B,E,F</math>
* <math>F \rightarrow B</math>

=== 2. Schritt: Rechtsreduktion ===
Für alle <math>\gamma \in \Gamma</math> ersetze <math>\Psi \rightarrow \Gamma</math> durch <math>\Psi \rightarrow \Gamma \setminus\{\gamma\}</math>, falls <math>\gamma</math> schon transitiv durch <math>\Psi</math> bestimmt ist.

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

An obigem Beispiel:
* <math>A \rightarrow B,E</math>
* <math>A \rightarrow B,D</math>
* <math>F \rightarrow C,D</math>
* <math>CD \rightarrow B,E,F</math>
* <math>F \rightarrow \underline{B}</math>

In der fünften funktionalen Abhängigkeit fällt das B weg.

* <math>A \rightarrow E</math>
* <math>A \rightarrow B,D</math>
* <math>F \rightarrow C,D</math>
* <math>CD \rightarrow E,F</math>

=== 3. Schritt: Leere Klauseln ===
Eliminiere Klauseln der Form <math> \Psi \rightarrow \varnothing </math>

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 <math>a \rightarrow b_0 , a \rightarrow b_1 \dots</math> zu <math>a \rightarrow b_0 \cup b_1 \dots</math> zusammen.

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

* <math>A \rightarrow E,B,D</math>
* <math>F \rightarrow C,D</math>
* <math>CD \rightarrow B,E,F</math>

== Neues Relationenschema ==

Aus allen <math>\Psi \to \Gamma</math> wird <math> R ( \Psi , \Gamma ) </math>.

Zusätzlich muss ein neuer [[Schlüssel (Datenbank)|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:
* <math>R_1(\underline{A},B,D,E)</math> # <math>A</math> ist [[Primärschlüssel]]
* <math>R_2(C,D,\underline{F})</math> # <math>F</math> ist Primärschlüssel
* <math>R_3(B,\underline{C,D},E,F)</math> # <math>CD</math> ist Primärschlüssel (Die Elemente dieser [[Relation (Mathematik)|Relation]] sind zwar schon durch <math>R_1</math> und <math>R_2</math> 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 <math>R_1</math>, <math>R_2</math> und <math>R_3</math> hergestellt werden. Das wird durch eine Relation <math>R_4</math> ermöglicht, die nur den Ursprungsschlüssel <math>AF</math> enthält (beachte, dass <math> AF^+=\{A,B,C,D,E,F\}</math> ist). Wir erhalten ein Schema in der 3. Normalform wie folgt:

* <math>R_1(\underline{A},B,D,E)</math>
* <math>R_2(C,D,\underline{F})</math>
* <math>R_3(B,\underline{C,D},E,F)</math>
* <math>R_4(\underline{A},\underline{F})</math>, wobei <math>A</math> und <math>F</math> jeweils [[Schlüssel (Datenbank)#Fremdschlüssel|Fremdschlüssel]] darstellen und zusammengenommen den Primärschlüssel von <math>R_4</math> erzeugen.

== Formaler Algorithmus ==
'''Eingabe:''' universelles Schema <math>R=(U,F)</math><br />
'''Ausgabe:''' 3. Normalform <math>D</math> von <math>R</math>

:<math>B := \operatorname{reduction}(F)</math>
:<math>R := \emptyset</math>
:<math>i := 0</math>
:<math>\mathbf{for\,each}\;Y\subseteq U\;\mathbf{where}\;\exist A \in U. (Y\rightarrow A) \in B</math>
::<math>i := i+1</math>
::<math>X_i := Y\cup\{\,A\in U\,|\,(Y\rightarrow A) \in B\,\}</math>
::<math>R_i := (X_i,\Pi_{X_{i}}(B))</math>
::<math>R := R\cup\{R_i\}</math>
:<math>\mathbf{if}\;\forall R_i\in R. (X_i\rightarrow U)\notin B^+</math>
::<math>i := i+1</math>
::<math>R := R\cup\{R_i\}</math>
:<math>D := (R,\emptyset)</math>

== Einzelnachweise ==
<references />https://normalizer.db.in.tum.de/index.py
[[Kategorie:Datenbankmodellierung]]

Synthesealgorithmus - Versionsgeschichte

~2026-23594-56: /* Hinzufügen einer Relation */