Functional Dependencies

Functional Dependencies

Definition: Let P and Q be sets of columns, then: P functionally determines Q, written P→Q if and only if any two rows that are equal on (all the attributes in) P must be equal on (all the attributes in) Q.

In other words, the functional dependency holds if

T1.P T2.P, then T1.Q=T2.Q

Where notation T1.P projects the tuple T1 onto the attribute in P.

For example: Consider a relation in which the roll of the student and his/her name is stored as follows:

Here, R->N is true. That means the functional dependency holds true here. Because for every assigned RollNuumber of student there will be unique name. For instance: The name of the Student whose RollNo is 1 is AAA. But if we get two different names for the same roll number then that means the table does not hold the functional dependency. Following is such table –

In above table for RollNumber 1 we are getting two different names - "AAA" and "XXX". Hence here it does not hold the functional dependency.

Computing Closure Set of Functional Dependency

The closure set is a set of all functional dependencies implied by a given set F. It is denoted by F⁺

The closure set of functional dependency can be computed using basic three rules which are also called as Armstrong's Axioms.

These are as follows -

i) Reflexivity: If XY, then X→ Y

ii) Augmentation: If X→Y, then XZ → YZ for any Z

iii) Transitivity: If X→Y and Y-Z, then X-Z

In addition to above axioms some additional rules for computing closure set of functional dependency are as follows -

• Union: If XY and X-Z then XYZ

• Decomposition: If X-YZ, then XY and X→ Z

Example 2.8.1 Compute the closure of the following set of functional dependencies for a relation scheme R(A,B,C,D,E), F={A->BC, CD->E, B->D, E->A)

Solution: Consider F as follows

A->BC

CD->E

B->D

E->A

The closure can be written for each attribute of relation as follows:

• (A)*= Step 1: {A}-> the attribute itself

Step 2: {ABC} as A->BC

Step 3: {ABCD} as B->D

Step 4: {ABCDE} as CD->E

Step 5: {ABCDE} as E->A and A is already present

Hence (A)+ ={ABCDE}

• (B)*=Step 1:{B}

Step 2: {BD} as B->D

Step 3: {BD} as there is no BD pair on LHS of F

Hence (B) ={BD}

• (C)*=Step 1:{C}

Step 2: {C} as there is no single C on LHS of F

Hence (C)* ={C}

• (D)⁺ = Step 1: {D}

Step 3: {D} as there is no BD pair on LHS of F

Hence (D)* ={D} .

• (E)⁺ =Step 1: {E}

Step 2: {EA} as E->A

Step 3: {EABC) as A->BC

Step 4: {EABCD} as B->D

Step 5: {EABCD} as CD->E and E is already present

By rearranging we get {ABCDE}

Hence (E)⁺ ={ABCDE}

• (CD)*=Step 1:{CD}

Step 2:{CDE}

Step 3: {CDEA}

Step 4:{CDEAB}

By rearranging we get {ABCDE}

Hence (CD)* ={ABCDE}

Example 2.8.2 Compute the closure of the following set of functional dependencies for a relation scheme R(A,B,C,D,E), F={A->BC, CD->E, B->D, E->A) and Find the candidate key.

Solution: For finding the closure of functional dependencies - Refer example 2.8.1.

We can identify candidate from the given relation schema with the help of functional dependency. For that purpose we need to compute the closure set of attribute. Now we will find out the closure set which can completely identify the relation R(A,B,C,D).

Let,  (A)⁺  = {ABCDE}

(B)⁺  = {BD}

(C)⁺ = {C}

(D)⁺ ={ABCDE}

(E)⁺ = {ABCDE}

(CD)⁺ = {ABCD}

Clearly, only (A), (E) and (CD)* gives us (ABCDE) i.e. complete relation R. Hence these are the candidate keys.

Canonical Cover or Minimal Cover

Formal Definition: A minimal cover for a set F of FDs is a set G of FDs such that:

1) Every dependency in G is of the form X->A, where A is a single attribute.

2) The closure F* is equal to the closure G*.

3) If we obtain a set H of dependencies from G by deleting one or more dependencies or by deleting attributes from a dependency in G, then F* H*.

Concept of Extraneous Attributes

Definition: 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. The formal definition of extraneous attributes is as follows:

Consider a set F of functional dependencies and the functional dependency α→β in F

• Attribute A is extraneous in α if A€ α and F logically implies (F - {α→ B}) U {(α- A) →β}

• Attribute A is extraneous in β if A€ βand the set of functional dependencies (F-{α→β}) U {(α→ (β - A) } logically implies F.

Algorithm for computing Canonical Cover for set of functional DependenciesF

Fc = F

repeat

Use the union rule to replace any dependencies in Fc of the form

α1 →β1 and αl→β2 and αl→β1β2

Find a functional dependency α→β in F_cwith an extraneous attribute either in α or in β

/* The test for extraneous attributes is done using Fc, not F */

If an extraneous attribute is found, delete it from α→βin Fc.

until (Fc does not change)

Example 2.8.3 Consider the following functional dependencies over the attribute set R(ABCDE) for finding minimal cover FD = {A->C, AC->D, B->ADE}

Solution: Step 1: Split the FD such that R.H.S contain single attribute. Hence we get

A->C

AC->D

B->A

B->D

 B->E

Step 2: Find the redundant entries and delete them. This can be done as follows –

For A->C: We find (A)* by assuming that we delete A->C temporarily. We get esimab (A)*={A}. Thus from A it is not possible to obtain C by deleting A->C. This means we can not delete A->C

• For AC->D: We find (AC)* by assuming that we delete AC->D temporarily. We get (AC)=(AC). Thus by such deletion it is not possible to obtain D. This means we can not delete AC->D

• For B->A: We find (B)* by assuming that we delete B->A temporarily. We get (B)*={BDE). Thus by such deletion it is not possible to obtain A. This means we can not delete B->A

• For B->D: We find (B)* by assuming that we delete B->D temporarily. We get (B)=(BEACD). This shows clearly that even if we delete B->D we can obtain D. This means we can delete B->A. Thus it is redundant.

• For B->E: We find (B) by assuming that we delete B->E temporarily. We get (B)*={BDAC). Thus by such deletion it is not possible to obtain E. This means we can not delete B->E

To summarize we get now

A->C

AC->D

B->A

B->E

Thus R.H.S gets simplified.

Step 3: Now we will simplify L.H.S.

Consider AC->D. Here we can split A and C. For that we find closure set of A and C.

(A)⁺ = {AC}

(C)⁺ = {C}

Thus C can be obtained from both A as well as C. That also means we need not have to have AC on L.H.S. Instead, only. A can be allowed and C can be eliminated. Thus after simplification we get

A->D

To summarize we get now

A->C

A->D

B->A

B->E

Thus L.H.S gets simplified.

Step 3: The simplified L.H.S. and R.H.S can be combined together to form

A->CD

B->AE

This is a minimal cover or Canonical cover of functional dependencies.