/    /  DBMS – Canonical Cover

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