函数依赖及范式

《函数依赖及范式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、函数依赖及范式函数依赖基本概念：·函数依赖：FD(functiondependency)，设有关系模式R(U)，X，Y是U的子集，r是R的任一具体关系，如果对r的任意两个元组t1,t2,由t1[X]=t2[X]导致t1[Y]=t2[Y],则称X函数决定Y,或Y函数依赖于X，记为X→Y。X→Y为模式R的一个函数依赖。·部分函数依赖：即局部依赖，对于一个函数依赖W→A，如果存在XW(X包含于W)有X→A成立，那么称W→A是局部依赖，否则称W→A为完全函数依赖。·传递依赖：在关系模式中，如果Y→X，X→A，且XY（X不决定Y），AX（A不属于X）,那么称Y→A是传递依赖。·函数依赖集F的

2、闭包F+:被逻辑蕴涵的函数依赖的全体构成的集合，称为F的闭包(closure),记为F+。·最小依赖集：如果函数集合F满足以下三个条件(1)F中每个函数依赖的右部都是单属性；(2)F中的任一函数依赖X→A，其F-{X→A}与F是不等价的；(3)F中的任一函数依赖X→A，Z为X的子集，（F-{X→A}）∪{Z→A}与F不等价。则称F为最小函数依赖集合，记为Fmin。函数依赖的公理系统：   设有关系模式R(U)，X，Y，Z，W均是U的子集，F是R上只涉及到U中属性的函数依赖集，推理规则如下：·自反律：如果YXU,则X→Y在R上成立。·增广律：如果X→Y为F所蕴涵，ZU，则XZ→YZ在

3、R上成立。(XZ表示X∪Z，下同)·传递律：如果X→Y和Y→Z在R上成立，则X→Z在R上成立。以上三条为Armstrong公理系统·合并律：如果X→Y和X→Z成立，那么X→YZ成立。·伪传递律：如果X→Y和WY→Z成立，那么WX→Z成立。·分解律：如果X→Y和ZY成立，那么X→Z成立。这三条为引理   注意：·函数依赖推理规则系统(自反律、增广律和传递律)是完备的。·由自反律所得到的函数依赖均是平凡的函数依赖。四种范式的含义：·如果某个数据库模式都是第一范式的，则称该数据库模式是属于第一范式的数据库模式。·如果关系模式R为第一范式，并且R中每一个非主属性完全函数依赖于R的某个候选键

4、，则称为第二范式模式。·如果关系模式R是第二范式，且每个非主属性都不传递依赖于R的候选键，则称R为第三范式模式。·若关系模式R是第一范式，且每个属性都不传递依赖于R的候选键。这种关系模式就是BCNF模式。四种范式，可以发现它们之间存在如下关系：       BCNF3NF2NF1NF1NF↓消去非主属性对键的部分函数依赖2NF↓消去非主属性对键的传递函数依赖3NF↓消去主属性对键的传递函数依赖BCNF　范式举例1.设有关系模型R（A，B，C，D，E），F是R上成立的函数依赖集，F={ABC→DE，BC→D，D→E}，试问R达到第几范式，并说明理由。　   R属于1NF。由于候选键是

5、ABC。而非主属性D和E部分函数依赖于候选键ABC，因此R不是2NF，只能是1NF。　2.数据模型分析，关系模型R（U，F）U=ABCDEG，F={AD→E，AC→E，CB→G，BCD→AG，BD→A，AB→G,A→C}（1）求此模型的最小函数依赖集。（2）求出关系模式的候选码。（3）此关系模型最高属于哪级范式。（4）将此模型按照模式分解的要求分解为3NF。依照题意，得出：（1）通过最小集求法:·分解函数依赖的右部，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→

6、A，AB→G，A→C}·消去冗余的函数依赖：Fm={A→E，BC→G，BD→A，A→C}                 也可以为： Fm={A→E，AB→G，BD→A，A→C}（2）候选码：BD（3）R中每一个非主属性完全函数依赖于R的候选键BD；但C,G，E都传递依赖于R的候选键BD，也就是说，R满足2NF的要求，而不满足3NF的要求。此关系模型最高属于2NF。（4）依据算法4.4     R1：U1=ABDF1={BD→A}     R2：U2=BCGF2={BC→G}     R3：U3=ACEF3={A→C，A→E}　模式分解模式分解的三个准则：·分解具有“无损连接性”·

7、分解要“保持函数依赖”·分解既要“保持函数依赖”，又要具有“无损连接性”　模式分解举例模式分解试分析下列分解是否具有无损联接和保持函数依赖的特点：设R(ABC)，F1={A→B}在R上成立，ρ1={AB,AC}。首先，检查是否具有无损联接特点：第1种解法--算法4.2:　ABCABa1a2b13ACa1b22a3ABCa1a2b13a1a2a3(1)构造表(2)根据A→B进行处理结果第二行全是a行，因此分解是无损联接分解。第2种解法:(定理4.8)　　R1(AB)∩R