database refinement - minimal cover of F (extraneous attributes)

Question

Schema R = (A, B, C, D, E, F)

FD F = {ABC -> D, CD -> B, BCF -> D, CDF -> BE, BCDF -> E}

Find Fc, the minimal cover (aka. canonical cover) of F.

This is the method using in my book:

Example: abc -> xyz

a is redundant (extraneous) if (bc)+ ⊇ a; x is redundant if (abc)+ ⊇ x.

NOTE: Here, the closures are computed using F, with a or x being deleted from abc -> xyz respectively.

I don't understand the last bold sentence.

one solution is:

Consider CDF -> BE

B is redundant: (CDF)+ = (CDFBE) ⊇ (B)

F becomes { ABC -> D, CD -> B, BCF -> D, CDF -> E}

but I don't understand.

according to this logic:

E can be redundant too,

coz:

Consider CDF -> BE

E is redundant: (CDF)+ = (CDFBE) ⊇ (E)

F becomes { ABC -> D, CD -> B, BCF -> D, CDF -> B}

I know I must overlook some important criteria. Can anyone tell me what is that?

Answer 1

If r(R) is a relational schema on which the set of functional dependencies F is defined, then an attribute A in R is extraneous to the functional dependency x->Y

if A belongs to X and A is extraneous then
  (F - {X->Y}) U {(X-A) -> Y} is equivalent to F

if A belongs to Y and A is extraneous then
  F is equivalent to (F - {X->Y}) U {X -> (Y-A)}

To compute if A is extraneous to X

1. Find (X-A)+ under F
2. If Y is a subset of (X-A)+ under F then A is extraneous

The idea is to check if we can acquire the removed attribute on the left hand side of this functional dependency and still be able to derive it with the other functional dependencies inside F. If yes then A is redundant, as it can be inferred from other FDs.

To compute if A is extraneous to Y

1. Find F' = (F - {X->Y}) U {X -> (Y-A)}
2. Find X+ under F'

3. If X+ under F' contains A then A is extraneous to Y

Here, we remove A from the left hand side, and check if the removed attribute can be inferred from the set of FDs which has A removed from this one. Kind of simulation that if we have the FD {X -> (Y-A)} and with the other FSs in the set F and finding the closure of X under this simulated FD. If we see that X+ contains the removed attribute from the original one then it was redundant in the original set, and thus we declare A as extraneous to Y and keep the set with removed A, which we call F', because F' has the same closure as F.

Note that we do not compute F' with the removed A as in the seconds case. This is because (X-A) is a subset of X and thus, (X-A)+ under F will always make (X-A) U Y in some step of attribute closure computation. This is the same as if we constructed F' = (F - {X->Y}) U {(X-A) -> Y} and computed the closure of (X-A) under this F', as (X-A) is a subset to itself, and the modified FD in F' will also compute into (X-A) U Y. This is the cause if A belongs to X , we do not compute F'. Although we could, but it does not make difference in the closure computation.

On the other hand when A belongs to Y, we have to compute the F' with A removed from Y, this is because when we find X+ under F' we get X U (Y-A) in a step, and if we find closure of X under F we get X U Y, that does not make sense, as it simply computes the closure of X under its original set from which we cannot tell if some attribute is extraneous.

Simply, check that if a removed attribute can be inferred from other FDs in the set. Remove the target FD from the original set, and check if you can logically infer the removed attribute of the removed FD from other attribute. Armstrong's Axioms could also be applied.

Note that if two attributes are extraneous to an FD on the left hand side or the right hand side, then you cannot remove both. In this case two FDs are generated, each one with, one of the extraneous attribute removed. As in your example

F = {ABC -> D, CD -> B, BCF -> D, CDF -> BE, BCDF -> E} because of CDF->BE, B is extraneous and also E is extraneous. So this generates two possibilities: F1 = {ABC -> D, CD -> B, BCF -> D, CDF -> B, BCDF -> E} F2 = {ABC -> D, CD -> B, BCF -> D, CDF -> E, BCDF -> E} (here you can remove CDF->E also as BCDF->E implies CDF->E)

You can find more than one Canonical Cover/Minimal Cover of a set of functional dependencies. So it is not unique. You do not need to keep track to all the possibilities that is generated like this. Just pick one.

AS per a quick calculation here is what i found as he canonical cover/minimal cover:

Fc = {AC->D, CD->B, CF->DE}

Let us know if there is some more problem.

EDIT1:

Consider

r(A, B, C)

and the set of FDs is

 F = {A->BC, B->AC, C->AB}

Here you see that under F, B is extraneous to A->BC. Also 'C' is extraneous to A->BC under F. But you cannot remove both, because when you find B is extraneous to A->BC , you have already remove B, and which results in A->C, and you now have a new functional dependency set: F1 = {A->C, B->AC, C->AB} where C in not extraneous to A->C under the set F1. Each step of removal gets you a new set of FD, under which you find if the next selected attribute is extraneous or not.

The above example is very interesting, as you can get 4 canonical cover from it as shown below.

                                         A->BC
                                         B->AC
                                         C->AB
                                           |
                         +-----------------+-----------------+
                         |                                   |
                       A->C                                A->B
                       B->AC                               B->AC
                       C->AB                               C->AB
                         |                                   |
                +--------+--------+                 +--------+--------+
                |                 |                 |                 |
              A->C            +---+---+         +---+---+           A->B
              B->A            | A->C  |         | A->B  |           B->AC
              C->AB           | B->C  |         | B->AC |           C->A
                |             | C->AB |         | C->B  |             |
                +             +-------+         +-------+         +---+---+
                |             |  Fc2  |         |  Fc3  |         | A->B  |
            +---+---+         +-------+         +-------+         | B->C  |
            | A->C  |                                             | C->A  |
            | B->A  |                                             +-------+
            | C->B  |                                             |  Fc4  |
            +-------+                                             +-------+
            |  Fc1  |
            +-------+

Note how the tree is formed, by the different possibilities of removal, and the calculation of extraneous attributes with respect to the latest FD which it is in. I mean you cannot remove the FD A->BC because B and C is extraneous to A->BC under F, because removal of B generates another FD with A->C (one branch) and removal of C from A->BC forms another set of FD which has A->B (another branch).