Wir betrachten folgendes Relationenschema:
ProfessorenAdr : | {[PersNr, Name, Rang, Raum, |
Ort, Straße, PLZ, Vorwahl, BLand, Landesregierung]} |
Hierbei sei Ort der eindeutige Erstwohnsitz des Professors, die Landesregierung sei die eindeutige Partei des Ministerpräsidenten, BLand sei der Name des Bundeslandes, eine Postleitzahl (PLZ) ändere sich nicht innerhalb einer Straße, Städte und Straßen gehen nicht über Bundesgrenzen hinweg.
Folgende Abhängigkeiten gelten:
1. | {PersNr} | ![]() |
{PersNr, Name, Rang, Raum, |
Ort, Straße, PLZ, Vorwahl, BLand, EW, Landesregierung} | |||
2. | {Ort, BLand} | ![]() |
{Vorwahl} |
3. | {PLZ} | ![]() |
{BLand, Ort} |
4. | {Ort, BLand, Straße} | ![]() |
{PLZ} |
5. | {BLand} | ![]() |
{Landesregierung} |
6. | {Raum} | ![]() |
{PersNr} |
Hieraus können weitere Abhängigkeiten abgeleitet werden:
7. | {Raum} | ![]() |
{PersNr, Name, Rang, Raum, |
Ort, Straße, PLZ, Vorwahl, BLand, Landesregierung} | |||
8. | {PLZ} | ![]() |
{Landesregierung} |
Bei einer gegebenen Menge F von funktionalen Abhängigkeiten über der
Attributmenge interessiert uns die Menge
aller aus
ableitbaren
funktionalen Abhängigkeiten, auch genannt die Hülle (engl. closure) von
.
Zur Bestimmung der Hülle reichen folgende Inferenzregeln, genannt Armstrong Axiome, aus:
Weitere Axiome lassen sich ableiten:
Wir wollen zeigen: {PLZ} {Landesregierung} läßt sich aus
den FDs 1-6 für das Relationenschema ProfessorenAdr herleiten:
Es gilt der Satz:
Die Menge kann aus einer Menge F von
FDs und einer Menge von Attributen
wie folgt bestimmt werden:
D. h. von einer Abhängigkeit
, deren linke Seite
schon in der Lösungsmenge enthalten ist, wird die rechte Seite hinzugefügt. Der
Algorithmus wird beendet, wenn keine Veränderung mehr zu erzielen ist, d. h.
wenn gilt:
Sei | U | = | {
![]() |
Sei | F | = | {
![]() |
![]() |
|||
Sei | X | = | {![]() |
![]() |
= | BD | |
![]() |
= | ![]() |
|
![]() |
= | ![]() |
|
![]() |
= | ![]() ![]() |
|
Also: | ![]() |
= | ![]() |
Zwei Mengen F und G von funktionalen Abhängigkeiten heißen genau
dann äquivalent (in Zeichen ), wenn ihre Hüllen gleich sind:
Zum Testen, ob , muß für jede Abhängigkeit
überprüft werden, ob gilt:
,
d. h.
. Analog muß für die
Abhängigkeiten
verfahren werden.
Zu einer gegebenen Menge von FDs interessiert oft eine kleinstmögliche
äquivalente Menge von FDs.
Eine Menge von funktionalen Abhängigkeiten heißt minimal
Sei ![]() |
= | {
![]() |
Sei ![]() |
= | { | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|||
![]() |
![]() |
![]() |
![]() |
|||
![]() |
![]() |
![]() |
![]() |
Aufspalten der rechten Seiten liefert
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Regel |
![]() |
ist redundant wegen | ![]() |
![]() |
![]() |
![]() |
ist redundant wegen | ![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|||
![]() |
![]() |
![]() |
|||
Regel |
![]() |
kann gekürzt werden zu | ![]() |
![]() |
![]() ![]() |