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)

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)

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 ₁ , t ₂ , such that t ₁ [A] = t ₂ [A], it is the case that t ₁ [A]= t ₂ [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 ₁ , t ₂ are any 2 tuples of R, then by A -> B means t ₁ [A] = t ₂ [A] and thus by A -> B it implies that t ₁ [B]= t ₂ [B] and by B -> H, it implies that t ₁ [H]= t ₂ [H].

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

Therefore we have proved that whenever t₁ and t₂ are tuples such that t ₁ [A] = t ₂ [A], it must be that t ₁ [H]= t ₂ [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.