Normalformen (1NF-4NF)

Zusammenfassung

Normalformen sind Guetekriterien fuer relationale Schemata, die aufeinander aufbauen und schrittweise Redundanzen sowie Anomalien (Einfuege-, Loesch-, Update-, Mutationsanomalie) verhindern. Fuer die Klausur muss man in einer gegebenen Relation mit funktionalen Abhaengigkeiten (FDs) erkennen koennen, welche hoechste Normalform (1NF, 2NF, 3NF, BCNF, 4NF) vorliegt. Kernwerkzeug ist die Analyse jeder FD gegen die Schluesselstruktur der Relation.

Kernkonzepte

1. Normalform (1NF)

Eine Relation ist in 1NF, wenn alle Attributwerte atomar sind, d.h. keine Mengen, Listen, geschachtelten Relationen oder Wiederholungsgruppen als Zellwert enthalten sind. Zusaetzlich gibt es einen Primaerschluessel, es existieren keine Wiederholungen und die Zeilenreihenfolge hat keine Bedeutung. Beispiel: Eltern(Vater, Mutter, {Else, Lucie}) verletzt 1NF, weil die Zelle Kinder eine Menge enthaelt. Aufloesung durch Ausrollen in mehrere Tupel, sodass jedes Attribut nur einen Wert enthaelt.

1NF = atomare Werte in jeder Zelle, keine Listen oder Mengen.

2. Normalform (2NF)

Eine Relation ist in 2NF, wenn sie in 1NF ist und jedes Nichtschluesselattribut voll funktional von jedem Kandidatenschluessel abhaengig ist. Bei zusammengesetzten Schluesseln bedeutet das: kein Nichtschluesselattribut darf bereits von einem Teilschluessel bestimmt werden (keine partielle Abhaengigkeit). Beispiel StudentenBelegung(MatrNr, VorlNr, Name, Semester): Schluessel ist {MatrNr, VorlNr}, aber {MatrNr} bestimmt bereits Name und Semester -> 2NF verletzt. Bei einfachen (nicht zusammengesetzten) Schluesseln ist 2NF automatisch erfuellt.

2NF verhindert partielle Abhaengigkeiten von Teilschluesseln.

3. Normalform (3NF)

Eine Relation ist in 3NF, wenn sie in 2NF ist und fuer jede FD alpha -> beta mindestens eine von drei Bedingungen gilt: (1) alpha ist Superschluessel, (2) beta ist Teilmenge von alpha (trivial), oder (3) jedes Attribut in beta ist prim, d.h. Teil eines Kandidatenschluessels. Ziel: keine transitiven Abhaengigkeiten zwischen Nichtschluesselattributen. Klassisches Anti-Beispiel: {MatrNr}->{FachbereichNr}->{FachbereichName} - hier gibt es eine transitive Abhaengigkeit ueber ein Nichtschluesselattribut.

3NF verhindert transitive Abhaengigkeiten Nichtschluessel -> Nichtschluessel.

Boyce-Codd-Normalform (BCNF)

BCNF ist eine Verschaerfung von 3NF. Eine Relation ist in BCNF, wenn fuer jede nicht-triviale FD alpha -> beta gilt: alpha ist Superschluessel. Unterschied zu 3NF: die dritte Ausnahme (beta ist prim) faellt weg. Typisches Erkennungs-Beispiel Staedte(Ort, BLand, Ministerpraesident, EW) mit FDs {BLand}->{Ministerpraesident} und {Ministerpraesident}->{BLand}: In 3NF, aber nicht in BCNF, weil BLand kein Superschluessel ist, obwohl Ministerpraesident prim ist. BCNF-Zerlegung ist immer verlustlos moeglich, aber nicht immer abhaengigkeitserhaltend.

BCNF: links jeder nicht-trivialen FD steht ein Superschluessel - keine Ausnahmen.

Mehrwertige Abhaengigkeit (MVD)

Eine MVD alpha ->-> beta bedeutet: fuer jeden Wert von alpha existiert eine Menge von beta-Werten, die unabhaengig von den restlichen Attributen ist. Jede FD ist auch eine MVD, aber nicht umgekehrt. MVDs treten auf, wenn zwei unabhaengige mehrwertige Beziehungen in einer Tabelle gemischt werden, z.B. PersNr ->-> Sprache und PersNr ->-> ProgSprache in einer Faehigkeiten-Relation. Das fuehrt zu Redundanz durch alle Kombinationen von Sprachen und Programmiersprachen.

MVD = zwei unabhaengige Mehrfachwerte in einer Tabelle gemischt.

4. Normalform (4NF)

Eine Relation ist in 4NF, wenn sie in BCNF ist und fuer jede nicht-triviale MVD alpha ->-> beta gilt: alpha ist Superschluessel. Wenn eine Relation keine mehrwertigen Abhaengigkeiten hat, ist sie automatisch in 4NF, sofern BCNF erfuellt. Erkennungs-Beispiel Faehigkeiten(PersNr, Sprache, ProgSprache): alle drei Attribute bilden zusammen den Schluessel, aber PersNr ->-> Sprache ist eine MVD, bei der PersNr kein Superschluessel ist -> 4NF verletzt. Zerlegung in zwei Tabellen (PersNr, Sprache) und (PersNr, ProgSprache) beseitigt das Problem.

4NF: keine nicht-trivialen MVDs ohne Superschluessel.

Erkennungs-Algorithmus fuer Normalformen

Systematisches Vorgehen in einer Aufgabe: (1) Attribute atomar? Nein -> nur 0NF/unnormalisiert. (2) Kandidatenschluessel identifizieren. (3) Alle FDs pruefen. (4) Gibt es partielle Abhaengigkeiten (Nichtschluessel-Attribut haengt von Teilschluessel ab)? Ja -> nur 1NF. (5) Gibt es transitive Abhaengigkeiten (Nichtschluessel -> Nichtschluessel)? Ja -> nur 2NF. (6) Ist bei jeder FD die linke Seite Superschluessel? Wenn nur bei prim-Attributen Ausnahme -> 3NF, aber nicht BCNF. Sonst BCNF. (7) Gibt es nicht-triviale MVDs ohne Superschluessel-Praefix? Nein -> auch 4NF.

Immer die hoechste erfuellte NF bestimmen, von oben nach unten pruefen.

Anomalien als Motivation

Schlecht normalisierte Schemata verursachen vier Typen von Anomalien: Update-Anomalie (redundant gespeicherte Werte muessen mehrfach geaendert werden), Loesch-Anomalie (beim Loeschen eines Tupels gehen andere Informationen ungewollt verloren), Einfuege-Anomalie (neues Objekt kann nicht eingefuegt werden, weil zwingende Attribute fehlen und NULL noetig waere) und Mutationsanomalie (durch Redundanz entstehen bei versehentlicher Aenderung inkonsistente Zustaende). Normalisierung eliminiert Redundanz und damit diese Anomalien.

Normalisierung existiert, um Anomalien und Redundanz zu vermeiden.

Wichtige Details

Jede hoehere NF impliziert die niedrigeren: 4NF -> BCNF -> 3NF -> 2NF -> 1NF.
Bei einfachen (nicht zusammengesetzten) Primaerschluesseln ist 2NF automatisch erfuellt, sobald 1NF erfuellt ist - dann fehlt fuer 3NF nur der Transitivitaets-Check.
3NF hat drei Rettungs-Bedingungen: Superschluessel, trivial, oder rechte Seite ist prim. BCNF hat nur die ersten zwei.
Der Unterschied zwischen 3NF und BCNF wird nur dann sichtbar, wenn es mehrere ueberlappende Kandidatenschluessel gibt.
BCNF-Zerlegung ist immer verlustlos, aber nicht immer abhaengigkeitserhaltend (Beispiel PLZverzeichnis).
3NF-Zerlegung durch Synthesealgorithmus garantiert verlustlos UND abhaengigkeitserhaltend.
Ein prim-Attribut ist ein Attribut, das in mindestens einem Kandidatenschluessel enthalten ist.
Jede FD alpha -> beta ist automatisch auch eine MVD alpha ->-> beta.
Wenn eine Relation nur zwei Attribute hat oder alle Attribute Teil des Schluessels sind, ist sie oft automatisch in hoeherer NF.
Nicht-normalisiert (NF^2) ist nicht dasselbe wie denormalisiert: NF^2 ist unnormalisiert (Mengen in Zellen), Denormalisierung ist bewusste Entscheidung.

Beispiele

Beispiel 1NF-Verletzung: Eltern-Relation

Die Relation Eltern(Vater, Mutter, Kinder) mit Zeile (Johann, Martha, {Else, Lucie}) verletzt 1NF wegen der Menge im Attribut Kinder. Aufloesung: aufspalten in mehrere Tupel.

Vorher (nicht 1NF):
| Vater  | Mutter | Kinder        |
| Johann | Martha | {Else, Lucie} |
| Johann | Maria  | {Theo, Josef} |

Nachher (1NF):
| Vater  | Mutter | Kind  |
| Johann | Martha | Else  |
| Johann | Martha | Lucie |
| Johann | Maria  | Theo  |
| Johann | Maria  | Josef |

Beispiel 2NF-Verletzung: StudentenBelegung

StudentenBelegung(MatrNr, VorlNr, Name, Semester) mit Schluessel {MatrNr, VorlNr}. FDs: {MatrNr}->{Name} und {MatrNr}->{Semester}. Name und Semester haengen nur von einem Teilschluessel ab -> partielle Abhaengigkeit, 2NF verletzt. Zerlegung: Studenten(MatrNr, Name, Semester) und hoeren(MatrNr, VorlNr).

FD-Check:
Schluessel: {MatrNr, VorlNr}
{MatrNr} -> {Name}      partiell! (Teilschluessel)
{MatrNr} -> {Semester}  partiell! (Teilschluessel)
=> nur 1NF, nicht 2NF

Zerlegung:
Studenten: {MatrNr, Name, Semester}
hoeren:    {MatrNr, VorlNr}

Beispiel BCNF-Verletzung (3NF erfuellt): Staedte

Staedte(Ort, BLand, Ministerpraesident, Einwohnerzahl). Kandidatenschluessel {Ort, BLand} und {Ort, Ministerpraesident}. FDs: {BLand}->{Ministerpraesident} und {Ministerpraesident}->{BLand}. Diese FDs haben keine Superschluessel als linke Seite, aber ihre rechten Seiten sind prim -> 3NF ist erfuellt, BCNF nicht.

Attribute: Ort, BLand, Ministerpraesident, EW
Kandidatenschluessel:
  K1 = {Ort, BLand}
  K2 = {Ort, Ministerpraesident}
Prim-Attribute: Ort, BLand, Ministerpraesident

FD-Check:
{Ort, BLand} -> {EW}                Superschluessel -> OK
{BLand} -> {Ministerpraesident}     kein SK, aber rechts prim -> 3NF OK, BCNF verletzt
{Ministerpraesident} -> {BLand}     kein SK, aber rechts prim -> 3NF OK, BCNF verletzt

Ergebnis: 3NF ja, BCNF nein

Beispiel 4NF-Verletzung: Faehigkeiten

Faehigkeiten(PersNr, Sprache, ProgSprache) mit unabhaengigen MVDs {PersNr}->->{Sprache} und {PersNr}->->{ProgSprache}. Alle drei Attribute bilden den Schluessel. BCNF ist erfuellt (nur triviale FDs), aber MVDs ohne Superschluessel verletzen 4NF. Zerlegung in Sprachen(PersNr, Sprache) und ProgSprachen(PersNr, ProgSprache).

Vor 4NF-Zerlegung (4 Zeilen fuer Person 3002):
| PersNr | Sprache    | ProgSprache |
| 3002   | griechisch | C           |
| 3002   | griechisch | Pascal      |
| 3002   | lateinisch | C           |
| 3002   | lateinisch | Pascal      |

MVDs: PersNr ->-> Sprache, PersNr ->-> ProgSprache
PersNr ist kein Superschluessel -> 4NF verletzt

Nach Zerlegung:
Sprachen(PersNr, Sprache), ProgSprachen(PersNr, ProgSprache)
=> nur noch 2+2 statt 4 Tupel

Grafik: Inklusionshierarchie der Normalformen

Die Normalformen liegen als konzentrische Bereiche ineinander: jede hoehere Normalform ist eine Teilmenge der niedrigeren. Aussen (rot) hohes Anomalie-Risiko, innen (gruen) redundanzfreies Schema. Der Zerlegungspfeil zeigt den schrittweisen Uebergang von aussen nach innen.

FAQ

Wie erkenne ich schnell, dass eine Relation nicht in 1NF ist?

Wenn in einer Zelle eine Menge, Liste, ein komma-separierter Wert oder eine geschachtelte Relation steht. Beispiel: Kinder=(Else, Lucie) oder ein Feld mit mehreren Telefonnummern in einer Zelle.

Wann ist 2NF automatisch erfuellt?

Immer dann, wenn der Primaerschluessel aus nur einem Attribut besteht. Partielle Abhaengigkeiten koennen nur bei zusammengesetzten Schluesseln entstehen.

Was ist der genaue Unterschied zwischen 3NF und BCNF?

3NF erlaubt eine dritte Rettungs-Bedingung: die rechte Seite der FD ist prim (Teil eines Kandidatenschluessels). BCNF fordert strikt, dass die linke Seite jeder nicht-trivialen FD ein Superschluessel ist. Der Unterschied wird nur bei mehreren ueberlappenden Kandidatenschluesseln sichtbar.

Warum reicht BCNF nicht immer?

BCNF-Zerlegung ist zwar verlustlos, aber nicht immer abhaengigkeitserhaltend. Beispiel PLZverzeichnis: die FD Strasse,Ort,BLand->PLZ geht bei der BCNF-Zerlegung verloren. In solchen Faellen bleibt man bei 3NF, um Abhaengigkeitserhalt zu sichern.

Was ist ein prim-Attribut?

Ein Attribut, das in mindestens einem Kandidatenschluessel enthalten ist. Es kann auch in mehreren enthalten sein. Nichtschluesselattribute sind Attribute, die in keinem Kandidatenschluessel vorkommen.

Was ist eine mehrwertige Abhaengigkeit (MVD)?

alpha ->-> beta bedeutet: fuer feste alpha-Werte ist die Menge der beta-Werte unabhaengig von den restlichen Attributen der Relation. Anschaulich sind zwei semantisch unabhaengige Mehrfach-Attribute in derselben Tabelle zusammengezogen.

Wann liegt automatisch 4NF vor?

Wenn eine Relation in BCNF ist und keine nicht-trivialen mehrwertigen Abhaengigkeiten enthaelt. In den meisten praktischen Faellen ist BCNF bereits ausreichend, 4NF wird nur relevant bei zwei unabhaengigen n:m-Beziehungen in einer Tabelle.

Was macht man mit einer Relation, die alle Bedingungen der 4NF erfuellt?

Nichts - sie ist optimal normalisiert bezueglich der Klausur-relevanten Stufen. Eine solche Relation kann fast direkt in ein physisches DB-Schema mit Primary Keys uebertragen werden.

Pruefungsfragen

0 von 12 Fragen beantwortet