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.
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.
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