Canonical Cover

Let F be a set of functional dependencies. Let F+ be the closure of F.

Let α → β is a functional dependency.

“An attribute of a functional dependency is said to be extraneous if we can remove it without changing the closure of the set of functional dependencies.

Extraneous Attribute :

1. The attribute A is extraneous in α, if A ϵ α and F logically imply        

( F – { α → β }) U { ( α – A ) → β }

1. The attribute A is extraneous in β, if A ϵ β and the set of functional dependencies ( F – { α → β }) U {  α → ( β – A ) } logically imply F.

Example-10 :     

Let S = (A, B, C, D, E)                                                                                    

F =  [ AB → CD,               A → E,             E → C ] 

Find whether C is extraneous in  AB → CD?

Output:  Let us check C is extraneous in AB → CD.

Here, α = AB  and  β = CD and

( F – { α → β })  =  [ A → E,  E → C ]                             …(1)

and  {  α → ( β – A )  =  [AB → D ]                                 ….(2)                    

The Combination of (1) and (2) gives  F.

Hence, we can say that  C is extraneous in  AB à CD.

Definition :

A Canonical Cover Fc for F is a set of dependencies such that:

• F logically implies all dependencies in Fc.
• Fc logically implies all dependencies in F and  Fc  must have the following properties :
• None of the functional dependencies in Fc contains an extraneous attribute.
• Each left side of an FD in Fc is unique. i.e., there are no two dependencies α1 à β1 and α2 à β2 in Fc such that α1 = α2.              

Example-11 :     

Let S= (A, B, C )                                                                                             

F =  [ A → BC,  B → C,   A → B,  AB → C ] 

Find the canonical cover of F ?

Output: Here, A is extraneous in AB → C. Similarly, C is extraneous in  A  → BC. 

Hence, the Canonical Cover of F is : Fc: A → B, B → C

Reference Links 

Canonical Cover