Eliminate the redundant functional dependencies to find minimal cover

Find the functional dependencies that are redundant in a given set of FDs / Eliminate the redundant functional dependencies to find minimal cover / Eliminating unnecessary FDs to find canonical cover in normalization process

Question:

9. Let R(A, B, C) be a relation with the following set F of functional dependencies;

F = { A → B, B → A, A → C, C → A, B → C }

If we would like to find the minimal cover of F, then which of the following redundancies should be eliminated? ;

(a) B → A and A → C

(b) B → C

(c) Either (a) or (b)

(d) F is already minimal

Answer:

(c) Either (a) or (b)

Note: There can be more than one minimal cover for a set of functional dependencies.

Steps to find the minimal cover;

1. Ensure singleton attribute on the right hand side of each functional dependency.

2. Remove extraneous (redundant) attribute from the left hand side of each functional dependency.

3. Remove redundant functional dependency if any.

In our case, the functional dependencies given are already satisfying the first two rules.

According to rule 1, if we have any FDs with more than one attribute on the Right Hand Side, that FD should be decomposed using decomposition rule. We don’t have such FDs.

According to rule 2, if we have any FDs that have more than one attribute on the Left Hand Side (determiner), that FD must be checked for partial dependency. We don’t have such FDs.

Hence, the given set satisfies both rules.

For the third one we need to check.

Procedure : [refer here for different explanation].

Given : F = { A → B, B → A, A → C, C → A, B → C }

For the first FD A → B find A⁺ by hiding the FD A → B. A⁺ = AC which does not include B in it. Hence, A → B is not redundant.

For the second FD B → A find B⁺ by hiding the FD B → A.  B⁺ = ABC which includes A in it. Hence, B → A is redundant. We have to remove it immediately.

Now with the removal of B → A, our F becomes,

F = { A → B, A → C, C → A, B → C }

Find A⁺ by hiding A → C. A⁺ = ABC which includes C. Hence A → C is redundant and remove it immediately from F.

After removal of A → C, F becomes,

F = { A → B, C → A, B → C }

Find C⁺ by hiding C → A. C⁺ = C and this does not include A in the result. Hence, C → A is not redundant.

Finally find B⁺ by hiding B → C. B⁺ = B. Hence, B → C is mandatory.

We don’t have any more FDs. Our final set of functional dependencies are minimal after the removal of FDs B → A and A → C.

Hence, the minimal cover of F is as follows;

F_c = { A → B, C → A, B → C }

[Work out for the option B → C. While applying the above said procedure, start with the FD B → C. You will get the F_c as { A → B, B → A, A → C, C → A }]

         Previous Question                                                                                Next Question