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