Acronyme done.

im Review wurde nichts beanstandet.

Rechtschreibfehler gecheckt (LOD1+LOD2).

Unbekannte Character ausgebessert.

Sourcecode repariert.

Einleitung

1

Auto

• Unkontrollierte Redundanzen in Relationsschemata können zu Datenanomalien führen
• Lösung:
  • Redundanzen durch Normalisierung beseitigen

• In dieser LU behandelte Normalformen:
  • Erste Normalform (1NF474)
  • Zweite Normalform (2NF475)
  • Dritte Normalform (3NF476)
• Nicht behandelte Normalformen:
  • Boyce-Codd Normalform Cod72
  • Vierte Normalform Fag77
  • Fünfte Normalform Fag79.

2

Auto

Beim Design von Relationsschemata ist es wichtig darauf zu achten, dass die einzelnen Tabellen (vgl. Relationen) keine unkontrollierten Redundanzen enthalten. Diese können nämlich, wie später gezeigt wird, zu Datenanomalien führen.

Unkontrollierte Redundanzen können durch einen Prozess, der Normalisierung genannt wird, beseitigt werden. Die Normalisierung kann durch Transformation der Tabellen in bestimmte Normalformen durchgeführt werden. In dieser LU wird auf die folgenden Normalformen näher eingegangen:

• Erste Normalform (1NF474)
• Zweite Normalform (2NF475)
• Dritte Normalform (3NF476)

Weitere Normalformen die jedoch nicht behandelt werden sind z.B.: Boyce-Codd Normalform Cod72, Vierte Normalform Fag77 und Fünfte Normalform Fag79.

Nachdem das Konzept der Normalisierung über Datenanomalien motiviert wird, müssen noch durch Wiederholung der verschiedenen Schlüsselbegriffe bzw. der Definitionen verschiedener Abhängigkeiten die theoretischen Grundlagen geschaffen werden.

Datenanomalien

1

Schlechtes Design

• Im folgenden Bsp. sind personenbezogene Daten wie Nach-/Vorname, Aufenthaltsort und Geburtsjahr mehrfach (siehe "Newton") enthalten:
  • Verschwendung von Speicherplatz
  • kann zu diversen Datenanomalien führen

Relation Schlechtes Design

Auto

• Updateanomalien:
  • Bei Änderung der personenbezogenen Daten müssen alle Einträge zu einer bestimmten Person berücksichtigt werden.
  • Werden nicht alle berücksichtigt ergeben sich Inkonsistenzen.
  • Performanz:
    • Schlecht, da mehrere Einträge bearbeitet werden müssen
• Einfügeanomalien:
  • Nicht alle nötigen Attribute für einen bestimmten Eintrag sind bekannt -> Attribute müssen auf NULL gesetzt werden müssen.
    • Bsp.: Neuer Kunde, der noch keine Artikel gekauft hat -> Produktnummer und Stückzahl müssen auf NULL gesetzt werden.
  • Grund:
    • Informationen zweier Entitytypen (siehe Entity-Relationship Modell) innerhalb einer Tabelle
• Löschanomalien:
  • Löschen von nur einer der beiden Entityinstanzen nicht möglich (gleicher Grund wie oben) -> beide Instanzen werden gelöscht
  • Bsp. Kunde Keppler gibt seine Teleskope zurück:
    • entsprechende Einträge werden gelöscht
    • personenbezogenen Daten gehen ebenso verloren

2

Auto

Sind Datenbankentabellen nicht normalisiert, so enthalten sie Redundanzen, die beim Manipulieren zu Datenanomalien führen können. Dies soll anhand eines schlechten Designs im folgenden Beispiel gezeigt werden.

Schlechtes Design

Relation Schlechtes Design

Auto

In obiger Tabelle werden vermietete Produkte bestimmten Kunden zugeordnet. Beim Vermieten eines weiteren Produktes muss ein neuer Eintrag eingefügt werden. Handelt es sich dabei um eine Person, die schon als Kunde registriert ist, so erscheinen die personenbezogenen Daten wie Nach-/Vorname, Aufenthaltsort und Geburtsjahr mehrfach (siehe "Newton"). Dies ist nicht nur eine Verschwendung von Speicherplatz, sondern kann auch zu diversen Datenanomalien führen.

Updateanomalien

Sollen personenbezogene Daten in obigem Beispiel geändert werden, so müssen aufgrund der Redundanz alle Einträge zu einer bestimmten Person berücksichtigt werden. Ändert zum Beispiel der Kunde "Newton" seinen Aufenthaltsort, so müssen beide vorhandenen Einträge modifiziert werden. Wird dies vergessen, so ergeben sich Inkonsistenzen.

Außerdem ergibt sich neben dem oben erwähnten Nachteil des hohen Speicheraufwandes noch das Problem längerer Bearbeitungszeiten, da mehrere Einträge bearbeitet werden müssen KE99.

Einfügeanomalien

Einfügeanomalien treten dann auf, wenn nicht alle nötigen Attribute für einen bestimmten Eintrag bekannt sind und so Attribute auf NULL gesetzt werden müssen. Will man z.B. einen neuen Kunden "Einstein" anlegen, der noch keine Artikel gemietet hat, so müssen die Felder Produktnummer und Stückzahl auf NULL gesetzt werden.

Der Grund dafür liegt darin, dass beim Entwurf der Tabelle Informationen zweier Entitytypen (siehe Entity-Relationship Modell) innerhalb einer Tabelle abgelegt wurden KE99.

Löschanomalien

Das Problem der Vermischung verschiedener Entitytypen kommt auch dann zum Tragen, wenn nur die Instanz eines der beiden Typen gelöscht werden soll.

Gibt z.B. der Kunde Keppler seine Teleskope zurück, so werden die entsprechenden Einträge gelöscht und seine personenbezogenen Daten gehen ebenso verloren. Ebenso wie oben wäre hier eine Trennung der Entitytypen in mehrere Tabellen hilfreich.

Schlüssel

1

Relation Schlüsselkandidaten

Auto

• Schlüssel:
  • Attribut oder eine Gruppe von Attributen eines Tupels, die dieses eindeutig von den anderen Tupeln der Relation unterscheidet
  • Schlüsselkandidaten:
    • besteht aus einem oder mehreren Attributen, die einen Eintrag einer Relation eindeutig bestimmen
    • mögliche Schlüsselkandidaten im obigen Bsp.: A2 und A4
  • Superschlüssel:
    • kann im Gegensatz zu einem Schlüsselkandidaten auch aufgeteilt werden und man würde trotzdem noch einen Schlüssel erhalten, der den Tabelleneintrag eindeutig identifiziert
    • Im obigen Beispiel:
      • z.B.: {A2, A3, A4}, da auch noch die Teilmengen {A2, A4} bzw. {A2} gültige Schlüsselkandidaten sind
  • Primärschlüssel:
    • ist ein Schlüsselkandidat
    • abgesehen von inhaltlichen Kriterien wird meist der kleinste Schlüsselkandidat als Primärschlüssel ausgewählt

2

Auto

Zum Verständnis des weiteren Inhalts ist die Kenntnis einiger Schlüssel notwendig. Ein Schlüssel ist ein Attribut oder eine Gruppe von Attributen eines Tupels, die dieses eindeutig von den anderen Tupeln der Relation unterscheidet.

Schlüsselkandidaten

Ein Schlüsselkandidat besteht aus einem oder mehreren Attributen, die einen Eintrag einer Relation eindeutig bestimmen. Dabei ist darauf zu achten, dass alle Attribute, die verwendet werden, auch wirklich notwendig sind. Die folgende Beispiel-Relation zeigt die Bestimmung von Schlüsselkandidaten:

Relation Schlüsselkandidaten

Auto

Die möglichen Schlüsselkandidaten dieser Relation wären A2 und A4, da diese einen Eintrag der Relation eindeutig identifizieren können.

Superschlüssel

Ein Superschlüssel kann im Gegensatz zu einem Schlüsselkandidaten auch aufgeteilt werden und man würde trotzdem noch einen Schlüssel erhalten, der den Tabelleneintrag eindeutig identifiziert. Im obigen Beispiel wäre dies z.B. {A2, A3, A4} , da auch noch die Teilmengen {A2, A4} bzw. {A2} gültige Schlüsselkandidaten darstellen.

Primärschlüssel

Der Primärschlüssel ist ein Schlüsselkandidat. Abgesehen von inhaltlichen Kriterien wird meist der kleinste Schlüsselkandidat als Primärschlüssel ausgewählt.

Abhängigkeiten

1

Funktionale Abhängigkeiten

Relation Funktionale Abhängigkeiten

Auto

• Spalte Produktnummer enthält mehrfach gleiche Einträge
• Eindeutige Auswahl eines Entries nur mit Kundennummer möglich =>
  • Produktnummer ist funktional abhängig von Kundennummer:
  • oder:
    Kundennummer bestimmt (determiniert) Produktnummer
  • Formal:
    Kundennummer -> Produktnummer

Allgemein:
Gilt für eine Relation R A->B, so gilt für zwei beliebige Tupel in R, dass, wenn sie denselben Wert für A haben, sie auch denselben Wert für B haben müssen.

Transitive Abhängigkeiten

Erweiterung der obigen Beispiel-Relation um ein weiteres Attribut:

Relation Transitive Abhängigkeiten

Auto

schon bekannt:
Produktnummer funktional abhängig von der Kundenummer

neu:
Da mehrere Teleskope von der gleichen Bauart sein können ergibt sich auch eine funktionale Abhängigkeit der Bauart von der Produktnummer

transitive Abhängigkeit :
(Kundennummer -> Produktnummer) (Produktnummer -> Bauart) =>(Kundennummer -> Bauart)

2

Auto

Bei den oben beschriebenen Vermischungen verschiedener Entitytypen kommt es zu Abhängigkeiten zwischen den einzelnen Attributen, die zu den erwähnten Anomalien führen. Im Folgenden werden die verschiedenen Ausprägungen der Abhängigkeiten näher erläutert, um in weiterer Folge beim Prozess der Normalisierung gezielt gegen diese vorgehen zu können.

Funktionale Abhängigkeiten

Man betrachte die folgende Tabelle mit den beiden Spalten Kundennummer und Produktnummer :

Relation Funktionale Abhängigkeiten

Auto

Das Attribut Kundennummer fungiert dabei als Primärschlüssel. Die Spalte Produktnummer enthält mehrfach gleiche Einträge. Soll nun ein bestimmter Eintrag anhand der Produktnummer eindeutig ausgewählt werden, so ist dies nur mit Hilfe der Kundennummer möglich. Es ergibt sich also eine Abhängigkeit zwischen den beiden Attributen Kundennummer und Produktnummer. Diese Abhängigkeit wird funktionale Abhängigkeit genannt und wird formal folgendermaßen angeschrieben:

Kundennummer -> Produktnummer

Dies bedeutet:
Produktnummer ist funktional abhängig von Kundennummer.

oder:
Kundennummer bestimmt (determiniert) Produktnummer . Wobei Kundennummer die Determinante von Produktnummer ist.

Allgemein:
Gilt für eine Relation R A->B, so gilt für zwei beliebige Tupel in R, dass, wenn sie denselben Wert für A haben, sie auch denselben Wert für B haben müssen.

Transitive Abhängigkeiten

Erweitert man die obige Beispiel-Relation um ein weiteres Attribut, welches die Bauart des Teleskops speichert, so ergibt sich zum Beispiel folgende Tabelle:

Relation Transitive Abhängigkeiten

Auto

Wie schon oben erwähnt, ist die Produktnummer funktional abhängig von der Kundenummer . Da mehrere Teleskope von der gleichen Bauart sein können ergibt sich auch eine funktionale Abhängigkeit der Bauart von der Produktnummer. Dies lässt sich in der folgenden Darstellung noch besser erkennen:

Relation Transitive Abhängigkeiten - Getrennte Darstellung 1

Relation Transitive Abhängigkeiten - Getrennte Darstellung 2

Auto

Die Sterne symbolisieren nicht relevante Tabelleneinträge.

Da nun Kundennummer Produktnummer determiniert und auch Produktnummer Bauart determiniert, kann man sagen, dass auch Bauart von Kundennummer funktional abhängig ist. Diese Abhängigkeit nennt sich transitive Abhängigkeit :

(Kundennummer -> Produktnummer) (Produktnummer -> Bauart) =>(Kundennummer -> Bauart)

Normalisierung

1

Erste Normalform (1NF)

Relation, die 1NF verletzt

Auto

• Attribut Produktnummer ist mengenwertig
• In der ersten Normalform nicht erlaubt
• mengenwertige Attribute vermeiden durch Auflösen in mehrere Tupel:

Relation in 1NF (Version 1)

Auto

Allgemein:
Eine Relation ist in 1NF474, wenn die Werte der Relation für jedes einzelne Attribut der Relation atomar sind.

Zweite Normalform (2NF)

• 1NF474 muss erfüllt sein und
• alle Nichtschlüsselattribute müssen voll funktional vom Schlüssel abhängig sein

Relation, die 2NF verletzt

Auto

• Primärschlüssel:
  (Kundennummer,Produktnummer)
• vollständige Abhängigkeit:
  • Stückzahl
• partielle Abhängigkeiten:
  • z.B.: Nachname , Vorname (nur von Kundennummer)
• Entfernen der partiellen Abhängigkeiten durch aufteilen in mehrere Tabellen:

Relation Kunde

Auto

Kundennummer->{Nachname, Vorname, Aufenthaltsort, Geburtsjahr}

Relation Verleih

Auto

(Kundennummer, Produktnummer)->Stückzahl

keine partiellen Abhängigkeiten vom Schlüssel mehr vorhanden:

Allgemein:
Ein Relationsschema ist in 2NF475, wenn es in 1NF474 ist und wenn kein Attribut, welches kein Teil des Schlüssels ist, nur teilweise vom Schlüssel abhängig ist.

Dritte Normalform (3NF)

• Erfüllung 1NF474 und 2NF475 und
• alle Nichtschlüsselattribute dürfen nur direkt und nicht transitiv vom Schlüssel abhängen

Relation, die 3NF verletzt

Auto

funktionalen Abhängigkeiten:

• Kundennummer->{Nachname, Vorname, Aufenthaltsort, Geburtsjahr}
• Aufenthaltsort -> Filtertyp

transitive Abhängigkeit enthalten:

Kundennummer -> Aufenthaltsort -> Filtertyp

Lösung:

• Entfernen der transitiven Abhängigkeit durch Auslagern von Filtertyp in neue Relation und
• Kopieren der Attributmenge Aufenthaltsort zum Filtertyp:

Relation Kunde

Relation Filtertyp

Relation Verleih

Auto

Allgemein:
Eine Relation ist in 3NF476, wenn sie in 2NF475 ist und jedes Nicht-Schlüssel Attribut direkt vom primären Schlüssel abhängig ist.

2

Auto

Nachdem die Notwendigkeit der Normalisierung nun durch das mögliche Auftreten von Datenanomalien motiviert wurde, und mit den Definitionen von Schlüsseln und Abhängigkeiten die theoretischen Voraussetzungen geschaffen wurden, ist es nun möglich das Konzept der Normalisierung zu erläutern.

Erste Normalform (1NF)

In der ersten Normalform müssen alle Attribute atomare Wertebereiche haben. Im folgenden Beispiel ist dies z.B. nicht der Fall:

Relation, die 1NF verletzt

Auto

Das Attribut Produktnummer ist mengenwertig. Dies ist in der ersten Normalform nicht erlaubt. Um die obige Relation in eine Form zu bringen, die der ersten Normalform entspricht ist es nötig mengenwertige Attribute zu vermeiden. Dies kann durch Auflösen in mehrere Tupel erreicht werden und würde bei diesem Beispiel in der folgenden schon bekannten Relation resultieren:

Relation in 1NF (Version 1)

Auto

Eine weitere Möglichkeit wäre, die Relation in zwei Tabellen aufzuspalten:

Relation in 1NF (Version 2, Teil 1)

Relation in 1NF (Version 2, Teil 2)

Auto

Allgemein kann gesagt werden:
Eine Relation ist in 1NF474, wenn die Werte der Relation für jedes einzelne Attribut der Relation atomar sind.

Zweite Normalform (2NF)

Um eine Relationsschema in die zweite Normalform zu bringen, so muss es die erste Normalform erfüllen und zusätzlich darf kein Attribut, das nicht zu einem Schlüssel gehört, nur teilweise vom Schlüssel abhängig sein. Bezogen auf die obige Relation bedeutet dies folgendes:

Relation, die 2NF verletzt

Auto

Der Primärschlüssel lautet in dieser Relation (Kundennummer,Produktnummer) . Stückzahl wäre z.B. vollständig von diesem Schlüssel abhängig. Alle anderen Attribute wie Nachname , Vorname , usw. sind hingegen nur teilweise vom Schlüssel abhängig (nur von Kundennummer). Um dieses Relationsschema in die zweite Normalform zu bringen wird das Schema so in mehrere Tabellen aufgeteilt, dass alle partiellen Abhängigkeiten verschwinden:

Relation Kunde

Auto

Kundennummer->{Nachname, Vorname, Aufenthaltsort, Geburtsjahr}

Relation Verleih

Auto

(Kundennummer, Produktnummer)->Stückzahl

In diesem Relationsschema sind alle Nichtschlüsselattribute voll funktional vom Schlüssel abhängig, d.h., es treten keine partiellen Abhängigkeiten vom Schlüssel auf.

Definition:
Ein Relationsschema ist in 2NF475, wenn es in 1NF474 ist und wenn kein Attribut, welches kein Teil des Schlüssels ist, nur teilweise vom Schlüssel abhängig ist.

Allgemein kann gesagt werden, dass ein Relationsschema die 2NF475 verletzt, wenn es mehrere Entitytypen umfasst KE99.

Dritte Normalform (3NF)

Ein Relationsschema in dritter Normalform muss in erster und zweiter Normalform sein und alle Nichtschlüsselattribute dürfen nur direkt und nicht transitiv vom Schlüssel abhängen. Um dies zu erläutern wird die Relation Kunde von zuvor um das Attribut Filtertyp , der für eine gewisse Stadt benötigt wird, erweitert:

Relation, die 3NF verletzt

Auto

Die funktionalen Abhängigkeiten dieser Relation sind die folgenden:

Kundennummer->{Nachname, Vorname, Aufenthaltsort, Geburtsjahr}
Aufenthaltsort -> Filtertyp

Dies bedeutet, dass die Relation auch nach der Erweiterung noch immer in 2NF475 ist. Was auffällt ist, dass hier eine transitive Abhängigkeit enthalten ist. Der Aufenthaltsort ist nämlich funktional von der Kundennummer abhängig und der Filtertyp vom Aufenthaltsort . Dies widerspricht der obigen Vorgabe, dass Relationen in 3NF476 keine Nichtschlüsselattribute enthalten dürfen, die indirekt vom Schlüssel abhängen.

Dieses Problem kann wiederum durch Aufspaltung nach dem folgenden Schema gelöst werden:

1. Entferne alle Attribute C, die die rechte Seite einer indirekten (transitiven) Abhängigkeit A->C darstellen aus der Relation. Alle anderen Attribute müssen erhalten bleiben.
2. Erzeuge für alle entfernten Attribute eine eigene Relation, die alle Attribute der Abhängigkeit B->C enthält.

Führt man dieses Prinzip aus, so ergibt sich folgendes Relationsschema:

Relation Kunde

Relation Filtertyp

Relation Verleih

Auto

Definition:
Eine Relation ist in 3NF476, wenn sie in 2NF475 ist und jedes Nicht-Schlüssel Attribut direkt vom primären Schlüssel abhängig ist.

Zusammenfassung

1

Auto

• 3NF476 zur Vermeidung der häufigsten Anomalien ausreichend
• Weitere Normalformen sind:
  • Boyce-Codd Normalform (BCNF477) Cod72
  • Vierte Normalform (4NF478) Fag77
  • Fünfte Normalform (5NF479) (vgl. Projection-Join Normal Form) Fag79

2

Auto

Zur Vermeidung der häufigsten Anomalien ist die 3NF476 ausreichend. Es gibt jedoch noch weitere Normalformen, auf deren Beschreibung hier jedoch verzichtet wird, z.B.:

• Boyce-Codd Normalform (BCNF477) Cod72
• Vierte Normalform (4NF478) Fag77
• Fünfte Normalform (5NF479) (vgl. Projection-Join Normal Form) Fag79

Neben den Artikeln Cod72, Fag77 und Fag79 sei auch auf KE99 und Bob97, die Zusammenfassungen aller Normalformen präsentieren.

Bibliographie

2

Auto

Cod70

Cod72

Fag77

Fag79

Bob97

KE99

MS04