6. Relationale Entwurfstheorie

- konzeptuelle Feinabstimmung des erstellten Schemas auf Basis funktionaler Abhängigkeiten

Funktionale Abhängigkeiten

- Eine funktionale Abhängigkeit stellt eine Bedingung an die möglichen gültigen Ausprägungen des Datenbankschemas dar. Eine FD wird dargestellt als A → B.

- A und B sind Teilmengen des Relationenschemas, es muss für Relation R und die FD A → B gelten: Für alle Paare von Tupeln r, t ∈ R mit r.A = t.A ⇨ r.B = t.B (wenn zwei Tupel gleiche Werte für alle Attribute in A haben, dann müssen auch ihre B-Werte übereinstimmen, B ist funktional abhängig von A, A ist Determinante von B)

- Bsp: Relation R = {A, B, C, D} Abhängigkeiten A → B A → C CD → B

- Algorithmus zum Bestimmen funktionaler Abhängigkeiten (O (n log n)

i. Eingabe: eine Relation R und eine FD A → B ii. Ausgabe: ja, falls A → B in R erfüllt ist, sonst nein iii. Einhaltung (R, A → B)

Sortiere R nach A-Werten falls alle Gruppen bestehend aus Tupeln mit gleichen A-Werten auch

gleiche B-Werte aufweisen: Ausgabe ja, sonst nein Schlüssel

- in der Relation R ist A ⊆ R ein Superschlüssel, falls A → R (A bestimmt alle anderen Attributwerte innerhalb der Relation

- A ∸> B heißt B ist voll funktional abhängig von A, falls A → B und A ist minimal (es kann kein Attribut aus A entfernt werden, ohne die FD zu zerstören)

- wenn A ∸> R, dann ist A ein Kandidatenschlüssel von R

Bestimmung funktionaler Abhängigkeiten - F+ ist die Hülle der Menge der FDs, kann bestimmt werden durch Inferenzregeln

(Armstrong-Axiome) i. Reflexivität: Falls A ⊆ A, dann gilt immer A → B. Außerdem gilt immer

A → A. ii. Verstärkung: Falls A → B, dann gilt auch AC → BC. iii. Transitivität: Falls A → B und B → C, dann gilt auch A → C. iv. Vereinigung: Falls A → B und A → C, dann gilt auch A → BC. v. Dekomposition: Falls A → BC, dann gelten auch A → B und A → C. vi. Pseudotransitivität: Falls A → B und CB → D, dann gilt auch AC → D.

- A+ ist die Hülle der Attribute (Menge der Attribute, die von A gemäß der Menge F

von FDs funktional bestimmt werden), Algorithmus zur Bestimmung von A+: i. Eingabe: eine Menge F von FDs und eine Menge von Attributen A ii. Ausgabe: die vollständige Menge von Attributen A+, für die gilt A → A+

iii. AttrHülle (F,A) Erg: = A; while (Änderungen an Erg) do foreach FD B → C in F do if B ⊆ Erg then Erg := Erg ∪ C; Ausgabe A+ = Erg;

- mittels AttrHülle kann man bestimmen, ob eine Menge an Attributen einen Superschlüssel bildet, nur falls k+ → R, dann ist k ein Superschlüssel

- minimale (kanonische) Überdeckung:

o zwei Mengen F und G von FDs heißen äquivalent, falls F+ = G+ o eindeutige Hülle F+ zu einer gegebenen Menge an FDs vorhanden, diese enthält

sehr viele auch unnötige und redundante Abhängigkeiten o gesucht wird die kleinstmögliche, noch äquivalente Menge Fc von FDs,

Eigenschaften von Fc: i. Fc

+ = F+ ii. A → B löschen, wobei A und/oder B überflüssige Attribute enthalten,

also: ∀a ∈ A : (Fc – (A → B) ∪ ((A – a) → B)) ≢ Fc ∀b ∈ B : (Fc – (A -> B) ∪ (A -> (B -> b))) ≢ Fc

iii. jede linke Seite einer FD in Fc einzigartig (Anwendung der Vereinigung)

o Algorithmus zum Bestimmen der minimalen Überdeckung: i. Linksreduktion ausführen für jede FD A → B: Überprüfe für alle

a ∈ A, ob a überflüssig (B ⊆ AttrHülle (F, A – a) ), wenn ja, dann ersetze A → B durch (A – a) → B

ii. Rechtsreduktion ausführen für jede verbliebene FD A → B: Überprüfe für alle b∈ B, ob B ∈ AttrHülle (F – (A → B) ∪ (A → (B → b)), A), wenn ja, dann ersetze A → B durch A → (B – b)

iii. Entferne FDs A → ∅, die unter ii. vielleicht entstanden sind iv. Vereinigung anwenden auf FDs

Anomalien

- Update: redundante Tupel in der Tabelle (z.B. mehrmals Sokrates in Professor) können beim Update leicht übersehen werden (erhöhter Speicherbedarf und erhöhter Aufwand beim Ändern)

- Einfügen: Informationen zweier Entitytypen in einer Relation vermischen, beim Einfügen eventuell viele NULL-Einträge (z.B neuer Professor ohne Vorlesung)

- Löschen: Situation wie oben, wenn Eintrag zu einer Information nur einmal vorkommt, gehen beim Löschen unabsichtlich anhängende Informationen mit verloren

Dekomposition von Relationen

- Normalisierung bedarf der Aufspaltung eines Relationenschemas - zwei grundlegende Korrektheitskriterien für solche Zerlegungen: Verlustlosigkeit und

Abhängigkeitserhaltung - Verlustlosigkeit:

o die in der Ausgangsrelation R enthaltenen Informationen dürfen nicht verloren gehen und müssen aus den Zerlegungen rekonstruierbar sein

o es muss gelten: ℛ = ℛ1 ∪ ℛ2 (R1 = ∏ℛ1(ℛ) und R2 = ∏ℛ2(ℛ))

o die Zerlegung von ℛ in ℛ1 und ℛ2 ist verlustlos, falls für jede Ausprägung R gilt: R = R1 ⋈ R2

o hinreichende Bedingung: eine der beiden FDs muss herleitbar sein (ℛ1 ∩ ℛ2) → ℛ1 oder (ℛ1 ∩ ℛ2) → ℛ2

o nicht verlustloses Beispiel: Biertrinker nur 1 FD vorhanden: {Kneipe, Gast} → {Bier} beide möglichen FDs: {Gast} → {Bier} {Gast} → {Kneipe} garantieren keine Verlustlosigkeit

o verlustloses Beispiel: Eltern {Kind} → {Mutter} {Kind} → {Vater}

- Abhängigkeitsbewahrung:

o die FDs für die Ausgangsrelation müssen auf die Zerlegungen übertragbar sein (eine hüllentreue Dekomposition sein)

o es wird gefordert: FR ≡ (FR1 ∪ … ∪ FRn) bzw. FR+ = (FR1 ∪ … ∪ FRn)+

o verlustloses aber nicht abhängigkeitserhaltendes Beispiel: die FD {Straße, Ort, BLand} → {PLZ} ist im zerlegten Schema nicht mehr enthalten, damit wird ein Einfügen inkonsistenter Tupel möglich

1. Normalform - Relation ist in 1NF, wenn alle Attribute atomare (nicht weiter zerlegbar sind)

Wertebereiche haben - Bsp: Tabelle Eltern, wenn Eltern mehr als 1 Kind haben, dürfen diese nicht als Eintrag

unter Kinder auftauchen, sondern getrennt als zwei Einträge

2. Normalform - verlangt, dass pro Relation nur Informationen über ein einziges Konzept modelliert

wurden (jedes Nichtschlüsselattribut = nicht-prim soll einen Fakt zu dem Schlüssel ausdrücken)

- Relation ist in 2NF, wenn alle Nichtschlüsselattribute voll funktional abhängig ist von jedem Kandidatenschlüssel = prim

3. Normalform

- ist verletzt, wenn Nichtschlüsselattribute von Nichtschlüsselattributen abhängig sind - Relation ℛ ist in 3NF, wenn für jede FD A → b mit A ⊆ ℛ und b ∈ ℛ

mindestens eine der Bedingungen erfüllt ist: i. b ∈ A, also FD ist trivial ii. Attribut b ist prim, also in einem Kandidatenschlüssel von ℛ enthalten iii. A ist Superschlüssel von ℛ

- Synthesealgorithmus gibt zu einem Relationenschema ℛ mit FDs F verlustlose,

abhängigkeitserhaltende Zerlegungen in 3NF: i. Bestimme die minimale Überdeckung Fc ii. für jede FD A → B ∈ Fc :

(a) mache ein Relationsschma ℛA := A ∪ B (b) FDs FA := {A’ → B’ ∈ Fc | A’ ∪ B’ ⊆ ℛA} werden zugeordnet zu ℛA

iii. wenn ℛA einen Kandidatenschlüssel enthält → fertig! Sonst wähle einen Kandidatenschlüssel k ⊆ ℛ und definiere zusätzliches Schema ℛk := k und Fk := ∅

iv. lösche Relationenschemata ℛA, die in ℛA’ enthalten sind - Bsp:

Boyce-Codd Normalform - Relation ℛ mit FDs F ist in BCNF, falls für jede FD A → B ∈ F mindestens eine

der zwei Bedingungen gilt: i. B ⊆ A (triviale FD) ii. A ist Superschlüssel von ℛ

- es ist immer möglich, Zerlegungen für ein Relationenschema anzugeben, die alle verlustlos und in BCNF sind (aber nicht immer abhängigkeitsbewahrend)

Mehrwertige Abhängigkeiten (MVD)

- sind Verallgemeinerungen funktionaler Abhängigkeiten, jede FD ist auch eine MVD, aber nicht umgekehrt

- ℛ = A ∪ B ∪ C, ist mehrwertig abhängig von A (A↠B), wenn in jeder gültigen Ausprägung von ℛ gilt: Für jedes Paar von Tupeln t1 und t2 mit t1.A = t2.A existieren zwei weitere Tupel t3 und t4 mit folgenden Eigenschaften: t1.A = t2.A = t3.A = t4.A

t3.B = t1.B t3.C = t2.C t4.B = t2.B t4.C = t1.C (bei zwei Tupeln mit gleichem A-Wert kann man die B-Werte vertauschen und die resultierenden Tupel müssen auch in der Relation sein)

- Bsp: es gelten A ↠ B und A ↠ C

- Ableitungsregeln: Reflexivität, Verstärkung, Transitivität, Komplement, Mehrwertige

Verstärkung, Mehrwertige Transitivität, Verallgemeinerung, Koaleszenz, Mehrwertige Vereinigung, Schnittmenge, Differenz

Vierte Normalform

- durch mehrwertige Abhängigkeiten verursachte Redundanz wird ausgeschlossen: Relationen in 4NF enthalten keine zwei voneinander unabhängigen mehrwertigen Fakten

- A↠B ist triviale MVD, gdw gilt: (a) B ⊆ A oder (b) B = ℛ - A - Relation ℛ mit Menge D von funktionalen und mehrwertigen Abhängigkeiten

ist in 4NF, wenn für jede MVD A ↠ B ∈ D+ eine der folgenden Bedingungen gilt:

i. MVD ist trivial ii. A ist ein Superschlüssel von ℛ

- jede Relation in 4NF ist automatisch in BCNF