Ü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.

U1

A B
1 1
2 2
3 3
4 4

U2

B C
1 1
2 2
3 3
5 4

U3

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.

Schreibe den ersten Kommentar

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.