Normalisierung (Datenbank)

Grundidee und Ziel

Normalisierung ist ein Entwurfsansatz für relationale Datenbanken. Sie strukturiert Daten mithilfe aufeinander aufbauender Regeln, der Normalformen. Ziel ist, redundante Speicherung zu verringern und dadurch Inkonsistenzen sowie Einfüge-, Änderungs- und Löschanomalien zu vermeiden. Änderungen sollen möglichst nur an einer Stelle vorgenommen werden müssen; zugleich wird die Konsistenz der Daten verbessert.

Beim Normalisieren werden Tabellen und Attribute anhand ihrer funktionalen Abhängigkeiten aufgeteilt. Eine funktionale Abhängigkeit bedeutet beispielsweise: Zu jedem Wert eines Attributs A gehört genau ein Wert des Attributs B, geschrieben A → B. Die Zerlegung soll die Informationen ohne Datenverlust wiederherstellbar machen. Für einzelne Zerlegungsschritte kann mit dem Satz von Delobel geprüft werden, ob ein Datenverlust entsteht.

Die gebräuchlichen Normalformen sind 1NF, 2NF, 3NF, Boyce-Codd-Normalform (BCNF), 4NF und 5NF. Jede höhere Normalform schließt die Anforderungen der vorhergehenden ein: 1NF ⊆ 2NF ⊆ 3NF ⊆ BCNF ⊆ 4NF ⊆ 5NF.

Vorgehen und praktischer Nutzen

Zunächst werden zusammengesetzte Informationen in einzelne Attribute zerlegt, zum Beispiel eine Adresse in Postleitzahl, Ort und Straße. Danach werden Tabellen aufgeteilt. Aus einer Tabelle tbl_AdressenAlles mit Firma, Straße, PLZ und Ort können etwa tbl_Adressen mit AdressID, Firma, Straße und PLZ sowie tbl_PLZOrt mit PLZ und Ort entstehen. Dabei erhält tbl_Adressen einen eindeutigen Primärschlüssel. Das Beispiel setzt allerdings voraus, dass jeder Postleitzahl genau ein Ortsname zugeordnet ist; dies trifft in Deutschland oft nicht zu.

Ein typischer Anwendungsfall betrifft Kunden, Adressen und Aufträge. Werden Kundendaten in jedem Auftrag erneut gespeichert, können unterschiedliche oder veraltete Adressangaben entstehen. In einer normalisierten Datenbank gibt es die Kundendaten nur einmal in der Kundentabelle; Aufträge verweisen beispielsweise über die Kundennummer darauf. Mehrere zeitlich gültige Datensätze können durch einen Gültigkeitszeitraum unterschieden werden, im Beispiel über die Kombination aus Auftragsdatum und Kundennummer. Zusätzlich sinkt bei vielen Datensätzen der Speicherbedarf.

Normalisierung verbessert Konsistenz und Eindeutigkeit, kann aber mit Verarbeitungsgeschwindigkeit oder einfacheren Anfragen konkurrieren. Deshalb kann eine Denormalisierung sinnvoll sein, um Performance zu erhöhen, Anfragen zu vereinfachen oder besondere Geschäftsprozesse abzubilden. Dann sollten automatische Abgleichroutinen eingesetzt oder die betreffenden Daten für Änderungen gesperrt werden. Normalisierte Schemata können bereits beim Entwurf mithilfe eines erweiterten Entity-Relationship-Modells (ERM) oder eines UML-Klassendiagramms entwickelt und anschließend durch Algorithmen überprüft oder erzeugt werden.

1NF und 2NF

Die Erste Normalform (1NF) verlangt, dass jedes Attribut einen atomaren Wertebereich besitzt und keine Wiederholungsgruppen vorhanden sind. Atomar bedeutet, dass zusammengesetzte, mengenwertige oder geschachtelte Werte nicht als ein einziger Attributwert gespeichert werden. Eine Adresse wird daher, sofern der zugrunde liegende Prozess dies erfordert und erlaubt, in PLZ, Ort, Straße und Hausnummer aufgeteilt. Eine Spalte mit mehreren Telefonnummern oder eine Gruppe Telefon1, Telefon2, Telefon3 kann eine Wiederholungsgruppe darstellen. Gleichartige wiederholte Informationen müssen dann in eine andere Relation ausgelagert werden.

Die 1NF erleichtert Abfragen, weil einzelne Werte sortiert und gezielt ausgewählt werden können. Ein Feld mit dem gesamten Namensstring aus Titel, Vorname und Nachname eignet sich beispielsweise schlecht zur Sortierung nach dem Nachnamen.

Im CD-Lied-Beispiel verletzt eine Tabelle mit dem Feld Album und einer mengenwertigen Titelliste die 1NF. Album wird in Albumtitel und Interpret zerlegt; Titelliste wird in Track und Titel aufgeteilt und auf mehrere Datensätze verteilt. Der zusammengesetzte Primärschlüssel aus CD_ID und Track macht die einzelnen Titel eindeutig.

Die Zweite Normalform (2NF) setzt die 1NF voraus. Kein Nichtprimärattribut, also kein Attribut außerhalb eines Schlüsselkandidaten, darf funktional von einer echten Teilmenge eines Schlüsselkandidaten abhängen. Jedes Nichtschlüsselattribut muss vollständig von jedem Schlüsselkandidaten abhängig sein. Die 2NF beseitigt damit partielle funktionale Abhängigkeiten.

In der CD-Lied-Tabelle besteht der Primärschlüssel aus CD_ID und Track. Albumtitel, Interpret, Gründungsjahr und Erscheinungsjahr hängen jedoch nur von CD_ID ab, nicht von Track. Deshalb wird die Tabelle in CD mit CD_ID, Albumtitel, Interpret, Gründungsjahr und Erscheinungsjahr sowie Lied mit CD_ID, Track und Titel zerlegt. CD_ID in Lied ist ein Fremdschlüssel auf den Primärschlüssel von CD; CD_ID und Track bilden dort den zusammengesetzten Primärschlüssel.

Besteht ein Schlüsselkandidat nur aus einem Attribut, erfüllt eine Relation in 1NF automatisch die 2NF. Bei einem Schlüsselkandidaten mit zwei Attributen können bei einer Zerlegung in die 2NF höchstens drei Relationen entstehen, bei drei Attributen höchstens sieben. Diese Obergrenze entspricht 2^n minus 1.

3NF und BCNF

Die Dritte Normalform (3NF) setzt die 2NF voraus und verbietet funktionale Abhängigkeiten zwischen Nichtschlüsselattributen. Solche Abhängigkeiten heißen transitive Abhängigkeiten. Formal gilt: Wenn P₁ → A₁ und A₁ → A₂, dann folgt P₁ → A₂. A₂ ist dann über A₁ transitiv vom Schlüsselkandidaten P₁ abhängig.

Ein Nichtschlüsselattribut darf also nicht von anderen Nichtschlüsselattributen abhängen, sondern nur direkt von einem Schlüsselkandidaten. Im CD-Beispiel bestimmt CD_ID den Interpreten; das Gründungsjahr hängt vom Interpreten ab und damit transitiv von CD_ID. Zur Auflösung werden CD und Künstler getrennt. CD enthält CD_ID, Albumtitel, Interpret oder Interpret_ID und Erscheinungsjahr; Künstler enthält den Interpreten beziehungsweise die Interpret_ID und das Gründungsjahr. Der Schlüssel der neuen Tabelle bleibt als Fremdschlüssel in CD erhalten. Eine Interpret-Bezeichnung als Schlüssel ist nur dann ausreichend, wenn der Interpret weltweit eindeutig ist; andernfalls wird eine synthetische Interpret_ID verwendet.

Die Boyce-Codd-Normalform (BCNF) ist strenger als die 3NF. Ein Relationenschema ist in BCNF, wenn es in 3NF ist und jede Determinante, also jede Attributmenge, von der andere Attribute funktional abhängen, ein Superschlüssel ist oder die Abhängigkeit trivial ist.

Im Beispiel zu Sportlern, Sportarten und Vereinen gilt Verein → Sportart, weil jeder Verein nur eine Sportart anbietet. Verein ist jedoch kein Schlüsselkandidat; mögliche Schlüsselkandidaten sind {Name,Verein} und {Name,Sportart}. Die Tabelle wird daher in Sportler mit Name und Verein sowie Verein mit Verein und Sportart aufgeteilt. Die BCNF verhindert damit Abhängigkeiten, die in einer 3NF-Relation noch zu doppelten Informationen führen können.

Ein BCNF-Zerlegungsalgorithmus sucht eine verletzende funktionale Abhängigkeit X → Y. Das Schema wird durch ein Schema mit den Attributen X und Y sowie ein weiteres Schema mit den übrigen Attributen und X ersetzt. Dieser Vorgang wird wiederholt, bis alle Schemata in BCNF sind. Die Zerlegung ist immer verlustfrei möglich, aber nicht immer abhängigkeitserhaltend; funktionale Abhängigkeiten, die Attribute aus beiden neuen Schemata benötigen, können verloren gehen.

4NF und 5NF

Die Vierte Normalform (4NF) verlangt, dass eine Relation in BCNF ist und nur triviale mehrwertige Abhängigkeiten enthält. Eine mehrwertige Abhängigkeit (MWA) liegt vor, wenn zu einem Schlüsselwert mehrere Werte eines Attributs gehören und diese Werte unabhängig von mehreren Werten eines anderen Attributs sind. Thematisch unabhängige 1:n- oder m:n-Beziehungen dürfen daher nicht gemeinsam in einer Relation gespeichert werden.

In der Tabelle Personnummer–Haustier–Fahrzeug gehören zu einer Person mehrere Haustiere und mehrere Fahrzeuge, ohne dass ein bestimmtes Haustier einem bestimmten Fahrzeug zugeordnet ist. Die Tabelle enthält deshalb unabhängige mehrwertige Abhängigkeiten Personnummer ↠ Haustier und Personnummer ↠ Fahrzeug und verletzt die 4NF. Die Lösung besteht aus den Relationen Füttert (Personnummer, Haustier) und Fährt (Personnummer, Fahrzeug).

Nicht jede Relation mit mehreren mehrwertigen Abhängigkeiten verletzt die 4NF. In der Tabelle Elternschaft sind Person ↠ Partner und Person ↠ Kind untereinander abhängig; solche abhängigen mehrwertigen Abhängigkeiten werden erst in der 5NF behandelt.

Die Fünfte Normalform (5NF) setzt die 4NF voraus und verbietet voneinander abhängige mehrwertige Abhängigkeiten. Relationen sollen so vereinfacht werden, dass alle Informationen der ursprünglichen Relation durch Projektionen und Verbundoperationen wiederhergestellt werden können.

Im Beispiel Lieferant–Teil–Projekt wird festgehalten, welche Lieferanten welche Bauteile an welches Projekt liefern können. Die Relation wird in Lieferant-Teil, Teil-Projekt und Lieferant-Projekt zerlegt. Beim anschließenden Verbund kann jedoch eine neue Kombination entstehen: Müller–Nagel–Projekt 1. Diese Kombination ist theoretisch möglich, weil Müller Nägel liefert und Projekt 1 Nägel benötigt, obwohl bisher Maier diese Lieferung übernommen hat. Die Überführung in 5NF ist deshalb nur passend, wenn Möglichkeiten von Verbindungen aus drei Beziehungen dargestellt werden sollen, nicht eine konkrete Verbindung zwischen allen drei Objekten.

Grenzen und Wiederherstellbarkeit

Fehlende Normalisierung kann neben den typischen Anomalien auch spätere Weiterentwicklungen erschweren. Umgekehrt kann aus Performancegründen bewusst auf Normalisierung verzichtet werden; ein genanntes Beispiel ist das Sternschema im Data-Warehouse. Die Erstellung normalisierter Schemata wird durch konzeptionelle Modelle und formale Algorithmen unterstützt.

Befindet sich ein Relationenschema nicht in der 1NF, heißt es auch Non-First-Normal-Form (NF²) oder Unnormalisierte Form (UNF). Die Normalisierung und Zerlegung in 1NF, 2NF und 3NF muss die Wiederherstellbarkeit der ursprünglichen Relation erhalten. Die Zerlegung muss daher verbundtreu und abhängigkeitstreu sein.

Merkregel: Ist eine Relation in 1NF, besteht ihr Primärschlüssel aus nur einem Attribut und gibt es keinen weiteren Schlüssel aus mehreren Attributen, liegt automatisch die 2NF vor.