Funktionale Abhängigkeiten
Eine Relation wird durch Attribute definiert. Bestimmen einige dieser Attribute eindeutig die Werte anderer Attribute, so spricht man von funktionaler Abhängigkeit. Sei R = {a, . . . , an} ein vereinfachtes Schema, α ⊆ ident(R), β ⊆ ident(R), und D ⊆ dom(R). Dann ist β funktional abhängig von α genau dann, wenn für alle zulässigen D gilt: ∀s, t ∈ D : s.α = t.α =⇒ s.β = t.β Man schreibt:a α → β ⇐⇒ Wenn α bekannt ist, dann auch β ⇐⇒ β ist funktional abhängig von α Für eine Menge von funktionalen Abhängigkeiten einer Relation R schreibt man FD bzw. FD(R)
Volle funktionale Abhängigkeiten
Sei R = {a, . . . , an} ein vereinfachtes Schema und α → β eine funktionale Abhängigkeit. Dann ist β voll funktional abhängig von α, wenn ∀γ ∈ P(α) − α : α − γ 6→ β Man schreibt:a α ·→ β ⇐⇒ α ist minimal
Schlüssel
Sei R = {a1, . . . , an} ein vereinfachtes Schema und α ⊆ ident(R). Dann ist • α ein Superschlüssel, falls α → ident(R), und • α ein Schlüsselkandidat, falls α ·→ ident(R). Ein Primärschlüssel ist ein ausgesuchter bzw. festgelegter Schlüsselkandidat. Ein Attribut a ∈ ident(R) heißt prim, falls a Attribut eines Schlüsselkandidaten von R ist, sonst nicht prim. Es macht Sinn, aus den möglichen Schlüsselkandidaten einer Relation R genau einen Primärschlüssel festzulegen, da Verweise auf Tupel aus R über Fremdschlüssel in anderen Relationen realisiert werden, also Schlüsselattribute dieses Primärschlüssels. Nicht jedes α mit α → ident(R) ist ein Schlüsselkandidat, denn α muss nicht minimal sein. Insbesondere ist α = ident(R) der triviale Superschlüssel
Armstrong Axiome
1. Reflexivität: Eine Menge von Attributen bestimmt eindeutig die Werte einer Teilmenge dieser Attribute (triviale Abhängigkeit): β ⊆ α =⇒ α → β 2. Erweiterungsregel, Verstärkung: Gilt α → β, so gilt auch αγ → βγ für jede Menge von Attributen γ ∈ schema(R): α → β =⇒ αγ → βγ ∀γ ∈ schema(R) 3. Transitivitätsregel: Gilt α → β und β → γ, so gilt auch α → γ: (α → β) ∧ (β → γ) =⇒ α → γ
Attributhülle
Zu einem Schema R und einer Menge von funktionalen Abhängigkeiten FD funktionaler Abhängigkeiten bestimmt die Attributhülle AttrHülle(FD, α) bzw. α + (wenn FD klar) alle Attribute, die bzgl. der FD funktional abhängig von α sind.
Kanonische Überdeckung
Zu einer gegebenen Menge FD von funktionalen Abhängigkeiten nennt man FDc eine kanonische Überdeckung, wenn folgende drei Eigenschaften erfüllt sind: • FDc ≡ FD, d.h. (FDc ) + = FD+ • Alle funktionalen Abhängigkeiten in α → β ∈ FDc sind minimal, d.h. – ∀a ∈ α : FDc −(α → β) ∪ (α − a → β) 6≡ FDc – ∀b ∈ β : FDc −(α → β) ∪ (α → β − b) 6≡ FDc • Jede linke Seite einer funktionalen Abhängigkeit in FDc ist einzigartig
Algorithmus Kanonische Überdeckung
Gegeben sind ein Schema R und eine Menge FD funktionaler Abhängigkeiten. 1. Linksreduktion: Für alle α → β ∈ FD überprüfe, ob ein a ∈ α überflüssig ist, d.h. ob: β ⊆ AttrHülle(FD, α − a) In diesem Fall wird α → β durch α − a → β in FD ersetzt. 2. Rechtsreduktion: Für alle α → β ∈ FD überprüfe, ob ein b ∈ β überflüssig ist, d.h. ob: b ⊆ AttrHülle(FD −{α → β} ∪ {α → β − b}, α) In diesem Fall wird α → β durch α → β − b in FD ersetzt. 3. Entfernung potentiell entstandener α → ∅. 4. Vereinigung potentiell entstandener α → β1 und α → β2 zu α → β1β2 (Vereinigung).
Tipps zur Berechnung der kanonischen Überdeckung
• Linksreduktion: – Hier sind nur die funktionalen Abhängigkeiten zu überprüfen, die links mindestens zwei Attribute besitzen • Rechtsreduktion: – Hier sind alle funktionalen Abhängigkeiten zu prüfen. – Es kann hilfreich sein, alle funktionalen Abhängigkeiten aus FD mit mehr auf einem Attribut auf der rechten Seite aufzuspalten (Dekomposition). Das führt zwar zu einer größeren Menge FD0 , aber die Komplexität der Abfragen wird deutlich reduziert. im letzten Schritt müssen die aufgespaltenen funktionalen Abhängigkeiten ohnehin wieder vereinigt werden.
Anomalie
Anomalien bezeichnen in relationalen Datenbanken Fehlverhalten der Datenbank durch Verletzung der Regel „every information once“. Das bedeutet, dass das zugrunde liegende Datenmodell Tabellen mit Spalten gleicher Bedeutung und darüber hinaus auch noch mit abweichenden (anomalen) Inhalten zulässt, so dass nicht mehr erkennbar ist, welche Tabelle bzw. Spalte den richtigen Inhalt enthält (Dateninkonsistenz) Man unterscheides zwischen: • Update-Anomalien – tritt generell auf, wenn redundante Daten in einem Tupel nur teilweise bzw. falsch aktualisiert werden • Einfüge-Anomalien – generell Daten so verbunden, dass sie nicht ohne andere (nicht NULL) eingegeben werden können • Lösch-Anomalien – entsteht, wenn durch das Löschen eines Datensatzes mehr Informationen als erwünscht verloren gehen
Verlustlosigkeit und Abhängigkeitserhaltung
Gegeben sei eine Relation R mit einer Menge funktionaler Abhängigkeiten. Diese Relation soll in neue Relationen Ri aufgeteilt werden, z.B. um Anomalien zu vermeiden. • Verlustlosigkeit/Verbundtreue: – Die in der ursprünglichen Relation R enthaltenen Informationen müssen aus den neuen Relationen R1, . . . , Rn mittels natürlichen Verbunds (Natural-Join) rekonstruierbar sein. – Eine Zerlegung einer Relation R in zwei Relationen R1 und R2 ist verlustlos, wenn man mindestens eine der beiden aus dem gemeinsamen Bereich (Überlappung der Attribute) wieder ableiten kann. – Es gilt: R1 ∩ R2 → R1 oder R1 ∩ R2 → R2 • Abhängigkeitserhaltung: – Die ursprünglich geltenden funktionalen Abhängigkeiten müssen auch auf der Zerlegung, also den neuen Relationen, gelten
Erste Normalform
Ein Schema in erster Normalform (1NF, auch NF1) besitzt nur atomare bzw. elementare Attribute, d.h. kein Attribut ist zusammengesetzt oder mehrwertig. Funktionale Abhängigkeiten spielen keine Rolle. Algorithmus: Überführung in erste Normalform Um 1NF zu erreichen, müssen Sachverhalte in mehrere Attribute getrennt und Mehrwertigkeiten, typischerweise in eine 1:n-Relation, aufgespalten werden.
Zweite Normalform
Ein Schema R ist in zweiter Normalform (2NF, auch NF2), wenn es in 1NF vorliegt und jedes Attribut entweder • prim ist, oder • voll funktional abhängig von jedem Schlüsselkandidaten ist. Algorithmus: Überführung in zweite Normalform Um 1NF zu erreichen, müssen Sachverhalte in mehrere Attribute getrennt und Mehrwertigkeiten, typischerweise in eine 1:N-Relation, aufgespalten werden. Für den Test, ob 2NF vorliegt, benötigt man alle Schlüsselkandidaten. Wenn jedes Attribut in irgendeinem Schlüsselkandidaten vorkommt, ist 2NF erfüllt, da es nur prim Attribute gibt. 2NF kann nur verletzt sein, wenn ein Schlüsselkandidat zusammengesetzt ist
Dritte Normalform
Ein Schema R ist in dritter Normalform (3NF, auch NF3), wenn es in 2NF vorliegt und jedes nicht-prim Attribut direkt, also nicht transitiv, von einem Schlüsselkandidaten abhängt. Gemeint ist, dass bei einer vorliegenden transitiven Abhängigkeit b von β, also β → a → b wobei β ein Schlüsselkandidat ist, hier a kein Schlüsselkandidat ist. Definition: Dritte Normalform (Alternative) Ein Schema R mit einer Menge funktionaler Abhängigkeiten FD ist in dritter Normalform (3NF, auch NF3), wenn für jede funktionale Abhängigkeit α → β ∈ FD+ mindesten eine der folgenden Bedingungen gilt: • α → β ist trivial, also β ⊆ α , • β enthält nur prim Attribute, • α ist Superschlüssel. Für den Test, ob 3NF vorliegt, benötigt man alle Schlüsselkandidaten. Die zweite Normalform ist eingeschlossen. Algorithmus: Überführung in dritte Normalform Der Synthesealgorithmus überführt R verlustlos und abhängigkeitserhaltend in 3NF
Synthesealgorithmus
1. Bestimme die kanonische Überdeckung FDc zu FD: a) Linksreduktion b) Rechtsreduktion c) Entfernung von funktionalen Abhängigkeiten der Form α → ∅ d) Zusammenfassung gleicher linker Seiten 2. Für jede funktionale Abhängigkeit α → β ∈ FDc : • Kreiere ein Relationenschema Ra := α ∪ β • Ordne Ra die funktionalen Abhängigkeiten FDa = {α 0 → β 0 ∈ FDc | α 0 ∪ β 0 ⊆ Ra} zu. 3. Falls eines der in Schritt 2. erzeugten Schemata einen Schlüsselkandidaten von R bzgl. FDc enthält, sind wir fertig. Sonst wähle einen Schlüsselkandidaten x ∈ R aus und definiere folgendes Schema: Rx = x ∧ FDx = ∅ 4. Eliminiere diejenigen Schemata Ra, die in einem anderen Relationenschema R 0 a enthalten sind, d.h.: Ra ⊆ R 0 a
Boyce Cott NF
Ein Schema R mit einer Menge funktionaler Abhängigkeiten FD ist in Boyce-Codd Normalform (BCNF), wenn für jede funktionale Abhängigkeit α → β ∈ FD+ mindestens eine der folgenden Bedingungen gilt: • α → β ist trivial, also β ⊆ α • α ist Superschlüssel Die dritte Normalform ist eingeschlossen. Man kann jedes Schema R mit funktionalen Abhängigkeiten FD so in Schemata R1, . . . , Rn zerlegen, dass die BCNF erfüllt ist.
Dekompositionsalgorithmus
Der Dekompositionsalgorithmus setzt genau das um und durch die Aufteilung der Relationen können funktionale Abhängigkeiten verloren gehen. Algorithmus: Dekompositionsalgorithmus 1. Starte mit Z = {R} 2. Solange es noch ein Relationenschema Ri in Z gibt, das nicht in BCNF ist, mache folgendes:a a) Finde eine solche funktionale Abhängigkeitb b) Zerlege Ri in Ri1 = α ∪ β und Ri2 = Ri − β c c) Entferne Ri aus Z und füge Ri1 und Ri2 ein: Z = (Z − {Ri}) ∪ {Ri1 } ∪ {Ri2 }
Last changeda year ago