Consider the relation schema R = (N, Y, P, M, C) and assume that the following s
ID: 3834724 • Letter: C
Question
Consider the relation schema R = (N, Y, P, M, C) and assume that the following set of functional dependencies hold on R:
F = { N M, NY P, M C}
g. [5 points] Show that F is already in canonical cover form.
h. [10 points] Use the algorithm we studied in class (slide 8.56) to find a lossless-join and dependency preserving decomposition of R into 3NF. Make sure to show all details.
i. [10 points] Consider the decomposition d = (R1, R2) where R1 = (N, Y, P) and R2 = (N, M, C). Is this decomposition lossless-join? Make sure to justify your answer and to show all details.
j. [10 points] Consider the decomposition d = (R1, R2, R3) where R1 = (N, M), R2 = (M, C) and R3 = (P, Y). Is this decomposition dependency preserving? Make sure to justify your answer and to show all details.
Explanation / Answer
g.
Let us assume that it is not the minimal set. We then use the following procedure to find minimal set
Rule-1 : split the FDs such that RHS contains single attributes. We get,
F' = { N M, NY P, M C}
Rule-2 : Find the redundant FDs and delete them [Ex :- In {A B, B C, A C}, the FD A C is redundant]. In the given set we don't have any redundant FDs. So, we get
F' = { N M, NY P, M C}
Rule-3 : Find all the redundant attributes on RHS and delete them [Ex :- In AB C, A can be removed if B+ has A]. In the given set, the only FD with more than one attributes on RHS is NY P, and both of them are independent. Therefore we get the minimal cover set to be
F' = { N M, NY P, M C}
You can see that we have got the same set of FDs in the minimal cover set F',(i.e, F = F') and therefore F is minimal cover set.
----------------------------------------------------------------------------------------------------------------------------------------
h.
Relation : R(NYPMC)
Function Dependencies : F = { N M, NY P, M C}
Candidate Key is NY
1. It is in 1NF as all the attibutes are assumed to be simple attributes
2. It is not in 2NF as there is a Partial Dependency. {N M} creates a partial dependency as N is a part of the candidate key, NY. We have to decompose the schema into
R(NYPMC) => R1(NYP), R2(NMC).
You can see that all the dependencies are preserved. FD-2 is preserved by R1 and FD-1, FD-3 are preserved by R2.
Note : Both 2NF and 3NF gurantees lossless decomposition and dependency preservation.
3. R2 are not in 3NF because there is a transitive dependency. From {N M, M C}, we can see that C, a non-prime attribute is transitively depending on N. We have to further decompose R2
R2(NMC) ==> R3(NM), R4(MC)
So, finally we have R1(NYP), R3(NM), R4(MC)
----------------------------------------------------------------------------------------------------------------------------------------
i.
We just showed in the above question (h) that R1 = (N, Y, P) and R2 = (N, M, C) is in 2NF and 2NF gurantees lossless decomposition and preserves functional dependencies.
----------------------------------------------------------------------------------------------------------------------------------------
j.
We just showed in the above question (h) that R1 = (N, Y, P) and R2 = (N, M) and R3 = (M, C) are in 3NF and it gurantees lossless decomposition and preserves functional dependencies. You can see that all the dependencies are preserved. NY P is preserved by R1, N M is preserved by R2, M C is preserved by R3.