Types of Functional Dependencies in Normalization

Functional Dependency:

In Relational database, Functional dependency is denoted as

X -> Y

X: Determinant

Y: Dependent

so, as per the concept the value of Y gets determined by the value of X.

that is in this case, if value of X gets duplicated, then in those rows value of Y shall also gets duplicated correspondingly.

if the determinant X value is unique (different) then the dependent Y could have any value meaning:

  • for same X , value of Y should be same.

  • for different X, value of Y could be same or different.

Flow chart used for F.D validation check:

FD.PNG

Reflexive Axiom:

According to reflexive axiom, always the trivial dependencies like X->X, Y->Y shall be true and valid for each and every instance of the relation.

Decomposition Axiom:

if there exist functional dependency X->YZ, then as per decomposition axiom, we can conclude => X->Y and X->Z are valid.

Decomposition axiom should always get applied on dependent side and ot the determinant side.

if there exist XY -> Z then X->Z and Y->Z are not valid.

Example:

A B C
1 2 3
2 2 3
3 2 3
4 3 2
5 2 3
6 3 2

All possible FD’s of the above relation:

  1. A->A : Valid (Determinant A’s values are unique)
  2. A->B : Valid (Determinant A’s values are unique)
  3. A->C : Valid (Determinant A’s values are unique)
  4. B->A : Not Valid (for same determinant B’s value  ‘2’, dependent A’s value ‘1’,’2′ is different)
  5. B->B : Valid (Trivial Dependency always valid according to Reflexive Axiom)
  6. B->C : Valid (for same determinant B value, same dependent C value, for different B value C value could be anything hence it is valid)
  7. C->A : Not Valid (for same determinant C value 3 there are 5 different dependent A values hence not valid)
  8. C->B : Valid (for same determinant C value that is 3, same dependent B value that is 2, for different C value B value could be anything hence it is valid)
  9. C->C : Valid (Trivial Dependency always valid according to Reflexive Axiom)
  10. AB->AValid (A’s values are unique hence determinant AB’s values will also be unique, hence dependent A’s value could be anything, AB->any attribute of above relation will be valid)
  11. AB->B : Valid (A’s values are unique hence determinant AB’s values will also be unique, hence dependent B’s value could be anything, AB->any attribute of above relation will be valid)
  12. AB->C Valid (A’s values are unique hence determinant AB’s values will also be unique, hence dependent C’s value could be anything, AB->any attribute or attributes combination of above relation will be valid)
  13. BC->A : Not Valid (for same value {2,3} of determinant BC there are two values {1},{2}of dependent A, hence not valid)
  14. BC->B : Valid (for same value {2,3} o determinant BC, same value {2} of dependent B exist. this holds for any combination of determinant to dependent. hence it is valid)
  15. BC->C : Valid (for same value {2,3} o determinant BC, same value {3} of dependent C exist. this holds for any combination of determinant to dependent. hence it is valid)
  16. CA->A : Valid (A’s values are unique hence determinant AC’s or CA’s values will also be unique, hence dependent A’s value could be anything, CA->any attribute or attributes combination of above relation will be valid)
  17. CA->B : Valid (A’s values are unique hence determinant AC’s or CA’s values will also be unique, hence dependent B’s value could be anything, CA->any attribute or attributes combination of above relation will be valid)
  18. CA->C : Valid (A’s values are unique hence determinant AC’s or CA’s values will also be unique, hence dependent C’s value could be anything, CA->any attribute or attributes combination of above relation will be valid)
  19. ABC->AValid (A’s values are unique hence determinant ABC’s values will also be unique, hence dependent C’s value could be anything, ABC->any attribute or attributes combination of above relation will be valid)
  20. ABC->BValid (A’s values are unique hence determinant ABC’s values will also be unique, hence dependent B’s value could be anything, ABC->any attribute or attributes combination of above relation will be valid)
  21. ABC->CValid (A’s values are unique hence determinant ABC’s values will also be unique, hence dependent C’s value could be anything, ABC->any attribute or attributes combination of above relation will be valid)

Different Types of Functional Dependencies used in Normalization process are:

  • Full Dependency
  • Partial Dependency
  • Transitive Dependency
  • Overlapping Candidate Key Dependency

Full Dependency:

A dependency is said to be full if and only if the determinant of the dependency is either a candidate key or a super key.

Note: Dependent of the full dependency can be either prime or non prime attribute.

X -> Y

  • X is either candidate key or super key
  • Y could be any attribute Prime or Non Prime.

Note: Full Dependency will always cause Zero % redundancy hence we need not to eliminate full dependency.

Partial Dependency:

If a Non prime or Non key attribute of the relation is dependent on only a part of the candidate key then such dependency is defined as partial dependency.

X->Y

X is subset of Candidate Key

Y is Non Prime or Non Key Attribute.

Note:

  1. While identifying the partial dependencies make sure that dependent is non prime/non key and determinant is part of candidate key.
  2. In order to have any partial dependencies, the relation should have at least one of the candidate key as composite.
  3. Partial dependencies will cause redundancies, hence they should get eliminated.

Transitive Dependency:

If a non prime attribute of the relation gets derived by either another non prime attribute or the combination of the part of the candidate key along with a non prime attribute is defined as transitive dependency.

X->Y

X: Non prime or combination of part of candidate key with at least one non prime attribute

Y: non prime attribute.

Note:

  1. While validating the transitive dependency, make sure the dependent is a non prime attribute and the determinant is either a non prime attribute or the combination of part of candidate key along with a non prime attribute.
  2. Transitive dependencies will cause redundancy in the relation and hence they should be eliminated.
  3. If a relation has zero non prime attribute then the total no of partial and transitive dependencies in that relation will be always zero.

Overlapping candidate key dependency:

If at least one candidate key of the relation is composite and the part of the candidate key id derived by another attribute combination X ∈ R, where X is not a candidate key then such dependency would be declared as OCD, as it causes the candidate key to get overlapped.

R(A,B,C)

{

AB->C

C->A

}

=> AB is candidate key.

A is part of candidate key and is derived by C which is not the candidate key.

=> c->A

=> CB -> AB

Note:

While Identifying OCD, make sure the dependent is part of candidate key and the determinant is not the candidate key also the relation should have at least one composite candidate key.

OCD could cause redundancies, hence they should be eliminated.

Recommended Articles :

  1. Super Key, Candidate Key and Primary Key
  2. Prime and Non Prime Attributes

One thought on “Types of Functional Dependencies in Normalization

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s