V06 - Normalisierung

Ziele

• Vermeidung von Anomalien
• Reduzierung von Redundanz

Vorgang

• Überführung eines Relationenschemas R in höhere Normalformen durch Aufspaltung in Schemata R1, R2, .. Rn--> Aufspaltung von Relationen in möglichst redundanzfreie Relationen
• Analyse der funktionalen Abhängigkeiten zwischen Attributen

Eigenschaften

• Verlustlosigkeit:
  • Die in den Tupeln der Relation R enthaltenen Informationen müssen aus den entsprechenden Tupeln der neuen Relationen R1, R2, ..., Rn rekonstruierbar sein.
• Abhängigkeitserhaltung:
  • Die für R geltenden Funktionalen Abhängigkeiten müssen auch für die Schemata R1, R2, ..., Rn gelten.

Ursache von Anomalien

• Information, die eigentlich zu verschiedenen Entity-Typen gehört, wurde in einer Relation zusammengefasst.

Arten von Anomalien

• Einfüge-Anomalie
  • Information vom Typ B kann nicht eingefügt werden, ohne zuvor eine Information vom Typ A einzufügen
• Lösch-Anomalie
  • Durch Löschen einer Information vom Typ A kann u.U. auch eine Information vom Typ B endgültig aus der Datenbank entfernt werden
• Änderungs-Anomalie
  • Änderungen an einem Attribut B müssen ggf. in vielen Tupeln durchgeführt werden

Definition

Sei R eine Relation: R (A1, A2, …, An)X ⊂ {A1, A2, …, An}, Y ⊂ {A1, A2, …, An}

• Y ist funktional abhängig von X, wenn es keine zwei Tupel geben darf, in denen für gleiche X-Werte verschiedene Y-Werte auftreten.

Notation

• Y ist funktional abhängig von X
  • X --> Y
  • X bestimmt Y
  • X determiniert Y

Regeln für funktionale Abhängigkeiten: 

s. Armstrong-Axiome

Armstrong-Axiome

• Reflexivität: Aus β ⊆ α    folgt: α→β
• Verstärkung: Aus α→β   folgt: αγ→βγ für γ ⊆ U (Menge aller verfügbaren Attribute)
• Transitivität: Aus α→β und β→γ   folgt: α→γ

Weitere Regeln (abgeleitet aus Armstrong-Axiomen):

• Vereinigung: Aus α→β und α→γ   folgt: α→βγ
• Dekomposition: Aus α→βγ   folgt: α→γ und α→β
• Pseudotransitivität: Aus α→β und γβ→δ   folgt: αγ→δ

Sei X → Y

• Y ist voll funktional abhängig von X, wenn es keine echte Teilmenge Z von X gibt, für die gilt Z → Y.
• Alle Attribute in X werden gebraucht, um Y zu bestimmen.

Beispiele:

• Matrikelnummer, Fach → Note
• Matrikelnummer → Name

= Attribut oder Attributkombination, von der alle Attribute einer Relation funktional abhängig sind

Jede Tabelle hat mindestens einen Superschlüssel!

= minimaler Superschlüssel

• keine Teilmenge des Schlüsselkandidaten ist ebenfalls Superschlüssel

= Attribut, das Teil eines Schlüsselkandidaten ist

• Nicht-Schlüsselattribut: Attribut, das an keinem Schlüsselkandidaten beteiligt ist

• sind definiert auf der Basis von funktionalen Abhängigkeiten
• vermeiden Anomalien
• bauen aufeinander auf--> (die (i+1)-te NF setzt stets die (i)-te NF voraus

Arten von Normalformen:

• Erste Normalform (1NF)
• Zweite Normalform (2NF)
• Dritte Normalform (3NF)
• Boyce-Codd-Normalform (BCNF)
• Vierte Normalform (4NF)
• Fünfte Normalform (5NF)
• Domain-Key-Normalform (DKNF)

= Eine Relation ist in erster Normalform (1NF), wenn sie nur atomare Attributwerte besitzt.

Für eine Relation (Tabelle) in 1NF gilt:

• Jeder Attributwert ist atomar.
• Es gibt keine zwei gleichen Tupel (Zeilen).
• Die Reihenfolge der Tupel ist unerheblich.
• Jeder Attributwert (in einer Spalte) gehört zum Wertebereich des Attributs.
• Jedes Attribut (jede Spalte) hat einen eindeutigen Namen.
• Die Reihenfolge der Attribute ist unerheblich.

Nicht in erster Normalform: NFNF

= Eine Relation ist in zweiter Normalform (2NF), wenn sie in erster Normalform ist und alle Nicht-Schlüsselattribute voll funktional von jedem Schlüsselkandidaten abhängen.

Lösung

Für jede Determinante einer FA, die ein Nicht-Schlüsselattribut bestimmt und Teil eines Schlüsselkandidaten ist, leg eine neue Relation an.

= Eine Relation ist in dritter Normalform (3NF), wenn kein Nicht-Schlüsselattribut transitiv abhängig von einem Schlüsselkandidaten ist.

Transitivität: Aus α→β und β→γ   folgt: α→γ

Transitive Abhängigkeit:

C ist transitiv abhängig von A, wenn es ein B gibt, so dass gilt: A --> B --> C,  aber A <-/- B

(B ist hier kein Schlüsselkandidat!)

Lösung

Für jede Determinante einer FA, die ein Nicht-Schlüsselattribut bestimmt und nicht Teil eines Schlüsselkandidaten ist, leg eine neue Relation an.

C ist transitiv abhängig von A, wenn es ein B gibt, so dass gilt:

= Eine Relation ist in Boyce-Codd-Normalform (BCNF), wenn jede Determinante einer FA ein Superschlüssel ist.

Algorithmus:

• Liste alle funktionalen Abhängigkeiten auf
• Erzeuge für jede FA, deren Determinante kein Superschlüsse ist, eine neue Relation.

Anmerkungen:

• Die BCNF ist eine Verschärfung der 3NF--> Eine Tabelle R, die in BCNF ist, ist immer auch in 3NF.
• Eine Tabelle R, die in 3NF ist, ist immer auch in BCNF, wenn R keine überlappenden Schlüsselkandidaten hat

= Eine Relation R ist in vierter Normalform (4NF), wenn für jede nicht-triviale Mehrwertige Abhängigkeit X -->-> A in R gilt: X ist Superschlüssel von R.

Superschlüssel:

Jede Obermenge eines Schlüsselkandidaten ist ein Superschlüssel.

Drei Kriterien:

• Die Relation muss mindestens drei Attribute haben.
• A bestimmt mehrere Werte von B und A bestimmt mehrere Werte von C.
• B und C sind unabhängig voneinander.

Auflösung der Redundanz:

• Jedes mehrwertig abhängige Attribut in eine eigene Relation extrahieren

= Ein Attribut ist mehrwertig abhängig von einem Attribut A, wenn durch den Wert von A eine Menge von Werten in B bestimmt wird.

• Mehrwertige Abhängigkeiten entstehen durch die Auflösung mehrwertiger Attribute im Rahmen der 1NF.
• Eine Mehrwertige Abhängigkeit A -->-> B in R ist nicht trivial, wenn B nicht in A enthalten ist UNDaußer A und B noch mehr Attribute in R enthalten sind.

Wann ist eine Denormalisierung angebracht?

• Seltene Änderungen
  • Es gibt keine "SELECT"-Anomalie
• Viele Joins
  • Damit sich die Regelverletzung "lohnt", muss eine Leistungsverbesserung durch das Einsparen von Verbundoperationen erreicht werden können.

Empfehlung

Design-Entscheidung sollte gut dokumentiert sein, weil die DB-Anwendungen ggf. mit der resultierenden Redundanz umgehen müssen.