How to find the extraneous attributes of functional dependency?

Question

I have a relation r(A,B,C,D,E,F) satisfying:

AB->C
C->A
BC->D
ACD->B
BE->C
CE->FA
CF->BD
D->EF

I need to find the canonical cover for this relation?

I know the algorithm to find the canonical cover. However in the algorithm, we need to find the extraneous attributes. Is there an algorithm to find extraneous attributes?

Answer 1

The algorithm to find extraneous attributes is the following:

let F the initial set of functional dependencies
assume that each dependency F is in the form A1, A2, ..., An -> B
for each functional dependency A1, A2, ..., An -> B in F with n > 1
    for each Ai
      if B ∈ ({A1, A2, ..., An} - Ai)+ 
         then Ai is an extraneous attribute and must be removed from the left hand side

Note that the closure of the remaining attributes must be computed by considering all the dependencies of F, including the dependency under examination (this can be counterintuitive).

For instance, applying this algorithm to your example, starting from the dependencies:

{ A B → C
  A C D → B
  B C → D
  B E → C
  C → A
  C E → A
  C E → F
  C F → B
  C F → D
  D → E
  D → F }

In A C D → B, A is estraneous since {C D}+ = (A B C D E F), while in C E → A, E is estraneous since {C}+ = (A C).