In this post we will see how to find closure of an attribute or a set of attributes. Before learning how to get closure, we should first know what is a closure. Closure of a given set C is the set of attributes that are functionally determined by the set C under the set of functional dependencies F. There can be closure for any set. Every attribute in the set whose closure is to be found out, will be a member of its closure set C+ also. Consider an example:
Schema : EMPLOYEE(empid,empname,dept,age,salary,experience)
Let the functional dependencies be as follows:
In above example, let us find the closure of the attribute empid, i.e, closure of {empid}
Since we are finding closure of empid. empid is an element of the closure set C+. Now we go step by step.
Step 1: Select each functional dependency and check whether the left side of functional dependency is a subset of closure. If yes, add the right side of that functional dependency to closure set. if not, check the next functional dependency
Step 2: Keep on checking the functional dependencies until there is no more functional dependencies with its left side as a subset of closure set C+.
What is a subset? A set M is said to be a subset of another set N only if all elements of set M is present in set N. Set N can have more elements than M.
Schema : EMPLOYEE(empid,empname,dept,age,salary,experience)
 |
| diagrammatic representation of functional dependencies |
- empid->empname
- {age,experience}->salary
- empid->{age,dept}
- dept->experience
In above example, let us find the closure of the attribute empid, i.e, closure of {empid}
Since we are finding closure of empid. empid is an element of the closure set C+. Now we go step by step.
Step 1: Select each functional dependency and check whether the left side of functional dependency is a subset of closure. If yes, add the right side of that functional dependency to closure set. if not, check the next functional dependency
Step 2: Keep on checking the functional dependencies until there is no more functional dependencies with its left side as a subset of closure set C+.
What is a subset? A set M is said to be a subset of another set N only if all elements of set M is present in set N. Set N can have more elements than M.
- So, in our example, empid is an element of the closure set C+. So, initially, C+={empid}.
- First functional dependency says empid functionally determines empname. Its left side ( {empid}) is subset of C+. Therefore, its right side is added to C+. Now C+={empid,empname}.
- Second fd (functional dependency) says {age,experience}->salary. Here left side ( {age,experience} ) is not a subset of C+. So we check the next fd.
- Third fd says, empid->{age,dept}. Here left side ( {empid} ) is subset of C+. Therefore, its right side is added to C+. Now, C becomes, C+={empid,empname,age,dept}.
- Fourth fd says, dept->experience. Here left side ( {dept} ) is a subset of C+. So we are adding its right side ( {experience} ) to Closure set. Now, C+={empid,empname,age,dept,experience}.
- We are looking again for a functional dependency with its left side as a subset of closure set. Since the closure set C+ is getting changed in some steps, there is more possibility to find another functional dependency with it s left side as a subset of C+. Again we go through every functional dependency.
- Since sets do not allow duplication, we should do nothing if the right side of the a functional dependency whose left side is subset of C+, is already present in closure set C+.
- Second fd has a left side that is subset of C+. {age,experience}->salary. Therefore salary is added to C+. Now, C+={empid,empname,age,dept,experience,salary}.
- There isn't any more functional dependency whose left side is subset of C+ and give at least one new attribute to closure set. Therefore we stop now.
Now closure of set C is C+={empid,empname,age,dept,experience,salary}.
Algorithm:
C+ = C;
while (there is changes to C+)
{
do (for each functional dependency X->Y in F)
{
if (X⊆C+)
then C+= C+∪Y
}
}
C Program:
#include<stdio.h>
#include<string.h>
#include<conio.h>
struct fd //functional dependency representation
{
int left[8];
int right[8];
int lcount,rcount;
}f[10];
int attrcount,closcount=0,fdcount;
int closure[10];
char attr[10][25];
void getclosure()
{
int i,j,k,l=0,issubset,found;
do
{
for(i=0;i<=fdcount;i++)//Checking each functional dependancy
{
issubset=1;
for(j=0;j<f[i].lcount;j++)//select each attr in leftside
{
found=0;
for(k=0;k<closcount;k++) //checking with each element of closure
{
if(closure[k]==f[i].left[j])
{
found=1;
break;
}
}
if(found==0)
{
issubset=0;
break;
}
}
if(issubset==1)
{
for(k=0;k<f[i].rcount;k++)
{
found=0;
for(j=0;j<closcount;j++)
{
if(closure[j]==f[i].right[k])
found=1;
}
if(found==0)
{
closure[closcount]=f[i].right[k];
closcount++;
}
}
}
}
l++;
}while(l<attrcount);
}
int compare(char temp[25])
{
int i;
for(i=0;i<attrcount;i++)
{
if(strcmp(temp,attr[i])==0)
return i;
}
}
void main() { int i,j,k,attcode; char schema[100],temp[45],temp1[50]; for(i=0;i<10;i++) { f[i].lcount=0; f[i].rcount=0; } printf("\nEnter the schema\n"); scanf("%s",schema); attrcount=0; for(i=0;schema[i]!='(';i++); do { j=0; i++; while(schema[i]!=','&&schema[i]!=')') { temp[j]=schema[i]; j++; i++; } temp[j]='\0'; strcpy(attr[attrcount],temp); attrcount++; }while(schema[i]==','); fdcount=-1; printf("\nEnter the functional dependancies\nEnter 0 to stop\n"); for(i=0;i<10;i++) { scanf("%s",temp1); if(strcmp(temp1,"0")==0) break; fdcount++; j=0; if(temp1[0]=='{'||temp1[0]=='(') j++; do { if(temp1[j]==',') j++; k=0; while(temp1[j]!=','&&temp1[j]!=')'&&temp1[j]!='}'&&temp1[j]!='-') { temp[k]=temp1[j]; k++; j++; } temp[k]='\0'; attcode=compare(temp); f[fdcount].left[f[fdcount].lcount]=attcode; f[fdcount].lcount++; }while(temp1[j]==','); if(temp1[j]==')'||temp1[j]=='}') j+=3; else if(temp1[j]=='-') j+=2; if(temp1[j]=='{'||temp1[j]=='(') j++; do { if(temp1[j]==',') j++; k=0; while(temp1[j]!=','&&temp1[j]!=')'&&temp1[j]!='}'&&temp1[j]!='\0') { temp[k]=temp1[j]; k++; j++; } temp[k]='\0'; attcode=compare(temp); f[fdcount].right[f[fdcount].rcount]=attcode; f[fdcount].rcount++; }while(temp1[j]==','); } printf("\nEnter an attribute whose closure is to be found\n"); scanf("%s",temp); attcode=compare(temp); closcount=1; closure[0]=attcode; getclosure(); printf("Closure of %s:\n",temp); for(i=0;i<closcount;i++) { printf("%s,",attr[closure[i]]); } getch(); }
C++ Program
#include<iostream.h>
#include<stdio.h>
#include<string.h>
#include<conio.h>
struct fd //functional dependency representation
{
int left[8];
int right[8];
int lcount,rcount;
}f[10];
int attrcount,closcount=0,fdcount;
int closure[10];
char attr[10][25];
void getclosure()
{
int i,j,k,l=0,issubset,found;
do
{
for(i=0;i<=fdcount;i++)//Checking each functional dependancy
{
issubset=1;
for(j=0;j<f[i].lcount;j++)//select each attr in leftside
{
found=0;
for(k=0;k<closcount;k++) //checking with each element of closure
{
if(closure[k]==f[i].left[j])
{
found=1;
break;
}
}
if(found==0)
{
issubset=0;
break;
}
}
if(issubset==1)
{
for(k=0;k<f[i].rcount;k++)
{
found=0;
for(j=0;j<closcount;j++)
{
if(closure[j]==f[i].right[k])
found=1;
}
if(found==0)
{
closure[closcount]=f[i].right[k];
closcount++;
}
}
}
}
l++;
}while(l<attrcount);
}
int compare(char temp[25])
{
int i;
for(i=0;i<attrcount;i++)
{
if(strcmp(temp,attr[i])==0)
return i;
}
return 0;
}
void main()
{
int i,j,k,attcode;
char schema[100],temp[45],temp1[50];
for(i=0;i<10;i++)
{
f[i].lcount=0;
f[i].rcount=0;
}
cout<<"\nEnter the schema\n";
gets(schema);
attrcount=0;
for(i=0;schema[i]!='(';i++);
do
{
j=0;
i++;
while(schema[i]!=','&&schema[i]!=')')
{
temp[j]=schema[i];
j++;
i++;
}
temp[j]='\0';
strcpy(attr[attrcount],temp);
attrcount++;
}while(schema[i]==',');
fdcount=-1;
cout<<"\nEnter the functional dependancies\nEnter 0 to stop\n";
for(i=0;i<10;i++)
{
gets(temp1);
if(strcmp(temp1,"0")==0)
break;
fdcount++;
j=0;
if(temp1[0]=='{'||temp1[0]=='(')
j++;
do
{
if(temp1[j]==',')
j++;
k=0;
while(temp1[j]!=','&&temp1[j]!=')'&&temp1[j]!='}'&&temp1[j]!='-')
{
temp[k]=temp1[j];
k++;
j++;
}
temp[k]='\0';
attcode=compare(temp);
f[fdcount].left[f[fdcount].lcount]=attcode;
f[fdcount].lcount++;
}while(temp1[j]==',');
if(temp1[j]==')'||temp1[j]=='}')
j+=3;
else if(temp1[j]=='-')
j+=2;
if(temp1[j]=='{'||temp1[j]=='(')
j++;
do
{
if(temp1[j]==',')
j++;
k=0;
while(temp1[j]!=','&&temp1[j]!=')'&&temp1[j]!='}'&&temp1[j]!='\0')
{
temp[k]=temp1[j];
k++;
j++;
}
temp[k]='\0';
attcode=compare(temp);
f[fdcount].right[f[fdcount].rcount]=attcode;
f[fdcount].rcount++;
}while(temp1[j]==',');
}
cout<<"\nEnter an attribute whose closure is to be found\n";
gets(temp);
attcode=compare(temp);
closcount=1;
closure[0]=attcode;
getclosure();
cout<<"Closure of ";
puts(temp);
cout<<"\n";
for(i=0;i<closcount;i++)
{
puts(attr[closure[i]]);
}
getch();
}
No comments :
Post a Comment