Intro to DBMS

Closure Method In DBMS

  • The closure method is used to find all possible candidate keys in the table.
  • A candidate key is the minimal key which can determine all the attributes in the relation.

Notation Of Closure Set

  • Closure of attribute {X} is denoted as {X}+.
  • Closure of {X}+ means what the X may or may not determine all the attributes in the given relation.

Keep in mind: If the Closure of any attribute ({X}+) can determine all attributes of a given relation, then the closure of that attribute can be used as a candidate key; otherwise, it cannot.

Method to Find Closure of an Attribute Set

  • Find all determined values from closure and add the recursive value of closure.
  • Find the closure and candidate key.

Whenever we need to find the closure of any relation the following two things will be given.

  1. Relation with attributes i.e. {R(ABCDEF)}
  2. Functional dependencies (FD), i.e. {A→B, BC→D, E→F} etc.

We need to find the closure of all those attributes that are on the left side of the FD.

Let’s explain with multiple Examples

Example 01

Suppose a relation (R) containing four attributes, A, B, C, and D, and functional dependencies, as given below.

  • R= {A, B, C, D}
  • FD = {A→B, B→C, C→D}

As attributes A, B, C, and D are present on the left side of FD, we will find the closure of all these attributes.

So, the Closure of all attributes is given under

Closure of attribute “A”

  • According to the recursive rule, Attribute “A” can determine Attribute “A” itself.
  • According to the given FD, Attribute “A” can directly determine Attribute “B”.
  • According to the transitive property, Attribute “A” can determine “C” through “B.”
  • According to the transitive property, As Attribute “A” already determines C, Attribute “A” can determine “D” through “C.”

So, Closure of A = A+ = ABCD

Closure of attribute “B”

  • According to the recursive rule, Attribute “B” can determine Attribute “B” itself.
  • According to the given FD, Attribute “B” can directly determine Attribute “C”.
  • According to the transitive property, Attribute “B” can determine “D” through “C”.
  • Attribute “B” cannot determine attribute “A”

So, Closure of B = B+ = BCD

Closure of attribute “C”

  • According to the recursive rule, Attribute “C” can determine Attribute “C” itself.
  • According to the given FD, Attribute “C” can directly determine Attribute “D.”
  • Attribute “C” cannot determine attributes “A” and “B”

So, Closure of C = C+ = CD

Closure of attribute “D”

  • According to the recursive rule, Attribute “D” can determine Attribute “C” itself.
  • Attribute “D” cannot determine attributes “A,” “B,” and “C.”

So, Closure of D = D+ = D

Conclusion: As we see, only the closure of attribute “A” can determine all attributes of the relation, so attribute “A” can be used as the Candidate key.

So, Candidate Key = {A}

Keep In Mind:

  • Attribute sets AB, AC, AD, or ABC, ACD, or ABCD can be used to determine all the attributes in the relation but cannot be considered candidate keys.
  • Because the candidate key is a minimal key to determine all attributes in the relation, so “A” is a candidate key, and a combination of A with others like (AB, AC, AD, or ABC, ACD, or ABCD) is considered a Super Key.

Example 02

Let suppose R= {A, B, C, D} and  FD = {A→B, B→C, C→D, D→A}

As attributes A, B, C, and D are present in the left side of FD so, we will find the closure of all these attributes.

Closure of attribute “A”

  • As Attribute “A” can determine itself.
  • According to FD, Attribute “A” can directly determine Attribute “B”.
  • According to the transitive property, Attribute “A” can determine “C” through “B”.
  • According to the transitive property, As Attribute “A” already determines C, Attribute “A” can determine “D” through “C”.

So, Closure of A = A+ = ABCD

Closure of attribute “B”

  • As Attribute “B” can determine itself.
  • According to FD, Attribute “B” can directly determine Attribute “C”.
  • According to the transitive property, Attribute “B” can determine “D” through “C”.
  • According to the transitive property, As Attribute “B” already determines D, Attribute “B” can determine “A” through “D”.

So, Closure of B = B+ = BCDA

Closure of attribute “C”

  • As Attribute “C” can determine itself.
  • According to FD, Attribute “C” can directly determine Attribute “D.”
  • According to the transitive property, As Attribute “C” already determines D, Attribute “C” can determine “A” through “D”.
  • As Attribute “C” already determines A So, Attribute “C” can determine “B” through “A”.

So, Closure of C = C+ = CDAB

Closure of attribute “D”

  • As Attribute “D” can determine itself.
  • According to FD, Attribute “D” can directly determine Attribute “A.”
  • According to transitive property, As Attribute “D” already determines A, Attribute “D” can determine “B” through “A”.
  • As Attribute “D” already determines B, Attribute “D” can determine “C” through “B”.

So, Closure of D = D+ = DABC

Conclusion: As we see, the closure of all attributes, “A,” “B,” “C,” and “D,” can determine all attributes of relation so all attributes can be used as Candidate keys.

So, Candidate Key = {A, B, C, D}

Example 03:  Find the closure and candidate key

Consider a relation R ( A, B, C, D, E, F, G ) with the functional dependencies-

  • A → BC
  • BC → DE
  • D → F
  • CF → G

Here we will find the closure of attributes “A,” “BC,” “D,” and “CF,” but keep in mind,  First, we have to find the closure of a single attribute, i.e. (A and D) and then find the closure of  multiple attributes (“BC” and “CF”)

Now, let us find the closure of some attributes and attribute sets-

Closure of attribute A

A+   = {A} According to the recursive property, A can determine itself.

Using FD, A → BC,  According to the decomposition rule, “A” can determine “B” and “C” )

A+   = { A , B, C }   

As B and C are already determined in A+ by Using BC → DE attributes, D and E can also be determined.

A+  = { A, B, C, D, E }     

As attribute “D” is determined in the closure of “A”, so by using  D → F. attribute “F” can also be determined.

A+  = { A, B, C, D, E, F }         

( Using D → F ) As attributes { A, B, C, D, E, F } are determined in the closure of “A”, so by using  (CF → G). attribute “G” can also be determined

A+  = { A, B, C, D, E, F, G }    ( Using CF → G )

Thus,

A+ = { A, B, C, D, E, F, G }

Closure of attribute D

D+   = { D }

D+= { D , F }   ( Using D → F )

We cannot determine any other attribute using attributes D and F contained in the result set.

Thus,

D+ = { D , F }

“D” is not a candidate key because it cannot determine the attribute”A,” “B,” and “C”.

Closure of attribute set {B, C}

{ BC }+= { B , C }

{ BC }+= { B , C , D , E }               ( Using BC → DE )

{ BC }+= { B , C , D , E , F }          ( Using D → F )

{ BC }+= { B, C, D, E, F, G }    ( Using CF → G )

Thus,

{ BC }+ = { B, C, D, E, F, G }

“BC” is not a candidate key because it cannot determine the attribute ”A.”

Closure of attribute set {C,F}

{ CF }+= { C , F }

{ CF }+= { C , F , G  }               ( Using CF → G )

Thus,

{CF }+ = {C, F , G }

“BC” is not a candidate key because it cannot determine the attribute ”A, Candidate key.

So, the candidate key is only “A” because the closure of A determines all the attributes of relations.

Short-cut to find the candidate’s key

Example 4:

The smart trick is to find all possible candidate keys in the relation.  Suppose the following relation

R(A,B,C,D,E)

FD= {A→B, BC→D, E→C, D→A}

1.    If any attributes do not exist on the right side of FD, then they must be part of the candidate key with some other attribute as well.

Check in the above-given relation that every attribute is determined from some attributes, but attribute E is not determined by any attribute. So, attribute “E” must be used in the candidate Key with some other Key to determine E itself.

2.  As Closure of EA+ can determines the all attributes of Relation, EA is the first candidate key. To make the rest of the candidate keys, follow the following

I.  Check either E or A attributes present on the right-hand side of any FD. If E or A is found on the Right side of the FD, then replace it with the Left side of that FD.

For the second candidate, key A is replaced with D, and E does not exist on the right side of any FD, so it remains the same. Therefore, the second candidate key will be ED.

II. In the same way, now D will check in all FD’s. If D is found on the Right-hand side of any FD, then it can also be replaced. Keep in mind the concept of decomposition if there are two attributes that determine the single attribute. 

In this case, D will be replaced either with B or C. Here, we check the closer of EB and EC and select one of them. So EB is the valid candidate key but EC cannot determines the entire attributes so

Candidate keys will be  (EA, ED, BE