Home » DBMS

Closure set of attribute and irreducible set of functional dependency

In this tutorial, we will learn how to calculate closure set of attributes and what is the irreducible set of functional dependency? Which is also known as a canonical form, canonical cover or canonical set. By Bharti Parmar Last updated : May 27, 2023

Closure set of attribute

It is a linear algorithm. The closure is a set of functional dependency from a given set also known a complete set of functional dependency. Here alpha is set of attributes which are a superkey and we need to find the set of attributes which is functionally determined by alpha.

α ---- > β

Examples

Here, we see two different type of problem-related to closure set of the attribute.

Question 1:

R (A, B, C) set of attribute having A ---- > B, B --- > C transactions.

Find closure of all set of the attribute?

Solution:

Given, transaction

A   --- > B
B   --- > C
{A}+	--- >	{A, B, C}
{B}+	--- >	{B, C}
{C}+	--- >	{C}

Question 2:

R (A, C, D, E, H) set of attribute having two function F & G with some set of attributes F: A --- > C, AC --- > D, E --- > AD, E --- > H and G: A --- > CD, E --- > AH transactions.

Conditions: a) F is the subset of G, b) G is the subset of F, c) F is equal to G, d) F is not equal to G

Find Equivalence Relation?

Solution:

Given,

F:  A  --- > C      G:	A --- > CD
    AC --- > D          E --- > AH
    E  --- > AD		
    E  --- > H

Here, first we find closure of all the attributes:

F:  {A}+	--- >	{A, C, D}
    {AC}+	--- >	{A, C, D}
    {E}+	--- >	{A, C, D, E, F}

G:  {A}+	--- >	{A, C, D}
    {E}+	--- >	{A, D, C, E, H}

Now, we check the Conditions:

1. F is the subset of G: True because F & G have {A}⁺ and{E}⁺ closure are the same set of attribute where {AC}⁺closure is same as {A}⁺ means F is the subset of G.
2. G is the subset of F: True, similarly to the first Condition F & G functions all attribute closure are same means G is a subset of F.
3. F is equal to G: If F is the subset of G and G is the subset of F means F is equal to G.
4. F is not equal to G: In the third condition, we have proved F is equal to G. So, this condition is false.

Hence proved this is an equivalence relation because F is equal to G.

Note: Redundancy (wastage of set of attribute) is also present in closure set of an attribute like AB --- > B (B present both the side known as redundancy).

Irreducible set of functional dependency (Canonical Cover / Canonical Set / Canonical form)

In an irreducible set of functional dependency, we try to reduce all the transactions to less waste of the set of attributes. We have to follow some steps to decompose the set of the attribute in functional dependency:

• Decompose all possible right side attribute not left side attribute.
• Find closure of all the transaction after decomposition of attribute including and excluding the same transaction.
• If any changes are done in closure set of the attribute after including and excluding the same transaction; then we can’t ignore the transaction otherwise, we ignore the transaction if the closure of that transaction is same in both cases.
• Follow this process in all decompose transactions then after check closure of the transactions we have after follow the aforesaid steps; if their closure is different then we can say that the transaction is in a reducible form otherwise, follow the steps again.

Presence and absence of element do not affect the capability of functional dependency.

α ---- > β
A --- > AB

Example

Ques:
R (w, x, y, z)
x  ---> w
wz ---> xy
y --- > wxz

Solution

Decompose all the transactions:

x  --- > w
wz --- > x
wz --- > y
y  --- > w
y  --- > x
y  --- > z

Now, find closure of all the decompose transactions:

1) x --- > w

• Including the transaction
  {x}⁺={x,w}
• Excluding the transaction
  {x}⁺={x}

Closure are different in both cases so we can’t ignore this transaction

2) wz --- > x

• Including the transaction
  {wz}⁺={x,y,w,z}
• Excluding the transaction
  {wz}⁺={w,x,y,z}

Closure is same in both cases so, we ignore this transaction.

3) wz --- > y

• Including the transaction
  {wz}⁺={x,y,w,z}
• Excluding the transaction
  {wz}⁺={w,z}

Closure is different in both cases so, we can’t ignore this transaction.

4) y --- > w

• Including the transaction
  {y}⁺={x,y,w,z}
• Excluding the transaction
  {y}⁺={w,x,y,z}

Closure are same in both cases so we ignore this transaction.

5) y --- > x

• Including the transaction
  {y}⁺={x,y,w,z}
• Excluding the transaction
  {y}⁺={y,z}

Closure are different in both cases so we can’t ignore this transaction.

6) y --- > z

• Including the transaction
  {y}⁺={x,y,w,z}
• Excluding the transaction
  {y}⁺={w,x,y}

Closure are different in both cases so we can’t ignore this transaction.

Now, write all the transactions which we can’t ignore:

x  --- > w
wz --- > y
y  --- > x
y  --- > z

Find closure of each attribute of wz --- > y for cross check its value are same or different.

{wz}+={w,x,y,z}
{w}+={w}
{z}+={z}

Closure are different so now we can say that it is in the reducible form. The, the final transactions are:

x  --- > w
wz --- > y
y  --- > xz

Conclusion

In this tutorial, we have learned how to use closure set of attribute and how to reduce the set of the attribute in functional dependency for less wastage of attributes with an example. I hope you understand the concepts of both. if you have any query feel free to ask in the comment section. Have a nice day! Happy Learning!