Normalisierung: Eine Einführung

Normalisierung: Eine Einführung#

In diesem Tutorium behandeln wir das Thema Normalisierung.

Einführung#

Um Normalisierung zu verstehen, ist es zunächst wichtig, das Prinzip der funktionalen Abhängigkeiten verstanden zu haben.

Funktionale Abhängigkeiten#

Eine funktionale Abhängigkeit ist eine Abhängigkeit, sodass mit einem oder mehreren Attributen die Werte eines oder mehreren anderen Attributen abgeleitet werden können. Insbesondere gelten diese Abhängigkeiten für das allgemeine Datenbankschema und sind somit keine Aussage über die spezifischen Instanzen der Datenbank. Das einfachste Beispiel einer funktionalen Abhängigkeit ist ein Primärschlüssel, da dieser alle anderen Attribute identifiziert. Meist werden wir in Zukunft aber funktionale Abhängigkeiten erst nutzen, um überhaupt unseren Primärschlüssel identifizieren zu können. Alternativ kann eine funktionale Abhängigkeit aber auch aus einer Attributmenge bestehen, sodass z.B. nur aus dem Wettkampfnamen “Berliner Marathon” und dem Datum, an dem dieser stattgefunden hat, der konkrete Wettkampf identifiziert werden kann.

Konkret werden wir diese funktionalen Abhängigkeiten in unseren Relationen identifizieren wollen, um Sie ausnutzen zu können, um z.B. Schlüsselattribute identifizieren zu können, aber auch um unsere Relationen zu zerlegen, da die Abhängigkeiten sonst auch zu Anomalien führen können.

Schreibweise von Funktionalen Abhängigkeiten#

Im Folgenden wiederholen wir kurz die in der Vorlesung eingeführten Notation zu funktionalen Abhängigkeiten.

Wenn A eindeutig B bestimmt und somit eine Funktionalität besteht, so notieren wir dies als A → B. Wenn zusätzlich B → C gilt, so können wir auch die Kurzform A, B → C nutzen, um zu notieren, dass sowohl A als auch B eigenständig alle Cs identifizieren können. Die gleiche Kurzform können wir auch verwenden, um anzugeben, dass ein Attribut mehrere Attribute eindeutig identifiziert, so bedeutet A → C, D z.B. dass A sowohl C als auch D eindeutig bestimmt. Zu guter Letzt müssen wir den Fall abdecken, dass wir nicht nur einzelne Attribute benötigen wie zuvor, sondern eine Menge von Attributen, in diesem Fall schreiben wir die Attribute zusammen in geschweiften Klammern um zu symbolisieren, dass diese Attribute eben nur im Verbund ein oder mehrere Attribute identifizieren. So würde z.B. {A, B} → E angeben, dass A und B im Verbund ebenfalls auch E identifizieren.

Armstrong Axiome und Basis#

Zuvor hatten wir die folgende Relation und die folgenden funktionalen Abhängigkeiten als Beispiele angegeben.

R(A, B, C, D, E)

Funktionale Abhängigkeiten:

  1. A → C

  2. B → C

  3. A, B → C

  4. A → C, D

  5. {A, B} → E

Da es potenziell sehr viele und auch ähnliche funktionale Abhängigkeiten geben kann, können die Armstrong Axiome genutzt werden, um die Aussagen der unterschiedlichen funktionalen Abhängigkeiten auf eine minimale Basis zu reduzieren.

Die Armstrong Axiome (Beispiele unabhängig von den obigen funktionalen Abhängigkeiten):

  • Reflexivität: A → A

  • Akkumulation: A → B => A, C → B, C

  • Transitivität: A → B, B → C => A → C

  • Dekomposition: A → B, C => A → B

  • Vereinigung: A → B, A → C => A → B, C

  • Pseudotransitivität: A → B, BX → C => AX → C

Somit können wir unsere vorherigen Funktionalitäten A → C und B → C zusammenfassen, wie wir es zuvor auch schon generell im Kontext der Notation demonstriert hatten, und A → C, D zu A → D vereinfachen, da wir A → C bereits haben. Somit können wir unsere funktionalen Abhängigkeiten vereinfacht und in reduzierter Form notieren:

  1. A, B → C

  2. A → D

  3. {A, B} → E

Diese minimale Menge an funktionalen Abhängigkeiten wird auch als Basis bezeichnet und kann nicht weiter reduziert werden. Aus einer Basis können aber andere funktionale Abhängigkeiten gewonnen werden.

Hülle#

Während wir zuvor die Menge der funktionalen Abhängigkeiten reduzieren wollten, wollen wir nun aus den funktionalen Abhängigkeiten identifizieren, wie viel ein oder mehrere Attribute bestimmen. Die Menge der Attribute, welche ein Attribut oder eine Menge von Attributen identifiziert, wird auch als Hülle bezeichnet und mit {}+ notiert.

Abgeleitet aus den vorherigen Funktionalitäten ist die Hülle von A also {A}+ = {A, C, D}, da A sich selbst bestimmt und wir aus Funktionalitäten 1 und 2 ablesen können, dass A auch C und D bestimmt. Die Hülle von A und B ist gemeinsam {A,B}+ = {A, B, C, D, E}.

Schlüssel#

Aus dieser überschaubaren Menge an Attributen können wir nun im Folgenden die unterschiedlichen Schritte durchgehen, um einen Primärschlüssel zu wählen.

Zuerst identifizieren wir beliebige Attributmengen einer Relation, welche es erlauben, alle Attribute der Relation zu identifizieren. Alle Attributmengen, welche uns dies erlauben, bezeichnen wir als Superschlüssel. Im einfachsten Fall sind dies alle Attribute der Relation.

Im nächsten Schritt wollen wir nur noch minimale Superschlüssel, wobei sich das Minimal auf die Attributmenge in sich bezieht und nicht minimal über mehrere Superschlüssel hinweg. Die Schlüssel, die dabei übrig bleiben, bezeichnen wir als Schlüsselkandidaten.

Zuletzt, für den Fall, dass es mehrere Schlüsselkandidaten gibt, wählen wir einen dieser Schlüsselkandidaten aus und machen diesen zu unserem Primärschlüssel. Meist wählt man dabei einen Schlüsselkandidaten als Primärschlüssel, welcher in der Menge der Attribute minimal über alle Superschlüssel hinweg ist, da dies sowohl für den Mensch von der Komplexität als auch für den PC rechentechnisch leichter zu handhaben ist.

Normalformen#

Mit dem vorherigen Wissen kommen wir zum Hauptthema dieser Woche, den Normalformen. Wenn es mehr Abhängigkeiten in unserem Datenbankdesign gibt als diejenige des Primärschlüssels, so kann es zu Anomalien kommen, z.B. wenn wir eine große Tabelle haben, in der jedes Buch einen Autor hat, wir das Buch löschen, womit dann aber auch womöglich (alle) Informationen über den Autor verloren gehen (mehr zu Anomalien später). Damit diese Anomalien nicht auftreten, versuchen wir unsere Relation(en) zu normalisieren. Im Folgenden wiederholen wir die Definitionen der vier unterschiedlichen Normalformen, die Sie in der Vorlesung kennengelernt haben, und demonstrieren, wie diese Abhängigkeiten aufzulösen sind, anhand eines Beispiels:

Gegeben sind die folgende Relation und die entsprechenden funktionalen Abhängigkeiten.

R1({ X(A, B) }, C, D, E, F, G, H)

  • A → B

  • E → A

  • D → C, F

  • G → E

  • {D,G} → H

  • H → G

  1. Erste Normalform: Nur atomare Attribute (keine komplexen Attribute).

    R1(D, G, A, C, E, F, H)
    R2(A, B)

  2. Zweite Normalform: Erste Normalform gilt UND bei Nicht-Schlüssel-Attributen existieren keine funktionalen Abhängigkeiten von Teilschlüsseln.

    R1(D, G, H)
    R2(A, B)
    R3(G, A, E)
    R4(D, C, F)

    Relevante funktionale Abhängigkeiten:

    • D → C, F

    • G → E

    • G → A (gilt transitiv über E → A)

    Hinweis: Alle Relationen mit nur einem Schlüsselattribut, die in der Ersten Normalform sind, sind auch in der Zweiten Normalform.

  3. Dritte Normalform: Zweite Normalform gilt UND es existiert kein Nicht-Schlüssel-Attribut das TRANSITIV von einem (Teil-)Schlüssel abhängig ist. Oder in anderen Worten: Es existiert keine funktionale Abhängigkeit zwischen Nicht-Schlüssel-Attributen.

    R1(D, G, H)
    R2(A, B)
    R3(G, E)
    R4(D, C, F)
    R5(E, A)

    Relevante funktionale Abhängigkeiten:

    • E → A

  4. Boyce-Codd-Normalform (BCNF): Dritte Normalform gilt UND es existiert bei Teilschlüsseln keine funtionale Abhängigkeit von Nicht-Schlüsselattributen.

    R1(D, H)
    R2(A, B)
    R3(G, E)
    R4(D, C, F)
    R5(E, A)
    R6(H, G)

    Relevante funktionale Abhängigkeiten:

    • H → G

Contents