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:
Schema : EMPLOYEE(empid,empname,dept,age,salary,experience)
Let the functional dependencies be as follows:
- empid->empname
- {age,experience}->salary
- empid->{age,dept}
- dept->experience
- 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.
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();
}
No comments:
Post a Comment