6.8.8.cpp

本代码包括函数最小覆盖算法（最小依赖）和无损分解的判断。

//algorithm 6.8.8
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;
//----------------------algorithm 6.6.13----------------
const int size = 1024;
struct Func	//函数依赖集，对于X->Y,X用数组X[size]来保存，Y用数组Y[size]来保存。
{
	Func()
	{
		for(int i=0;i<size;i++)
		{
			X[i]=Y[i]="";
		}
	}
	string X[size];
	string Y[size];

	int count;//用来计数，即有多少个函数依赖
}; //数据结构的定义 

void first_step(Func F,Func &H)
{
	H.count=0;
	for(int i=0;i<F.count;i++)
	{
		if(F.Y[i].length()>1)
		{	//Y[i]包含多个属性，则每个属性都形成H的一个函数依赖
			for(int j=0;j<F.Y[i].length();j++)
			{
				H.X[H.count]=F.X[i];
				H.Y[H.count]=F.Y[i].substr(j,1);
				H.count++;
			}
		}
		else
		{
			H.X[i]=F.X[i];
			H.Y[i]=F.Y[i];
			H.count++;
		}
	}
}//第一步
void print(list<char> L)
{
	list<char> :: iterator it;
	for(it=L.begin();it!=L.end();it++)
	{
		cout<<(*it)<<" ";
	}
	cout<<endl;

}

//对于X[I]->Y[I]，如果Y[I]已在X[i]的属性集合中，则返回false，即不加入，否则返回真，加入Y[I]。
bool not_exist(string y,list<char>front)
{
	
	list<char> :: iterator it;

	for(it=front.begin();it!=front.end();it++)
	{
		if(y[0]==(*it))
		{
			return false ;
		}
	}
	return true;
}
//判定x[i]是否被已存在的闭包所包含。
//即把x[i]中的每个元素都拿到闭包中去搜索。全部存在返回真，否则返回假。
bool X_exist(string x,list<char>front)
{
	    int i=0;
		while(i<x.length())
		{
			bool in = false;
			list<char> :: iterator it;
			for(it=front.begin();it!=front.end();it++)
			{
				if(x[i] == *it)
				{
					in=true;
				}
			}
			i++;
			if(in==false)
			{
				return false;
			}
		};
	return true;
}
//下面的函数实现属性集x关于函数依赖H的闭包 xF+ 
list<char> Set_Closure(string x,Func H)
{
	int i=0;
	string A[size];
	list<char>front,back;
	for(int t=0;t<x.length();t++)
	{
		front.push_back(x[t]);
	}//把x中所含有的单一属性都压入list中
	while( (front!=back) )
	{
		back = front;
		for(int i=0;i<H.count;i++)
		{	list<char> :: iterator it;
			for(it=front.begin();it!=front.end();it++)
			{
				if( ( X_exist(H.X[i],front) )&& not_exist(H.Y[i],front) )
				{
	
					front.push_back(H.Y[i][0]);	//如果X[I]->Y[I]，把Y[I]给装入属性集
					
				}
			}
		}

	};
	return front;
}
Func delete_elem(Func H,int i)
{
	    Func J;
		for(int j=0;j<i;j++)//两个for循环得到函数集J = {H- {其中一个函数依赖}}
		{
			J.X[j] = H.X[j];
			J.Y[j] = H.Y[j];
		}
		for(int j=H.count-1;j>i;j--)
		{
			J.X[j-1] = H.X[j];
			J.Y[j-1] = H.Y[j];
		}
		J.count = H.count-1;
		return J;
}

//第二步，删除非关键的函数依赖
void secend_step(Func &H)
{
	Func temp = H;
	for(int i=0;i<H.count;i++)
	{
		Func J;
		J=delete_elem( H, i);
		list<char>result;
		result = Set_Closure(H.X[i],J);

		list<char> :: iterator it;
		for(it=result.begin();it!=result.end();it++)
		{
			
			if((*it)==H.Y[i][0])
			{
				temp.X[i]="";
				temp.Y[i]="";
			}//表示删除函数依赖i后仍然可以推出 Y[i]，则说明x第i个函数依赖不是关键的 
		}

	}
	H=temp;

}
//重写==函数，只要result1，result2含有相同的元素就反回真。
bool operator==(list<char>result1,list<char>result2)
{
	list<char> :: iterator it1;
	list<char> :: iterator it2;
	for(it1=result1.begin();it1!=result1.end();it1++)
	{
		bool right = false;
		for(it2=result2.begin();it2!=result2.end();it2++)
		{
			if( (*it1)==(*it2) )
			{
				right =true;
			}
		}
		if(right == false)
		{
			return false;
		}
	}
	return true;
}

//第三步，对于左边可以减少属性元素，即对属性的闭包集无影响的依赖，用少的属性来代替。
void third_step(Func &H)
{
	Func H1 =H;
	Func H2 = H;
	for(int i=0;i<H.count;i++)
	{
		if(H.X[i].length()>1)
		{for(int j=0;j<H.X[i].length();j++)
		{
			
			string x =H.X[i];
			Func J  = H;
			J.X[i] = x.replace(j,1,"");//去除H.X[i]中的某一个元素
	
			list<char>result1,result2;
			result1 = Set_Closure(J.X[i],H);
			result2 = Set_Closure(J.X[i],J);
	
			if((result1==result2) &&(result2==result1) )
			{
			
				H.X[i] = x;
				j--;
			}
			
		}
		}
		
	}
		secend_step(H);
}

//第四步，对于左边相同的函数依赖，进行整合。
void forth_step(Func &H)
{
	for(int i=0;i<H.count;i++)
	{
		for(int j=0;j<H.count;j++)
		{
			if( (H.X[i]==H.X[j])&& (i!=j) )
			{
				H.Y[i]=H.Y[i]+H.Y[j];
				H.X[j]=H.Y[j]="";
			}
		}
	}
}

//去除空字符，并输出结果 
void print(Func H)
{
	for(int i=0;i<H.count;i++)
	{
		if(H.X[i]=="")
		{
			for(int j=i;j<H.count;j++)
			{
				H.X[j]=H.X[j+1];
				H.Y[j]=H.Y[j+1];
			}
			H.count--;
			i--;
		}
	}

	for(int i=0;i<H.count;i++)
	{
		cout<<H.X[i]<<" -> "<<H.Y[i]<<endl;
	}
}

//----------------------end of 6.6.13-------------------
struct heading{
       string vs;
       };//heading,此结构体也用来表示一个候选键 
struct tables{
       vector<heading>vt;
       };//代表集合S 
bool attrbelong(char s,heading h)
{
     int i;
     for(i=0;i<h.vs.length();i++)
     if(s==h.vs[i])return true;
     return false;
}//判断一个属性是否已经包含在头部中 
bool belong(heading h1,heading h2)
{
   int i;
   for( i=0;i<h1.vs.length();i++)
   {
      if(!attrbelong(h1.vs[i],h2))
      return false;
   }
   return true;
     
}//判断一个头部是否被另一个已经包含，若已经包含，则不加入S中，反之加入 
bool belongtoS(heading h,tables S)
{
     int i=0;
     for(i=0;i<S.vt.size();i++)
     if(belong(h,S.vt[i]))
     return true;
     return false;
}     
     
int main()
{
    Func H,F;
	F.count=1;
	int i,j;
	//用A表示instructor，B表示class_no,C表示class_room,D表示text 
	//唯一的一个候选键是AB 
	F.X[0]="B";		
	F.Y[0]="CD";
	first_step(F,H);//第一步 
	secend_step(H);//第二步 
	third_step(H);//第三步 
	forth_step(H);//第四步 
    cout<<"符合第三范式且保持函数依赖的无损连接算法（测试例子6.8.10）"<<endl;
	cout<<"最小函数依赖为："<<endl;
	print( H);//输出最小函数依赖 
	tables S,temp;
   	for(i=0;i<H.count;i++)
	{
		heading temp;
		string s1=H.X[i];
		string s2=H.Y[i];
		for(j=0;j<s1.size();j++)
		{
        char stemp=s1[j];
		temp.vs.push_back(stemp);
        }
		for(j=0;j<s2.size();j++)
		{
        char stemp=s2[j];
		temp.vs.push_back(stemp);
        }
		if(!belongtoS(temp,S))
		S.vt.push_back(temp);
	}
	heading c_keys;
    c_keys.vs="AB";
    if(!belongtoS(c_keys,S))
    S.vt.push_back(c_keys);
    cout<<"符合第三范式且保持函数依赖的无损连接分解结果是："<<endl; 
    for(i=0;i<S.vt.size();i++)
    {
     cout<<"heading of table"<<i+1<<endl;
     heading ht=S.vt[i];
     string st=ht.vs;
     for(j=0;j<st.size();j++)
     cout<<st[j]<<"  ";
     cout<<endl;
    }
	system("pause");
}