Bestimmung funktionaler Abhängigkeiten

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}	$\rightarrow$	{PersNr, Name, Rang, Raum,
			Ort, Straße, PLZ, Vorwahl, BLand, EW, Landesregierung}
2.	{Ort, BLand}	$\rightarrow$	{Vorwahl}
3.	{PLZ}	$\rightarrow$	{BLand, Ort}
4.	{Ort, BLand, Straße}	$\rightarrow$	{PLZ}
5.	{BLand}	$\rightarrow$	{Landesregierung}
6.	{Raum}	$\rightarrow$	{PersNr}

Hieraus können weitere Abhängigkeiten abgeleitet werden:

7.	{Raum}	$\rightarrow$	{PersNr, Name, Rang, Raum,
			Ort, Straße, PLZ, Vorwahl, BLand, Landesregierung}
8.	{PLZ}	$\rightarrow$	{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:

• Reflexivität: Aus $\beta$ $\subseteq$ $\alpha$ folgt: $\alpha$ $\rightarrow$ $\beta$
• Verstärkung: Aus $\alpha$ $\rightarrow$ $\beta$ folgt: $\alpha$$\gamma$ $\rightarrow$ $\beta$$\gamma$ für $\gamma$ $\subseteq$ U
• Transitivität: Aus $\alpha$ $\rightarrow$ $\beta$ und $\beta$ $\rightarrow$ $\gamma$ folgt: $\alpha$ $\rightarrow$ $\gamma$

Die Armstrong-Axiome sind sound (korrekt) und complete (vollständig). Korrekt bedeutet, daß nur solche FDs abgeleitet werden, die von jeder Ausprägung erfüllt sind, für die F erfüllt ist. Vollständig bedeutet, daß sich alle Abhängigkeiten ableiten lassen, die durch F logisch impliziert werden.

Weitere Axiome lassen sich ableiten:

• Vereinigung: Aus $\alpha$ $\rightarrow$ $\beta$ und $\alpha$ $\rightarrow$ $\gamma$ folgt: $\alpha$ $\rightarrow$ $\beta$$\gamma$
• Dekomposition: Aus $\alpha$ $\rightarrow$ $\beta$$\gamma$ folgt: $\alpha$ $\rightarrow$ $\beta$ und $\alpha$ $\rightarrow$ $\gamma$
• Pseudotransitivität: Aus $\alpha$ $\rightarrow$ $\beta$ und $\gamma$$\beta$ $\rightarrow$ $\delta$ folgt $\alpha$$\gamma$ $\rightarrow$ $\delta$

Wir wollen zeigen: { PLZ} $\rightarrow$ { Landesregierung} läßt sich aus den FDs 1-6 für das Relationenschema ProfessorenAdr herleiten:

• {PLZ} $\rightarrow$ {BLand} (Dekomposition von FD Nr.3)
• {BLand} $\rightarrow$ {Landesregierung} (FD Nr.6)
• {PLZ} $\rightarrow$ {Landesregierung} (Transitivität)

Oft ist man an der Menge von Attributen $\alpha^{+}_{}$ interessiert, die von $\alpha$ gemäß der Menge F von FDs funktional bestimmt werden:

$$\alpha^{+}_{}$$ : = {$$\beta$$ $$\subseteq$$ U | $$\alpha$$ $$\rightarrow$$ $$\beta$$ $$\in$$ F⁺}

Es gilt der Satz:

$\alpha$ $\rightarrow$ $\beta$ folgt aus Armstrongaxiomen genau dann wenn $\beta$ $\alpha^{+}_{}$.

Die Menge $\alpha^{+}_{}$ kann aus einer Menge F von FDs und einer Menge von Attributen $\alpha$ wie folgt bestimmt werden:

X⁰ : = $$\alpha$$

X^{i + 1} : = Xⁱ $$\cup$$ $$\gamma$$  falls $$\beta$$ $$\rightarrow$$ $$\gamma$$ $$\in$$ F$$\land$$$$\beta$$ $$\subseteq$$ Xⁱ

D. h. von einer Abhängigkeit $\beta$ $\rightarrow$ $\gamma$, 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: X^{i + 1} = Xⁱ.

Beispiel

:

Sei	U	=	{ A, B, C, D, E, G}
Sei	F	=	{ AB $\rightarrow$ C, C $\rightarrow$ A, BC $\rightarrow$ D, ACD $\rightarrow$ B,
			D $\rightarrow$ EG, BE $\rightarrow$ C, CG $\rightarrow$ BD, CE $\rightarrow$ AG}
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:

F $$\equiv$$ G $$\Leftrightarrow$$ F⁺ = G⁺

Zum Testen, ob F⁺ = G⁺, muß für jede Abhängigkeit $\alpha$ $\rightarrow$ $\beta$ F überprüft werden, ob gilt: $\alpha$ $\rightarrow$ $\beta$ G⁺, d. h. $\beta$ $\subseteq$ $\alpha^{+}_{}$. Analog muß für die Abhängigkeiten $\gamma$ $\rightarrow$ $\delta$ 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 $\Leftrightarrow$

1. Jede rechte Seite hat nur ein Attribut.
2. Weglassen einer Abhängigkeit aus F verändert F⁺.
3. Weglassen eines Attributs in der linken Seite verändert F⁺.

Konstruktion der minimalen Abhängigkeitsmenge geschieht durch Aufsplitten der rechten Seiten und durch probeweises Entfernen von Regeln bzw. von Attributen auf der linken Seite.

Beispiel

:

Sei U

=

{ A, B, C, D, E, G}

Sei F	=	{	AB	$\rightarrow$	C,	D $\rightarrow$ EG
			C	$\rightarrow$	A,	BE $\rightarrow$ C,
			BC	$\rightarrow$	D,	CG $\rightarrow$ BD,
			ACD	$\rightarrow$	B,	CE $\rightarrow$ AG }

Aufspalten der rechten Seiten liefert

AB	$\rightarrow$	C
C	$\rightarrow$	A
BC	$\rightarrow$	D
ACD	$\rightarrow$	B
D	$\rightarrow$	E
D	$\rightarrow$	G
BE	$\rightarrow$	C
CG	$\rightarrow$	B
CG	$\rightarrow$	D
CE	$\rightarrow$	A
CE	$\rightarrow$	G

Regel	CE $\rightarrow$ A	ist redundant wegen	C	$\rightarrow$	A
	CG $\rightarrow$ B	ist redundant wegen	CG	$\rightarrow$	D
			C	$\rightarrow$	A
			ACD	$\rightarrow$	B
Regel	ACD $\rightarrow$ B	kann gekürzt werden zu	CD	$\rightarrow$	B, wegen C $\rightarrow$ A