Closure of Attribute Set / Closure of Attribute Set Algorithm / How do we find a key given a set of attributes? / How to find super key? / Attribute Closure in DBMS / Closure of Attributes Set Example / How to find key for a relation?
Closure of Attribute Set
After finding a set of functional
dependencies that are hold on a relation, the next step is to find the Super
key for that relation (table). The set of identified functional dependencies
play a vital role in finding the key for the relation. We can decide whether an
attribute (or set of attributes) of any table is a key for that table or not by
identifying the attribute or set of attributes’ closure. If A is an attribute,
(or set of attributes) then its attribute closure is denoted as A+.
Algorithm:
The following algorithm will help
us in finding the closure of an attribute;
result
:=
A;
while
(changes
to result) do
for
each functional dependency B → C in F
do
begin
if
B ⊆ result then result := result ∪ C;
end
|
Let us discuss this algorithm
with an example;
Assume a relation schema R = (A,
B, C) with the set of functional dependencies F = {A → B,
B →
C}.
Now, we can find the attribute closure of attribute A as follows;
Step 1: We start with the
attribute in question as the initial result. Hence, result = A.
Step 2: Take the first FD A → B.
Its left hand side (i.e, A) is in the result, hence the right hand side can be
included with the result. This lead to result = AB.
Step 3: Take the second FD B → C.
Its left hand side (i.e, B) is in the result (or subset of result), hence the
right hand side can be included with the result. Now, result = ABC.
We have no more attributes. Hence
the algorithm exits. As the result, A+ includes all the attributes
of relation R. now we would say A+ is ABC. And, A is one of the keys
of the relation R.
Example:
Question:
Consider a relation R with the
schema R(A, B, C, D, E, F) with a set of functional dependencies F as follows;
{AB → C, BC → AD, D → E, CF → B}
Find the super key for this
relation.
Solution:
Finding (AB)+
First, let us find (AB)+
, the closure of attribute set AB (We do not need to test all the attributes
individually. Instead we can try with those attributes that are on the left
hand side of any FD.)
·
result = AB
·
As AB determines C, C can be included
with the result. Hence, result = AB U C = ABC.
·
According to second FD BC → AD, the attributes B and C together can
identify both A and D. Hence, result = ABC U AD = ABCD
·
If
you know D, you will know E according to third FD D → E. so, result = ABCD U E = ABCDE.
·
F
cannot be identified by any of these FDs. And our result can include ABCDE attributes
only.
Hence, the solution is AB is not
the key for R. The reason is, the closure of AB, i.e., (AB)+ does
not include all the attributes of R in the result.
Finding (ABF)+
Then what would be the key for
R?. As I told you initially, we can try all the left hand side attributes
(because they are the determiners), or some of their combination. From the
above example, we would get an idea to include F as one of the key attribute. So,
let us try to find (ABF)+ , the closure of attribute set ABF.
·
result = ABF
·
from the above example, we could say (AB)+
= ABCDE
·
we know C and F, then according to CF → B, we would deduce the result as ABCDEF,
which includes all the attributes from R.
Hence, the solution is ABF is one
of the key for R. because, (ABF)+ includes all the attributes of R.
Go to Normalization Exercises - Solved page
Go to How to find closure of set of functional dependencies page