Zerlegung von Relationen

Unter Normalisierung verstehen wir die Zerlegung eines Relationenschemas ${\cal R}$ in die Relationenschemata ${{\cal R}_1, {\cal R}_2, \dots R_n}$, die jeweils nur eine Teilmenge der Attribute von ${\cal R}$ aufweisen, d. h. ${\cal R}_i \subseteq {\cal R}$. Verlangt werden hierbei

• Verlustlosigkeit:
  Die in der ursprünglichen Ausprägung R des Schemas ${\cal R}$ enthaltenen Informationen müssen aus den Ausprägungen $R_1, \dots, R_n$ der neuen Schemata ${\cal R}_1, {\cal R}_2, \dots {\cal R}_n$ rekonstruierbar sein.
• Abhängigkeitserhaltung: Die für ${\cal R}$ geltenden funktionalen Abhängigkeiten müssen auf die Schemata ${{\cal R}_1, \dots,{\cal R}_n}$ übertragbar sein.

Wir betrachten die Zerlegung in zwei Relationenschemata. Dafür muß gelten ${{\cal R = R}_1 \cup {\cal R}_2}$. Für eine Ausprägung R von ${\cal R}$ definieren wir die Ausprägung $R_1$ von ${\cal R}_1$ und $R_2$ von ${\cal R}_2$ wie folgt:

$$R_1 := \Pi_{{\cal R}_1} (R)$$

$$R_2 := \Pi_{{\cal R}_2} (R)$$

Eine Zerlegung von ${\cal R}$ in ${{\cal R}_1}$ und ${{\cal R}_2}$ heißt verlustlos, falls für jede gültige Ausprägung R von ${\cal R}$ gilt:

$$R = R_1 \bowtie R_2$$

Es folgt eine Relation Biertrinker, die in zwei Tabellen zerlegt wurde. Der aus den Zerlegungen gebildete natürliche Verbund weicht vom Original ab. Die zusätzlichen Tupel (kursiv gesetzt) verursachen einen Informationsverlust.

Biertrinker
Kneipe	Gast	Bier
Stiefel	Wacker	Pils
Stiefel	Sorglos	Hefeweizen
Zwiebel	Wacker	Hefeweizen

Besucht
Kneipe	Gast
Stiefel	Wacker
Stiefel	Sorglos
Zwiebel	Wacker

Trinkt
Gast	Bier
Wacker	Pils
Sorglos	Hefeweizen
Wacker	Hefeweizen

Besucht $\bowtie$ Trinkt
Kneipe	Gast	Pils
Stiefel	Wacker	Pils
Stiefel	Wacker	Hefeweizen
Stiefel	Sorglos	Hefeweizen
Zwiebel	Wacker	Pils
Zwiebel	Wacker	Hefeweizen

Eine Zerlegung von ${\cal R}$ in ${{\cal R}_{1}}$, ..., ${{\cal R}_{n}}$ heißt $abh\uml {a}ngigkeitsbewahrend$ (auch genannt $h\uml {u}llentreu$) falls die Menge der ursprünglichen funktionalen Abhängigkeiten äquivalent ist zur Vereinigung der funktionalen Abhängigkeiten jeweils eingeschränkt auf eine Zerlegungsrelation, d. h.

• $F_{\cal R} \equiv (F_{{\cal R}_{1}} \cup \dots \cup F_{{\cal R}_{n}})$ bzw.
• $F^{+}_{\cal R} = (F_{{\cal R}_{1}} \cup \dots \cup F_{{\cal R}_{n}})^{+}$

Es folgt eine Relation PLZverzeichnis, die in zwei Tabellen zerlegt wurde. Fettgedruckt sind die jeweiligen Schlüssel.

PLZverzeichnis
Ort	BLand	Straße	PLZ
Frankfurt	Hessen	Goethestraße	60313
Frankfurt	Hessen	Galgenstraße	60437
Frankfurt	Brandenburg	Goethestraße	15234

Straßen
PLZ	Straße
15234	Goethestraße
60313	Goethestraße
60437	Galgenstraße

Orte
Ort	BLand	PLZ
Frankfurt	Hessen	60313
Frankfurt	Hessen	60437
Frankfurt	Brandenburg	15234

Es sollen die folgenden funktionalen Abhängigkeiten gelten:

• {PLZ} $\rightarrow$ {Ort, BLand}
• {Straße, Ort, BLand} $\rightarrow$ {PLZ}

Die Zerlegung ist verlustlos, da PLZ das einzige gemeinsame Attribut ist und {PLZ} $\rightarrow$ {Ort, BLand} gilt.

Die funktionale Abhängigkeit {Straße, Ort, BLand} $\rightarrow$ {PLZ} ist jedoch keiner der beiden Relationen zuzuordnen, so daß diese Zerlegung nicht abhängigkeitserhaltend ist.

Folgende Auswirkung ergibt sich: Der Schlüssel von Straßen ist {PLZ, Straße} und erlaubt das Hinzufügen des Tupels [15235, Goethestraße].

Der Schlüssel von $Orte$ ist {PLZ} und erlaubt das Hinzufügen des Tupels [Frankfurt, Brandenburg, 15235]. Beide Relationen sind lokal konsistent, aber nach einem Join wird die Verletzung der Bedingung {Straße, Ort, BLand} $\rightarrow$ {PLZ} entdeckt.