Sunday, March 2, 2014

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 2n+1 possible functional dependencies. For example, if R has 3 attributes, then 23+1 = 16 functional dependencies are possible.


Go to Normalization - Solved Exercises page

Go to How to find closure of an attribute? page



Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery