Question

Q1.

a. Given a schema R (A, B, C, D, E, F) and a set F of functional

dependencies {A → B, A → D, CD → E, CD → F, C → F, C → E, BD → E}, find the closure of the set of functional dependencies ?+

b. Given a schema R = CSJDPQV and a set FDs of functional dependencies FDs = {C → CSJDPQV, SD → P, JP → C, J → S}

1. Find the Canonical (Minimal) Cover set ? ?

2. Check whether the decomposition obtained by computing ? in step 1

in 3NF or not. Justify your answer.

c. Given R = (A, B, C, D) and F = {AB→C, AB→D, C→A, D→B} 1. Is R in 3NF, why? If it is not, decompose it into 3NF

2. Is R in BCNF, why? If it is not, decompose it into BCNF

Answer 1

Question 1.a)

The question is asked to find the closure of the set of functional dependencies ?+. F+ is the closure of F that contains the set of all possible regular functional dependencies that can be derived from F. It suggests the overall closure of the given functional dependencies.

Given relation, R = (A, B, C, D, E, F) and functional dependencies, F = {A → B, A → D, CD → E, CD → F, C → F, C → E, BD → E}

Thus, from the given FD, {A}⁺ = {A, B, D, E}

{B}⁺ = {B }

{C}⁺ = {C, F, E}

{D}⁺ = {D}

{E}⁺ = {E}

{F}⁺ = {F}

Now, using these, and also the combination of these closures, closure of the F⁺ or closure of functional dependencies can be found. Closure of the set of functional dependencies, F⁺ is given as the following FDs:

F⁺ = { A → A, A → B, A → D, A → E, B → B, C → C, C → F, C → E, D → D, E → E, F → F, AB → A, AB → B, AB → D, AB → E, AB → B, AB → AB, AC → A, AC → B, AC → D, AC → E, AC → C, AC → F, AC → AC, AD → A, AD → B, AD → E, AD → D, AD → AD, AE → A, AE → B, AE → D, AE → E, AE → AE, BC → B, BC → C, BC → F, BC → E, BC → BC, BD → B, BD → D, BD → BD, BE → B, BE → E, BE → BE, BF → B, BF → F, BF → BF, CD → C, CD → F, CD → E, CD → D, CD → CD, CE → C, CE → F, CE → E, CE → CE, CF → C, CF → F, CF → E, CF → CF, DE → D, DE → E, DE → DE, DF → D, DF → F, DF → DF, EF → E, EF → F, EF → EF, ABC → A, ABC → B, ABC → C, ABC → D, ABC → E, ABC → F, ABC → E, ABD → A, ABD → B, ABD → D, ABD → E, ABE → A, ABE → B, ABE → D, ABE → E, ABF → A, ABF → B, ABF → D, ABF → E, ABF → F, ACD → A, ACD → B, ACD → C, ACD → D, ACD → E, ACD → F, ADE → A, ADE → B, ADE → D, ADE → E, ADF → A, ADF → B. ADF → E, ADF → F, ADF → D, AEF → A, AEF → B, AEF → D, AEF → E, AEF → F, BCD → B, BCD → C, BCD → E, BCD → F, BCD → D, BCE → B, BCE → E, BCE → F, BCE → C, BCF → B, BCF → C, BCF → E, BCF → F, BDE → B, BDE → D, BDE → E, BDF → B, BDF → D, BDF → F, BEF → B, BEF → E, BEF → F, CDE → C, CDE → E, CDE → F, CDE → D, CDF → C, CDF → E, CDF → F, CDF → D, CEF → C, CEF → E, CEF → F, DEF → D, DEF → E, DEF → F, ABCD → A, ABCD → B, ABCD → C, ABCD → D, ABCD → E, ABCD → F, ABCE → A, ABCE → B, ABCE → C, ABCE → F, ABCE → E, ABCE → D, ABCF → A, ABCF → B, ABCF → C, ABCF → D, ABCF → E, ABCF → F, ACDE → A, ACDE → B, ACDE → C, ACDE → D, ACDE → E, ACDE → F, ACDF → A, ACDF → B, ACDF → C, ACDF → E, ACDF → F, ACDF → D, ADEF → A, ADEF → B, ADEF → D, ADEF → E, ADEF → F, BCDE → B, BCDE → E, BCDE → C, BCDE → F, BCDE → D, BCDF → B, BCDF → C, BCDF → E, BCDE → F, BCDF → D, BDEF → B, BDEF → D, BDEF → E, BDEF → F, CDEF → C, CDEF → D, CDEF → E, CDEF → F, ABCDE → A, ABCDE → B, ABCDE → C, ABCDE → E, ABCDE → D, ABCDE → F, ABCDF → A, ABCDF → B, ABCDF → C, ABCDF → E, ABCDF → D, ABCDF → F, BCDEF → B, BCDEF → C, BCDEF → D, BCDEF → E, BCDEF → F ..........and so on}

The above closure of functional dependencies have been found using considering the individual FDs of the left hand side.

Question 1.b)

Given schema R = CSJDPQV and the set of functional dependencies, FDs = {C → CSJDPQV, SD → P, JP → C, J → S}.

Part question 1: Find the Canonical (Minimal) Cover set ? ?

Ans: For the production rule, to minimal cover is required to find. Now, to find so, we have to check whether there are extra attributes in each production rules. To do so, find the closure of the LHS of the rule without using that rule. If the RHS contains extra repetitive attribute(s) then it is extra. The extra attributes will be removed.

Finding Closure of SD without using the rule (SD → P) = {SD}⁺ = {S, D}

Now, no extra attribute has been found in the RHS, so production rule (SD → P) is mandatory.

Finding Closure of JP without using the rule (JP → C) = {JP}⁺ = {J, P}

No extra attribute has been found in the RHS, so production rule (JP → C) is mandatory.

Finding Closure of J without using the rule (J → S) = {J}⁺ = {J }

No extra attribute has been found in the RHS, so production rule (J → S) is mandatory.

Finding Closure of C without using the rule (C → CSJDPQV) = {C}⁺ = {C}

No extra attribute has been found in the RHS. But, in the RHS of the rule, additional attributes are present that can be generated by other rules. For example,

Closure of SD = {SD}⁺ = {S, D, P}

Closure of JP = {JP}⁺ = {J, P, C}

Closure of J = {J}⁺ = {J, S}

Thus, attributes S, D, P, J can be derived from the other rules. So these are extra in the production rule of C. Thus the production rule of C can be minimized to , C → QV. Also, C → C can be eliminated since LHS can always derive itself on the RHS. So, the Canonical (Minimal) Cover set ? ? is given as : {C → QV, SD → P, JP → C, J → S}.

Part question 2:

For a schema R = CSJDPQV and a set FDs of functional dependencies FDs = {C → QV, SD → P, JP → C, J → S} , first, find the key.

Here, JD must be present in the primary key or candidate key, since it is not present in RHS of any production rule. Now, let us check if JD alone is sufficient to be the candidate key.

Closure of JD = {JD}⁺ = {J, D, S, P, C, Q, V}. So all attributes can be generated. So, JD is the key here.

Now, for production J → S, part of a key (key=JD) is determining something. So, it is a partial dependency. Thus the above computed decomposition is not in 3NF since it contains partial dependency.

Question 1.c) Given R = (A, B, C, D) and F = {AB→C, AB→D, C→A, D→B}

Ans: First, find the key of the given relation. All the attributes here are present in both RHS and LHS of the production rules.

Closure of AB = {AB}⁺ = {A, B, C, D}

Closure of CD = {CD}⁺ = {A, B, C, D}

So, AB and CD both are keys here.

Part question 1:

A relation R is in 3NF, if there is any functional dependency X → Y in R, such that any of the following holds,

• X is a super key.
• Y is a key or prime attribute.

Also, it can be said that the relation must be in 2NF and it does not have any transitive dependency.

Now, if we consider AB as the key, then find the closure of the LHS of the production rules,

{AB}⁺ = {A, B, C, D}

{C}⁺ = {C, A}

{D}⁺ = {D, B}

Now, since AB can derive C and D, these two will be added to a new relation, R₁= (A,B,C,D) with FDs as: {AB → C, AB → D}

Closure of C contains A as additional attribute, so it will be added to a new relation along with C, R₂= (C, A) with FDs as: {C → A}

Closure of D contains B as additional attribute, so it will be added to a new relation along with D, R₃= (D, B) with FDs as: {D→ B}

Now, all the relations holds any of the first two rules mentioned above, which can satisfy a relation to be 3NF.

Thus, the converted 3NF relations are:

R₁= (A,B,C,D) with FDs as: {AB → C, AB → D}

R₂= (C, A) with FDs as: {C → A}

R₃= (D, B) with FDs as: {D→ B}

Part question 2:

A relation R is in BCNF, if there is any functional dependency X → Y in R, such that,

• X is a super key.

Now, considering AB as the key, it is clear for functional dependencies as: {AB→C, AB→D, C→A, D→B} , C→A and D→B does not hold the property of the BCNF which is mentioned above.

Thus, the relation is not in BCNF.

Now, for every decomposition, the left hand side of the production rule must be a superkey. Thus, the relation can be converted into BCNF by decomposing it in following way:

S₁= (A,B,C,D) with FDs as: {AB → C, AB → D}.

Here, the key is AB. So, in both the production rules, the left hand side is a super key.

S₂= (C, A) with FDs as: {C → A}

Here, the key is C. Thus, in the production rules, the left hand side is a super key.

S₃= (D, B) with FDs as: {D→ B}

Here, the key is D. Thus, in the production rules, the left hand side is a super key.

Thus, the relation has been converted to BCNF, where the relation is given below:

S₁= (A,B,C,D) with FDs as: {AB → C, AB → D}

S₂= (C, A) with FDs as: {C → A}

S₃= (D, B) with FDs as: {D→ B}