Closure of Set of Functional Dependencies

Closure / Closure of Set of Functional Dependencies / Different ways to identify set of functional dependencies that are holding in a relation / what is meant by the closure of a set of functional dependencies illustrate with an example

Introduction

Functional Dependencies are the important components in database design which would help us in identifying bad designs. Another important functionality of FDs is that they really express the facts about the database we are designing. Hence, it is very vital to identify all the possible set of functional dependencies hold in a table (relation).

What are the ways to identify functional dependencies?

1. Very simple way is to look for the dependency of one or more columns on the other columns using a sample data set.
The problem here is that the data set we are about to use is not complete. Hence, for some attributes we can anticipate the future set of values to be stored. But for most of the attributes, it is impossible. Especially, when a table is of more number of columns, it’s a kind of impossibility to express all the FDs holding by all the attributes. Hence, the set of functional dependencies which one could infer from the table directly is incomplete.

2. The second way is to identify the basic set of functional dependencies holding on a table which are easily visible and error free. Then, apply closure of set of Functional dependencies rules to derive the other hidden functional dependencies holding on the relation. We would mention those hidden functional dependencies as “functional dependencies that are logically implied”. When we are able to identify all the set of FDs holding by a relation, then we could say that the set F of FDs is complete.

In this post let us discuss about Closure of Set of Functional Dependencies.

Closure of Set of Functional Dependencies

"The closure of F, denoted as F+, is the set of all regular Functional Dependencies that can be derived from F".

This is used to discover some of the hidden functional dependencies so as to design a better database.

Consider the Armstrong's axioms developed by William W.Armstrong. Those axioms provide simpler technique to identify set of other functional dependencies (hidden). Let us list all the axioms along with the additional rules once again.

Reflexivity rule	If X is a set of attributes, and Y is subset of X, then we would say, X → Y.
Augmentation rule	If X → Y, and Z is another set of attributes, then we write XZ → XY.
Transitivity rule	If X → Y, and Y → Z, then X → Z is true.
Union rule	If X → Y and X → Z, then X → YZ is true.
Decomposition rule	Its reverse of Rule 4. If X → YZ, then X → Y, and X → Z are true
Pseudotransitivity rule	If X → Y and ZY → A are true, then XZ → A is also true.

Let us consider set F of functional dependencies hold on a relation R. We can derive additional functional dependencies from the set of given functional dependencies. But, still we may have some more hidden functional dependencies. We could derive some of the additional hidden functional dependencies from F on applying the above listed rules. In other words, we could deduce a new functional dependency from two or more functional dependencies of set F. Suppose, R is a relation with attributes (A, B, C, D, E, F) and with the identified set F of functional dependencies as follows;

F = { A → B, A → C, CD → E, B → E, CD → F }

Let us apply the above listed rules on every functional dependency of F to identify the member of F⁺ (the closure of functional dependency is termed as F⁺, i.e, set F added with new members resulting in F⁺).

1. A → E is logically implied. From our F we have two FDs A → B and B → E. By applying Transitivity rule, we could infer A → E. That is, if A can uniquely determine B and B can uniquely determine E then A can determine E (through B).

2. A → BC is logically implied. It can be inferred from the FDs A → B and A → C using Union rule.

3. CD → EF is logically implied by FDs CD → E and CD → F using Union rule.

4. AD → F is logically implied by FDs A → C and CD → F using Pseudotransitivity rule.

Like this, we can continue identifying the new members for F⁺. The procedure to find set F+ can be written as follows in pseudo code.

F+ = F Repeat                 For each functional dependency FD in F+                                 Apply reflexivity and augmentation rules on f                                 Add the result to F+                 For each pair of functional dependencies f1 and f2 in F+                                 If f1 and f2 can be combined using Transitivity                                                 Add the result to F+ Until F+ does not change any further.

This procedure does not show the additional rules Union, Decomposition, and Pseudotransitivity. The reason is, these additional rules are actually inferred from basic axioms. Also additional rules can be proved using Armstrong’s axioms. The procedure can be stopped when we started to get the functional dependencies already existing in F⁺.

For a relation with set of n attributes, there are 2ⁿ⁺¹ possible functional dependencies. For example, if R has 3 attributes, then 2³⁺¹ = 16 functional dependencies are possible.

Go to Normalization - Solved Exercises page

Go to How to find closure of an attribute? page