TU Wien:Datenmodellierung VU (Seyr)/Stoffausarbeitung SS06

Nun, ein wiki kann das ganze glaub ich uebersichtlicher darstellen:

14.10.2005

Ich beschraenke mich auf F1, da das wirklich interessante (2b) nur darauf aufbaut.

Angabe: F = {A->BCE, B->ACDE, EF->A}

Kanonische Ueberdeckung

Linksableitungen:

1. AttrH(F, E) = {E}
   1. Da sich von E allein nichts herleiten laesst.
2. AttrH(F, F) = {F}
   1. Da sich von F allein nichts herleiten laesst.

daher es laesst sich nichts streichen.

Rechtsableitungen:

1. fuer B: AttrH( {A->CE, B->ACDE, EF->A}, A) = {A, C, E}
   1. mit A laesst sich C & E herleiten, da A->CE.
2. fuer C: AttrH( {A->BE, B->ACDE, EF->A}, A) = {A, B, E, C, D} --> streichen!
   1. A ist auf jeden fall drinnen (siehe erste Zeile im Algorithmus im Buch)
   2. mit A laesst sich B & E aus A->BE herleiten. F(c) ist bis jetzt {A, B, E}
   3. Nun laesst sich mit dem B (<- ist in {A, B, E} enthalten!) A, C, D und E herleiten, F(c) ist also jetzt {A, B, E, C, D}
   4. Nun sind wir fertig, da sich keine Weiteren Elemente mehr herleiten lassen.
3. fuer E: AttrH( {A->B, B->ACDE, EF->A}, A) = {A, B, C, D, E} --> streichen!
4. fuer A: AttrH( {A->B, B->CDE, EF->A}, B) = {B, C, D, E}
5. fuer C: AttrH( {A->B, B->ADE, EF->A}, B) = {B, A, D, E}
6. fuer D: AttrH( {A->B, B->ACE, EF->A}, B) = {B, A, C, E}
7. fuer E: AttrH( {A->B, B->ACD, EF->A}, B) = {B, A, C, D}

Das die Versuche 1, 5, 6 und 7 nichts bringen kann man schon sehr leicht sehen, wenn man ueberlegt C, D und E sich nirgendwo anders herleiten lassen --> woher sollen sie dann in die Attributhuelle kommen?

Wir sind also jetzt bei:

F(c) = {A->B, B->ACDE, EF->A}

Die letzten beiden punkte der kanonischen ueberdecken bringen keine vorteile

Schluessel

• Da F nirgendwo hergeleitet werden kann, muss es auf jedenfall teil des schluessels sein
  • mit F und A kann man sich A->B herleiten, damit dann B->ACDE, und schlieszlich EF->A
  • mit F und B kann man sich B->ACDE herleiten, damit dann A->B und EF->A.
  • mit F und C kann man sich leider nichts herleiten
  • ditto mit F und D
  • mit F und E kann man sich EF->A herleiten, damit dann A->B und damit dann B->ACDE.

Daher gibt es folgende Schluesselkandidaten:

{AF, BF, EF}

Aufsplitten

• Nun splitten wir die ursprungsrelation mit dem Schema ABCDEF anhand der FDs aus F(c) auf:
  • Fuer jede FD in F(c) brauchst du ein Schema, daher z.B. fuer A->B ein Schema AB.
  • Es gibt dann (zunaechst) 3 Relationen mit folgenden Schemen: AB, BACDE, EFA

• Da EFA bereits den Schluesselkandidaten EF enthaelt brauchen wir keine zusaetzliche Relation dafuer (siehe 3. Punkt auf S. 181!)
  • Waere z.B. EF->A nur E->A: Das enthaelt keinen Schluesselkandidaten, also muessten wir noch eine Relation mit einem beliebigen Schluesselkandidaten als Schema einbauen!

• Nun koennen wir noch AB eliminieren, da das Schema eine teilmenge von BACDE ist. Da es aber ein A->B und ein B->A gibt, gibt es zu jedem A nur ein B, daher wird AB zum schluessel.

• Fertige Schemen:

BACDE und EFA

2b

Nun... Der reihe nach ;-)

Erst mal erklaere ich ganz abstrakt wie das funktioniert:

• Verlustfrei:

Zuerst muesst ihr schauen, welche Teile von R1 und R2 gemeinsam sind. Dann wendet ihr den AttrHuelle Algorithmus an mit den FDs aus F(c) und dem gemeinsamen Teil als zweiten Parameter. Wenn die Attributhuelle zumindest einen der nicht gemeinsamen Teile enthaelt, ist die Zerlegung verlustfrei

• Abhaengigkeitstreue:

Die Zerlegung ist abhaengigkeitstreu, wenn ihr alle FDs zumindest einer der beiden Relationen (oder auch beiden) zuordnen koennt. Ihr koennt dabei A->BC nach A->B und A->C zerteilen, wenn es hilft. Wichtig: Schreibt euch fuer die 3. NF gleich auf, welche Relation welche FDs bekommt

• 3. Normalform:

Hier ist die Aufgabenstellung etwas irrefuehrend. Es geht hier nicht wie bei den beiden oberen punkten um die Zerlegung sondern _nur noch_ um die einzelnen Relationen. Das bedeutet, das in der ursprungsrelation gewonnene erkenntnisse (i.e. Schluesselkandidaten) hier nicht mehr gelten!!

Folgendes muesst ihr nun fuer beide Relationen machen, wenn beide Relationen in 3. NF sind, dann muesst ihr ja ankreuzen, wenn zumindest eine nicht in 3. NF ist, muesst ihr nein ankreuzen:

• Zuerst einmal muesst ihr euch aufschreiben (falls ihr es oben schon nicht gemacht habt) welche FDs die Relation von der Ursprungsrelation bekommen hat
• Jetzt muesst ihr euch fuer die (aufgespaltene) Relation ueberlegen, was da die Schluesselkandidaten sind
• Nun muss fuer jede FD in der Relation eine der drei Punkte aus S. 180 gelten.

Was (zumindest in meinem Jahrgang) viele nicht begriffen haben, ist der 2. Punkt: Ihr muesst die jeweiligen schluessel der aufgespaltenen Relation nehmen, nicht die der ursprungsrelation!

Hauptsaechlich unklar ist hier, ob man AB->CDE oder A->B und B->ACDE als FDs zum zuteilen verwenden soll. 1. und 3. Beispiel funktionieren nur mit ersteren, 2. aber nur mit zweiterem :-(

Erstmal die erste Zeile:

• R1(ABCD) und R2(ABEF).
  • Verlustfrei weil:
    • AB ist in beiden enthalten
    • AttrH(F, AB) = {A, B, C, D, E} was {C, D} enthaelt
  • Abhaengigkeitstreu weil:
    • AB->CDE wird auf AB->CD und AB->E aufgeteilt
      • AB->CD geht nach R1(ABCD)
      • AB->E geht nach R2(ABEF) --> Reihenfolge ist natuerlich egal (da Mengen)!
    • EF->A geht in R2(ABEF)
  • 3.NF weil:
    • R1 enthaelt ja (s.o.) AB->C und AB->D
      • Schluessel ist also AB.
      • Da sowohl bei AB->C als auch AB->D jeweils die linke seite ein Superschluessel ist, haben wir gewonnen.
    • R2 enthaelt AB->E und EF->A
      • Schluessel ist also auf jedenfall mit B und F (da nicht herleitbar) und noch entweder A oder E, also ABF oder ABE.
      • Bei beiden FDs ist die rechte seite teil eines kandidatenschluessels.

---

• R1(AEF) und R2(BCDEF)
  • Verlustfrei weil
    • EF ist gemeinsam
    • AttrH(F, EF) = {E, F, A, B, C, D} was alles enthaelt ;-)
  • nicht Abhaengkeitstreu weil:
    • AB->CDE passt nirgendwohin, da weder R1 noch R2 A und B enthalten
    • EF->A passt in R1 rein
  • 3. NF
    • R1 enthaelt EF->A
      • EF->A: A ist teil eines Kandidatenschluessels

---

• R1(ABCDE), R2(AEF)
  • Verlustfrei weil
    • AE gemeinsam
    • AttrH(F, AE) = {A, E, B, A, C, D, E, F} --> enthaelt sogar beide rest-Schemen (BCD und F)!
  • Abhaengigkeitstreu
    • A->B passt in R1(ABCDE)
    • B->ACDE passt in R1(ABCDE)
    • EF->A geht in R2(AEF)
  • 3. NF: Wieder wuerden die relationen die rechts nur ein Symbol haben auf die selbe regel zu treffen. Aber stimmt das?