属性集合的闭包
输入:
属性集合{A1,A2,…,An},FD集合S
输出:
闭包{A1,A2,…,An}+



方法:

可以分解S中的FD,使每个FD的右边只有一个属性
设集合X是为闭包,初始化为{A1,A2,…,An}.
反复寻找形如 B1,B2,…,Bn->C,使得B1,B2,…,Bn在X中，而C不在X中,将C加入到X中,重复这个过程.
当没有新元素添加时,算法结束,返回X作为结果集合.


计算最小函数依赖集


方法:

利用分解规则,将所有函数依赖变成右边都是单个属性的函数依赖.
去掉F中多余的函数依赖(因为最小函数依赖集中删除任一FD,集合不再是基本集)
去掉各函数依赖左边多余的属性(因为最小函数依赖集从其左边删除一个或多个属性,集合不再是基本集)


函数依赖集的投影
输入:
关系R和通过投影R1=πL®计算得到的关系R1,以及在R中成立的FD的集合S
输出:
在R1中成立的FD集合



方法:

令T为最终输出的FD集合,初始化T为空集
对于R1的属性集合的每一个子集X,计算X+.该计算依据FD集合S,可能会涉及一些在R模式中而不在R1模式中的属性.对于所有在X+中且属于R1的属性A,将所有非平凡的FD X -> A添加到T中.
经过上面的步骤,T是在R1中成立的FD基本集,但可能还不是最小化基本集.通过下面的方法对T进行修改来构造最小化基本集:

如果T中的某个FD F能从T中其他FD推断出来，则从T中删除F．
设Y -> B是T中的一个FD,Y至少有两个属性,从Y中删除一个属性并记为Z.如果Z -> B能从T中的FD推断出来,则使用Z -> B代替Y -> B.
重复以上步骤,直到T不再变化



例题:

设有关系模式R(A,B,C,D,E),F是R上成立的函数依赖集,F={AD->B,AC->E,CD->B,B->A,E->D},把关系R分解成S(A,B,C)和其它关系,请给出S中成立的函数依赖并给出S中的FD集合的最小化基本集


BCNF分解算法
输入:
关系R0和其上的函数依赖集S0
输出:
由R0分解出的关系集合,每个关系均属于BCNF



方法: 下面的方法递归进行,初始R=R0,S=S0

检验R是否属于BCNF.如果是,直接返回R作为结果
如果存在BCNF违例,假设为X->Y.先计算属性X的闭包,选择R1=X+作为一个关系模式,令R2包含属性X以及那些不在X+中的属性.
计算S0在R1和R2的函数依赖集投影,分别记为S1和S2.
使用本算法递归分解R1和R2,返回这些分解得到的结果集合.




总结
BCNF分解算法从违反BCNF的FD开始分解.

对一个关系进行BCNF分解,则原始关系可以通过自然连接来精确的恢复.


具有无损链接和依赖保持性质的3NF综合算法
输入:
关系R和其上成立的函数依赖集F
输出:
由R分解出的关系集合,其中每个关系均属于3NF.分解具有无损连接和依赖保持性质



方法:

找出F的一个最小基本集记为G．
对于G中的每一个FD X -> A ,将XA作为分解出的某个关系的模式.
如果第2步分解出的关系的模式均不包含R的超键,增加一个关系,其模式为R的任何一个键．


chase 算法
作用
用来检验一个关系在其分解上的投影是否可以通过重新连接来恢复原关系.
无损链接的定义
将分解的关系自然连接后的每个元组都属于R,称为分解包含无损链接



方法:

一、闭包的计算
二、候选码的相关计算
三、函数依赖集的等价
四、函数依赖集的最小覆盖的计算
一、闭包的计算
计算X的闭包：
首先XF+=X
之后对于F中的每个函数依赖，A->B，只要A在XF+中，那么XF+就并上B，直到XF+不再改变为止，得到的结果就是X的闭包。




二、候选码的相关计算
1、得到一个候选码
首先令K=U，然后逐个删除K中的元素，如果删除之后的K在F上的闭包是U，那么K=K-X（X为删除的元素），直到不能再删除元素为止，最后得到的就是一个候选码（这个方法其实就是从候选码与函数依赖之间的关系得到的，也就是说如果是候选码的话，那么就可以函数决定所有的属性）。

2、得到所有的候选码

可以重复使用得到一个候选码的方法直到得到所有的候选码，还有直接求出所有的候选码的方法：

首先求出一个候选码，然后得到该候选码中的所有的双部属性，对于其每一个双部属性，如果F中存在函数依赖X->Y，其中有双部属性A属于Y(注意是属于，并不是等于，只要属于就可以了)那么就用X代替该候选码中的A得到新的候选码，知道不能得到新的候选码。
三、函数依赖集的等价
如果F=G，那么就是F属于G的闭包，G属于F的闭包。
四、函数依赖集的最小覆盖的计算
函数依赖集的最小覆盖应该满足的条件是：

单属性化：也即是说如果函数依赖集的右边是多个属性的话，就要分开，直接左边的属性集保持不变，右边拆开就可
即约化：也就是说在函数依赖中左边有多个属性，即约化就是为了将左边的属性集合简化，方法就是通过不断删除元素，计算闭包，注意即约化计算闭包的时候考虑的函数依赖集是F，也就是说包括要进行既约的这个函数依赖也在内
无冗余：将某个函数以来删除，然后看其左边的属性集的闭包在新的函数依赖集G（也就是在F的基础上去掉删除的函数依赖得到的新的属性集合）上的闭包是否包括删除的函数依赖的右边的部分，如果包括，那么就说明该函数依赖是冗余的，将其删除。（注意的是在计算闭包的时候，参考的函数依赖集合是G，也就是在F的基础上删除被删除的函数依赖的新的函数依赖集合)
在求解函数依赖集的最小覆盖的时候，一般是先单属性，然后是既约化，最后是无冗余化，

并且既约化和无冗余化以依赖的函数依赖集合是不同的。

满足第三范式3NF的函数依赖保持分解算法
----------------------------------------------------------------------------------------------------------------------------------------------------------

输入：关系模式R和函数依赖集合F
输出：结果为满足第三范式的一个依赖保持的分解 
条件：
1.如果R中有某些属性与F的最小覆盖Fmin中的左边右边都没有关系，则这个（些）属性构成一个关系模式。如果没有就进行2 
2. 如果Fmin中有一个函数依赖涉及R中的所有属性，则输出R。否则，进行3
3.对于Fmin，其中有X->Ai这样的函数依赖，则添加XAi到一个分解集合p中，但是当X->A1,X->A2,...，X->An时(即X可与决定Fmin中多个属性)，用XA1A2...An来替换之前的XAi 
----------------------------------------------------------------------------------------------------------------------------------------------------------
回顾一下什么是1NF,2NF,3NF以及BCDF:http://blog.csdn.net/scnujack/article/details/6539642
----------------------------------------------------------------------------------------------------------------------------------------------------------

程序:

//满足第三范式3NF的函数依赖保持分解算法
//输入：关系模式R和函数依赖集合F
//输出：结果为满足第三范式的一个依赖保持的分解 
//条件：1.如果R中有某些属性与F的最小覆盖Fmin中的左边右边都没有关系，则这个（些）属性构成一个关系模式。如果没有就进行2 
//2. 如果Fmin中有一个函数依赖涉及R中的所有属性，则输出R。否则，进行3
//3.对于Fmin，其中有X->Ai这样的函数依赖，则添加XAi到一个分解集合p中，但是当X->A1,X->A2,...，X->An时(即X可与决定Fmin中多个属性)，用XA1A2...An来替换之前的XAi 
#include <iostream>
#include <string>
using namespace std;

struct FunctionDependence//函数依赖 
{
	string X;//决定因素 
	string Y;	
};

struct Hash//散列 
{
	int num;//用来记录字符串出现的次数 
	string s; 
};

void Init (FunctionDependence FD[],int n)
{
	//函数依赖关系初始化
	int i;
	string x,y;
	cout<<"请输入F中的函数依赖（决定因素在左，被决定因素在右）"<<endl; 
	//输入函数依赖集合F 
	for (i=0;i<n;i++)
	{		
		cin>>x>>y;
		FD[i].X=x;
		FD[i].Y=y;	
	} 
	cout<<"函数依赖集合"; 
	cout<<"F={" ;
	for (i=0;i<n;i++)
	{
		//显示已知的函数依赖集合F 
		cout<<FD[i].X<<"->"<<FD[i].Y;
		if (i<n-1)cout<<", ";	
	} 
	cout<<"}"<<endl; 
}
bool CharIsIn(char f, string zz)
{
	bool flag = false;
	int len = zz.length();
	int k = 0,  count1 = 0;
	for (k = 0;k<len;k++)
	{
			if (f == zz[k])
			{
				flag= true;;
			}
	}
	return flag;
}
string CutAndSort(string mm)//将最终得到的闭包去除其中重复的元素，并且进行排序 
{
	int size=mm.length();
	string ss="\0"; 
	int kk=0,ii=0;;
	int a[200]={0};//用来记录各个命题出现的次数
	for(kk=0;kk<size;kk++) 
	{
		a[(int)mm[kk]]++;//强制转换类型，储存各个因素的次数 
	}

	for (ii=0;ii<200;ii++)
	{
		if (a[ii]>=1)
		ss+=(char)ii;
	} 
	return ss;
} 

bool IsIn(string f,string zz)//能够判断F中决定因素f里所有的因素是否在X中，但这样可能导致结果出现重复 
{
	bool flag1=false;
	int len1=f.length();
	int len2=zz.length();
	int k=0,t=0,count1=0;
	for (k=0;k<len1;k++)
	{
		for (t=0;t<len2;t++)
		{
			if (f[k]==zz[t])
			{
				//flag1=true;break;
				count1++;
			}
		}
	}
	if (count1==len1)
	{
		flag1=true;
	}
	else flag1=false;
	return flag1;
}
string X_Fn(FunctionDependence FD[],int n,string &xx)  
{  
    string yy=xx;  
    for (int i=0;i<n;i++)  
    {  
        if (IsIn(FD[i].X,yy)==true)  
        {  
            xx+=FD[i].Y;  
        }         
    }  
    yy=CutAndSort(yy);  
    xx=CutAndSort(xx);    
    if (xx!=yy)  
    {  
        X_Fn(FD,n,xx);//递归   
    }  
    return xx;   
}  

string FD_Fun(FunctionDependence FD[],int n,string xx)
{
    //求X关于F的闭包   
	return X_Fn(FD,n,xx); 
}

//从函数依赖集F中删除某个依赖关系 left->right
void  Cut(FunctionDependence FD[],int n,string left,string right,FunctionDependence Dyna[])
{	
	int i=0,j=0,count=0;
	for (i=0;i<n;i++)
	{
		if((FD[i].X==left)&&(FD[i].Y==right))
		{
		}
		else
		{
			Dyna[count].X=FD[i].X;
			Dyna[count].Y=FD[i].Y;
			count++;
		}
	}
	cout<<"去掉"<<left<<"->"<<right;
	cout<<"后的函数依赖集F："<<endl;
	cout<<"F={" ; 
	for(j=0;j<count;j++)
	{
		cout<<Dyna[j].X<<"->"<<Dyna[j].Y;
		if (j<count-1)cout<<",";
	}
	cout<<"}"<<endl;	
	
}

bool RA(FunctionDependence a,FunctionDependence b)//判断冗余属性
{
	if ((IsIn(a.X,b.X)==true)&&(a.Y==b.Y)) 
	{
		return true;
	}
	else return false;
} 

string StringCutChar(char f, string zz) //从中去掉一个属性
{ 
    int len = zz.length();  
    int k = 0;
    string tt;
    for (k = 0;k<len;k++)  
    {  
            if (f == zz[k])  
            {  
            }
			else 
			{
				tt+=zz[k];
			}  
    } 
	return tt;
} 

FunctionDependence Dyna[200]; 
int Fmin_Size;
void CutSameFD(FunctionDependence FD[],int n)//除去重复的函数依赖 
{
	FunctionDependence Dyna1[n+20];
	FunctionDependence Dyna2[n+20];

	int i=0,j=0,k=0,count=0,count1=0;//count2=0;
	for (i=0;i<n;i++)
	{
			for (j=0;j<count;j++)
			{
				if((FD[i].X==FD[j].X)&&(FD[i].Y==FD[j].Y))//有函数依赖重复
				{
					break;//跳过当前的函数依赖 
				} 
			}
			if (j==count)
			{
				Dyna1[count].X=FD[i].X;
				Dyna1[count].Y=FD[i].Y;
				count++; 
			}			
	}
	cout<<"去掉重复后的函数依赖集F="<<"{";
	for (k=0;k<count;k++)
	{
		//去掉重复后的函数依赖集
		cout<< Dyna1[k].X<<"->"<<Dyna1[k].Y;
		if (k<count-1)cout<<",";
	}
	cout<<"}"<<endl;
	
	for (k=0;k<count;k++)
	{
		//从第一个函数依赖X→Y开始将其从F中去掉，
		Cut( Dyna1,count,Dyna1[k].X,Dyna1[k].Y,Dyna2);
		//然后在剩下的函数依赖中求X的闭包X+，看X+是否包含Y
		cout<<Dyna1[k].X<<"关于F的闭包：";
		cout<<FD_Fun(Dyna2,count,Dyna1[k].X);//在剩下的函数依赖中求X的闭包X+
		if(IsIn(Dyna1[k].Y,FD_Fun(Dyna2,count,Dyna1[k].X))==true)//在闭包中 
		{
			cout<<"\n"<<Dyna1[k].X<<"->"<<Dyna1[k].Y<<"冗余"<<endl;
		}
		else 
		{
			cout<<"\n"<<Dyna1[k].X<<"->"<<Dyna1[k].Y<<"不冗余"<<endl;			
			Dyna[count1].X=Dyna1[k].X;
			Dyna[count1].Y=Dyna1[k].Y;
			count1++;
		}
	}
	cout<<"\n去冗余函数依赖后的函数依赖集F={";
	for (i=0;i<count1;i++)
	{
			cout<<Dyna[i].X<<"->"<<Dyna[i].Y;
			if (i<count1-1)cout<<",";
	} 
	cout<<"}"<<endl;
	//去掉冗余属性
	for (i=0;i<count1;i++)
	{
		for (j=0;j<Dyna[i].X.length();j++)
		{
			//X-Bj
			string temp_x=StringCutChar((Dyna[i].X)[j],Dyna[i].X);
			if (IsIn(Dyna[i].Y,FD_Fun(Dyna,count1,temp_x))==true)//即X->A,X=B1B2..Bm,A属于{X去掉某个其中的属性Bi的闭包} 
			{
				Dyna[i].X= temp_x;
			}
		}
			
	}
	//求得最小覆盖 
	cout<<endl; 
	cout<<"最小覆盖Fm="<<"{";
	for (k=0;k<count1;k++)
	{
			cout<<Dyna[k].X<<"->"<<Dyna[k].Y;
			if (k<count1-1)cout<<",";		
	} 
	cout<<"}"<<endl;
	Fmin_Size=count1;
} 

void SingleR(FunctionDependence FD[],int n) //使F所有函数依赖的右部分解成单一属性 
{
	int lengthR=0,i=0,j=0,k=0;
	static int D=n;
	int count=0;
	FunctionDependence  DynamicFD[D+20];//建立新的空间来存储所有的函数依赖 
	cout<<"右侧属性单一化后的函数依赖集F为："<<endl;
	cout<<"F={" ;
	for (i=0;i<n;i++)
	{
			lengthR=(FD[i].Y).size();			
			for (j=0;j<lengthR;j++)//将右部分解成单一属性，添加到属性集合的后面 
			{
				DynamicFD[count].X=FD[i].X;
				DynamicFD[count].Y= (FD[i].Y)[j];
				count++;
			}
			
	}
	for (k=0;k<count;k++)
	{
		cout<<DynamicFD[k].X<<"->"<<DynamicFD[k].Y;	
		if (k<count-1)cout<<", ";	
	}
	
	cout<<"}"<<endl; 
	D=count; 
	CutSameFD(DynamicFD,D);


}

bool DinamicCompare(string a,Hash b[],int n)
{
	int count_dc=0;
	for (int i=0;i<n;i++)
	{
		if (a!=b[i].s)count_dc++;
	}
	if (count_dc==n) return true;
	else return false;
}

void Fmin(FunctionDependence FD[],int n)//求最小覆盖 
{
	Init(FD,n);	
	SingleR(FD,n);	
	
}

int main()
{
	cout<<"请输入关系模式R（中间无间隔，无回车）"<<endl; 	
	string A;
	cin >> A;
	int lengthR = A.length();
	cout<<"关系模式R={";
	for (int i = 0;i<lengthR;i++)
	{
		cout << A[i] ;
		if (i<lengthR-1)cout<<",";
	}
	cout<<"}"<<endl;
	
	int N;
	cout<<"请输入F中函数依赖的组数:"; 
	cin>>N;
	//第一步：求出F的最小覆盖 
	FunctionDependence fd[N];
	//FunctionDependence Dyna3[N+20];
	Fmin(fd,N);

	//第二步：如果R中有某些属性与F的最小覆盖Fmin中的左边右边都没有关系，则这个（些）属性构成一个关系模式。如果没有就进行2 
	
	int count_i = 0,count=0;
	string R[lengthR+20];

	Hash left_type[lengthR+20];//用来储存Fmin的不同决定因素 
	int temp1=0,l_type=0,l_num=0;
	for (int n=0;n<Fmin_Size;n++)
	{
		if (DinamicCompare(Dyna[n].X,left_type,l_type)==false)//和之前的有相等的，跳过 
		{
			continue;
		}
		for (int nn=0;nn<Fmin_Size;nn++)
		{
			if (Dyna[n].X==Dyna[nn].X)
			{
				l_num++;
				left_type[l_type].s=Dyna[n].X;
				left_type[l_type].num=l_num;//出现的次数 
			}
		}
		l_type++;
		l_num=0;
	} 
	int k=0;
	bool my_flag=0;
	for (int i = 0;i<lengthR;i++)
	{
		while (Dyna[k].X!="\0")
		{
				if (CharIsIn(A[i],Dyna[k].X)==false&&CharIsIn( A[i], Dyna[k].Y)==false)
				{
					count_i++;
				}
				else if (CutAndSort(Dyna[k].X+Dyna[k].Y)==CutAndSort(A))
				{
					cout<<"分解就是A本身"<< CutAndSort(A)<<endl;
					my_flag=1;break;
				}
				k++;	
		} 	
		if (count_i==Fmin_Size)	
		{
			R[count]=A[i];
			count++;			
		}
		if (my_flag==1)break;
	}
	//3.对于Fmin，其中有X->Ai这样的函数依赖，则添加XAi到一个分解集合p中，但是当X->A1,X->A2,...，X->An时(即X可与决定Fmin中多个属性)，用XA1A2...An来替换之前的XAi 
	if (my_flag==0)
	{
			for (int m=0;m<l_type;m++)
			{
				R[count]=left_type[m].s;//+Dyna[m].Y;
				for (int aa=0;aa<Fmin_Size;aa++)
				{
					//if (aa==m)continue;			
					if (left_type[m].s==Dyna[aa].X)
					{
						R[count]+=Dyna[aa].Y;						
					}
				}
				count++;
			}
			cout<<"满足第三范式3NF的函数依赖保持分解p={";
			for (int bb=0;bb<count;bb++)
			{
				cout<<R[bb];
				if (bb<count-1)cout<<",";
			} 
			cout<<"}"<<endl;
	}
	
	return 0;
} 





其中求最小覆盖等函数，沿用或者部分改变自之前编写的函数，如有疑问可以查看之前的文章。

数据库设计时要满足规范化这个道理大家都非常清楚，甚至有数据库的三范式, 好吧, 这有点让我想起了机器人的三定律.但是否数据的规范化程度越高越好呢？这还是由实际需求来决定。

因为规范化越高，那么产生的关系就越多，关系过多的直接结果就是导致表之间的连接操作越频繁，而表之间的连接操作是性能较低的操作，直接影响到査询的速度，所以，对于査询较多的应用，就需要根据实际情况运用逆规范化对数据进行设计，通过逆规范化来提高査询的性能。

例如，移动电话的用户每月都会査询自己的账单，账单信息一般包含用户的名字和本月消费总金额，设想一下，如果用户的姓名和属性信息存放在一个表中，假设表名为A,而用户的 编号和他对应的账单信息存放在另外一张B表中，那么，用户每次查询自己的月账单时，数据库査询时都要进行表连接，因为账单表B中并不包含用户的名字，所以必须通过关联A表取 过来，如果在数据库设计时考虑到这一点，就可以在B表增加一个冗余字段存放用户的名字， 这样在査询账单时就不用再做表关联，可以使査询有更好的性能。
反规范的好处是降低连接操作的需求、降低外码和索引的数目，还可能减少表的数目，相 应带来的问题是可能出现数据的完整性问题。加快查询速度，但会降低修改速度。因此，决定 做反规范时，一定要权衡利弊，仔细分析应用的数据存取需求和实际的性能特点，好的索引和 其他方法经常能够解决性能问题，而不必采用反规范这种方法。

在进行反规范操作之前，要充分考虑数据的存取需求、常用表的大小、一些特殊的计算（例 如合计）、数据的物理存储位置等。常用的反规范技术有增加冗余列、增加派生列、重新组表 和分割表。

增加冗余列：指在多个表中具有相同的列，它常用来在查询时避免连接操作。
增加派生列：指增加的列来自其他表中的数据，由其他表中的数据经过计算生成。增 加的派生列其作用是在查询时减少连接操作，避免使用集函数。
重新组表：指如果许多用户需要查看两个表连接出来的结果数据，则把这两个表重新 组成一个表来减少连接而提高性能.
另外，逆规范技术需要维护数据的完整性。无论使用何种反规范技术，都需要一定的管理 来维护数据的完整性，常用的方法是批处理维护、应用逻辑和触发器。 

1.  批处理维护是指对复制列或派生列的修改积累一定的时间后，运行一批处理作业或存 储过程对复制或派生列进行修改，这只能在对实时性要求不高的情况下使用. 

2. 数据的完整性也可由应用逻辑来实现，这就要求必须在同一事务中对所有涉及的表进 行增、删、改操作.用应用逻辑来实现数据的完整性风险较大，因为同一逻辑必须在所有的应 用中使用和维护，容易遗漏，特别是在需求变化时，不易于维护。 

3. 另一种方式就是使用触发器，对数据的任何修改立即触发对复制列或派生列的相应修 改，触发器是实时的，而且相应的处理逻辑只在一个地方出现，易于维护•一般来说，是解决 这类问题比较好的办法。