Functional Dependency in DBMS With Examples

Greetings!
We have recently published 100+ articles on android tutorials with kotlin and java. If you need, you may visit Android Tutorial for beginners page. You can also check Kotlin Tutorial for beginners. Also, if you are interested in content writing, you can mail us at tutorialwing@gmail.com.

Let us look at the concept of functional dependency in dbms with examples. Let R be a relational schema and let X and Y be non empty sets of attributes in R. We say that an instance‘r’ of R satisfies the functional Dependency X->Y (read as ‘X’ functionally determines ‘Y’ or ‘Y is functionally dependent on X’) if the following holds for every pair of tuples t1 and t2 in r.

If t1.X = t2.X

Then t1.Y = t2.Y

It means that if two tuples agree on the values in attribute X i.e. for both the rows the values for the attribute X is same then they must also have same values for the attribute Y.

Using functional dependency notations, we say that k is a super key if whenever t 1 [k] = t 2 [k]. It is also the case that t 1 [R] =t 2 [R]. That means that if each and every attribute of the relation R is functionally dependent on k, then k is said to be the super key of R.

We shall use the functional dependency in dbms in the following two ways.

  1. To specify constraints on the set of legal relations.
  2. To test relations to see whether the relations are legal under a given set of functional dependencies.

Let r be a relation schema for relation r(R). r satisfies the functional dependency a -> β if a given set of values for each attribute in α uniquely determines each of the values of the attributes in β. β is said to be functionally dependent on α.

In order to verify if a given FD, α -> β is satisfied by a relation r on a relation schema R, we find any two tuples with the same α value; if the FD α -> β is satisfied in r, then the β values in these tuples must be same. We repeat this procedure until we have examined all such pairs of tuples with the same α value.

Example 1

Consider the following relation and relation-schema

Schedule = (Prof, Course, Room, Max-Enroll, Day, Time)

Professor Course Room Max-enroll Day Time
Sachin 353 A 40 Mon 11.45
Sachin 353 A 40 Wed 11.45
Sachin 351 C 60 Tue 1.15
Sachin 351 C 60 Thur 1.15
Rahul 355 A 300 Tue 8.45
Ajay 456 B 45 Thur 10.15
Rahul 355 A 300 Mon 8.45
Ajay 456 B 40 Tue 10.15

FD, Course -> Prof is satisfied, but Prof. -> Course is not satisfied

Example 2

Consider this,

Loan-Info-Schema = (branch-name, loan-no, cust-name, amount)

Branch-name Cust-name Loan-no Amount (Rs.)
SBI Sachin 15 10,000
ICICI Rahul 31 20,000
HDFC Raj 29 1,50,000
HDFC Ramesh 21 1,50,000
BOI Ajay 25 29,000
CITI BANK Anil 69 3,00,000
BOM Rahul 93 10,000
BOI Sachin 51 20,000

The set of functional dependencies that hold on relation schema is

Loan-no -> amount
Loan-no -> branch name

It cannot hold

Loan-no -> cust-name

8.2.1 Trivial dependencies

Some functional dependencies are said to be trivial dependencies because they are satisfied by all relations.

Example

A-> A is satisfied by all relations involving the attribute A. Considering the definitions of functional dependency literally, we see that for all tuples t 1 , t 2 , such that t 1 [A] = t 2 [A], it is the case that t 1 [A]= t 2 [A]. Similarly AB -> A is satisfied by all relations involving attribute A.

8.2.2 Closure of Set of Functional Dependencies.

Let R be a relational schema and F be set of functional dependencies defined on R.

The set F contains all functional dependencies that are semantically obvious. But in addition, there are numerous other functional dependencies that hold on all legal relational instances that satisfy dependencies in F. such functional dependencies are logically implied from F.

Example 1

If R= (A, B, C, G, H) is a relational schema and F= {A -> B, A -> C, B -> H} then the functional dependency A -> H is logically implied. Since if t 1 , t 2 are any 2 tuples of R, then by A -> B means t 1 [A] = t 2 [A] and thus by A -> B it implies that t 1 [B]= t 2 [B] and by B -> H, it implies that t 1 [H]= t 2 [H].

Therefore we have proved that whenever t 1 and t 2 are tuples such that t 1 [A] = t 2 [A], it must be that t 1 [H]= t 2 [H].

Therefore we have proved that whenever t1 and t2 are tuples such that t 1 [A] = t 2 [A], it must be that t 1 [H]= t 2 [H] and that is exactly the definition of A -> H.

Given F, we can compute F directly from the formal definition of functional dependency.

But if F were large, then this process would be lengthy and difficult.

Thus there is a Set of Inference rules or a set of axioms, also called as Armstrong’s axioms that is used to compute F.

The Armstrong’s axioms are as follows.

  1. Relativity Rule: If α is a set of attributes and β ⊆ α, then α -> β holds.
  2. Augmentation Rule: If α -> β holds and y is a set of attributes then yα -> yβ holds
  3. Transitivity Rule: If α -> β holds and β -> y holds then α -> y.

Below are some additional rules

  1. Union rule: If α -> β holds and α -> y holds then α -> βy holds.
  2. Decomposition Rule: If α -> βy holds, then α -> y holds.
  3. Pseudo transitivity Rule: If α -> β holds and yβ -> δ holds then αy -> δ.

8.2.3 Closure of Attribute Set

To test whether a set α is a super key, we must devise an algorithm for computing the set of attributes functionally determined by α, We can see that such an algorithm is useful also as part of the computation of the closure of a set F of functional dependencies.

Let α be a set of attributes. We call the set of all attributes functionally determined by α under a set F of functional dependencies the closure of α under F, denote it as α + as follows.

Algorithm

Result: = α;
While (changes to result) do
For each FD β -> y in F do
begin
If β ⊆ result then result: = result ∪ y;
End

Example 1

To illustrate how the algorithm works, we shall use the algorithm to computer (AG) + with the FDs,

A -> B,
A -> C,
CG -> H,
CG -> I,
B -> H.

The input to the algorithm will be

F = {A -> B, A -> C, CG -> H, CG -> I, B -> H} and α = {A G}

We start with result = AG

The first time we execute the while loop to test each FD, we find that

A -> B, causes us to include B in result
A -> B is in F, A ⊆ result, so result: = result ∪ B.
A -> C, causes result to become ABCG.
CG -> H causes result to become ABCGH.
CG -> I, causes result to become ABCGHI.

 

That’s end of our post on functional dependency in dbms with example.

Support Us

If you like Tutorialwing and would like to contribute, you can email an article on any educational topic at tutorialwing@gmail.com. We would love to publish your article. See your article on Tutorialwing and help others with your knowledge. Follow Facebook, LinkedIn, Google+, Twitter, Youtube for latest updates.
Greetings!
We have recently published 100+ articles on android tutorials with kotlin and java. If you need, you may visit Android Tutorial for beginners page. You can also check Kotlin Tutorial for beginners