Seite 1 von 1

Syntheseverfahren: Gruppen mit äquivalenter linker Seite

Verfasst: 5. Sep 2012 00:31
von Mark_G
Was genau versteht man unter "Gruppen mit äquivalenter linker Seite zusammenfassen"?

Durch Reverse Engineering aus den Lösungen verstehe ich darunter, dass man FDs zusammenfasst, bei denen es sozusagen eine Zirkel-Implikation gibt.

Also zum Beispiel bei R = ABC und folgenden FDs nach dem Schritt 3 ("FDs mit identischer linker Seite gruppieren")
A -> B, A -> dummy
B -> C
C -> A
würde man A -> B und C -> A zusammenfassen und damit
A -> B, C -> A
B -> C
bekommen. Bildet man dann die Relationenschemata, so bekommt man
R1 = (ABC, { {A}, {C} } )
R2 = (BC, { {B} } ).
Dann würde man feststellen, dass bei R1, wenn man {A} als Primärschlüssel wählt, eine transitive Abhängigkeit A -> C besteht und daher C aus der Relation entfernen (um die 3. NF zu erreichen). Am Ende hätte man also:
R1 = (AB, { {A} } )
R2 = (BC, { {B} } ).

Ist das richtig?

Re: Syntheseverfahren: Gruppen mit äquivalenter linker Seite

Verfasst: 5. Sep 2012 10:14
von Markus1189
Ich stelle mir das immer als Graph vor (was allerdings bei Umfangreichen FDs nicht mehr ganz so gut klappt, hier reichts aber)

Code: Alles auswählen

A -----> B
^        |
|        |
+-- C <--+
Da wir hier einen Zyklus haben, sind alle (theoretischen, hier gibt es ja nur die 3) anderen Attribute (C,D,E...) von allen 3 erreichbar.
Beispiel mit hinzugefuegten FDs:
A -> B, A -> dummy
B -> C
C -> A
A -> D
A -> E
A -> F
...

Wenn man das wieder als Graph betrachtet:

Code: Alles auswählen

D <-+--A -----> B
E <-+  ^        |
F <-+  |        |
       +-- C <--+
Alle Attribute, die von A aus erreichbar sind sind demnach auch von B (C) erreichbar. Daher wuerde ich sagen alle drei (A,B,C) sind damit aequivalent.

Hoffe das hilft :)

Re: Syntheseverfahren: Gruppen mit äquivalenter linker Seite

Verfasst: 5. Sep 2012 11:44
von Mark_G
Danke für deine Antwort, aber es hilft ehrlich gesagt nicht. Wenn man ALLE als äquivalent sieht, dann würde man alle FDs zusammenfassen und hätte am Ende entsprechend auch nur eine Relation. Und die wäre auch nur in der 2. NF.

Re: Syntheseverfahren: Gruppen mit äquivalenter linker Seite

Verfasst: 5. Sep 2012 12:12
von Markus1189
Das vereinfachte Syntheseverfahren garantiert nicht, dass das Ergebnis in 3.NF ist.
Siehe dazu auch Tutorium 5 Aufgabe T-5.0

Re: Syntheseverfahren: Gruppen mit äquivalenter linker Seite

Verfasst: 5. Sep 2012 12:31
von Mark_G
Ja, aber es sollte ja wohl was Anderes rauskommen als am Anfang, oder?

Bei deinem Beispiel
R = ABCDEF und

A -> B
B -> C
C -> A
A -> D
A -> E
A -> F

wäre wenn ABC äquivalent sind das Ergebnis des vereinfachten Syntheseverfahrens

R1 = (ABCDEF, { {A}, {B}, {C} })

womit die Synthese nichts gebracht hätte... oder?


Also ich hab den Eindruck dass die Tutoriumsaufgaben hier widersprüchlich sind... bei 4.2 werden eben nicht alle FDs des Zirkels zusammengefasst, sondern sozusagen nur zwei benachbarte wie in meinem Beispiel am Anfang (A->B, B->C, C->A; es werden nur A->B und C->A zusammengefasst), bei 5.0 hingegen alle. Nur zwei benachbarte zusammenzufassen scheint allerdings die besten Resultate zu bringen.

Re: Syntheseverfahren: Gruppen mit äquivalenter linker Seite

Verfasst: 5. Sep 2012 13:42
von TobiasF
Ich weiß nicht genau, was du mit benachbart meinst.

Die Definition der Äquivalenz folgt über die transitive Hülle, das ist aber etwas unhandlich.
Deshalb kann man sich das auch klar machen im Sinne von: Wenn ich prüfen will ob X und Y äquivalent sind (hierbei seien X und Y Mengen von Attributen) dann muss ich X -> Y und Y -> X zeigen können. Die Zwischenschritte, die ich benutze, gehören zunächst nicht zur Äquivalenz.

In deinem Beispiel sind A, B und C tatsächlich äquivalent:
A ~ B:
A -> B trivial
B -> A: B -> C, C -> A

B ~ C und A ~ C entsprechend analog.

In diesem Fall hätte das vereinfachte Syntheseverfahren tatsächlich nichts gebracht.
Aufgabe T4.2 enthält keinen echten Zirkel, deshalb werden auch nicht alle Elemente draus aus äquivalent angesehen. Das hatte Markus ja auch schon bemerkt, dass es bei komplexeren FDs nicht mehr so einfach mit einem Zirkel geht).

Re: Syntheseverfahren: Gruppen mit äquivalenter linker Seite

Verfasst: 6. Sep 2012 12:58
von Mark_G
Danke, ich glaube ich hab's mittlerweile verstanden.

Mir war nicht klar, dass es bei Aufgabe T4.2 kein "echter Zirkel" ist... aber ich versuche die Äquivalenz für die anderen Elemente zu beweisen, dann sehe ich was du meinst :)