函数依赖及范式

1、函数依赖及范式函数依赖基本概念：函数依赖：FD（functiondependency），设有关系模式R（U）,X,Y是U的子集，r是R的任一具体关系，如果对r的任意两个元组t1，t2,由tX=t2X导致tY=t2Y,则称X函数决定Y,或Y函数依赖于X,记为X-YoX-Y为模式R的一个函数依赖。部分函数依赖：即局部依赖，对于一个函数依赖W-A,如果存在XW（X包含于W）有X-A成立，那么称W-A是局部依赖，否则称W-A为完全函数依赖。传递依赖：在关系模式中，如果Y-X,X-A,且X兴Y（X不决定Y）,炉X（A不属于X），那么称Y-A是传递依赖。函数依赖集F的闭包F+:被逻辑蕴涵的函数依赖的全体构

2、成的集合，称为F的闭包（closure）,记为F+o最小依赖集：如果函数集合F满足以下三个条件（1）F中每个函数依赖的右部都是单属性：（2）F中的任一函数依赖X-A，其F-X-A与F是不等价的；（3）F中的任一函数依赖X-A,Z为X的子集，（F-XA）1丿ZA与F不等价。则称F为最小函数依赖集合.记为Fmin。函数依赖的公理系统：设有关系模式R（U）,X,Y,乙W均是U的子集，F是R上只涉及到U中属性的函数依赖集，推理规则如下：自反律：如果皆X匚U,则X-Y在R上成立。增广律：如果X-Y为F所蕴涵，Z匚U,则XZ-YZ在R上成立。（XZ表示XUZ,下同）传递律：如果X-Y和Y-Z在R上成立，则

3、X-Z在R上成立。以上三条为Armstrong公理系统合并律：如果X-Y和X-Z成立，那么X-YZ成立。伪传递律：如果X-Y和WY-Z成立，那么WX-Z成立。分解律：如果X-Y和Z匚Y成立，那么X-Z成立。这三条为引理函数依赖推理规则系统自反律、增广律和传递律是完备的。_由自反律所得到的函数依赖均是平凡的函数依赖。_四种范式的含义：如果某个数据库模式都是第一范式的，则称该数据库模式是属于第一范式的数据库模式。如果关系樟式R为第一范式，并日R中每一个非主属性完全函数依赖干R的某个候选键.则称为第二范式模式。如果关系模式R是第一范式.日每个非主属性都不传递依赖干R的候选键.则称R为第三范式模式。若

4、关系模式R是第一范式.日每个属性都不传递依赖干R的候选键。这种关系模式就是BCNF模式。四种范式，可以发现它们之间存在如下关系：BCNF匚3NF匚2NF匚1NF1NFI消去非主属性对键的部分函数依赖2NFI消去非主属性对键的传递函数依赖3NFI消去主属性对键的传递函数依赖BCNF1.设有关系模型R(A,B,C,D,E),F是R上成立的函数依赖集，F=ABC-DE,BC-D,D-E,试问R达到第几范式，并说明理由。R属于1NF。由于候选键是ABC。而非主属性D和E部分函数依赖于候选键ABC,因此R不是2NF,只能是1NF。2.数据模型分析，关系模型R(U,F)U=ABCDEG,F=AD-E,AC

5、-E,CB-G,BCD-AG,BD-A,AB-G,A-C求此模型的最小函数依赖集。求出关系模式的候选码。此关系模型最高属于哪级范式。将此模型按照模式分解的要求分解为3NF。依照题意,得出：通过最小集求法:分解函数依赖的右部,F=AD-E,AC-E,BC-G,BCD-A,BCD-G,BD-A,AB-G,A-C消去左边的冗余属性：F=A-E,A-E,BC-G,BD-A,BC-G,BD-A,AB-G,A-C消去冗余的函数依赖：Fm=A-E,BC-G,BD-A,A-C也可以为：Fm=A-E,AB-G,BD-A,A-C候选码：BDR中每一个非主属性完全函数依赖于R的候选键BD；但C,G,E都传递依赖于R

6、的候选键BD,也就是说，R满足2NF的要求，而不满足3NF的要求。此关系模型最高属于2NF。(4)依据算法4.4R1：U1=ABDF1=BDAR2：U2=BCGF2=BCGR3：U3=ACEF3=A-C,A-E模式分解分解具有“无损连接性”分解要“保持函数依赖”分解既要“保持函数依赖”，又要具有“无损连接性模式分解试分析下列分解是否具有无损联接和保持函数依赖的特点设R(ABC),F1=A-B在R上成立，1=AB,AC首先，检查是否具有无损联接特点第1种解法-算法4.2:ABCABala2b13ACalb22a3ABCala2b13ala2a3(1)构造表(2)根据A-B进行处理结果第二行全是a行，因此分解是无损联接分解。第2种解法:(定理4.8)R1(AB)QR2(AC)=AR2-R1=B丁A-B,该分解是无损联接分解。然后，检查分解是否保持函数依赖R1(F1)=A-B，以及按自反率推出的一些函数依赖R2(F1)=按自反率推出的一些函数依赖F1被R1(F1)所蕴涵，所以该分解保持函数依赖。模式分解与范式的关系如果关系模式没有达到所需的范式，则需要模式分