数据库原理重点提示之函数依赖及范式

七、函数依赖及范式

函数依赖基本概念：

函数依赖：FD(function dependency)，设有关系模式R(U)，X，Y是U的子集， r是R的任一具体关系，如果对r的任意两个元组t₁,t₂,由t₁[X]=t₂[X]导致t₁[Y]=t₂[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的闭包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在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的某个候选键，则称为第二范式模式。
如果关系模式R是第二范式，且每个非主属性都不传递依赖于R的候选键，则称R为第三范式模式。
若关系模式R是第一范式，且每个属性都不传递依赖于R的候选键。这种关系模式就是BCNF模式。

四种范式，可以发现它们之间存在如下关系：
BCNF 数据库原理重点提示之函数依赖及范式

3NF

2NF

1NF

↓

消去非主属性对键的部分函数依赖

2NF

↓

消去非主属性对键的传递函数依赖

3NF

↓

消去主属性对键的传递函数依赖

BCNF

　范式举例

1. 设有关系模型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→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→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=ABD F1={BD→A}

R2：U2=BCG F2={BC→G}

R3：U3=ACE F3={A→C，A→E}　

模式分解

模式分解的三个准则：

分解具有“无损连接性”
分解要“保持函数依赖”
分解既要“保持函数依赖”，又要具有“无损连接性”

　模式分解举例

模式分解

试分析下列分解是否具有无损联接和保持函数依赖的特点：

设R(ABC)，F1={A→B} 在R上成立，ρ1={AB,AC}。

首先，检查是否具有无损联接特点：
第1种解法--算法4.2:

	A	B	C
AB	a1	a2	b13
AC	a1	b22	a3

A	B	C
a1	a2	b13
a1	a2	a3

(1) 构造表

(2)根据A→B进行处理

结果第二行全是a行，因此分解是无损联接分解。

第2种解法:(定理4.8)
　　R1(AB)∩R2(AC)=A
　　R2- R1=B
　　∵A→B,∴该分解是无损联接分解。

然后，检查分解是否保持函数依赖
　　π_R1（F1）={A→B，以及按自反率推出的一些函数依赖}
　　π_R2（F1）={按自反率推出的一些函数依赖}
　　F1被π_R1（F1）所蕴涵，∴所以该分解保持函数依赖。　

模式分解与范式的关系

如果关系模式没有达到所需的范式，则需要模式分解

模式分解的几个重要事实：