# Closure set of attribute and irreducible set of functional dependency

In this article, we are going to discuss **how to calculate closure set of attribute and what is the irreducible set of functional dependency**? Which is also known as a canonical form, canonical cover or canonical set.

Submitted by Bharti Parmar, on November 02, 2018

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

**α ---- > β**

**Example:**

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

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

Find closure of all set of the attribute?

**Solve:** Given, transaction

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

**Ques2:** **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?

**Solve:** 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:

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

**Solve:** 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 article, 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!

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.