Funktionale Abhängigkeiten und Normalisierung

Nach der Überführung eines ER-Modells in Relationen stellt sich die Frage: Sind diese Relationen gut strukturiert? Speichern sie Daten redundant? Drohen beim Ändern, Einfügen oder Löschen Inkonsistenzen?

Dieser Abschnitt führt drei aufeinander aufbauende Konzepte ein: Anomalien als Probleme schlecht strukturierter Datenbanken, funktionale Abhängigkeiten als formales Werkzeug zur Analyse, und Normalisierung als systematisches Verfahren zur Optimierung.

Anomalien

Bevor die Normalisierung formal eingeführt wird, lohnt ein Blick auf die konkreten Probleme, die in unzureichend strukturierten Relationen entstehen. Diese Probleme heißen Anomalien und entspringen alle derselben Ursache: Redundanz — also dieselbe Information, mehrfach gespeichert.

Folgende, bewusst schlecht entworfene Relation einer Schulbibliothek dient als Ausgangspunkt. Schnell fällt auf: Buchdaten (Titel, Autor, Standort) und Schülerdaten (Name, Klasse) tauchen mehrfach auf. Genau diese Vermischung verursacht die drei klassischen Anomalien.

Untersuche in der interaktiven Demo die drei verschiedenen Anomalien:

Das Buch „1984" soll in einen anderen Raum (205) aufbewahrt werden. Was passiert, wenn nicht alle betroffenen Zeilen synchron geändert werden.

Bibliothek_schlecht
BuchID	Titel	Autor	Standort	SchuelerID	SchuelerName	Klasse
B001	1984	Orwell	Raum 203	S123	Anna Schmidt	10a
B001	1984	Orwell	Raum 203	S456	Max Müller	10b
B002	Harry Potter	Rowling	Raum 204	S123	Anna Schmidt	10a
B003	Der Prozess	Kafka	Raum 203	NULL	NULL	NULL

Wähle aus, wie viele Zeilen geändert werden:

nur die erste B001-Zeilealle B001-Zeilen

Hinweis: Das Buch B001 kommt in zwei Zeilen vor — die Information „Standort" ist redundant gespeichert.

Update-Anomalie

Update-Anomalie: dieselbe Information mehrfach gespeichert — bei einer Änderung müssen alle Kopien synchron aktualisiert werden.

Wird das Buch 1984 von Raum 203 nach Raum 205 verlegt, müssen alle Zeilen mit B001 geändert werden. Wird auch nur eine vergessen, steht das Buch laut Datenbank gleichzeitig in zwei Räumen — ein Widerspruch, den die Datenbank selbst nicht auflösen kann.

Einfüge-Anomalie

Einfüge-Anomalie: Daten lassen sich nicht speichern, weil dafür künstlich abhängige Werte erfunden werden müssten.

Ein neues Buch Faust (B004) soll in die Bibliothek aufgenommen werden, ist aber noch nicht ausgeliehen. Die Tabellenstruktur erzwingt jedoch Werte für SchuelerID, SchuelerName und Klasse. Drei Auswege bleiben — keiner überzeugt:

• NULL-Werte (verfälschen Auswertungen),
• Dummy-Werte (verfälschen die Daten),
• gar kein Eintrag (die Bibliothek "kennt" das Buch nicht).

Lösch-Anomalie

Lösch-Anomalie: Beim Löschen verschwinden unbeabsichtigt unabhängige Informationen mit.

Gibt Max Müller (S456) sein einziges ausgeliehenes Buch zurück und wird die zugehörige Zeile gelöscht, verschwindet mit der Ausleihinformation auch Max Müller selbst: Die Schule weiß nicht mehr, dass er existiert oder in welche Klasse er geht.

Gemeinsame Ursache

Anomalie	Symptom
Update	Inkonsistenzen bei Änderungen
Einfügen	Neue Daten nicht ohne Krücken speicherbar
Löschen	Unbeabsichtigter Verlust unabhängiger Daten

Alle drei Anomalien wurzeln darin, dass mehrere unabhängige Konzepte (Buch, Schüler, Ausleihe) in derselben Tabelle vermischt werden. Das systematische Werkzeug, um solche Vermischungen zu erkennen, sind funktionale Abhängigkeiten.

Training — Anomalien erkennen

Gegeben sei folgendes nicht-normalisiertes Relationenschema:

Bestellung(Kunden_ID, Kunde_Name, Kunde_Adresse, Artikel_Name, Artikel_Preis, Lieferant, Lieferant_Telefon, Menge, Datum)

1. Erkläre an einem eigenen Beispiel, wie eine Update-Anomalie entstehen kann.
2. Beschreibe eine Situation, in der eine Einfüge-Anomalie das Speichern wichtiger Informationen verhindert.
3. Konstruiere einen Fall, in dem das Löschen eines einzelnen Tupels zu einer Lösch-Anomalie führt.

Funktionale Abhängigkeiten

Definition

Sei $R$ eine Relation mit Attributmenge $\mathcal{A}$, und seien $X,Y\subseteq \mathcal{A}$ Attributteilmengen. Eine funktionale Abhängigkeit $X\to Y$ liegt vor, wenn für alle Tupel $t_1,t_2$ in $R$ gilt:

$$t_1[X]=t_2[X]\Rightarrow t_1[Y]=t_2[Y].$$

• $t[X]$ bezeichnet die Werte, die das Tupel $t$ in den Attributen $X$ trägt. Siehe Tupel.
• $X\to Y$ liest sich „X bestimmt Y" oder „Y ist funktional abhängig von X".

In Worten: Stimmen zwei Tupel in den Werten von $X$ überein, dann zwangsläufig auch in den Werten von $Y$. Die Werte von $X$ legen die von $Y$ eindeutig fest.

Einzelne und zusammengesetzte Determinanten

Determinante: linke Seite einer funktionalen Abhängigkeit $X\to Y$, also die Attribute, die andere Werte „determinieren" (festlegen).

Oft bestimmt schon ein einzelnes Attribut weitere Werte (einfache Determinante):

Schüler(SchuelerID, Name, Geburtsdatum, Klasse, Klassenlehrer)

mit den Abhängigkeiten

• SchuelerID → Name, Geburtsdatum, Klasse
• Klasse → Klassenlehrer

Schüler
SchuelerID	Name	Geburtsdatum	Klasse	Klassenlehrer
S001	Anna Schmidt	2008-04-12	10a	Frau Meyer
S002	Max Müller	2008-09-03	10a	Frau Meyer
S003	Lisa Weber	2007-11-21	10b	Herr Schmidt
S004	Tom Koch	2008-02-08	10b	Herr Schmidt

Konkret in der Tabelle ablesbar: Die Zeilen S001 und S002 stimmen in Klasse überein (beide 10a) und tragen folglich denselben Klassenlehrer (Frau Meyer). Genauso bei S003 und S004: gleiche Klasse 10b, gleicher Klassenlehrer Herr Schmidt. Das ist Klasse → Klassenlehrer.

In anderen Fällen genügt ein einzelnes Attribut nicht — erst die Kombination mehrerer Attribute bestimmt einen Wert eindeutig (zusammengesetzte Determinante):

Prüfung(SchuelerID, FachID, Datum, Note, Punktzahl)

Prüfung
SchuelerID	FachID	Datum	Note	Punktzahl
S001	MAT	2024-03-15	1.7	13
S001	MAT	2024-06-20	2.3	11
S001	DEU	2024-03-15	2.0	12
S002	MAT	2024-03-15	2.7	9

In der Tabelle lassen sich alle „kleineren" Determinanten ausschließen:

• SchuelerID allein reicht nicht — Anna (S001) hat drei verschiedene Noten.
• FachID allein reicht nicht — in MAT stehen drei unterschiedliche Noten (1.7, 2.3, 2.7).
• {SchuelerID, FachID} reicht nicht — Anna hat in MAT zweimal geschrieben (1.7 am 15.03., 2.3 am 20.06.).
• {SchuelerID, Datum} reicht nicht — Anna hat am 15.03.2024 sowohl in MAT (1.7) als auch in DEU (2.0) eine Note bekommen.
• {FachID, Datum} reicht nicht — am 15.03.2024 schrieben in MAT zwei Schüler (Anna 1.7, Max 2.7).

Erst die volle Kombination {SchuelerID, FachID, Datum} → Note bestimmt die Note eindeutig.

Volle vs. partielle Abhängigkeit

Faustregel: Lässt sich aus der linken Seite ein Attribut weglassen, ohne die Abhängigkeit zu verlieren? Dann ist sie partiell.

Ein Attribut $Y$ ist voll funktional abhängig von $X$, wenn $X\to Y$ gilt und keine echte Teilmenge von $X$ schon $Y$ bestimmt. Andernfalls liegt eine partielle Abhängigkeit vor.

In der Prüfungsrelation oben ist Note voll abhängig von {SchuelerID, FachID, Datum}. Eine vereinfachte Variante mit Zwei-Attribut-Schlüssel und ergänztem SchuelerName zeigt dagegen ein Problem:

Prüfung_schlecht(SchuelerID, FachID, SchuelerName, Note)

Prüfung_schlecht
SchuelerID	FachID	SchuelerName	Note
S001	MAT	Anna Schmidt	1.7
S001	DEU	Anna Schmidt	2.0
S002	MAT	Max Müller	2.7
S002	DEU	Max Müller	1.3

In der Tabelle direkt sichtbar: Annas Name steht in jeder ihrer Prüfungszeilen erneut. SchuelerName hängt nur von SchuelerID ab — FachID ist überflüssig. Das ist eine partielle Abhängigkeit und führt direkt zu Redundanz.

Transitive Abhängigkeit

Eine transitive Abhängigkeit „springt" über ein Nichtschlüsselattribut. Genau das wird in der 3NF beseitigt.

Wenn $A\to B$ und $B\to C$ gelten, $B$ aber kein Schlüsselattribut ist, dann ist $C$ transitiv abhängig von $A$.

In einer reduzierten Schüler-Relation, die nur Klasseninfo trägt:

Schüler(SchuelerID, Klasse, Klassenlehrer)

Schüler
SchuelerID	Klasse	Klassenlehrer
S001	10a	Frau Meyer
S002	10a	Frau Meyer
S003	10b	Herr Schmidt
S004	10b	Herr Schmidt

Der Klassenlehrer hängt eigentlich an der Klasse, nicht am Schüler — Frau Meyer taucht zweimal auf (für jede 10a-Schülerzeile), Herr Schmidt ebenfalls. Über den Umweg Klasse ergibt sich eine indirekte Abhängigkeit von SchuelerID. Folge: Wechselt die 10a den Klassenlehrer, müssen sämtliche Schülerzeilen der 10a nachgezogen werden.

Übersicht

Typ	Bedeutung	Beispiel
Funktionale Abhängigkeit	$X\to Y$	SchuelerID → Name
Volle funktionale Abhängigkeit	$Y$ braucht alle Attribute aus $X$	{SchuelerID, FachID} → Note
Partielle Abhängigkeit	$Y$ hängt schon von einer echten Teilmenge von $X$ ab	{SchuelerID, FachID} → SchuelerName
Transitive Abhängigkeit	$A\to B\to C$, $B$ kein Schlüssel	SchuelerID → Klasse → Klassenlehrer

Training — Funktionale Abhängigkeiten

Gegeben sei die Relation

Reservierung(RaumID, Tag, Stunde, LehrerID, Fach, Klasse)

mit den Annahmen, dass jeder Raum zu jeder Stunde an jedem Tag von höchstens einem Lehrer für genau eine Klasse in einem Fach genutzt wird.

1. Liste alle funktionalen Abhängigkeiten auf.
2. Welche davon sind voll funktional, welche partiell?
3. Gibt es transitive Abhängigkeiten? Begründe.

Normalisierung

Normalisierung ist ein schrittweises Verfahren, das Relationen so umformt, dass Redundanzen verschwinden und Anomalien strukturell ausgeschlossen sind. Die Normalformen 1NF, 2NF, 3NF und BCNF bauen aufeinander auf — jede strenger als die vorhergehende.

Erste Normalform (1NF)

1NF: atomare Werte — keine Listen, keine zusammengesetzten Werte, keine Mehrfachzuordnungen pro Zelle.

Eine Relation ist in 1NF, wenn alle Attributwerte atomar sind — also nicht weiter zerlegbar.

Folgende Relation verletzt die 1NF, weil das Attribut Hobbys mehrere Werte enthält:

Schüler_alt
SchuelerID	Name	Hobbys
S001	Anna Schmidt	Tennis, Lesen, Schwimmen
S002	Max Müller	Fußball, Gitarre

Die saubere Lösung lagert die mehrwertige Eigenschaft in eine eigene Relation aus:

Schüler
SchuelerID	Name
S001	Anna Schmidt
S002	Max Müller

Hobby
SchuelerID	Hobby
S001	Tennis
S001	Lesen
S001	Schwimmen
S002	Fußball
S002	Gitarre

Zweite Normalform (2NF)

2NF ist nur dann eine echte Hürde, wenn der Primärschlüssel mehrere Attribute umfasst.

Eine Relation ist in 2NF, wenn sie in 1NF ist und jedes Nichtschlüsselattribut voll funktional abhängig vom gesamten Primärschlüssel ist — also keine partiellen Abhängigkeiten existieren.

Folgende Prüfungsrelation hat den zusammengesetzten Schlüssel {SchuelerID, FachID}:

Prüfung
SchuelerID	FachID	SchuelerName	Fachname	Note
S001	MAT	Anna Schmidt	Mathematik	1.7
S001	DEU	Anna Schmidt	Deutsch	2.3
S002	MAT	Max Müller	Mathematik	2.0

SchuelerName hängt nur von SchuelerID ab, Fachname nur von FachID — beides sind partielle Abhängigkeiten. Die 2NF stellt sie ab, indem sie diese Attribute in eigene Relationen auslagert:

Schüler
SchuelerID	SchuelerName
S001	Anna Schmidt
S002	Max Müller

Fach
FachID	Fachname
MAT	Mathematik
DEU	Deutsch

Prüfung
SchuelerID	FachID	Note
S001	MAT	1.7
S001	DEU	2.3
S002	MAT	2.0

Dritte Normalform (3NF)

3NF beseitigt Abhängigkeiten zwischen Nichtschlüsselattributen.

Eine Relation ist in 3NF, wenn sie in 2NF ist und kein Nichtschlüsselattribut transitiv vom Primärschlüssel abhängt.

Schüler
SchuelerID	Name	Klasse	Klassenlehrer	Raum
S001	Anna Schmidt	10a	Frau Meyer	A201
S002	Max Müller	10a	Frau Meyer	A201
S003	Lisa Weber	10b	Herr Schmidt	A202

Hier gilt Klasse → Klassenlehrer und Klasse → Raum zwischen Nichtschlüsselattributen. Klassenlehrer und Raum werden für jeden Schüler einer Klasse erneut gespeichert — Redundanz. Die Auflösung trennt den Klassenkontext in eine eigene Relation ab:

Schüler
SchuelerID	Name	Klasse
S001	Anna Schmidt	10a
S002	Max Müller	10a
S003	Lisa Weber	10b

Klasse
Klassenname	Klassenlehrer	Raum
10a	Frau Meyer	A201
10b	Herr Schmidt	A202

Boyce-Codd-Normalform (BCNF)

BCNF verschärft die 3NF: Auf der linken Seite jeder funktionalen Abhängigkeit muss ein Superschlüssel stehen.

Eine Relation ist in BCNF, wenn sie in 3NF ist und für jede nichttriviale funktionale Abhängigkeit $X\to Y$ gilt: $X$ ist ein Superschlüssel (eine Attributmenge, die alle Tupel eindeutig identifiziert).

Beispiel mit den Annahmen "Ein Schüler kann mehrere Kurse belegen, ein Kurs kann von mehreren Lehrern unterrichtet werden, aber jeder Lehrer unterrichtet höchstens einen Kurs":

Kursanmeldung
SchuelerID	Kurs	Lehrer
S001	Informatik	Herr Weber
S002	Informatik	Herr Weber
S003	Informatik	Frau Klein
S004	Mathematik	Frau Meyer

Die Abhängigkeit Lehrer → Kurs verletzt die BCNF, weil Lehrer kein Superschlüssel ist. Die Auflösung:

Anmeldung
SchuelerID	Lehrer
S001	Herr Weber
S002	Herr Weber
S003	Frau Klein
S004	Frau Meyer

Lehrer_Kurs
Lehrer	Kurs
Herr Weber	Informatik
Frau Klein	Informatik
Frau Meyer	Mathematik

Trade-off: BCNF-Zerlegungen sind nicht immer abhängigkeitserhaltend. Hier lässt sich {SchuelerID, Kurs} → Lehrer nicht mehr in einer einzigen Relation prüfen — eine bewusste Einbuße zugunsten von Redundanzfreiheit.

Übersicht der Normalformen

NF	Bedingung (zusätzlich zur Vorgängerstufe)
1NF	atomare Attributwerte
2NF	keine partiellen Abhängigkeiten vom Primärschlüssel
3NF	kein Nichtschlüsselattribut ist transitiv vom Primärschlüssel abhängig
BCNF	jede Determinante ist Superschlüssel

In der Praxis ist die 3NF ein guter Kompromiss zwischen Redundanzfreiheit und Performance. BCNF wird selten zwingend benötigt, ist aber konzeptionell wichtig.

Praktisches Vorgehen

Beim Normalisieren einer gegebenen Relation hilft folgender Ablauf:

1. Funktionale Abhängigkeiten identifizieren. Welche Attribute bestimmen welche?
2. Primärschlüssel bestimmen. Welche Attributkombination identifiziert jedes Tupel eindeutig?
3. 1NF prüfen. Sind alle Werte atomar? Falls nein: Mehrwertige Attribute auslagern.
4. 2NF prüfen (nur bei zusammengesetztem Schlüssel). Partielle Abhängigkeiten? Falls ja: in eigene Relationen auslagern.
5. 3NF prüfen. Transitive Abhängigkeiten? Falls ja: Zwischenstufen auslagern.
6. BCNF prüfen (optional). Sind alle Determinanten Superschlüssel?

Training — Normalisierung

Gegeben sei folgende Relation einer Schulbibliothek. Die AusleihID wird pro Buch fortlaufend vergeben — derselbe AusleihID-Wert kann also bei verschiedenen Büchern erneut auftauchen, weshalb erst die Kombination aus BuchID und AusleihID einen Ausleihvorgang eindeutig identifiziert.

Bibliothek(BuchID, AusleihID, Buchtitel, Autor, ISBN, SchuelerID, SchuelerName, Klasse, Ausleihdatum, Rückgabedatum)

mit den funktionalen Abhängigkeiten:

• BuchID → Buchtitel, Autor, ISBN
• ISBN → Buchtitel, Autor
• SchuelerID → SchuelerName, Klasse
• {BuchID, AusleihID} → SchuelerID, Ausleihdatum, Rückgabedatum

1. In welcher Normalform ist die Relation? Begründe.
2. Überführe die Relation schrittweise in 3NF und gib das resultierende Relationenschema an.
3. Skizziere ein passendes ER-Diagramm zur normalisierten Lösung.