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 U interessiert uns die Menge F+ aller aus F ableitbaren funktionalen Abhängigkeiten, auch genannt die Hülle (engl. closure) von F.
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:
Xi + 1 = Xi.
Sei | U | = | { A, B, C, D, E, G} |
Sei | F | = | {
AB ![]() ![]() ![]() ![]() |
D ![]() ![]() ![]() ![]() |
|||
Sei | X | = | {B, D} |
X0 | = | BD | |
X1 | = | BDEG | |
X2 | = | BCDEG | |
X3 | = | ABCDEG = X4, Abbruch. | |
Also: | (BD)+ | = | ABCDEG |
Zwei Mengen F und G von funktionalen Abhängigkeiten heißen genau
dann äquivalent (in Zeichen
F G), wenn ihre Hüllen gleich sind:
Zum Testen, ob
F+ = G+, muß für jede Abhängigkeit
F überprüft werden, ob gilt:
G+,
d. h.
. Analog muß für die
Abhängigkeiten
G verfahren werden.
Zu einer gegebenen Menge F von FDs interessiert oft eine kleinstmögliche äquivalente Menge von FDs.
Eine Menge von funktionalen Abhängigkeiten heißt minimal
Sei U | = | { A, B, C, D, E, G} |
Sei F | = | { | AB |
![]() |
C, |
D ![]() |
C |
![]() |
A, |
BE ![]() |
|||
BC |
![]() |
D, |
CG ![]() |
|||
ACD |
![]() |
B, |
CE ![]() |
Aufspalten der rechten Seiten liefert
AB |
![]() |
C |
C |
![]() |
A |
BC |
![]() |
D |
ACD |
![]() |
B |
D |
![]() |
E |
D |
![]() |
G |
BE |
![]() |
C |
CG |
![]() |
B |
CG |
![]() |
D |
CE |
![]() |
A |
CE |
![]() |
G |
Regel |
CE ![]() |
ist redundant wegen | C |
![]() |
A |
CG ![]() |
ist redundant wegen | CG |
![]() |
D | |
C |
![]() |
A | |||
ACD |
![]() |
B | |||
Regel |
ACD ![]() |
kann gekürzt werden zu | CD |
![]() |
B, wegen
C ![]() |