Algorithm, C and C++ Programs to find Closure From Functional Dependencies

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)

how to Find closure of an attribute from given set of functional dependencies using c program diagram block picture representation algorithm C C++ program explained with examples and pictorial representaion tutorial article chapter candidate key employee

diagrammatic representation of functional dependencies

Let the functional dependencies be as follows:

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();
 }

My online Text