23.06.2006 - Kanonische Überdeckung

  • mich würde es auch interessieren.... die Anleitung aus dem Buch check ich nicht so ganz.

    ... So I open my door to my enemies
    And I ask could we wipe the slate clean
    But they tell me to please go fuck myself
    You know you just can't win ...

  • Naja ich würde es auch gerne wissen. Die ganzen SQL, ER,... Sachen sind eh klar wie die gehen, nur viele der "Theorie" Sachen sind echt sooo unverständlich erklärt, dass man (zumindest ich und die die ich kenne) es net checken.

  • So, da sich bei dem Thema anscheinend keine Sau auskennt haben wir versucht eine Deppen-sichere Kanonische-Überdeckungs-Anleitung zu schreiben. Wir (enemy2k, superstar & rookie) sind uns nicht 100% sicher ob dies auch 100% richtig ist. Eine Bestätigung von jemanden der die Buch-Anleitung wirklich verstanden hat, wäre nett. Danke!

  • Auskennen bei dem Thema vielleicht schon. Gibt ein paar ältere Threads wo es erklärt ist.
    Nur vielleicht bei dem Beispiel nicht. :) Schon eine Lösung?


    Habs am Donnerstag vergeblich probiert. Komm nicht drauf.


  • Ich habe eine Frage zu der Lösung dieses Beispiels. In der Angabe kommt ein A vor, die Lösung enthält aber kein A mehr. Ist das so richtig, ich dachte es darf nichts verloren gehen?

  • Hier mal mein Lösungsweg (=der im Buch)
    Was man dazu braucht:
    Hirnschmalz + Buch (wasn scheiss Beispiel dort)


    F = {
    1. BCE→D
    2. E→F
    3. BC→EF
    4. D→CE
    5. AF→A
    }


    Vorüberlegung:
    Bevor wir loslegen. Schauen wir uns die FD's an.
    2. hat links und rechts nur ein Element,
    somit ist das sicherlich (vllt nicht in dieser Form; Schritt4!)
    in der Lösung dabei
    5. kurz Axiome durchblättern, Reflexivität bzw. Verstärkung finden, verwerfen ;)
    Kleiner Tipp: soviel wie möglich mit den Axiomen machen,
    geht einfach schneller


    Schritt1: Linksreduktion
    (alle FD's betrachten, die links mehr als 2 Elemente haben)


    1. D c a) AttrHülle(F, CE) b) AttrHülle(F, BE) c) AttrHülle(F, BC) ?
    a) AH(F, CE) = {CEF}
    b) AH(F, BE) = {BEF}
    c) AH(F, BC) = {BCEFD} ; Alle Elemente erreichbar = E ist überflüssig
    => BC -> D


    3. EF c a) AttrHülle(F, C) a) AttrHülle(F, B)
    a) AH(F, C) = {C}
    b) AH(F, B) = {B}
    => BC→EF ; hat also nix gebracht


    Zwischenergebnis:
    F' = {
    1'. BC→D
    2. E→F
    3. BC→EF
    4. D→CE
    }


    Schritt2: Rechtsreduktion


    3.
    E c AttrHülle(F'-(BC→EF) u (BC→F), BC) ?
    AttrHülle() = {BCDEF} ; Alle Elemente erreichbar = E ist überflüssig
    F c AttrHülle(F'-(BC→EF) u (BC→E), BC) ?
    AttrHülle() = {BCDEF} ; Alle Elemente erreichbar = F ist überflüssig
    => BC -> 0


    4.
    C c AttrHülle(F'-(D→CE) u (D→E), D) ?
    AttrHülle() = {DEF}
    E c AttrHülle(F'-(D→CE) u (D→C), D) ?
    AttrHülle() = {DC}
    => D -> CE ; hat also nix gebracht


    Zwischenergebnis:
    F'' = {
    1'. BC→D
    2. E→F
    3''. BC→0
    4. D→CE
    }


    Schritt 3 : alle FD's der Form "x -> 0" entfernen


    F'' - (BC->0) = F'''


    Schritt 4: Vereinigen ; hier gibts nix zu tun


    Einschub:
    Gäbs jetzt z.B. noch die FD "E -> H",
    könnte man "E -> F" damit vereinigen,
    also insgesamt würde man "E -> FH" erhalten
    (deshalb auch der Hinweis in der Vorüberlegung)


    Lösung = {
    1'. BC -> D
    2. E -> F
    4. D -> CE
    }


    -----------


    Anhang:
    A) Wie kommt das BC in AttrHülle(F, BC) zustande?
    Wir wollen die FD BCE -> D vereinfachen. Dazu lassen wir
    jeweils ein Element der linken Seite weg (in der Formel "alpha-A")
    somit hier zb. BCE - E = BC, also haben wir E weggelassen


    B) Wie berechnet man die AttrHülle(F, BC)?


    1. alpha = BC;
    2. alle FD's durchgehen und
    schauen ob sich links vom ->
    eine Teilmenge von BC befindet (also {B},{C},{BC})
    tatsächlich in F gibts "BC -> EF"
    => alpha = {BCEF}
    (also es kommen die Elemente hinzu,
    die mit der Startmenge BC erreichbar waren)
    3. so wir wiederholen 2. bis wir nicht mehr weiterkommen


    also weiter: es finden sich noch BCE -> D (alpa = {BCEFD})


    Man versucht also einen Pfad druch die FD's zu finden.
    BC -> BCEF -> BCEFD
    hat mal alle Elemente einmal aufgelistet, kann man aufhören.


    ----------


    @shingo
    so erklär ich mir das:


    "AF -> A" ist äquivalent laut Reflexivität "F -> 0";
    In Schritt 3 werden alle F -> 0 entfernt, somit passt das.




    So das wars,
    hoffe ich konnte wem helfen

  • vielen dank, ChVo! :thumb:
    hab's endlich verstanden. :D das beispiel im buch war ja echt ein witz...


    nur ne kleine frage, bei schritt 2 punkt 4:
    die AttrHülle(F'-(D→CE) u (D→E), D) sollte doch {D,E,F} sein, oder hab ich was übersehen?
    (da ja im ersten Durchlauf D->E und im 2. dann E->F dazukommen)
    und die AttrHülle(F'-(D→CE) u (D→C), D) sollte {D,C} sein? (D->C)


    ändert aber nichts daran, dass in dem fall die rechtsreduktion nichts ändert.


    edit: die folien von diesem semester sind übrigens sehr zu empfehlen: http://www.dbai.tuwien.ac.at/e…on/dm/Folien/vo06-2x2.pdf http://www.dbai.tuwien.ac.at/e…/dm/Folien/vo06-2-2x2.pdf

  • Danke, für die Erklärung ChVo, kann die kanonische Überdeckung jetzt auch lösen :).
    Für den synthese Algortihmus hast du nicht zufällig, auch so eine einfache Erklärung :)?