Functional Dependency | Gate Vidyalay

Functional Dependency-

In any relation, a functional dependency α → β holds if-

Two tuples having same value of attribute α also have same value for attribute β.

Mathematically,

If α and β are the two sets of attributes in a relational table R where-

α ⊆ R
β ⊆ R

Then, for a functional dependency to exist from α to β,

If t1[α] = t2[α], then t1[β] = t2[β]

α	β
t1[α]	t1[β]
t2[α]	t2[β]
…….	…….

f_d : α → β

Types Of Functional Dependencies-

There are two types of functional dependencies-

Trivial Functional Dependencies
Non-trivial Functional Dependencies

1. Trivial Functional Dependencies-

A functional dependency X → Y is said to be trivial if and only if Y ⊆ X.
Thus, if RHS of a functional dependency is a subset of LHS, then it is called as a trivial functional dependency.

Examples-

The examples of trivial functional dependencies are-

AB → A
AB → B
AB → AB

2. Non-Trivial Functional Dependencies-

A functional dependency X → Y is said to be non-trivial if and only if Y ⊄ X.
Thus, if there exists at least one attribute in the RHS of a functional dependency that is not a part of LHS, then it is called as a non-trivial functional dependency.

Examples-

The examples of non-trivial functional dependencies are-

AB → BC
AB → CD

Inference Rules-

Reflexivity-

If B is a subset of A, then A → B always holds.

Transitivity-

If A → B and B → C, then A → C always holds.

Augmentation-

If A → B, then AC → BC always holds.

Decomposition-

If A → BC, then A → B and A → C always holds.

Composition-

If A → B and C → D, then AC → BD always holds.

Additive-

If A → B and A → C, then A → BC always holds.

Rules for Functional Dependency-

Rule-01:

A functional dependency X → Y will always hold if all the values of X are unique (different) irrespective of the values of Y.

Example-

Consider the following table-

A	B	C	D	E
5	4	3	2	2
8	5	3	2	1
1	9	3	3	5
4	7	3	3	8

The following functional dependencies will always hold since all the values of attribute ‘A’ are unique-

A → B
A → BC
A → CD
A → BCD
A → DE
A → BCDE

In general, we can say following functional dependency will always hold-

A → Any combination of attributes A, B, C, D, E

Similar will be the case for attributes B and E.

Rule-02:

A functional dependency X → Y will always hold if all the values of Y are same irrespective of the values of X.

Example-

Consider the following table-

A	B	C	D	E
5	4	3	2	2
8	5	3	2	1
1	9	3	3	5
4	7	3	3	8

The following functional dependencies will always hold since all the values of attribute ‘C’ are same-

A → C
AB → C
ABDE → C
DE → C
AE → C

In general, we can say following functional dependency will always hold true-

Any combination of attributes A, B, C, D, E → C

Combining Rule-01 and Rule-02 we can say-

In general, a functional dependency α → β always holds-

If either all values of α are unique or if all values of β are same or both.

Rule-03:

For a functional dependency X → Y to hold, if two tuples in the table agree on the value of attribute X, then they must also agree on the value of attribute Y.

Rule-04:

For a functional dependency X → Y, violation will occur only when for two or more same values of X, the corresponding Y values are different.

Next Article- Equivalence of Functional Dependencies

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Equivalence of Two Sets of Functional Dependencies-

Before you go through this article, make sure that you have gone through the previous article on Functional Dependency.

In DBMS,

Two different sets of functional dependencies for a given relation may or may not be equivalent.
If F and G are the two sets of functional dependencies, then following 3 cases are possible-

Case-01: F covers G (F ⊇ G)

Case-02: G covers F (G ⊇ F)

Case-03: Both F and G cover each other (F = G)

Case-01: Determining Whether F Covers G-

Following steps are followed to determine whether F covers G or not-

Step-01:

Take the functional dependencies of set G into consideration.
For each functional dependency X → Y, find the closure of X using the functional dependencies of set G.

Step-02:

Take the functional dependencies of set G into consideration.
For each functional dependency X → Y, find the closure of X using the functional dependencies of set F.

Step-03:

Compare the results of Step-01 and Step-02.
If the functional dependencies of set F has determined all those attributes that were determined by the functional dependencies of set G, then it means F covers G.
Thus, we conclude F covers G (F ⊇ G) otherwise not.

Case-02: Determining Whether G Covers F-

Following steps are followed to determine whether G covers F or not-

Step-01:

Take the functional dependencies of set F into consideration.
For each functional dependency X → Y, find the closure of X using the functional dependencies of set F.

Step-02:

Take the functional dependencies of set F into consideration.
For each functional dependency X → Y, find the closure of X using the functional dependencies of set G.

Step-03:

Compare the results of Step-01 and Step-02.
If the functional dependencies of set G has determined all those attributes that were determined by the functional dependencies of set F, then it means G covers F.
Thus, we conclude G covers F (G ⊇ F) otherwise not.

Case-03: Determining Whether Both F and G Cover Each Other-

If F covers G and G covers F, then both F and G cover each other.
Thus, if both the above cases hold true, we conclude both F and G cover each other (F = G).

PRACTICE PROBLEM BASED ON EQUIVALENCE OF FUNCTIONAL DEPENDENCIES-

Problem-

A relation R (A , C , D , E , H) is having two functional dependencies sets F and G as shown-

Set F-

A → C

AC → D

E → AD

E → H

Set G-

A → CD

E → AH

Which of the following holds true?

(A) G ⊇ F

(B) F ⊇ G

(D) All of the above

Solution-

Determining whether F covers G-

Step-01:

(A)⁺ = { A , C , D } // closure of left side of A → CD using set G
(E)⁺ = { A , C , D , E , H } // closure of left side of E → AH using set G

Step-02:

(A)⁺ = { A , C , D } // closure of left side of A → CD using set F
(E)⁺ = { A , C , D , E , H } // closure of left side of E → AH using set F

Step-03:

Comparing the results of Step-01 and Step-02, we find-

Functional dependencies of set F can determine all the attributes which have been determined by the functional dependencies of set G.
Thus, we conclude F covers G i.e. F ⊇ G.

Determining whether G covers F-

Step-01:

(A)⁺ = { A , C , D } // closure of left side of A → C using set F
(AC)⁺ = { A , C , D } // closure of left side of AC → D using set F
(E)⁺ = { A , C , D , E , H } // closure of left side of E → AD and E → H using set F

Step-02:

(A)⁺ = { A , C , D } // closure of left side of A → C using set G
(AC)⁺ = { A , C , D } // closure of left side of AC → D using set G
(E)⁺ = { A , C , D , E , H } // closure of left side of E → AD and E → H using set G

Step-03:

Comparing the results of Step-01 and Step-02, we find-

Functional dependencies of set G can determine all the attributes which have been determined by the functional dependencies of set F.
Thus, we conclude G covers F i.e. G ⊇ F.

Determining whether both F and G cover each other-

From Step-01, we conclude F covers G.
From Step-02, we conclude G covers F.
Thus, we conclude both F and G cover each other i.e. F = G.

Thus, Option (D) is correct.

Next Article- Canonical Cover in DBMS

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Tag: Functional Dependency