Übungsblatt 5

Zusatzaufgabe 12 (Azyklische 3NF-Zerlegung)

Gegeben: Ein Relationenschema R = (U,F) mit

U = {A, B, C, D, E}
F = {B->A, C->B, CD->E}

a) Es ist mit dem GYO-Algorithmus zu zeigen, dass die gegebene 3NF-Zerlegung D={AB, BC, CDE} azyklisch ist. Dies ist der Fall, da der resultierende Hypergraph leer ist. (Grafiken bzw. PDFs reiche ich nach)

b) Es ist ein Join-Tree und ein voll reduzierendes Semi-Join-Programm anzugeben.

Join Tree: AB->BC->CDE, wobei U1=AB, U2=BC und U3=CDE

Daraus ergibt sich folgendes Semi-Join-Programm:

r2 = r2 >< r3

r1 = r1 >< r2

–

r2 = r2 >< r1

r3 = r3 >< r2

d) Es ist eine erlaubte Datenbankinstanz d von D anzugeben, die nicht global konsistent

ist, wobei jede Relation aus der Reduktion mindestens 3 Tupel zu enthalten hat.

A	B
1	1
2	2
3	3
4	4

B	C
1	1
2	2
3	3
5	4

C	D	E
1	1	1
2	2	2
3	3	3
6	6	6

Aufgabe 13 (Zyklische 3NF- und BCNF-Zerlegungen)

Gegeben: Relationenschema R = (U,F) mit

U = {A, B, C, G, H, I}
F = {AGH->B, BHI->C, CGI->A}

a) Es ist eine 3NF-Zerlegung mit dem Synthese-Algorithmus zu bestimmen.

F* = F = {AGH->B, BHI->C, CGI->A}

Die Zerlegungen sind ABGH, BCHI, ACGI und AGHI (AGHI wird im letzten Schritt als Oberschlüssel hinzugefügt)

b) Mit dem GYO-Algorithmus ist zu zeigen, dass die erzeugte Zerlegung zylisch ist.

Keine der Regeln des GYO-Algorithmus kann angewendet werden. Der Hypergraph ist also zyklisch.

c) Es ist zu zeigen, dass die Zerlegung ABGH, BCHI und AGHI mit dem BCNF-Dekompositionsalgorithmus erzeugt werden kann.

Statt den Baum zu visualisieren, erkläre ich kurz die Schritte von der Wurzel zu den Blättern.

ABCGHI (Wurzel) nach ABGH (linker Ast) und ACGHI (rechter Ast) mittels AGH->B (angewandte Regel)
ACGHI nach BCHI und AGHI mit BHI->C
Die Blätter entsprechen nun der angegebenen Zerlegung.

d) Es ist mit dem GYO-Algorithmus zu zeigen, dass die erzeugte Zerlegung zyklisch ist.

Der GYO-Algorithmus liefert keinen leeren Hypergraphen. Die gegebene Zerlegung ist also zyklisch.