Gegeben ist immer ein Schema bestehend aus den Attributen der Relation und den Funktionalen Abhängigkeiten (FDs) bzw. Mehrwertigen Abhängigkeiten (MVDs).
Beispiel:
Zunächst müssen wir alle Kandidatenschlüssel bestimmen, das sind alle Mengen von Attributen, die minimal sind und mithilfe denen sich alle anderen Attribute über die FDs erreichen lassen. Am einfachsten ist es, erstmal alle Attribute zu finden, die nirgendwo rechts stehen. Alle diese Attribute müssen auf jeden Fall in jeden Schlüssel. Wir betrachten das Schema von oben: hier tauchen die Attribute B und E nirgendwo rechts auf. Achtung, vergiss hier nicht das Attribut E! Das Attribut E kommt nämlich in keiner FD irgendwo vor und wird somit oft fälschlicherweise übersehen.
Jetzt schauen wir, ob BE tatsächlich ein Schlüssel ist. Durch die zweite FD erreichen wir DA von B aus, über alle anderen FDs danach auch noch das C, womit wir alle Attribute entweder vorher schon hatten oder über die FDs erreichen konnten. Aber pass auf, es muss nicht unbedingt so sein, dass alles, was rechts nirgendwo steht, auch der Schlüssel ist; möglicherweise reicht das nicht aus, um alles andere zu erreichen. In diesem Fall muss man dann schauen, welche Attribute noch hinzugefügt werden müssen, damit man alles erreichen kann. Auch mehrere Kandidatenschlüssel sind möglich. Außerdem wichtig: MVDs werden bei der Schlüsselbestimmung komplett ignoriert; nur die FDs müssen hier betrachtet werden.
Wir wissen jetzt also, dass wir genau einen Kandidatenschlüssel haben, nämlich
Als nächstes bestimmen wir die höchste Normalform, in der sich die Relation befindet. Ein Schema ist in einer bestimmten Normalform, wenn entsprechende Bedingungen vom Schema erfüllt werden.
Wir fangen bei der ersten Normalform (1NF) an:
Das heißt, dass jedes Attribut einen Wert (und keine Liste/Menge von Werten) enthalten muss. Das ist bei uns (wenn nicht explizit anders angegeben) immer erfüllt. Die erste Normalform ist also auch für das obige Schema erfüllt:
Die 1NF ist erfüllt, also überprüfen wir als nächstes die 2NF. Die ist nicht ganz so trivial:
b auf der rechten Seite gilt:
b ist Teil eines Kandidatenschlüssels oderb ist nicht von einer echten Teilmenge eines Kandidatenschlüssels abhängigWir müssen jetzt also jede rechte Seite von jeder FD anschauen. Wenn wir ein Attribut rechts finden, das keine der beiden Bedingungen erfüllt, ist das Schema nicht in 2NF.
Also schauen wir uns mal die erste FD
an. C (das einzige Attribut rechts) ist nicht Teil eines Kandidatenschlüssels (Bedingung 1), es ist aber auch nicht von einer echten Teilmenge eines Kandidatenschlüssels abhängig. AB ist nämlich keine echte Teilmenge unseres einzigen Kandidatenschlüssels BE, somit ist die zweite Bedingung erfüllt und die erste FD verletzt somit nicht die 2NF. Also machen wir weiter und betrachten die zweite FD
Schauen wir uns das erste Attribut rechts (D) an. D ist auch kein Teil eines Kandidatenschlüssels, ist aber abhängig von einer echten Teilmenge unseres Kandidatenschlüssels (B ist echte Teilmenge von BE). Hier ist also auch die zweite Bedingung verletzt, somit haben wir schon eine "böse" FD gefunden; wir können also direkt aufhören und sagen: die 2NF ist nicht erfüllt:
Da eine höhere Normalform alle niedrigeren Normalformen mit einschließt, können wir jetzt komplett aufhören und müssen gar nicht mehr die 3NF, BCNF und 4NF überprüfen. Heißt: wenn ein Schema nicht in 2NF ist, dann kann es auch nicht in 3NF usw. sein. Die höchste Normalform ist also für unser Beispiel die erste Normalform:
Wir schauen uns aber trotzdem noch die anderen Normalformen an. Hier wäre das wie beschrieben nicht nötig, weil wir schon wissen, dass die nicht erfüllt sind, aber sonst käm das ja gar nicht im Tutorial vor ;)
Hier also die Bedingungen für die 3NF:
α->β mindestens eine der folgenden Bedingungen erfüllt:
α->β ist trivial (β⊆α)α ist Superschlüsselβ ist in einem Kandidatenschlüssel enthalten
Offensichtlich ist z.B. die erste FD nicht in 3NF: AB->C ist weder trivial, noch steht links ein Superschlüssel, noch ist das C auf der rechten Seite in einem Kandidatenschlüssel enthalten. Wir können hier also schon aufhören und sagen: 3NF ist nicht erfüllt. In diesem Beispiel ist es sogar so, dass keine der FDs die 3NF erfüllen würde. Also ganz klar (was wir auch schon vorher wussten):
Wenn wir die BCNF überprüfen wollen würden, dann würden wir folgendes checken:
α->β mindestens eine der folgenden Bedingungen erfüllt:
α->β ist trivial (β⊆α)α ist SuperschlüsselMan sieht sofort, dass im Vergleich zur 3NF nur die letzte Bedingung verschwunden ist. Man kann also 3NF und BCNF gleichzeitig prüfen: Wenn ein Schema in 3NF ist, aber man mal die dritte Bedingung "nutzen" muss, weiß man direkt, dass es zwar in 3NF ist, aber nicht in BCNF. Unser Beispiel war ja schon eh nicht in 3NF und deshalb schon lange nicht in BCNF. Sieht man natürlich auch an den Bedingungen der BCNF; keine der FDs erfüllt irgendeine davon.
Für die 4NF betrachten wir erstmals auch zusätzlich die MVDs. Ansonsten sind die Bedingungen quasi die selben wie bei der BCNF:
α->>β mindestens eine der folgenden Bedingungen erfüllt:
α->>β ist trivial (β⊆α oder α∪β = R)α ist SuperschlüsselDa jede FD auch eine MVD ist, kann ein Schema, das nicht in BCNF ist, auch nicht in 4NF sein. In unserem Beispiel stellen wir uns jetzt alle FDs als MVDs vor und sehen schon (wie vorher), dass z.B. die erste MVD AB->>C keine der Bedingungen erfüllt. Es ist sogar so, dass nichtmal eine MVD (also wie vorher keine der FDs und auch nicht die "reine" MVD C->>A) eine der Bedingungen erfüllt. Zu beachten ist, dass für MVDs eine leicht andere Definition von trivial gilt. Wir wussten es zwar schon vorher, aber haben jetzt nochmal gesehen:
Wir wollen nun die Kanonische Überdeckung der gegebenen FDs ermitteln. Die Kanonische Überdeckung ist äquivalent zu den ursprünglichen FDs, ist aber im Gegensatz zu den ursprünglichen FDs in jedem Fall minimal (d.h. es gibt keine "Redundanzen" mehr). Zur Bestimmung der Kanonischen Überdeckung müssen vier Schritte nacheinander durchgeführt werden:
Als erstes schauen wir, welche Attribute wir auf den linken Seiten weglassen können, ohne die Aussage der FDs zu verändern. In unserem Beispiel können wir - wenn überhaupt - nur die erste FD linksreduzieren; bei allen anderen FDs steht links nur ein Attribut. Würden wir da was weglassen stünde links die leere Menge und die Aussage der FD wäre komplett anders als vorher. Und das wollen wir nicht.
Wir betrachten also die erste FD
Erste Frage lautet jetzt also: "Kann ich A weglassen?". Anders formuliert: "Komme ich mit dem Rest trotzdem zur kompletten rechten Seite?". Die Antwort: Ja, weil man kommt auch nur mit dem B zum C, sogar über zwei verschiedene Wege:
B->CB->DA: Mit dem B bekommen wir das A, dann haben wir AB und können wieder die erste FD gehen, um das C zu erreichen.
A weglassen, weil wir auch nur mit dem B zum C kommen. B können wir natürlich nicht auch noch weglassen, dann hätten wir nämlich eine leere linke Seite.
Die FDs sehen nach der Linksreduktion also so aus:
Natürlich kommt nach der Links- auch eine Rechtsreduktion. Die funktioniert im Prinzip gleich. Auch hier fragen wir uns für jedes Attribut rechts, ob wir dieses Attribut weglassen können, ohne die Aussage der FDs zu verändern. Im Gegensatz zur Linksreduktion muss man hier wirklich alle Attribute rechts betrachten; hier ist es durchaus möglich (und erlaubt), dass rechts eine leere Menge entsteht.
Wir betrachten also die erste FD aus der Linksreduktion
und fragen uns: "Kann ich C weglassen?". Also: "Komme ich mit dem B sonst noch irgendwie zum C?". Die Antwort ist: Ja, klar, zum Beispiel über die letzte FD. Also lassen wir das C rechts weg und unsere FDs sehen jetzt so aus:
Nächste Frage: "Kann ich in der zweiten FD das D weglassen?". Natürlich nicht, man sieht nämlich sofort, dass rechts nirgendwo sonst ein D steht. Wie sollen wir dann sonst irgendwie anders da hin kommen? D bleibt also. Was ist mit dem A in der zweiten FD, können wir das wegreduzieren? Die Antwort ist: Ja! Es gibt nämlich noch einen anderen Weg, um vom B zum A zu kommen, nämlich über die dritte FD: mit dem B haben wir ja das D (zweite FD), und mit dem D erreichen wir das A (dritte FD). Aktuell sehen unsere FDs also so aus:
Bei der dritten FD kann nichts rechtsreduziert werden, bei der letzten FD können wir das C weglassen. Die Begründungen seien dem Leser überlassen :). Wir haben nach der Rechtsreduktion also diese FDs:
Der dritte Schritt ist einfach: Wir löschen alle FDs, bei denen die rechte Seite leer ist. Übrig bleiben also:
Im letzten Schritt müssen wir FDs, die die gleiche linke Seite haben, zusammenfassen. Diesen Fall haben wir hier nicht, also sind wir fertig. Zusammenfassen heißt: Wenn wir z.B. die FDs A->BC und A->E hätten, würden wir diese zu A->BCE zusammenfassen.
Wir haben jetzt also die Kanonische Überdeckung unserer Beispiel-FDs bestimmt, nämlich
Mit dem Synthesealgorithmus können wir jedes beliebige Schema verlustlos und abhängigkeitsbewahrend in die 3NF überführen. Da unser Beispiel-Schema nur in der 1NF ist, machen wir das natürlich! Auch hier sind vier Schritte notwendig:
Das haben wir gerade schon erledigt :). Zur Erinnerung, die kanonische Überdeckung für unser Beispiel ist
Da unsere Relation nicht in 3NF ist, müssen wir diese in mehrere kleinere Relationen aufteilen, die dann jeweils in 3NF sein sollen. Zunächst entsteht aus jeder FD der kanonischen Überdeckung eine neue Relation, indem wir alle Attribute einer FD in eine Relation packen. Wir erhalten also zwei Relationen:
Wenn keiner der Kandidatenschlüssel der ursprünglichen Relation in irgend einem der neuen Relationen enthalten ist, müssen wir nochmal eine neue Relation hinzufügen, die die Attribute von irgend einem Kandidatenschlüssel enthält (da sucht man sich dann einfach einen aus; niemals alle Kandidatenschlüssel hinzufügen!). Unser (einziger) Kandidatenschlüssel BE ist weder in R1 noch in R2 enthalten, somit fügen wir ein neues Schema R3 hinzu:
Wenn ein Schema in einem anderen komplett enthalten ist, dann können wir das "kleinere" Schema entfernen. Diesen Fall haben wir hier nicht. Kurz ein Beispiel, wo man ein Schema eliminieren müsste: Wenn wir R1:={ABD} und R2:={AB} hätten, würden wir R2 streichen.
Unser Schema in 3NF besteht also aus den drei Relationen
Wir wollen jetzt noch für jede neue Relation einen Primärschlüssel bestimmen und unterstreichen. Dazu müssen wir erstmal für jede Relation schauen, welche FDs in dieser Relation gelten. Zum Beispiel:
Hier gilt B->D. Dies ist genau die erste FD der kanonischen Überdeckung (bzw. ein Teil der zweiten FD des ursprünglichen Schemas. Die FD B->DA ist nämlich nichts anderes als B->D und B->A. B->A gilt natürlich nicht, aber B->D offensichtlich schon).
Jetzt haben wir eine Relation mit FDs und können ganz normal wie oben die (Kandidaten-)Schlüssel bestimmen. R1 hätte hier den (einzigen) Kandidatenschlüssel B, den wir dann auch als Primärschlüssel wählen und entsprechend unterstreichen. Die Herleitung aller (Kandidaten-)Schlüssel der anderen beiden Relationen sei dem Leser überlassen. Hier das Endergebnis:
Mit dem Dekompositionsalgorithmus kann man ein Schema verlustlos (aber nicht unbedingt abhängigkeitsbewahrend!) in die BCNF überführen. Dazu sucht man sich eine FD, die die BCNF verletzt, und teilt die Relation Ri anhand dieser FD (bezeichnen wir die FD mal als α->β) in zwei neue Relationen folgendermaßen auf:
Für diese neuen Relationen überprüft man wiederum die Normalform und teilt sie wieder auf, sofern sie nicht in BCNF sind.
In unserem Beispiel verletzt z.B. die erste FDAB->C die BCNF (weder trivial noch steht links ein Superschlüssel). Wir wählen diese FD und spalten die Relation folgendermaßen auf:
Die erste Relation erfüllt die BCNF (warum?), sodass wir die nicht weiter aufteilen müssen. In der zweiten Relation ist das aber nicht der Fall: hier verletzt z.B. die FD B->DA die BCNF (Kandidatenschlüssel in R2 ist BE, links steht also kein Superschlüssel und trivial ist die FD auch nicht). Also teilen wir R2 anhand von B->DA folgendermaßen auf:
Jetzt schauen wir wieder ob die Relationen in BCNF sind. In der zweiten Relation gilt keine FD, also kann auch keine FD die BCNF verletzen, also das passt. R21 ist allerdings noch nicht in BCNF. In R21 gelten nämlich die FDs
Kandidatenschlüssel ist also B, somit ist die erste FD okay (links Superschlüssel), die zweite aber nicht (links kein Superschlüssel, und nicht trivial). Also teilen wir R21 wieder auf. Das Ergebnis ist dann
Jetzt sind wir fertig, beide Relationen sind in BCNF. Das Gesamtergebnis (also das komplette Schema in BCNF) ist also:
Der Dekompositionsalgorithmus für 4NF ist im Prinzip genau gleich wie der für BCNF, nur dass man jetzt eben MVDs statt FDs betrachtet (d.h. man denkt sich die FDs als MVDs und nimmt noch die "reinen" MVDs (im Beispiel C->>A) hinzu). Am Ende kommt in unserem Beispiel fast das gleiche Schema wie oben für BCNF raus, mit einem Unterschied: in R1 gilt ja die MVD, die wir jetzt neu betrachten (C->>A), und die ist in der Relation weder trivial noch steht links ein Superschlüssel. Im Gegensatz zu vorher sind wir hier also nicht fertig, sondern müssen R1 nochmal anhand C->>A splitten. Es entstehen die Relationen
In R11 gilt nur die MVD C->>A, somit ist der Kandidatenschlüssel AC. Die linke Seite ist also kein Superschlüssel, aber die MVD ist trivial (schau nochmal die geänderte Definition für "triviale MVDs" im Vergleich zu "triviale FDs" an!). Also ist R11 okay. R12 ist auch okay, da gilt nur B->C, also erfüllt diese FD (bzw. hier im Kontext diese MVD) sogar beide Bedingungen: links steht ein Superschlüssel (sogar der Kandidatenschlüssel selbst), und die MVD ist auch trivial.
Wichtig bei der Suche nach den geltenden MVDs für eine Relation ist auch folgendes: eine MVD lässt sich (im Gegensatz zur FD) nicht anhand der rechten Seite aufteilen. Die MVD A->>BC ist also nicht das selbe wie A->>B und A->>C!
Alle anderen Aufspaltungen sind wie oben bei der Transformation in BCNF, das Endergebnis in 4NF ist also: