Quick links
Latest articles
Internship
Members
New...
Algorithms
Discrete Mathematics
Big data
Languages
C
C++
C++ STL
Java
Data Structure
C#.Net
Android
Kotlin
SQL
Web
PHP
Python
JavaScript
CSS
Ajax
Node.js
Web prog.
Programs
C
C++
DS
Java
C#
Python
Aptitude
C
C++
Java
DBMS
Interview
C
Embedded C
Java
SEO
HR
CS Subjects
CS Basics
O.S.
Networks
DBMS
Embedded Systems
Cloud Computing
Machine learning
CS Organizations
Linux
DOS
More...
Articles
Puzzles
News/Updates

Home » DBMS

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:

  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

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!






Quick links:
C FAQ(s) C Advance programs C/C++ Tips & Tricks Puzzles JavaScript CSS Python Linux Commands PHP Android Articles More...

Featured post:
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distribution Software (Distros) of 2018

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates



© https://www.includehelp.com (2015-2018), Some rights reserved.