DBS-Blatt 10

Datenbank Schema für Gebrauchtwagen

Der Autohändler Huber möchte seinen Bestand gebrauchter Wagen in einem relationalen Datenbanksystem organisieren. Die Anforderungsanalyse ergibt eine ganze Liste zu speichernder Informationen für jedes Fahrzeug, die Huber direkt in ein relationales Schema umsetzt. Sofort beginnt er mit der Erfassung seiner Daten und erhält die folgende Relation Auto:

mnr	hnr	hersteller	typ	ps	fznr	baujahr	km-stand	n-preis	h-preis	ek-preis
1	1	Opel	Kadett	60	K674	1990	10000	18000	13000	12000
1	1	Opel	Kadett	60	K634	1988	34000	18000	12000	9000
2	1	Opel	Vectra	90	V459	1990	15000	25000	18000	17000
3	1	Opel	Omega	110	O634	1987	45000	30000	22000	15000
4	2	VW	Golf	90	G789	1991	11000	25000	21000	16000
4	2	VW	Golf	90	G713	1991	31000	25000	16000	13000
5	2	VW	Golf	105	G762	1992	28000	28000	19000	17000
6	2	VW	Käfer	60	K634	1986	71000	19000	10000	8000

Die verschiedenen Modelle werden von Huber fortlaufend nummeriert (mnr). Ein bestimmtes Model ist charakterisiert durch Hersteller, Typ und Motorleistung (ps). Für jedes Model ist ferner die Fahrzeugnummer (fznr) eindeutig. Beide Attribute zusammen werden daher also Primärschlüssel gewählt. Nach kurzer Zeit stellt Huber fest, dass ihm seine neue Datenbank nicht so recht Freude machen will, die Datenmodellierung scheint nicht gut durchdacht.

Aufgabe 10-1 Problem bei nicht normalisierten DB

Aufgabenstellung

Beschreiben Sie die Problem (Redundanzen, Anomalien), die bei Nutzung des o.g. Relationenschemas in der Datenbank des Autohandlers auftreten können.

• Redundanz:
  • Hersteller und hnr geben beide die gleiche Information wieder und sind somit redundant.
  • mnr und typ geben auch die gleichen Daten wieder.
  • ps ist redundant, da es für jede mnr und typ die gleiche Information speichert.
• Einfügeanomalie:
  • Man kann beispielsweise keinen Hersteller hinzufügen, ohne dass diesem ein Typ vom Auto zugewiesen wird (partielle Einfügung nicht möglich).
• Entfernungsanomalie:
  • Man kann keinen Typ vom Auto löschen, ohne auch Informationen über den Hersteller zu verlieren.
• Änderungsanomalie:
  • Änderungen der PS eines Modells müssen in allen Tupeln eingetragen werden, oder bei Änderungen des Namens des Herstellers müssen alle Tuple geändert werden.

---

Aufgabe 10-2 2. Normalform (2NF)

Aufgabenstellung

Die Menge der vollen und nicht-trivialen funktionalen Abhängigkeiten sei im Folgenden gegeben durch:

• mnr → hnr, hersteller, typ, ps
• hnr → hersteller
• mnr, fznr → baujahr, km-stand, n-preis, h-preis, ek-preis

a) Erläutern Sie, warum das gegebene Schema nicht der 2. Normalform (2.NF) genügt. [2. Normalform (2NF)]

2. NF besagt: - Für jedes Attribute A gilt: - A ist primär oder - A ist voll funktional abhängig von jedem Schlüsselkandidaten.

• Schlüsselkandidaten sind $SK=\{mnr,fznr\}$
• Voll funktionale Attribute, die von jedem Schlüsselkandidaten abhängig sind, sind $A=\{baujahr,km-stand,n-preis,h-preis,ek-preis\}$

→ Attribute die keine Schlüsselkandidaten sind, sind also $R=\{hnr,hersteller,typ,ps\}$ Da es also Attribute gibt die nicht prim oder voll funktional abhängig von jedem Schlüsselkandidaten sind und $|R|\ne 0$, ist die 2.NF nicht erfüllt

b) Überführen Sie die Relation in die 2.NF und geben Sie die so entstehenden Relationen an.

1. Relation: Modell - Erstelle eine neue Relation für jeden partiellen Schlüssel mit seinen abhängigen Attribute - mnr → hnr, hersteller, typ, ps - hnr → hersteller $$Modell(\underline{mnr},hnr,hersteller,typ,ps)$$
2. Relation: Fahrzeug - Attribute, die voll funktional vom (ursprünglichen) Schlüssel abhängig sidn, bleiben in der ursprünglichen Relation - mnr, fznr → baujahr, km-stand, n-preis, h-preis, ek-preis $$Fahrzeug(\underline{mnr},\underline{fznr},baujahr,km-stand,n-preis,h-preis,ek-preis)$$

---

Aufgabe 10-3 3. Normalform (3NF)

Aufgabenstellung

Falls das in Aufgabe 10-2 entstandene Relationenschema noch nicht der 3. Normalform (3.NF) genügt, führen Sie dieses in die 3.NF über und geben Sie die so entstehenden Relationen an. Andernfalls begründen Sie, warum das Relationenschema aus Aufgabe 10-2 bereits der 3.NF genügt.

• mnr → hnr, hersteller, typ, ps
• hnr → hersteller
• mnr, fznr → baujahr, km-stand, n-preis, h-preis, ek-preis

3.NF besagt:

• 2.NF ist erfüllt.
• Für alle nicht-trivialen funktionalen Abhängigkeiten 𝑋 → 𝑌 muss 𝑋 einen Schlüsselkandidaten enthalten, oder
• 𝑌 muss ein Primärattribut sein.

Basierend auf der Musterlösung und der Analyse der Relationen aus Aufgabe 10-2 erkennen wir, dass die Relation Fahrzeug bereits der 3. Normalform entspricht. Die Relation Model hingegen erfüllt die 3. Normalform nicht, da die funktionale Abhängigkeit hnr → hersteller eine transitive Abhängigkeit darstellt, die in 3NF nicht zulässig ist. Um das Schema vollständig in die 3. Normalform zu überführen, wird folgende Anpassung vorgenommen:

Korrigierte und ergänzte Relationen für 3NF:

1. Relation Fahrzeug bleibt unverändert, da sie bereits die 3NF Kriterien erfüllt:$$ Fahrzeug(\underline{mnr}, \underline{fznr}, baujahr, km-stand, n-preis, h-preis, ek-preis)

   \underbrace{\underbrace{mnr,fznr}{Schlüsselkandidaten}→ baujahr, km-stand, n-preis, h-preis, ek-preis}{Erfüllt \ 3.NF}

2. Relation Model wird angepasst, um die transitive Abhängigkeit zu entfernen. Dazu wird die Abhängigkeit hnr → hersteller in eine eigene Relation extrahiert:

   $$Modell(\underline{mnr},hnr,typ,ps)$$ $$\underset{\text{Erfu¨llt nicht 3. NF, da linke Seite kein Schlu¨sselkandidat bzw. rechts kein prima¨res Attribut}}{\underbrace{hnr\to hersteller}}$$

3. Neue Relation Hersteller wird eingeführt, um die transitive Abhängigkeit aufzulösen:

   $$Hersteller(\underline{hnr},hersteller)$$

Durch diese Änderung wird sichergestellt, dass:

• Jedes Attribute in Fahrzeug und Model entweder ein Primärattribut ist oder voll funktional von dem Primärschlüssel abhängt, ohne transitive Abhängigkeiten.
• Die neue Relation Hersteller speichert die Zuordnung zwischen hnr und hersteller, wobei hersteller direkt von hnr abhängig ist und somit die 3NF erfüllt.

Zusammenfassend:

Das überarbeitete Schema erfüllt nun die Kriterien der 3. Normalform. Es wurden alle transitiven Abhängigkeiten entfernt, indem die Informationen in separate Relationen aufgeteilt wurden, wodurch die Datenintegrität und die Reduktion von Redundanzen verbessert werden.

$$\text{Fahrzeug}(\underline{\text{mnr}},\underline{\text{fznr}},\text{baujahr},\text{km-stand},\text{n-preis},\text{h-preis},\text{ek-preis})$$ $$\text{Modell}(\underline{\text{mnr}},\text{hnr},\text{typ},\text{ps})$$ $$\text{Hersteller}(\underline{\text{hnr}},\text{hersteller})$$

1. Für die funktionale Abhängigkeit innerhalb der Relation Model: $$\underset{\text{Erfu¨llt 3.NF, da die linke Seite (mnr) ein Schlu¨sselkandidat ist}}{\underbrace{mnr\to hnr,hersteller,typ,ps}}$$

$$>2.F\ddot{u}rdiefunktionaleAbh\ddot{a}ngigkeit,diedurchdie\ast \ast RelationHersteller\ast \ast adressiertwird:>$$

\underbrace{hnr \rightarrow hersteller}_{\text{Erfüllt \ 3.NF, da die linke Seite (hnr) ein Schlüsselkandidat der Relation Hersteller ist}}

$$>3.F\ddot{u}rdiefunktionaleAbh\ddot{a}ngigkeitinnerhalbder\ast \ast RelationFahrzeug\ast \ast :>$$

\underbrace{\underbrace{mnr, fznr}{\text{Schlüsselkandidaten}} \rightarrow baujahr, km-stand, n-preis, h-preis, ek-preis}{\text{Erfüllt \ 3.NF}}

--- # Aufgabe 10-4 [[Normalformen und Synthesealgorithmus#boycecodd-normalform-bcnf|Boyce–Codd Normalform (BCNF)]] >[!note] Aufgabenstellung > >Geben Sie ein beliebiges Beispiel an, bei dem das Einhalten der 3.NF noch nicht zu einem "guten" Datenbankdesign führt, sondern erst die Zerlegung in ein der Boyce-Codd-NF genügendes Schema alle Redundanzen beseitigt. **Beispiel:**

FLS={\underline{Fach},Lehrer,\underline{Schüler}}

*Es gilt:* - Jeder Schüler hat einen Lehrer pro Fach: - 𝑆𝑐ℎü𝑙𝑒𝑟, 𝐹𝑎𝑐ℎ → 𝐿𝑒ℎ𝑟𝑒r - Jeder Lehrer Vertritt nur ein Fach (aber zu jedem Fach kann es mehrere Lehrer geben: - 𝐿𝑒ℎ𝑟𝑒𝑟 → 𝐹𝑎𝑐ℎ - X ist primär aber Y primär → <span style="color:red">Kein BCNF</span> [[Normalformen und Synthesealgorithmus#boyce-codd-normalform-bcnf|(siehe Merkhilfe)]] *Schlüsselkandidaten sind:*

SKs = {{Schüler,Fach},{Schüler, Lehrer}}

*Diese funktionalen Abhängigkeiten führen zu den Schlüsselkandidaten:* - {Schüler, Fach}, weil ein Schüler für jedes Fach genau einen Lehrer hat. Dieses Attributpaar kann jede Tuple in der Relation eindeutig identifizieren. - {Schüler, Lehrer}, weil, obwohl ein Lehrer nur ein Fach unterrichtet, ein Schüler bei verschiedenen Lehrern in unterschiedlichen Fächern sein kann. Daher kann die Kombination aus Schüler und Lehrer auch jede Tuple eindeutig identifizieren. ## Normalformen: ### 2.NF: Jedes Attribute ist prim ### 3NF: ((Schüler,Fach) Enthält SK und Fach ist prim) -> auch 2NF und 1NF ### BCNF: (Lehrer enthält keinen SK) → <span style="color:red">Kein BCNF</span> ## Anomalien: - Einfügen: kein Lehrer mit zugehörigem Fach ohne Schüler - Entfernen: mit letztem Schüler wird Info über Lehrer und Fach gelöscht ## BCNF: Die Relationen in BCNF sind:

LehrerFach(\underline{Lehrer}, Fach)

SchülerLehrer(\underline{Schüler}, \underline{Lehrer})

\rightarrow Nicht abhängigkeitserhaltend

### Was bedeutet "nicht abhängigkeitserhaltend"? Eine Zerlegung einer Relation in eine Normalform ist "nicht abhängigkeitserhaltend", wenn nach der Zerlegung nicht alle ursprünglichen funktionalen Abhängigkeiten direkt in den zerlegten Relationen abgebildet werden können. Das bedeutet, dass manche funktionalen Abhängigkeiten möglicherweise nur durch das Joinen mehrerer Relationen rekonstruiert werden können. Dies kann die Integrität und die Konsistenz der Datenbank beeinträchtigen, da zusätzliche Einschränkungen erforderlich sind, um sicherzustellen, dass die ursprünglichen Abhängigkeiten gewahrt bleiben. --- # Aufgabe 10-5 [[Normalformen und Synthesealgorithmus#synthesealgorithmus|Synthesealgorithmus]] >[!note] Aufgabenstellung > >Gegeben sei das Relationenschema `R(A, B, C, D, E, F)`, sowie die Menge `F` der zugehörigen >nicht-trivialen funktionalen Abhängigkeiten: >`{ C, A → D ; C → F, D ; B → A, E ; E → F, A }` ## a) Begründen Sie, warum `{B, C}` der einzige Schlüsselkandidat ist. ### Gedankengang: Abzudecken sind: $A,B,C,D,E,F$ - $B$ deckt folgende ab: $A,E$ - welche wiederum folgende abdecken: $D,F$ - Es fällt also weg $\not A,\not B, C,\not D,\not E,\not F$ und es bleibt nur noch C übrig was keine Herleitung hat - Dies hat zur Folge, dass C auch ein Schlüsselkandidat werden muss - B und C sind die Minimalsten Attribute die alle anderen abdecken. ### Formelle Schreibweise: $$\mathcal{F} = \{C, A \rightarrow D \;|\; C \rightarrow F, D \;|\; B \rightarrow A, E \;|\; E \rightarrow F, A\}

1. Eindeutigkeit: $$\text{AttrHu¨lle}(F,\{B,C\})=\{B,C,F,D,A,E\}$$
2. Minimalität $$\text{AttrHu¨lle}(F,\{B\})=\{B,A,E,F\}\ne \{A,B,C,D,E,F\}$$ $$\text{AttrHu¨lle}(F,\{C\})=\{C,F,D\}\ne \{A,B,C,D,E,F\}$$ $$\text{Weder B noch C lassen sich herleiten (stehen nur auf linker Seite)}$$

b) Bringen Sie das Relationenschema R mithilfe des Synthesealgorithmus in die 3. Normalform. Führen Sie jeden Schritt (inklusive Teilschritte) des Algorithmus durch, begründen Sie diesen kurz (Attributhüllen bei Links- und Rechtsreduktion, etc.) und kennzeichnen Sie Stellen, an denen nichts zu tun ist, deutlich.

1. Bestimmung der kanonischen Überdeckung 𝐹𝑐 zu 𝐹

$$F=\{C,A\to D|C\to F,D|B\to A,E|E\to F,A\}$$

• $C,A\to D$
• $C\to F,D$
• $B\to A,E$
• $E\to F,A$

a) Linksreduktion

1. $(C,A\to D)\text{ist u¨berflu¨ssig}$

   • wird zu $C\to D$ da gilt:
     • $D\in (F,\{C,A\}-A)=\{C,F,D\}$
     • auch ohne A wird D abgedeckt durch C in 2.

2. $(C\to F,D)\text{ist no¨tig}$

3. $(B\to A,E)\text{ist no¨tig}$

4. $(E\to F,A)\text{ist no¨tig}$

b) Rechtsreduktion

1. $(C\to D)$

   • wird zu $(C\to \varnothing )$ da:

   • $D\in AttrH\ddot{u}lle((F-(C\to D)\cup (C\to \varnothing ),\{C\})=\{C,F,D\}$

   • D wird abgedeckt durch 2.

2. $(C\to F,D)$

3. $(B\to A,E)$

   • wird zu $B\to E$

   • $A\in AttrH\ddot{u}lle((F-(B\to A,E)\cup (B\to E),B)=\{B,E,F,A\}$

   • A wird abgedeckt durch 4.

4. $(E\to F,A)$

c) Entfernung von rechtsleeren Abhängigkeiten

$$F=\{C\to \varnothing |C\to F,D|B\to E|E\to F,A\}$$ $$\text{wird zu}$$ $$F=\{C\to F,D|B\to E|E\to F,A\}$$

d) Zusammenfassen von Abhängigkeiten mit gleicher linker Seite

$$F=\{C\to F,D|B\to E|E\to F,A\}$$ $$Nixzutun$$ $$⟹F_c=\{C\to F,D|B\to E|E\to F,A\}$$

2. Erzeugen eines neues Relationenschemas aus 𝐹𝑐

• $R_1(\underline{C},F,D)\to F_1=\{C\to F,D\}$

• $R_2(\underline{B},E)\to F_2=\{B\to E\}$

• $R_3(\underline{E},F,A)\to F_3=\{E\to F,A\}$

3. Rekonstruktion eines Schlüsselkandidaten:

Neue Relation für Schlüsselkandidaten $\{B,C\}$

$$⟹R_4(\underline{B},\underline{C})\to F_4=\varnothing$$

4. Elimination überflüssiger Relationen

In diesem Schritt nix zu tun

Finale Relationen:

• $R_1(\underline{C},F,D)$

• $R_2(\underline{B},E)$

• $R_3(\underline{E},F,A)$

• $R_4(\underline{B},\underline{C})$

---