Normalformen und Synthesealgorithmus

Warum Normalformen?

• Redundanzen im DB-Schema erzeugen Anomalien in Datenbanksystemen
  • Änderungsanomalie → Wenn eine Änderung vergessen wird, entsteht eine Inkonsistenz.
  • Einfügeanomalie → Das Einfügen eines partiellen Eintrags ist nicht möglich.
  • Entfernungsanomalie → Das Entfernen des letzten Eintrags löscht ungewollt Informationen.
• Ziele:
  • Vermeidung von Redundanzen und Anomalien.
  • Schrittweise Beseitigung funktionaler Abhängigkeiten (außer vom gesamten Schlüssel).

→ Zerlegen des Schemas in ein äquivalentes Schema ohne Redundanzen und Anomalien ist gleichbedeutend mit der Normalisierung.

---

Funktionale Abhängigkeiten

Seien 𝑋, 𝑌 Attributmengen des Relationenschemas 𝑅, d.h. 𝑋, 𝑌 ⊆ 𝑅. Y ist von X funktional abhängig (oder X bestimmt Y funktional), das heißt 𝑋 → 𝑌 gilt genau dann, wenn für alle möglichen Ausprägungen von R gilt: Zu jedem Wert in X existiert genau ein Wert in Y. Formal ausgedrückt: 𝑋 → 𝑌 ⇔ ∀𝑟1, 𝑟2 ∈ 𝑅: 𝑟1.𝑋 = 𝑟2.𝑋 ⇒ 𝑟1.𝑌 = 𝑟2.𝑌.

Beispiele für funktionale Abhängigkeiten

• Triviale funktionale Abhängigkeit: 𝑋 → 𝑌, falls 𝑌 eine Teilmenge von 𝑋 ist. Beispiel: Passnummer → Passnummer.
• Voll funktionale Abhängigkeit: 𝑋 → 𝑌, falls keine echte Teilmenge 𝑋’ von 𝑋 existiert, sodass 𝑋’ → 𝑌. Beispiel: Passnummer → Name.
• Partiell funktionale Abhängigkeit: Wenn eine Teilmenge 𝑋’ von 𝑋 existiert, sodass 𝑋’ → 𝑌. Beispiel: Passnummer, Land → Name.
• Transitive funktionale Abhängigkeit: Wenn 𝑋 → 𝑌 und 𝑌 → 𝑍, dann gilt auch 𝑋 → 𝑍. Beispiel: Passnummer → Ort, da Passnummer → PLZ und PLZ → Ort.

---

Schlüssel

Eine Teilmenge 𝑆 der Attribute eines Relationenschemas 𝑅 heißt Schlüssel, falls gilt:

1. Eindeutigkeit: Keine mögliche Ausprägung von 𝑅 kann zwei verschiedene Tuple enthalten, die sich in allen Attribute von 𝑆 gleichen.
2. Minimalität: Keine echte Teilmenge von 𝑆 erfüllt bereits Bedingung (1). Ein Attribute heißt primär, falls es Teil eines Schlüsselkandidaten ist.

---

Attributhülle

Eingabe: Eine Menge F von funktionalen Abhängigkeiten und eine Menge X von Attribute. Ausgabe: Die vollständige Menge von Attribute 𝑋+ für die gilt 𝑋 → 𝑋+, also die Menge an Attribute, die man von X mit allen F herleiten kann. Solange es Änderungen an 𝑋+ gibt, geht man jede FD 𝑌 → 𝑍 aus F durch. Wenn die linke Seite eine echte Teilmenge von aktueller 𝑋+ ist, dann ist Z in der neuen 𝑋+.

---

Zerlegung von Relationen

Eine Zerlegung von Relation 𝑅 in 𝑅1, … , 𝑅𝑛 ist:

• Verlustlos, falls gilt: Jede mögliche Ausprägung 𝑟 von 𝑅 lässt sich durch den natürlichen Join der Ausprägungen 𝑟1, … , 𝑟𝑛 konstruieren: 𝑟 = 𝑟1 ⋈ ⋯ ⋈ 𝑟𝑛.
• Abhängigkeitserhaltend, falls gilt: Alle FD ∈ F auf 𝑅 bleiben in den lokalen funktionalen Abhängigkeiten Fi bewahrt: F = F1 ∪ ⋯ ∪ Fn.

---

Normalformen Erklärvideo

1. Normalform (1NF)

Merkhilfe

Alle Attribute sind atomar

Was die 1NF bricht

• Die Verwendung der Zeilenreihenfolge zur Übermittlung von Informationen verstößt gegen die 1.NF.
• Gemischte Datentypen innerhalb von Spalten.
• Eine Tabelle ohne Primärschlüssel.
• Wiederholende Gruppen sind in Spalten nicht erlaubt (z.B. Inventory1, Inventory2,…).

Erklärung:

Alle Attribute enthalten atomare Werte (String, Integer, …) und keine Tuple, Listen, usw. In relationalen Datenbanken sind nicht-atomare Werte nicht erlaubt/möglich, daher sind relationale Datenbanken immer in 1. Normalform.

→ In dieser Vorlesung oft schon erfüllt.

---

2. Normalform (2NF)

Merkhilfe

1.NF +

• jedes Nicht-Schlüssel-Attribut (NSA) ist voll funktional abhängig von jedem Schlüsselkandidaten

$⟹$ ! Transitive Abhängigkeiten zwischen nicht Schlüsselkandidaten sind erlaubt, nur falls eine Abhängigkeit zu einem Schlüsselkandidaten besteht muss eine Abhängigkeit zu allen Schlüsselkandidaten auch bestehen!

(Each non-key attribute must depend on the entire primary key)

Was die 2NF bricht

• Nicht alle Nicht-Primärattribute hängen vollständig von jedem Teil des Schlüssels ab.
• Attribute, die nicht vom Schlüssel abhängen, sollten nicht in der gleichen Tabelle sein.

Erklärung:

Für jedes Attribute A in einer Relation gilt in der 2. Normalform, dass:

• A ein Primärattribut ist (also Teil eines Schlüsselkandidaten) oder
• A voll funktional abhängig von jedem Schlüsselkandidaten ist.

Primärattribut bedeutet, dass das Attribute Teil eines Schlüsselkandidaten ist. Ein Schlüsselkandidat ist eine minimale Menge von Attribute, die eindeutig jede Tuple in einer Relation identifizieren kann.

Voll funktional abhängig bedeutet, dass die Abhängigkeit zwischen einem Attribute und einem Schlüsselkandidaten komplett ist. Das heißt, das Attribute kann nur eindeutig identifiziert oder abgeleitet werden, wenn der gesamte Schlüsselkandidat bekannt ist, nicht nur ein Teil davon.

Die 2NF beseitigt partielle funktionale Abhängigkeiten von Nicht-Primärattributen von einem Teil eines zusammengesetzten Schlüssels, indem sichergestellt wird, dass jedes Nicht-Primärattribut vollständig von jedem Schlüsselkandidaten abhängt. Das führt zu einer Reduzierung von Redundanzen und Anomalien bei der Datenmanipulation.

Ein einfaches Beispiel für die 2. Normalform (2NF) in einer Datenbank könnte eine Tabelle für Studentenleistungen sein:

Student_ID	Vorname	Nachname	Kurs_ID	Kursname	Dozent_ID	Dozent_Name
001	Max	Mustermann	101	Mathematik	201	Dr. Schmidt
002	Maria	Müller	102	Englisch	202	Prof. Wagner
003	Ali	Khan	101	Mathematik	201	Dr. Schmidt

In diesem Beispiel ist die Spalte “Student_ID” ein Primärattribut, da sie Teil des Schlüssels ist und jede Zeile eindeutig identifiziert. Die Spalten “Kurs_ID” und “Dozent_ID” sind ebenfalls Teil des Primärschlüssels.

Um sicherzustellen, dass die Tabelle die 2NF erfüllt, müssen wir prüfen, ob jedes Nicht-Primärattribut voll funktional von jedem Schlüsselkandidaten abhängt.

In diesem Fall hängt der “Kursname” von der “Kurs_ID” ab, und der “Dozent_Name” hängt von der “Dozent_ID” ab. Beide erfüllen die Anforderungen der 2NF, da sie voll funktional von ihren jeweiligen Schlüsselattributen abhängen.

Die 2NF ist wichtig, um Redundanzen zu vermeiden und die Datenintegrität zu gewährleisten, indem partielle funktionale Abhängigkeiten eliminiert werden.

---

3. Normalform (3NF)

Merkhilfe

• Keine transitiven Abhängigkeiten (Kein Nichtschlüssel zu anderem Nichtschlüssel), wobei der eine Nichtschlüssel wiederum von einem Schlüsselkandidaten abhängt.
• ”Vermittler” hängt also von einem Schlüsselkandidaten ab, ist aber selber keiner und hat eine Abhängigkeit zu einem Nicht-Schlüsselkandidaten.
• Reicht, wenn ein Nichtschlüssel-Attribut von irgendeinem Schlüsselkandidaten abhängig ist.
  

Z.B. $R=(\underline{A},B,C,D)$
Die 3.NF ist hier nicht gegeben, da es eine Abhängigkeit $A\to B$ geben kann und dann wiederum eine Abhängigkeit $B\to C$, wobei $B$ also der Vermittler dient Beispiel aus Klausur WS23-24.

• Every non-key attribute in a table should depend on the key, the whole key, and nothing but the key.
• BCNF: Every non-key attribute in a table should depend on the key, the whole key, and nothing but the key.

Was die 3NF bricht

• Transitive Abhängigkeiten von Nicht-Schlüsselattributen.
• Nicht-Schlüsselattribute, die nicht direkt vom Primärschlüssel abhängen, sondern von anderen Nicht-Schlüsselattributen.
• Fehlende Normalisierung von wiederholten Gruppen von Attributen in separate Tabellen.

$$\underset{\text{Erfu¨llt 3.NF}}{\underbrace{\underset{\text{Schlu¨sselkandidaten}}{\underbrace{mnr,fznr}}\to \text{baujahr, km-stand, n-preis, h-preis, ek-preis}}}$$ $$\underset{\text{Erfu¨llt nicht 3.NF, da linke Seite kein Schlu¨sselkandidat bzw. rechts kein prima¨res Attribut}}{\underbrace{hnr\to \text{hersteller}}}$$

Erklärung:

Nicht-triviale funktionale Abhängigkeiten 𝑋 → 𝑌 bedeuten, dass das Attribut-Set 𝑌 nicht vollständig innerhalb des Attribut-Sets 𝑋 enthalten ist und 𝑌 funktional von 𝑋 abhängt. Das heißt, die Kenntnis von 𝑋 ermöglicht es eindeutig, 𝑌 zu bestimmen, ohne dass 𝑌 ein Teil von 𝑋 ist.

In der 3. Normalform (3NF) wird gefordert, dass:

• 2.NF erfüllt ist.
• Für alle nicht-trivialen funktionalen Abhängigkeiten 𝑋 → 𝑌 muss 𝑋 einen Schlüsselkandidaten enthalten (bzw. kein Nicht-Schlüsselattribut hängt von einem anderen Nicht-Schlüsselattribut ab), oder
• 𝑌 muss ein Primärattribut sein.

Die 3NF baut auf der 2. Normalform (2NF) auf und zielt darauf ab, transitive Abhängigkeiten zwischen Nicht-Schlüsselattributen zu beseitigen. Das heißt, es dürfen keine funktionalen Abhängigkeiten zwischen Nicht-Schlüsselattributen bestehen, die über einen Umweg (transitiv) von einem Schlüsselkandidaten abhängen. So wird sichergestellt, dass die Relationen frei von Anomalien sind, die bei Einfüge-, Lösch- oder Änderungsoperationen entstehen können, und dass die Datenintegrität gewahrt bleibt.

Anwendungsbeispiel

### Weiteres Beispiel

Stellen wir uns eine Datenbanktabelle Angestellter vor, die folgende Spalten hat:

• AngestelltenID (Primärschlüssel)
• Name
• AbteilungsID
• Abteilungsname

Funktionale Abhängigkeiten:

• AngestelltenID → Name, AbteilungsID
• AbteilungsID → Abteilungsname

Die Tabelle ist nicht in der 3. Normalform, weil Abteilungsname funktional von AbteilungsID abhängt, welches kein Teil des Primärschlüssels ist (transitive Abhängigkeit).

Um die 3. Normalform zu erreichen, teilen wir die Tabelle in zwei:

1. Angestellter:

   • AngestelltenID
   • Name
   • AbteilungsID

2. Abteilung:

   • AbteilungsID
   • Abteilungsname

Jetzt hängt in jeder Tabelle jedes Nicht-Schlüsselattribut direkt vom Primärschlüssel ab, ohne transitive Abhängigkeiten. Dies entspricht der 3. Normalform.

---

Synthesealgorithmus

Merkhilfe > Schritte des Synthesealgorithmus:

• Linksreduktion
• Rechtsreduktion
• Entfernung von rechtsleeren Abhängigkeiten
• Zusammenfassen von Abhängigkeiten mit gleicher linker Seite
• Neues Relationsschema erzeugen
• Rekonstruktion eines Schlüsselkandidaten
• Elimination überflüssiger Relationen

Aufgabe 10-5 Normalformen und Synthesealgorithmus Synthesealgorithmus

Der Synthesealgorithmus wird verwendet, um ein beliebiges Relationenschema $R$ mit funktionalen Abhängigkeiten $F$ in Relationen $R_1,\dots ,R_n$ zu zerlegen, für die gilt:

• $R_1,\dots ,R_n$ ist eine verlustlose Zerlegung von $R$.
• $R_1,\dots ,R_n$ ist abhängigkeitserhaltend.
• $R_1,\dots ,R_n$ sind alle in der 3. Normalform.

Synthesealgorithmus Schritt 1 – Kanonische Überdeckung $F_c$ zu $F$

a) Linksreduktion:

• Prüfe für jede $X\to Y\in F$:
  • Prüfe für jedes $A\in X$:
    • Wenn $Y\subseteq \text{AttrHu¨lle}(F,X-A)$, ist $A$ in $X$ überflüssig und kann entfernt werden.
    • Aus $X\to Y$ wird dann $(X-A)\to Y$.

b) Rechtsreduktion:

• Prüfe für jede (linksreduzierte) $X\to Y\in F$:
  • Prüfe für jedes $B\in Y$:
    • Wenn $B\subseteq \text{AttrHu¨lle}(F-\{X\to Y\}\cup \{X\to Y-B\},X)$, ist $B$ auf der rechten Seite überflüssig.
    • Aus $X\to Y$ wird dann $X\to (Y-B)$.

c) Entfernen überflüssiger funktionaler Abhängigkeiten:

• Entferne alle funktionalen Abhängigkeiten (FD) mit leerer rechter Seite, also $X\to \{\}$.

d) Zusammenfassen von FDs:

• Fasse alle FDs mit gleicher linker Seite zusammen:
  • Aus $X\to Y_1,\dots ,X\to Y_n$ wird $X\to (Y_1\cup \cdots \cup Y_n)$.

Synthesealgorithmus Schritt 2 – Erzeuge Relationenschemas aus $F_c$

• Für jede FD $X\to Y\in F_c$:
  • Erzeuge das Relationenschema $R_X:=X\cup Y$.
  • Ordne $R_X$ die FDs $F_X:=\{X^{\prime }\to Y^{\prime }\mid X^{\prime }\cup Y^{\prime }\subseteq R_X\}$ zu.
  • Schlüssel sind alle Attribute aus $X$.

Synthesealgorithmus Schritt 3 – Rekonstruiere einen Schlüsselkandidaten

• Falls eines der in Schritt 2 erzeugten Schemata einen Schlüsselkandidaten von $R$ bezüglich $F_c$ enthält, ist nichts zu tun.
• Wenn nicht:
  • Wähle einen Schlüsselkandidaten $S\subseteq R$ aus und definiere folgendes Schema: $R_S:=S$ mit $F_S:=\{\}$.

Synthesealgorithmus Schritt 4 – Eliminiere überflüssige Relationen

• Eliminiere diejenigen Schemata $R_X$, die in einem anderen Relationenschema $R_{X^{\prime }}$ enthalten sind, d.h. $R_X\subseteq R_{X^{\prime }}$.

---

Boyce-Codd-Normalform (BCNF)

Merkhilfe

• Jede Abhängigkeit schaut streng auf Superkeys. Jede linke Seite ist ein Superkey.
• Also, falls $X$ kein Superkey ist und $Y$ ein Superkey ist, ist es KEINE BCNF.

$$\underset{\text{Erfu¨llt BCNF, da linke Seite ein Superkey}}{\underbrace{SK\to A}}$$ $$\underset{\text{Erfu¨llt nicht BCNF, da X kein Superkey}}{\underbrace{X\to Y}}$$

Die Boyce-Codd-Normalform (BCNF) ist eine Verschärfung der 3. Normalform, die zusätzlich verlangt, dass:

• 3.NF erfüllt ist.
• Für alle nicht-trivialen funktionalen Abhängigkeiten $X\to Y$ in einer Relation muss $X$ ein Superkey sein., bzw. $X$ enthält Schlüsselkandidaten.
• Ein Superkey ist eine Attributkombination, die so erweitert ist, dass sie alle Attribute in einer Relation eindeutig identifiziert. Jeder Superkey ist auch ein Schlüsselkandidat, aber nicht jeder Schlüsselkandidat ist ein Superkey.

BCNF zielt darauf ab, verbleibende Anomalien zu beseitigen, die in 3NF noch möglich sind, insbesondere solche, die aus funktionalen Abhängigkeiten resultieren, bei denen die linke Seite kein Schlüsselkandidat ist. Dies stellt sicher, dass keine Abhängigkeiten von Nicht-Superkeys zu anderen Attributen bestehen, wodurch Redundanzen und Anomalien weiter reduziert werden.

Anwendungsbeispiel

### Weiteres Beispiel

Ein Beispiel, das oft zur Illustration von BCNF verwendet wird, betrifft eine Tabelle Vorlesung mit folgenden Attributen:

• Dozent
• Fach
• Raum

Funktionale Abhängigkeiten:

• Dozent, Fach → Raum
• Raum → Dozent

Hier erfüllt die Tabelle die 3NF, da keine transitiven Abhängigkeiten zwischen Nicht-Schlüsselattributen bestehen. Jedoch ist Raum kein Superkey, was zu Redundanz führen kann, da derselbe Dozent in verschiedenen Fächern denselben Raum nutzen könnte.

Um BCNF zu erreichen, könnte die Tabelle wie folgt aufgeteilt werden:

1. DozentFach:

   • Dozent
   • Fach
   • (Primärschlüssel könnte hier eine Kombination aus Dozent und Fach sein)

2. RaumZuweisung:

   • Raum
   • Dozent
   • (Primärschlüssel wäre hier Raum, wenn wir annehmen, dass ein Raum zu einer Zeit nur von einem Dozenten genutzt werden kann)

Durch diese Aufteilung wird sichergestellt, dass in jeder Relation alle nicht-trivialen funktionalen Abhängigkeiten von einem Superkey abhängen, wodurch die BCNF erfüllt wird.

---

×

MyUniNotes is a free, non-profit project to make education accessible for everyone. If it has helped you, consider giving back! Even a small donation makes a difference.

These are my personal notes. While I strive for accuracy, I’m still a student myself. Thanks for being part of this journey!