Syntheseverfahren: Gruppen mit äquivalenter linker Seite

Benutzeravatar
Mark_G
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 8. Okt 2008 23:07

Syntheseverfahren: Gruppen mit äquivalenter linker Seite

Beitrag 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?

Markus1189
Erstie
Erstie
Beiträge: 22
Registriert: 12. Apr 2011 21:14

Re: Syntheseverfahren: Gruppen mit äquivalenter linker Seite

Beitrag 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 :)

Benutzeravatar
Mark_G
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 8. Okt 2008 23:07

Re: Syntheseverfahren: Gruppen mit äquivalenter linker Seite

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

Markus1189
Erstie
Erstie
Beiträge: 22
Registriert: 12. Apr 2011 21:14

Re: Syntheseverfahren: Gruppen mit äquivalenter linker Seite

Beitrag von Markus1189 »

Das vereinfachte Syntheseverfahren garantiert nicht, dass das Ergebnis in 3.NF ist.
Siehe dazu auch Tutorium 5 Aufgabe T-5.0

Benutzeravatar
Mark_G
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 8. Okt 2008 23:07

Re: Syntheseverfahren: Gruppen mit äquivalenter linker Seite

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

TobiasF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 203
Registriert: 18. Apr 2011 11:57

Re: Syntheseverfahren: Gruppen mit äquivalenter linker Seite

Beitrag 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).

Benutzeravatar
Mark_G
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 8. Okt 2008 23:07

Re: Syntheseverfahren: Gruppen mit äquivalenter linker Seite

Beitrag 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 :)

Antworten

Zurück zu „Archiv“