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 :
- The attribute A is extraneous in α, if A ϵ α and F logically imply
( F – { α → β }) U { ( α – A ) → β }
- 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