Zerlegungsalgorithmus Normalform

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Unter Normalisierung eines relationalen Datenbankschemas versteht man die schrittweise Zerlegung von Relationen (in der Datenbank: Tabellen), mittels Normalisierungsalgorithmen (siehe z. B. Synthesealgorithmus (3NF), Zerlegungsalgorithmus (BCNF)), in mehrere Relationen auf der Grundlage funktionaler Abhängigkeiten. Eine Normalisierung ist notwendig, um Redundanzen der Daten zu vermeiden, die bei der Änderung von Daten zu Inkonsistenzen führen können und einen erhöhten Speicherplatz benötigen.

Das Relationenschema wird dabei in die erste, zweite, dritte usw. Normalform überführt. Damit ein Relationenschema in einer Normalform vorliegt, muss es die Kriterien der jeweiligen Normalform erfüllen.

Vorgehen

Ziel: Redundanzvermeidung und Konsistenzerhöhung

Aufspaltung der Tabelle tbl_AdressenAlles

Bei der Normalisierung werden zunächst Spalten (synonyme Begriffe: Felder, Attribute) von Tabellen innerhalb der Datenbank in neue Spalten aufgeteilt, z. B. Adressen in Postleitzahl, Ort und Straße. Zweitens werden Tabellen aufgeteilt, z.B. eine Tabelle tbl_AdressenAlles mit den Feldern Firma, Straße, PLZ und Ort in die Tabellen

• tbl_Adressen mit den Feldern Firma, Straße und PLZOrtID und eine Tabelle
• tbl_PLZOrt mit den Feldern PLZOrtID, PLZ und Ort

(s. nebenstehende Abbildung - wobei die Tabelle tbl_Adressen noch einen eindeutigen Primärschlüssel AdressID erhält).

Der Sinn der Normalisierung besteht darin, Redundanzen (gleiche, mehrmals vorhandene Information) zu verringern und dadurch verursachte Anomalien (z. B. einander widersprechende Dateninhalte) zu verhindern, um so die Wartung einer Datenbank zu vereinfachen sowie die Konsistenz der Daten zu gewährleisten.

Beispiel

Deutlich wird dies an einem einfachen Beispiel: Eine Datenbank enthält Kunden und deren Adressen sowie Aufträge, die den Kunden zugeordnet sind. Da es mehrere Aufträge vom selben Kunden geben kann, würde eine Erfassung der Kundendaten (womöglich mit Adressdaten) in der Auftragstabelle dazu führen, dass sie dort mehrfach vorkommen, obwohl der Kunde immer nur einen Satz gültiger Daten hat (Redundanz). So kann es – in dieser Tabelle oder auch gegenüber anderen Tabellen – zu widersprüchlichen Daten kommen. Die Daten wären dann nicht konsistent.

Bei einer normalisierten Datenbank gibt es für die Kundendaten nur einen einzigen Eintrag in der Kundentabelle.

Ein weiterer Vorteil von Redundanzfreiheit ist der geringere Speicherbedarf, wenn der Datensatz einer Tabelle z. B. tbl_Auftrag auf einen Datensatz einer anderen Tabelle z. B. tbl_Kunde verweist, anstatt diese Daten selbst zu enthalten.

Aufspaltung von Tabellen zur Normalisierung

Dieses sind die Empfehlungen, die ausgehend von der Theorie der Normalisierung bei der Datenbankentwicklung gegeben werden, um vor allem Konsistenz der Daten und eine eindeutige Selektion von Daten zu gewährleisten. Die hierzu angestrebte Redundanzfreiheit steht allerdings in speziellen Anwendungsfällen in Konkurrenz zur Performance oder/und zu anderen Zielen. Es kann daher sinnvoll sein, auf eine Normalisierung zu verzichten oder diese durch eine Denormalisierung rückgängig zu machen, um

• die Performance (Verarbeitungsgeschwindigkeit) zu erhöhen oder
• Anfragen zu vereinfachen und damit die Fehleranfälligkeit zu verringern oder
• Besonderheiten von Prozessen (z.B. Geschäftsprozessen) abzubilden.

In diesen Fällen sollten regelmäßig automatische Abgleichroutinen implementiert werden, um Inkonstistenzen zu vermeiden. Alternativ kann man die betreffenden Daten auch für Änderungen sperren.

Normalformen

Zurzeit gebräuchliche Normalformen sind:

• 1. Normalform (1NF)
• 2. Normalform (2NF)
• 3. Normalform (3NF)
• Boyce-Codd-Normalform (BCNF)
• 4. Normalform (4NF)
• 5. Normalform (5NF)

Zum einen dienen sie der Beurteilung der Qualität eines betrachteten Datenbankschemas, zum anderen helfen sie, Fehler beim Erzeugen neuer Schemata zu vermeiden.

Außerdem können mit Hilfe der Normalisierung Datenstrukturen aus nichtrelationalen Quellen gewonnen werden, die im Sinne des Normalisierungskonzepts formal korrekt sind und die Daten aus ihren jeweiligen nichtrelationalen Quellen, aus denen sie entstanden sind (z. B. Formulardaten oder Spreadsheets), aufnehmen können.

Nachfolgend werden die Kriterien der jeweiligen Normalformen erklärt. Dabei ist zu beachten, dass jede Normalform die Kriterien der „vorherigen“ Normalformen mit einschließt.

Erste Normalform (1NF)

Jedes Attribut der Relation muss einen atomaren Wertebereich haben und frei von Wiederholungsgruppen sein. (Anm.: statt „atomar“ wird auch die Bezeichnung „atomisch“ verwendet.^[1])

Das heißt, zusammengesetzte, mengenwertige oder geschachtelte Wertebereiche (relationenwertige Attributwertebereiche) sind nicht erlaubt. Kurz: Kein Attributwertebereich kann in weitere (sinnvolle) Teilbereiche aufgespalten werden (Beispiel: Die Adresse darf nicht als Attribut verwendet werden, sondern muss – sofern es der zugrunde liegende Prozess erfordert – in PLZ, Ort, Straße, Hausnummer aufgeteilt werden).

Dass die Relation frei von Wiederholungsgruppen sein muss, bedeutet, dass Attribute, die gleiche oder gleichartige Information enthalten, in eine andere Relation ausgelagert werden müssen.

Beispiele dafür könnten sein: { .., Telefon1, Telefon2, Telefon3,.. }. In diesem Fall umfasst die Gruppe nur ein Attribut und tritt dreimal auf. { .., Ländervorwahl1, Netzvorwahl1, Telefon1, Durchwahl1, Ländervorwahl2, Netzvorwahl2, Telefon2, Durchwahl2, .. } ist ein Beispiel für eine Wiederholungsgruppe mit 4 Attributen, die zweimal auftritt.

Ob Inhalte atomar sind bzw. ob tatsächlich eine Wiederholungsgruppe vorliegt, lässt sich oft nur im Licht der Anwendung entscheiden: Wo z. B. für praktisch jede kommerzielle Anwendung eine Spalte „Telefonnummer“ (ohne Vor- & Durchwahlen) als atomar betrachtet werden darf, könnte es für einen Telekommunikationsbetreiber durchaus sinnvoll sein, weiter aufzuteilen: { .., Zifferngruppe1, Zifferngruppe2, Zifferngruppe3,.. }.

Praktischer Nutzen
Abfragen der Datenbank werden durch die 1NF erleichtert bzw. überhaupt erst ermöglicht, da die Attributwertebereiche atomar sind. So ist es beispielsweise in einem Feld, das einen ganzen Namensstring aus Titel, Vorname und Zuname enthält, schwierig bis unmöglich, nach Zunamen zu sortieren.

Alternative Formulierungen
Alle Attribute enthalten atomare Inhalte, und die Relation hat eine feste Breite. Diese Formulierung bezieht sich darauf, dass niemals weitere Attribute in die Relation aufgenommen werden müssen, weil die Wiederholungszahl der Wiederholungsgruppe zu klein wird (z. B.: es wird bei drei Attributen Telefon1-3 eine 4. Telefonnummer für eine Person bekannt). Sie ist insofern interessant, als sie helfen kann zu entscheiden, ob tatsächlich eine Wiederholungsgruppe vorliegt: Obwohl z. B. { .., Telefon1, Telefon2, Telefon3,.. } sehr stark das Vorhandensein einer Wiederholungsgruppe impliziert, könnte es bei lediglich anderen Attributnamen klar werden, dass - freilich unter dem Licht der Anwendung - dem nicht so sein muss: { .., Telefon, Fax, Mobil,.. }

Eine weitere Variante entsteht durch folgenden Zusatz: .. und die Relation einen Primärschlüssel hat. Obwohl diese Formulierung so nicht bei Codd nachgelesen werden kann, handelt es sich um eine Erweiterung, die zu ausgesprochen praxistauglichen Datenstrukturen führt.

Beispiel

CD_Lieder

CD_ID	Album	Jahr der Gründung	Titelliste
4711	Anastacia - Not That Kind	1999	{1. Not That Kind, 2. I'm Outta Love, 3. Cowboys & Kisses}
4712	Pink Floyd - Wish You Were Here	1964	{1. Shine On You Crazy Diamond}
4713	Anastacia - Freak of Nature	1999	{1. Paid my Dues}

Verletzung der 1NF

• Das Feld Album beinhaltet die Attributwertebereiche Interpret und Albumtitel.
• Das Feld Titelliste enthält eine Menge von Titeln.

Dadurch hat man ohne Aufspaltung folgende Probleme bei Abfragen:

• Zur Sortierung nach Albumtitel muss das Feld Album in Interpret und Albumtitel aufgeteilt werden.
• Die Titel können (mit einfachen Mitteln) nur alle gleichzeitig als Titelliste oder gar nicht dargestellt werden.

Lösung

CD_Lieder

CD_ID	Albumtitel	Interpret	Jahr der Gründung	Track	Titel
4711	Not That Kind	Anastacia	1999	1	Not That Kind
4711	Not That Kind	Anastacia	1999	2	I'm Outta Love
4711	Not That Kind	Anastacia	1999	3	Cowboys & Kisses
4712	Wish You Were Here	Pink Floyd	1964	1	Shine On You Crazy Diamond
4713	Freak of Nature	Anastacia	1999	1	Paid my Dues

Die Attributwertebereiche werden in atomare Attributwertebereiche aufgespalten:

• Das Feld Album wird in die Felder Albumtitel und Interpret gespalten.
• Das Feld Titelliste wird in die Felder Track und Titel gespalten sowie auf mehrere Datensätze aufgeteilt.

Da jetzt jeder Attributwertebereich atomar ist sowie die Tabelle einen eindeutigen Primärschlüssel (Verbundschlüssel aus den Spalten CD_ID und Track) besitzt, befindet sich die Relation in 1NF.

Zweite Normalform (2NF)

Eine Relation ist in der zweiten Normalform, wenn die erste Normalform vorliegt und jedes Nichtschlüsselattribut von jedem Schlüsselkandidaten voll funktional abhängig ist.

Anders gesagt: Jedes nicht-primäre Attribut (nicht Teil eines Schlüssels) ist jeweils vom ganzen Schlüssel abhängig, nicht von nur einem Teil eines Schlüssels.

In einer Relation R(A,B) ist das Attribut B von dem Attribut A funktional abhängig, falls zu jedem Wert des Attributs A genau ein Wert des Attributs B gehört. In einer Relation R(S1,S2,B) ist das Attribut B von den Schlüsselattributen S1 und S2 voll funktional abhängig, wenn B von den zusammengesetzten Attributen (S1,S2) funktional abhängig ist, nicht aber von einem einzelnen Attribut S1 oder S2.

Diese informelle Definition kann wie folgt präzisiert werden:

Eine Relation ist genau dann in zweiter Normalform, wenn sie

1. in der ersten Normalform ist und
2. für jeden Schlüsselkandidaten (Key Candidate, KC) und jedes Attribut a der Relation gilt:
   • a gehört zu KC oder
   • a ist nicht von einer echten Teilmenge von KC abhängig.

a ist voll funktional abhängig von jedem Schlüsselkandidaten (wobei die Schlüsselkandidaten KC auch durch die Kombination mehrerer Attribute gebildet werden können). Die 2NF eliminiert alle partiellen funktionalen Abhängigkeiten, d. h. funktionale Abhängigkeiten von Teilen des Schlüsselkandidaten.

Falls ein Schlüsselkandidat zwei Attribute besitzt, können bei der Zerlegung in die 2NF höchsten drei Relationen entstehen. Falls ein Schlüsselkandidat drei Attribute besitzt, können bei der Zerlegung in die 2NF höchsten sieben Relationen entstehen. Das sind jeweils die Anzahl der Teilmengen einer gegebenen Menge minus 1 (leere Menge) und entspricht der Anzahl der Elemente der Potenzmenge als Obergrenze.

Praktischer Nutzen
Die 2. NF erzwingt wesentlich „monothematische“ Relationen im Schema: jede Relation modelliert nur einen Sachverhalt.

Dadurch werden Redundanz und die damit einhergehende Gefahr von Inkonsistenzen reduziert. Nur noch logisch/sachlich zusammengehörige Information findet sich in einer Relation. Dadurch fällt das Verständnis der Datenstrukturen leichter.

Beispiel

CD_Lieder

CD_ID	Albumtitel	Interpret	Jahr der Gründung	Track	Titel
4711	Not That Kind	Anastacia	1999	1	Not That Kind
4711	Not That Kind	Anastacia	1999	2	I'm Outta Love
4711	Not That Kind	Anastacia	1999	3	Cowboys & Kisses
4712	Wish You Were Here	Pink Floyd	1964	1	Shine On You Crazy Diamond
4713	Freak of Nature	Anastacia	1999	1	Paid my Dues

Verletzung der 2NF

• Der Primärschlüssel der Relation ist aus den Feldern CD_ID und Track zusammengesetzt.
• Die Felder Albumtitel, Interpret und Jahr der Gründung sind zwar vom Feld Track alleine unabhängig, aber nicht vom Feld CD_ID. Dies verletzt die 2.Normalform, da die drei nicht-primären Attribute nicht nur von einem Teil des Schlüssels (hier CD_ID) abhängen dürfen.

Probleme, die sich daraus ergeben:
Die Informationen aus diesen beiden Feldern sind, wie am Beispiel der CD Not That Kind zu erkennen, mehrfach vorhanden, d. h. redundant. Dadurch besteht die Gefahr, dass die Integrität der Daten verletzt wird. So könnte man den Albumtitel für das Lied Not That Kind in I Don’t Mind ändern, ohne jedoch die passenden Einträge bei den Liedern I'm Outta Love und Cowboys & Kisses zu ändern (Update-Anomalie).

CD_Lieder (inkonsistent)

CD_ID	Albumtitel	Interpret	Jahr der Gründung	Track	Titel
4711	I Don’t Mind	Anastacia	1999	1	Not That Kind
4711	Not That Kind	Anastacia	1999	2	I'm Outta Love
4711	Not That Kind	Anastacia	1999	3	Cowboys & Kisses
4712	Wish You Were Here	Pink Floyd	1964	1	Shine On You Crazy Diamond
4713	Freak of Nature	Anastacia	1999	1	Paid my Dues

In diesem Fall ist ein Zustand erreicht, den man als Dateninkonsistenz bezeichnet. Über die komplette Tabelle betrachtet, „passen“ die Daten nicht mehr zusammen.

Lösung

Die Daten in der Tabelle werden in zwei Tabellen aufgeteilt: CD und Lieder. Die Tabelle CD enthält nur noch Felder, die voll funktional von CD_ID abhängen, hat also nur noch CD_ID als Primärschlüssel und liegt damit automatisch in der 2. Normalform vor. Die Tabelle Lieder enthält schließlich nur noch Felder, die voll funktional von CD_ID und Track abhängen, liegt also auch in der 2. Normalform vor. Mit Hilfe dieser verlustfreien Zerlegung sind auch die genannten Redundanzen der Daten beseitigt.

CD CD_ID Albumtitel Interpret Jahr der Gründung 4711 Not That Kind Anastacia 1999 4712 Wish You Were Here Pink Floyd 1964 4713 Freak of Nature Anastacia 1999

Lieder CD_ID Track Titel 4711 1 Not That Kind 4711 2 I'm Outta Love 4711 3 Cowboys & Kisses 4712 1 Shine On You Crazy Diamond 4713 1 Paid my Dues

Das Attribut CD_ID aus der Tabelle Lieder bezeichnet man als Fremdschlüssel, der auf den Primärschlüssel der Tabelle CD verweist. Zugleich stellen die Attribute CD_ID und Track den zusammengesetzten Primärschlüssel der Tabelle Lieder dar.

Dritte Normalform (3NF)

Die dritte Normalform ist erreicht, wenn sich das Relationenschema in 2NF befindet, und jedes Nichtschlüsselattribut von keinem Schlüsselkandidaten transitiv abhängt.

Ein Attribut A ist vom Schlüsselkandidaten P transitiv abhängig, wenn es ein Attribut B gibt, sodass $(P \rightarrow B)$ und $(B \rightarrow A)$, aber nicht $(P \rightarrow A)$.

Hierbei handelt es sich um eine Abhängigkeit, bei der ein Attribut A₂ über ein anderes Attribut A₁ von einem Schlüsselkandidaten P₁ der Relation abhängig ist (ohne dass zugleich auch A₂ direkt von P₁ abhängig ist). Das heißt: Wenn Attribut A₁ von Attribut P₁ (dem Primärattribut) abhängt und Attribut A₂ von A₁, dann ist A₂ transitiv abhängig von P₁. Formal ausgedrückt: $(P_1 \rightarrow A_1) \wedge (A_1 \rightarrow A_2) \Rightarrow P_1 \rightarrow A_2$.

Einfach gesagt: Ein Nichtschlüsselattribut darf nicht von einer Menge abhängig sein, die ausschließlich aus Nichtschlüsselattributen besteht. Ein Nichtschlüsselattribut darf also nur direkt von einem Schlüssel abhängen.

Siehe auch: Transitivität (Mathematik), Synthesealgorithmus-Normalform

Praktischer Nutzen
Transitive Abhängigkeiten sind sofort ersichtlich, ohne dass man die Zusammenhänge der Daten kennen muss. Sie sind durch die Struktur der Relationen wiedergegeben.

Außerdem werden verbliebene thematische Durchmischungen in der Relation behoben: nach der 3NF sind die Relationen des Schemas zuverlässig monothematisch.

Beispiel

CD

CD_ID	Albumtitel	Interpret	Jahr der Gründung
4711	Not That Kind	Anastacia	1999
4713	Freak of Nature	Anastacia	1999
4712	Wish You Were Here	Pink Floyd	1964

Verletzung der 3NF

Offensichtlich lässt sich der Interpret einer CD aus der CD_ID bestimmen, das Gründungsjahr der Band hängt dagegen vom Interpreten und damit transitiv von der CD_ID ab.

Das Problem ist hierbei wieder Datenredundanz. Wird zum Beispiel eine neue CD mit einem existierenden Interpreten eingeführt, so wird das Gründungsjahr zweimal gespeichert.

Lösung

CD CD_ID Albumtitel Interpret 4711 Not That Kind Anastacia 4713 Freak of Nature Anastacia 4712 Wish You Were Here Pink Floyd

Künstler Interpret Jahr der Gründung Anastacia 1999 Pink Floyd 1964

Die Relation wird aufgeteilt, wobei die beiden voneinander abhängigen Daten in eine eigene Tabelle ausgelagert werden. Der Schlüssel der neuen Tabelle muss als Fremdschlüssel in der alten Tabelle erhalten bleiben.

Boyce-Codd-Normalform (BCNF)

Eine Relation ist in BCNF, wenn sie die Voraussetzungen der 3NF erfüllt, und jede Determinante (Attributmenge, von der andere Attribute funktional abhängen) ein Superschlüssel ist (oder die Abhängigkeit ist trivial). Ein Superschlüssel ist eine Menge von Attributen, von der alle Attribute der Relation funktional abhängig sind.

Die BCNF (nach Raymond F. Boyce und Edgar F. Codd) verhindert, dass Teile zweier aus mehreren Feldern zusammengesetzten Schlüsselkandidaten voneinander abhängig sind.

Die Überführung in die BCNF ist zwar immer verlustfrei möglich, aber nicht immer abhängigkeitserhaltend. Die Boyce-Codd-Normalform war ursprünglich als Vereinfachung der dritten Normalform gedacht, führte aber zu einer neuen Normalform, die die 3NF verschärft.

Beispiel

In diesem Beispiel gibt es eine einfache Datenbank, in der die Vereinszugehörigkeit von Sportlern gespeichert wird. Es sollen die folgenden Bedingungen gelten:

• jeder Verein bietet nur eine Sportart an.
• ein Sportler kann in verschiedenen Vereinen spielen, aber nur, wenn diese Vereine unterschiedliche Sportarten betreiben. Damit wird sichergestellt, dass der Sportler nie gegen einen Verein spielt, in dem er selbst Mitglied ist.

Sportler

Name	Sportart	Verein
Schuster	Fußball	FC Musterhausen
Leitner	Fußball	FC Musterhausen
Leitner	Eishockey	EC Beispielstadt

Verletzung der BCNF

Aus den oben genannten Bedingungen folgt, dass das Attribut Sportart funktional abhängig vom Attribut Verein ist, d. h. Verein ist eine Determinante. Jedoch ist Verein kein Schlüsselkandidat.

Durch diese Konstellation ist die Relation nur in 3NF, nicht in BCNF. Jedoch ist eine Konvertierung in BCNF möglich, indem (Name, Verein) als Primärschlüssel verwendet und die Relation aufgeteilt wird:

Lösung

Sportler Name Verein Schuster FC Musterhausen Leitner FC Musterhausen Leitner EC Beispielstadt

Verein Verein Sportart FC Musterhausen Fußball EC Beispielstadt Eishockey

Zerlegungsalgorithmus

Es existiert ein Algorithmus, der relationale Schemata durch Zerlegung (engl. decomposition) in die Boyce-Codd-Normalform überführt. Alle Schemata werden dabei solange aufgespalten, bis keines mehr die BCNF bricht. Jede Aufspaltung erfolgt anhand einer, die BCNF verletzenden, funktionalen Abhängigkeit. Die Attribute der verletzenden Abhängigkeit bilden das erste neue Schema, und die restlichen Attribute plus die Determinante ein weiteres Schema. Die beiden neuen Schemata enthalten von den ursprünglichen funktionalen Abhängigkeiten lediglich solche, welche nur Attribute des jeweiligen Schemas nutzen, der Rest geht verloren.

Folgender Pseudocode beschreibt den Zerlegungsalgorithmus:^[2]

1:	Gegeben ist ein relationales Schema $R = (\overline R, \mathcal{F})$, mit der Menge aller Attribute $\overline R$ und der Menge der funktionalen Abhängigkeiten $\mathcal{F}$ über diesen Attributen.
2:	Die Ergebnismenge Dekomposition, bestehend aus den zerlegten Schemata, wird mit R initialisiert.
3:	Solange es ein Schema S in der Menge Dekomposition gibt, das nicht in der BCNF ist, führe folgende Zerlegung aus:
4:	Sei $\overline X\overline Y\subseteq\overline S$ eine Attributmenge für die eine funktionale Abhängigkeit $\overline X\rightarrow \overline Y$ definiert ist, welche der BCNF widerspricht.
5:	Ersetze S in der Ergebnismenge Dekomposition durch zwei neue Schemata $S_1 = (\overline X\overline Y, \mathcal{F}_1)$, ein Schema bestehend nur aus den Attributen der Abhängigkeit, welche die BCNF ursprünglich verletzt hat; und $S_2 = ((\overline S - \overline Y) \cup \overline X, \mathcal{F}_2)$, ein Schema mit allen Attributen, außer denen die nur in der abhängigen Menge $\overline Y$ und nicht in der Determinante $\overline X$ enthalten sind. Die Menge der funktionalen Abhängigkeiten $\mathcal{F}_1$ enthält nur noch die Abhängigkeiten, welche lediglich Attribute aus $\overline X\overline Y$ enthalten, entsprechendes gilt für $\mathcal{F}_2$. Damit fallen alle Abhängigkeiten weg, welche Attribute aus beiden Schemata benötigen.
6:	Ergebnis: Dekomposition - eine Menge von relationalen Schemata, welche in der BCNF sind.

Durchlauf des Algorithmus am obigen Beispiel (ohne Darstellung aller trivialen Abhängigkeiten):

• 1: R = ( { Name, Sportart, Verein }, { ( { Name, Sportart } → { Verein } ), ( { Verein } → { Sportart } ), ( { Name, Verein } → { Name, Verein } ) } )
• 2: Dekomposition = { R }
• 3: da R aus Dekomposition nicht die BCNF erfüllt mache folgendes:
  • 4,5: { Verein } → { Sportart } ist die Abhängigkeit, die die Verletzung der BCNF bedingt, damit ist S₁ = ( { Verein, Sportart }, { ( { Verein } → { Sportart }) } ) und S₂ = ( { Name, Verein }, { ( { Name, Verein } → { Name, Verein } ) } )
• 6: Ergebnis: Dekomposition: = {S₁,S₂}

Vierte Normalform (4NF)

Die 4. Normalform beschreibt die mehrwertige Abhängigkeit (MWAs). Eine Datenbank ist dann in der 4. Normalform, wenn sie nur noch triviale mehrwertige Abhängigkeiten enthält oder die nicht-trivialen mehrwertigen Abhängigkeiten von Superschlüsseln ausgehen. Einfach gesagt: Es darf in einer Relation nicht mehrere, voneinander unabhängige, 1:n-Beziehungen zu einem Schlüsselwert geben, z. B. gehört zu einem Schlüsselwert i-mal Attribut a, aber davon unabhängig auch m-mal Attribut b).

Beispiel

Besitz

Personnummer	Haustier	Fahrzeug
1	Katze	Volkswagen
1	Katze	Ferrari
1	Pelikan	Volkswagen
1	Pelikan	Ferrari
2	Hund	Porsche

Verletzung der 4NF

Zu einer Personennummer gibt es mehrere Haustiere und Fahrzeuge. Haustier und Fahrzeug sind aber unabhängig voneinander. Personnummer → Haustier ist dabei eine mehrwertige Abhängigkeit (MWA), Personnummer → Fahrzeug auch. Diese beiden MWAs sind unabhängig voneinander, also können wir diese Tabelle in die 4NF aufspalten.

Lösung

Haustier Personnummer Haustier 1 Katze 1 Pelikan 2 Hund

Fahrzeug Personnummer Fahrzeug 1 Volkswagen 1 Ferrari 2 Porsche

Hinweis

Folgende Relation erfüllt die 4NF:

Familie

Personnummer	Partner	Kind

Person → Partner und Person → Kind sind zwar zwei MWAs, aber diese beiden sind auch untereinander abhängig: Partner → Kind. Solche untereinander abhängigen MWAs werden erst in 5NF gelöst.

Fünfte Normalform (5NF)

Die 5NF vereinfacht Relationen soweit, dass durch Projektions- und Verbundoperationen die Informationen der ursprünglichen Relation wiederhergestellt werden. Sie ist somit sehr generell gehalten und dadurch (vorerst) die letzte Normalform. So können Relationen in einzelne Abfragen aufgeteilt werden und durch spätere Verbundsoperationen wieder zusammengefügt werden, wobei eine Teilmenge des so genannten kartesischen Produkts entsteht. Einfach gesagt: Eine Relation ist in 5NF, wenn sie sich nicht weiter in Relationen aufspalten lässt, ohne dass Information verloren geht.

Beispiel

Die folgende Relation zeigt, welche Lieferanten welche Bauteile an welches Projekt liefern können:

Lieferant	Teil	Projekt
Müller	Schraube	Projekt 1
Müller	Nagel	Projekt 2
Maier	Nagel	Projekt 1

Verletzung der 5NF

Die Relation kann weiter zerteilt werden, ohne dass Information verloren geht.

Lösung

Um diese Relation in die 5. Normalform umzuwandeln, müssen drei Relationen erstellt werden (Lieferant-Teil, Teil-Projekt und Lieferant-Projekt).

• Welche Teile kann welcher Lieferant liefern?

Lieferant-Teil

Lieferant	Teil
Müller	Schraube
Müller	Nagel
Maier	Nagel

• Welche Teile werden von welchem Projekt benötigt?

Teil-Projekt

Teil	Projekt
Schraube	Projekt 1
Nagel	Projekt 2
Nagel	Projekt 1

• Welche Projekte können von welchem Lieferanten beliefert werden?

Lieferant-Projekt

Lieferant	Projekt
Müller	Projekt 1
Müller	Projekt 2
Maier	Projekt 1

Hinweis

Anders als bei der Umformung zwischen den bisherigen Normalformen wird durch diese Umwandlung etwas anderes durch die neuen Relationen ausgedrückt, als zuvor in der 4. Normalform.

Das merkt man leicht, wenn man die drei Relationen aus dem Beispiel oberhalb wieder vereinigt:

Lieferant	Teil	Projekt
Müller	Schraube	Projekt 1
Müller	Nagel	Projekt 2
Müller	Nagel	Projekt 1
Maier	Nagel	Projekt 1

Neu ist das Tupel: Müller – Nagel – Projekt 1.

Denn Müller könnte theoretisch das Projekt 1 mit Nägeln beliefern, da

• er auch Projekt 2 mit Nägeln beliefert und
• Projekt 1 auch Nägel benötigt (die jedoch bisher von Maier geliefert wurden).

Die Überführung in 5NF ist also nur dann möglich, wenn man die Möglichkeiten der Verbindungen aus drei Beziehungen ausdrücken möchte und nicht eine konkrete Verbindung zwischen den dreien haben möchte.

Bemerkungen

Schwächen im Datenmodell aufgrund fehlender Normalisierung können – neben den typischen Anomalien – einen höheren Aufwand bei einer späteren Weiterentwicklung bedeuten. Andererseits kann beim Datenbankentwurf aus Performance-Überlegungen bewusst auf Normalisierungsschritte verzichtet werden. Typisches Beispiel dafür ist das Sternschema im Data-Warehouse.

Die Erstellung eines normalisierten Schemas wird durch automatische Ableitung aus einem konzeptuellen Datenmodell gestützt; hierzu dient in der Praxis ein erweitertes Entity-Relationship-Modell (ERM) oder ein Klassendiagramm der UML als Ausgangspunkt. Das aus dem konzeptionellen Entwurf abgeleitete Relationenschema kann dann mit Hilfe der Normalisierungen überprüft werden; es existieren jedoch Formalismen und Algorithmen, die diese Eigenschaft bereits sicherstellen können. Statt des ursprünglichen ER-Modells (Chen, 1976) werden heute erweiterte ER-Modelle verwendet: Das Structured-ERM (SERM), das E3R-Modell, das EER-Modell sowie das von der SAP AG verwendete SAP-SERM.

Befindet sich ein Relationenschema nicht in einer der Normalformen, so nennt man diese Form auch NF² (Non-First-Normal-Form) bzw. UNF (Unnormalisierte Form).

Der Prozess der Normalisierung und Zerlegung einer Relation in die 1NF, 2NF und 3NF muss die Wiederherstellbarkeit der ursprünglichen Relation erhalten, das heißt die Zerlegung muss verbundtreu und abhängigkeitstreu sein.

Merkspruch

Als eine Gedächtnisstütze für die Grade von Abhängigkeit vom Schlüssel in den ersten drei Normalformen wird gerne folgender Spruch genannt: the key, the whole key, and nothing but the key - so help me Codd (Der Schlüssel, der ganze Schlüssel und nichts als der Schlüssel - so wahr mir Codd helfe.):

• alle (impliziert: atomaren) Werte beziehen sich auf den Schlüssel - 1. NF
• bei zusammengesetzten Schlüsseln beziehen sie sich jeweils auf den gesamten Schlüssel - 2. NF
• die Werte hängen nur vom Schlüssel ab, und nicht von weiteren Werten - 3. NF

Merkregeln

1. Ist die Relation in 1. Normalform und besteht der Primärschlüssel aus nur einem Attribut, so liegt automatisch die 2. Normalform vor.
2. Ist eine Relation in 2. Normalform und besitzt sie außer dem Primärschlüssel höchstens ein weiteres Attribut, so liegt die Tabelle in 3. Normalform vor.

Quellen

1. ↑ Paul Alpar: Datenorganisation und Datenbanken, S. 31 (PDF)
2. ↑ Philip M. Lewis, Arthur Bernstein, Michael Kifer: Databases and transaction processing: an application-oriented approach. Addison-Wesley, 2002, ISBN 0-201-70872-8, S. 232. 

Literatur

• Ramez Elmasri, Shamkant B. Navathe: Grundlagen von Datenbanksystemen. Pearson Studium, 2002, ISBN 3-8273-7021-3
• Alfons Kemper, Andre Eickler: Datenbanksysteme. Eine Einführung. Oldenbourg, München 2004, ISBN 3-486-27392-2
• Stefan M. Lang, Peter C. Lockemann: Datenbankeneinsatz. Springer, Berlin u. a. 1995, ISBN 3-540-58558-3

Weblinks

• Der Königsweg: Normalisierung, Hochschule der Medien Stuttgart
• Access: Grundlagen der Datenbanknormalisierung, Microsoft Hilfe und Support
• Normalisierung von Datenbanken, Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
• Erklärung der Normalformen, Ziemer's Informatik
• Interaktiver Normalformentrainer bis zur 3. Normalform