Jag har länge sökt i min studentlitteratur och föreläsningsanteckningar för hitta svar på några normalizations- och functional dependency-frågor.

Detta är ingen hemtentamen eller inlämningsuppgift, det är bara något jag vill lära mig hur man ska gå till väga för att lösa. Man kanske har nytta av kunskapen i framtiden, men förstår inte frågorna riktigt.

Frågorna lyder:

Given a Relation R ( A,B,C,D,E,G ), F1 = { AD -> C, EA -> D, D -> E, CD -> G }

a) What is the closure of {D, C, E }
b) Does F1 equivalent to F2 = { AD-> CE, EA -> CD, D -> E, CD -> G }
c) Find one candidate key of relation R. ( denna fråga kan jag nog lösa själv)
d) Which of the above funtion dependencies in F1 are violate the BCNF.

Skulle vara kul om någon har ett tips eller ledtråd för hur man kan lösa detta.

<b>a) What is the closure of {D, C, E }</b>

Höljet (closure) av en mängd fält X vill jag minnas är den mängd fält som kan fås ur X genom de funktionella beroendena F1.

Vi börjar med {D, C, E}.
Eftersom CD -> G kan vi lägga till G.
Sedan kan vi inte lägga till något mer. De två första funktionella beroendena (fb) AD -> C och EA -> D kräver A i vänsterledet, men inget fb ger A, och dessutom ger dessa bara C och D som vi redan har med.
Likaså ger D -> E bara E som vi redan har med.
Alltså får vi {D, C, E, G}.

Tackar så mycket för ditt lösningsförslag :)

<b>b) Does F1 equivalent to F2 = { AD-> CE, EA -> CD, D -> E, CD -> G }</b>

Kan vi få F2 ur F1 och F1 ur F2?

F2 ur F1:
Eftersom AD -> C och D -> E (och därmed AD -> E) gäller AD -> CE (första fb i F2).
Eftersom EA -> D och trivialt EA -> A, gäller EA -> AD. Tillsammans med AD -> CE ger detta EA -> CE, och därmed EA -> C. Nu har vi både EA -> D och EA -> C, varför EA -> CD (andra fb i F2) gäller.
D -> E och CD -> G finns redan i F1.

F1 ur F2 är trivialt.

Alltså är F1 och F2 ekvivalenta.


Vi kan sätta upp några regler för funktionella beroenden:
0) Trivialt beroende: a -> a.
1) Om a -> b och a -> c, så gäller a -> bc.
2) Om a -> bc, så gäller både a -> b och a -> c.
3) Om a -> b och b -> c, så gäller a -> c.
(ytterligare regler?)
Här är a, b, c mängder av fält (t.ex. a = AD).

Exempel (2:a delen av F2 ur F1):
Tag först a = EA. Enligt (0) gäller a -> a, dvs EA -> EA.
Enligt (2), med a = EA, b = E och c = A, gäller sedan a -> c, dvs EA -> A.
Utnyttja nu (1) med a = EA, b = A och c = D för att utifrån a -> b (dvs EA -> A) och a -> c (dvs EA -> D) dra slutsatsen att a -> bc (dvs EA -> AD).
Sedan använder vi (3) med a = EA, b = AD och c = CE och får ur a -> b (dvs EA -> AD) och b -> c (dvs AD -> CE) att a -> c (dvs EA -> CE).
Ur EA -> CE får vi sedan EA -> C genom att sätta a = EA, b = C och c = E i (2).
Slutligen sätter vi a = EA, b = C och c = D i (1) för att ur EA -> C och EA -> D erhålla EA -> CD.

Hoppas att du hängde med.

(dubbelpost)

Mycket kul att du tagit dig tid att bjuda på din kunskap! Jag håller på lära mig de regler som gäller för funktionella beroendena och när de sitter ska jag förhoppningsvis kunna lista ut lösningarna också!

Jag undrar dock en sak angående "Closure of set {A,B,C} ", vad är syftet med det? Är det något som har att göra med att man ska kolla efter lämplig nyckel till relationen R{A,B,C,D,E,F} eller om settet {A,B,C} uppfyller ett speciellt krav?

Höljet av en nyckel skall vara mängden av alla fält. Jag tror att man använder höljet när man söker kandidatnycklar.

<b>c) Find one candidate key of relation R. ( denna fråga kan jag nog lösa själv)</b>

Ur AD kan vi få samtliga fält:
AD -> C
D -> E
AD -> CD -> G

Därför är AD en kandidatnyckel.

<b>d) Which of the above funtion dependencies in F1 are violate the BCNF.</b>

"A relation R is said to be in BCNF if whenever X -> A holds in R, and A is not in X, then X is a candidate key for R."
(http://www.cs.jcu.edu.au/Subjects/cp1500/1998/Lecture_Notes/normalisation/bcnf.html)

AD -> C: Vänsterledet är en kandidatnyckel, så detta fb bryter ej mot BCNF.
EA -> D: Eftersom EA -> AD och AD är en kand.nyckel, är även EA en kand.nyckel, så inte heller detta fb bryter mot BCNF.
D -> E: Enbart D är ingen kandidatnyckel. Detta fb bryter därför mot BCNF.
CD -> G: Eftersom A inte finns i något fb:s högerled, måste A ingå i varje kand.nyckel. Därför är CD ingen kand.nyckel och detta fb bryter sålunda mot BCNF.

Angående kandidatnyckel till R: Okej. Så man behöver inte komma åt fältet B, är det p.g.a. att B inte ingår i något funktionellt beroende?

Oops... Självklart måste B vara med i en kandidatnyckel.

hehe, vad bra då hänger jag med, så då är kandidatnyckeln alltså ABD?

Japp.

Okej, då får fråga <b> d) </b> en ny innebörd då AD inte är kandidatnyckel längre.

Ja, då bryter ju alla fb:na mot BCNF.

Känns som detta är antingen en kuggfråga (B har tagits med avsiktligt), eller så har frågeskaparen gjort ett misstag när B tagits med.

Ja jag antar det jag också, att det är ett misstag, för det brukar ofta vara misstag av denne :) Jag tackar för din hjälp och förklarar dessa frågor lösta nu!