第4章 关系模式设计理论

第4章关系模式设计理论主要内容：重点：

●函数依赖

●模式的范式化解决的主要问题：从理论上来讲，如何设计一个比较好的关系模式的集合？●数据依赖（函数依赖、关键字、函数依赖的推理规则）●关系模式的分解（两种特性：无损联接性和保持依赖性）●模式的范式理论（1NF-4NF）其中：数据依赖是基础。即：范式理论和关系模式的分解都是建立在数据依赖的概念基础之上。

4.1关系模式使用中的异常问题例:设有关系模式R（TNAME，ADDR，C#，CNAME）（分别为：教师名，地址，课程号，课程名）其关系如下：TNAMEADDRC#CNAMEt1t1t1t2t2t3a1a1a1a2a2a3c1c2c3c4c5c6n1n2n3n4n5n6R现实世界的事实可知：一个教师只有一个地址一个教师可讲若干课程每门课程只有一个教师任教R的侯选关键字为:(TNAME,C#)在使用过程中会存在以下问题：（1）数据冗余：当一个教师若讲多门课程，则其地址值会重复存储多次。数据冗余：同一个数据重复被存储在DB不同的位置中。

数据冗余会引起：①浪费存储空间；②造成修改数据不一致性。（2）更新操作异常①修改异常：由数据冗余引起的。如上例：t1教师讲了三门课，其地址值a1重复存储了三次；若t1搬家，则它的地址值必须修改三处值，若只修改一处，则会产生修改不一致性。②插入异常：指该插入的数据而不能插入到关系中。如：新增加一个教师，但尚未分配讲课任务，则不能将其姓名和地址值插入到R中。原因：R的候选关键字（TNAME，C#）中，C#为空值。即：候选关键字中主属性为空或部分为空的元组违反了实体完整性原则。③删除异常：指不该从关系中删除的数据被删除了。如：若要把原来上过课，但目前未上课的教师的所有元组删去，则将该教师的姓名和地址信息也从R中删除了。什么原因使得关系产生操作异常和数据冗余呢？原因：关系模式中的属性之间存在依赖问题；这就是引入属性之间函数依赖的原因。现在采用函数依赖的概念，利用分解方法，将R分解两个等价的关系：R1（TNAME，ADDR）R2（C#,CNAME,TNAME）TNAMEADDRt1t2t3a1a2a3数据冗余大减，上述情况的异常消除。关系模式如何分解；分解到一个什么程度为好？将是本章讨论的问题。R1R2C#CNAMETNAMEc1c2c3c4c5c6n1n2n3n4n5n6t1t1t1t2t2t3

4.2函数依赖一、函数依赖（FunctionalDependency

简称FD）的定义定义1：设有关系模式R（U），U={A1，A2，…，An}，，若对R的所有具体关系r都存在：对于每一个X值，都有唯一的Y值与之对应，则称X函数决定Y；或说Y函数依赖于X，记为：X→Y如：学号→姓名，姓名→年龄，姓名→性别。定义2：设有关系模式R(A1,A2,…,An),X和Y均为{A1,A2,…,An}的子集，r是R的任一具体的关系(R-型,r值),t1和t2是r中任意两个元组,若由t1[X]=t2[X]导致t1[Y]=t2[Y],则称X函数决定Y,或说Y函数依赖于X,记为：X→Y

注：(1)FD是对R一切可能的当前值r定义的，不是针对某个特定关系。(2)FD是语义范畴的概念，只有通过属性之间的语义来确定是否存在函数依赖关系，不能用数学方法推导或证明。它是现实世界中属性之间客观存在或设计者人为强制相结合的产物。例:若设计者限定：无同名同姓；则：姓名→年龄（反之：年龄

姓名），若有同名同姓：则，姓名

年龄。(3)

X→Y中，X称为决定的因素，只要X取一个值，则有Y唯一的值与之对应。二、函数依赖与属性间联系的关系设关系模式R，，则：(1)如果X,Y之间是1:1联系，则存在:X→Y和Y→X，即X,Y相互函数依赖记为。(2)如果X,Y之间是m:1联系，则存在

X→Y

,YX。(3)如果X,Y之间是n:m

联系，则X,Y之间不存在函数依赖，即，.结论：根据关系r当前值，可从属性间的联系入手来决定函数依赖是否存在。例：已知关系r如下ABCDEa1a1a2a2b1b2b1b1c1c2c3c4d1d2d3d3e1e1e1e1r下列函数依赖中，关系r满足哪些依赖？a、A→Bb、(A,B)→Dc、C→(B,D,E)d、E→Ae、A→E

三、关键字（键、码）用FD概念精确定义关键字定义：设关系模式R（A1，A2，…，An），F是R上的函数依赖集，X是（A1，A2，…，An）的一个子集，如果：（1）X→A1，A2，…，An且（2）在X中不存在真子集Y，使得Y→A1，A2，…，An成立，则称X是R的候选关键字。注：条件（1）表示X能唯一决定一个元组。(唯一性)条件（2）表示X是满足（1）而无多余的属性集。（无多余性）例：关系模式R（学号，姓名，性别，年龄）中，按语义：学号→姓名，学号→性别，学号→年龄

∵学号→（学号，姓名，性别，年龄）

∴学号是R一个候选关键字。也可说明：（学号，姓名）也可决定R中的全部属性，但（学号，姓名）不是候选关键字。

∵（学号，姓名）存在真子集：“学号”可以决定全部属性；“姓名”属性多余。说明：主属性：包含在候选关键字中的属性。非主属性：不包含在候选关键字中的属性。四、函数依赖的分类

根据不同性质，函数依赖分类：完全函数依赖部分函数依赖传递函数依赖1、完全函数依赖与部分函数依赖定义：在关系模式R（U）中，如果X→Y，并且对X的任何一个真子集X′，都有则称Y完全函数依赖于X，记作。如果对X某个真子集X′,有X′→Y，则称Y对X的函数依赖是部分的函数依赖，记作：。例：关系模式SC(学号，课程号，成绩)中，显然：

学号

成绩，课程号

成绩，而：(学号，课程号)→成绩,可见：(学号、课程号)是候选关键字：学号，课程号是主属性；成绩为非主属性。又如：部分函数依赖的例子f

注：只有决定因素是组合属性，才存在部分函数依赖，当决定因素是单属性时，只能是完全函数依赖。TNAMEADDRC#CNAMEt1t1t1t2t2t3a1a1a1a2a2a3c1c2c3c4c5c6n1n2n3n4n5n6前面的例子，如右边的关系：主键：（TNAME,ADDR）因为：C#→CNAME,TNAMECNAME∴（TNAME,ADDR）→CNAMEP2、传递函数依赖定义：在关系模式R（U）中，如果，，且，,,则称Z传递函数依赖于

，记作:。注：当条件不成立时，即，则，实际上是直接函数依赖而非传递函数依赖。例：在关系模式R（学号，姓名，系名，系主任名）中。学号→系名，系名学号，系名→系主任名，则有：学号→系主任名。另外，学号→姓名，设无同名同姓：姓名→系名，姓名→学号，则有：学号→系名，是完全函数依赖。t五、函数依赖的逻辑蕴涵有时需要从一些已知的FD去判断另一些FD是否成立。如：已知F={A→B，B→C}在模式R中成立，那么A→C在R中是否成立。这个问题称为FD的逻辑蕴涵问题。定义：设F在关系R上成立的函数依赖集,X→Y是一个其他的FD(X⊆R,Y⊆R)。如果从F中的函数依赖能推出X→Y，则称F逻辑蕴涵X→Y，记为：F|＝X→Y。定义：被F函数蕴涵的函数依赖的全体构成的集合称为F的闭包(closure),

记为：F+

={x→Y|F⊨X→Y}一般，FF+，若F=F+

则称F是函数依赖的完备集。值得注意：依据F计算F+

是很麻烦的，即使F不大，F+

也可能很大。如：有关系R(X,Y,Z)其函数依赖集F={X→Y,Y→Z}则共有43个依赖这些函数依赖怎么出来？待学习了函数依赖的推理规则，再回答此问题。

4.2.4FD公理目的：确定函数依赖的逻辑蕴涵。即从给定的F中的函数依赖，推出F+中的函数依赖。也就是说给定了F和X,Y，判断是X→Y否在F+中。

为此，要有一套推理规则。一、Armstrong公理

设有关系R(A1,A2,…,An)和属性全集U=A1A2…AnX，Y，Z，W均是U的子集；F是U上的一个函数依赖集，推导规则是：A1

自反性(Reflexivity)：若，则F逻辑蕴涵

X→Y。（平凡的函数依赖）A2

增广性(Augmentation)：若F中X→Y成立，则F逻辑蕴涵:XZ→YZ。A3传递性(Transitivity)：若F中X→Y,Y→Z成立,则F逻辑蕴涵:

X→Z。例：设R(C,S,Z)，其中：C为城市名，S为街名，Z为邮编，给定F={CS→Z,Z→C}

即函数依赖图如下：CSZ由Armstrong公理，有(1)Z→C(已知)说明：Z→C逻辑蕴涵F+中。(2)SZ→CS(由(1)和A2增广性)说明:SZ→CS逻辑蕴涵在F+中。(3)CS→Z(已知)(4)CS→CSZ(由(3)和A2增广性)说明：CS→CSZ在F+，也说明CS是R的一个候选关键字。(5)SZ→CSZ(由(2)和A2增广性，或由(2),(4)和A3传递性)说明：SZ→CSZ在F+中，也说明SZ是R的另一个候选关键字。注：可以证明候关键字：CS和SZ中没有多余的属性存在。说明：①

通过公理可以推出F中的隐含的FD，尤其可推出关系R的候选关键字。②

能否保证由公理推出的函数依赖都是正确的，即所推出的函数依赖都是否都属于F+？

——公理的正确性。正确性：只要F的FD为真，由公理推出的FD也为真，则推出的FD都由F+逻辑蕴涵。若公理正确，求F+，则可根据F通过公理推出所有的函数依赖。③属于F+中函数依赖是否都能够由公理通过F中的FD推出？——公理完备性。

推论：由阿氐公理可以得出如下推论：(1)合并规则：若，成立，则成立(2)分解规则：若成立，则，成立(3)伪传递规则：若，成立，则成立证明：用公理证明(1)∵(已知)(2)∵ (3)∵(已知)∴(公理A2)

∴(公理A1)

∴(公理A2)

又∵(已知)同理(公理A1)∵(已知)∴(公理A2)∵(已知)∴(公理A3)∴(公理A3) ∴(公理A3)

同理(公理A3)二.推论根据推论中(1)和(2)合并和分解规则：得出推论：若Ai(i=1,2,…,n)是关系模式R的属性集则X→A1A2…An成立的充分必要条件是X→Ai(i=1,2,…,n)均成立。例：判断下列推论是否正确，若正确给出相关证明；若错误，试举出一反例说明(1)如果AB→C，则B→C(2)如果AB→C，则A→B,或A→C(3)如果A→B并且BC→D,则ABC→D解：(1)错误 (2)错误 (3)正确ABC010001ABC000101RR∵A→B∴ABC→BC又∵BC→D∴ABC→D（公理A3）R满足AB→C但B

C;R满足AB→C但AC，AB说明：①

通过规则A1，得出平凡的FD概念：对于函数依赖X→Y,若,则称X→Y是平凡的函数依赖；若，X→Y则为非平凡的FD。如：A→A,A→Φ是平凡FD.平凡FD总是成立的，对A的语义无影响，对模式设计也没有影响。一般不考虑平凡FD已知函数依赖集F,利用阿氏公理求逻辑蕴涵在F中的函数依赖（未知的FD，也就是包含F+中），工作量是指数级的。寻找求FD的工作量小的方法：属性集的闭包。②属性集的闭包概念定义：设有关系模式R(A1,A2,…,An)，U=A1,A2…,An；F是U上的一个函数依赖集X是U的子集，则称所有用公理从F推出的函数依赖X→Ai中的Ai的属性集合为X的属性闭包，记为X+即：

X+={Ai∣用阿氏公理从F推出X→Ai

}。显然：下列定理告诉我们判断：从X+一眼看出某一函数依赖是否是用阿氏公理从F推出。定理：设F是关系模式R(A1,A2,…,An)的FD集，U=A1,A2…,An。若X,Y是U的子集，则X→Y是用阿氐公理从F推出的充要条件是。例：设关系模式R(A,B,C),R的FD集F={A→B,B→C}则：

C+=C(意味着：C→C成立)B+=BC(意味着：B→B,B→C,B→BC都成立)A+=ABC(意味着：A→A，A→B，A→C；A→AB,A→BC,A→AC,A→ABC7个成立)

∴A是R的侯选关键字

可见：计算属性闭包X+比从F利用FD公理计算F+中的FD要简单得多。三、Armstrong公理是完备的。

证明略。Armstrong公理是完备的，说明：包含在中F+的所有FD,都能用阿氐公理从F推导出。阿氏公理三个规则够用了。

(2)把计算F+

转化为X+计算，可达到同样的目的。通过计算X+，若，则X→Y是由阿氐定理从F推出，则

X→Y是成立的。即：

,则X→Y成立。就是：算法：求属性集在F上的属性闭包。输入：关系模式R的全部属性集U，F为U上的函数依赖集输出：在F上的属性闭包方法：按下列规则计算；(1)置初值(2)其中A是这样的属性：在F中寻找尚未用过的左边是的子集的函数依赖：其中：在Z中寻找中未出现过的属性集合A；若无这样的A则转(4)，否则：(3)判断是否有，若是则转(4)，否则转(2)(4)输出，即为上述方法计算步骤是很有限的，因为U,X,F是有限集。四、属性集闭包的计算例：设函数依赖集F={AB→C,D→EG,C→A,BE→C,BC→D,CG→BD,ACD→B,CE→AG}

试用算法，求(BD)+解：设=BD(1)=BD

(2)在F中找左边是BD子集的FD，只有：D→EG∴，显然(i=0)接下来在F中找左边是BDEG子集的FD，(但用过的不再考虑)：BE→C

∴，显然(i=1)

又在F中找左边是BCDEG的子集的FD：C→A,BC→D,CG→BD,CE→AG

于是：BCDEG→ABCDG(不考虑用过的FD)，在中未出现的属性是A∴此时，虽然，但发现已包含了全部属性，所以不再计算下去。若即使计算下去，很快发现或再也找不到在中未出现的属性。

∴(BD)+=ABCDEG说明：判断计算终止的4种方法：(1)；(2)当包含了全部属性；(3)在F中FD的右边属性中再也找不到中未出现过的属性；(4)在F中未用过的FD的左边属性已经没有的子集。

例：设关系模式R(A,B,C,D,E,G),R的FD集F:F＝﹛AB→C，C→A，BC→D，ACD→B，D→EG，BE→C，CG→BD，CE→AG﹜求:（CG）+＝?,（CD）+=?解：（CG）+＝CGABDE(意味着：CG→CGABDE成立,说明CG是R的候选关键字)也意味着：CG→A，CG→B，…，CG→AB，…，

CG→CGA，…，CG→CGAB，…都成立。

（CD）+=CDABEG(意味着：CD→CGABDE成立,CD是R的另一个候选关键字)

4.3关系模式的分解一、关系模式分解中的问题1．模式分解的目的为了消除更新异常（插、删、改）和减少数据冗余，设计一个较好的关系模式。2．模式分解的定义定义：设有关系模式R（A1，A2，A3，……An）,Ri(i=1,2…,k)是R的一些属性子集，R1∪R2∪…∪Rk=U则称用={R1,R2,…,Rk}代替R的过程称为关系模式R的分解。注：关系模式的分解，不仅仅是属性集合的分解，它是对模式上的函数依赖集以及关系模式当前值的分解的具体表现。例，设关系模式R(S#,SD,MN)（其中S#为学号，SD为系名，MN为系主任名），F={S#→SD,SD→MN},R中当前值的关系r如下：

S#SDMNS1S2S3S4D1D1D2D3张五张五李四王一关系r若不分解R，存在的问题：删除异常：若S4学生毕业了，删除S4则D3系的系主任的王一的信息随之丢失。插入异常：若一个系D5尚无学生，则这个系的系主任赵某信息无法插入R中。数据冗余：系和系主任的名称会多次重复存储。3．模式分解中的问题（1）将R分解为ρ1={R1(S#),R2(SD),R3(MN)},则对每一个ri

有：将R按下列3种方式分解：rr1⋈

r2⋈r3

R1(r)⋈

R2(r)⋈

R3(r)r3=∏R3(r)=｛张五，李四，王一｝分解的特性:既不保持函数依赖性，又不保持无损连接性。R1R2R3的属性之间不能保持F中的函数依赖：不能回答“S1在哪个系学习？”和“D1系的系主任是谁？”的问题。分解后r1r2r3难以恢复原来r值，即:一般表示：r1=∏R1(r)={s1,s2,s3,s4}r2=∏R2(r)={D1,D2,D3}（2）将R分解为ρ2={R4(S#,SD)，R5(S#,MN)}则得r4和r5的关系如下：S#SDS1S2S3S4D1D1D2D3S#MNS1S2S3S4张五张五李四王一r4r5不保持SD

MN，不能回答“D1系的系主任是谁？”的问题仍存在前面提到的数据冗余插入和删除异常。保持无损的连接性：分解后r4和r5中没有损失r中的数据,即用连接运算可以恢复：r=r4⋈r5=

R4(r)⋈

R5(r)(与原来r中的元组一致)分解的特性：不保持FD性,但保持无损的连接性。总之：模式分解特性的四种情况：

1）既不具有无损连接性，又不具有函数依赖的保持性。（不可取的分解）2）具有无损连接性。3）具有函数依赖的保持性。4）既具有无损连接性，又具有函数依赖的保持性。（最好的分解特性）（3）将R按F中的两个依赖分解：ρ3={R4(S#,SD),R6(SD,MN)}SDMND1D2D3张五李四王一r6分解特性:既保持FD性,又保持无损的连接性。即保持F中的FD，又不损失r中原来的数据即：

r=r4⋈r6

异常操作不存在.二、无损连接的分解1、定义：设F是关系模式R的一个依赖集，

ρ={R1,R2,….,Rk}是R的一个分解，如果对于R的任意一个满足F的关系r都有：r=

R1(r)⋈

R2(r)⋈…

⋈

Rk(r)

,则称这个分解ρ是满足F的无损连接分解。

注：若设mρ(r)=

R1(r)⋈

R2(r)⋈

…

⋈

Rk(r)=⋈

Ri(r)

分解具有无损连接性的条件是：r=mρ(r)。

分解不具有无损连接性的条件：

r≠mρ(r)，一般：r

mp(r)

引理：设关系模式R的一个分解

ρ={R1,R2,…,Rk}，r为R任一关系，ri=∏Ri

(r)(1≤i≤k)则：

(a)r

mp(r)(b)∏

Ri

(mp(r))=∏

Ri

(r)(c)mp(mp(r))=mp(r)i=1k例：有模式R(A,B,C),分解为R1(A,B)和R2(B,C)各有具体关系r,r1,r2如下：rr1=∏A,B(r)r2=∏B,C(r)

R={∏A,B(R),∏B,C(R)}而mp(r)=∏A,B(r)⋈

∏B,C(r)如下表

显然比r多出一个元组（a2,b1,c1）：寄生元组

这就是r

mp(r)的含义。可见将R分解R1和R2不具有无损联接性,但保持函数依赖性（AB）ABca1a2a1b1b1b1c1c2c2ABca1a1a2a2b1b1b1b1c1C2c1c2ABa1a2b1b1Bcb1b1c1c21).寄生元组使得原来信息确定的元组变得不确定即损失了信息的真实性。ABa1a2b1b1Bcb1b1c1c2Aca1a2a1c1c2c2Aca1a2a1c1c2c2∏A,B(r)∏A,C(r)∏A,C(r)∏B,C(r)2).3).mp(r)=∏A,B(r)⋈

∏A,C(r):∴r=mρ(r)，具有无损的连接性分解：既保持函数依赖（A→B），又具有无损的连接性。

ABca1a2a1b1b1b1c1c2c2mp(r)=∏A,C(r)⋈

∏B,C(r):∴r=mρ(r)，

具有无损的连接性分解：不保持函数依赖性（A↛B），但具有无损的连接性。ABca1a2a1b1b1b1c1c2c2第2种分解最理想，其次第3种分解，第1种分解不好。注：无损连接的分解应是关系模式分解时所必须满足的条件。因为分解前后的数据，作同样的查询，应产生同样的结果。保持函数依赖性就是保持属性间的语义在分解后不变（不割裂属性间的语义）。

一个具有无损连接分解不一定保持依赖保持性；反之，一个具有依赖保持性的分解也不一定具有无损连接性。2．无损连接分解的判断算法：无损连接的判断(判定表法)输入：关系模式R（A1，A2，……An），它的函数依赖集F，以及R的一个分解ρ={R1,R2,……Rk}输出：判断ρ相对于F是否具有无损连接特性。方法：（1）构造一个k行n列的表：每列对应一个属性Aj（1≤j≤n），每行对应一个模式Ri（1≤i≤K），若Aj∈

Ri，则在第i行处填上符号aj,否则填上符号bij。（构造初始表）（2）逐个地检查F中的每个函数依赖，并修改表中元素。(修改表)方法如下：取F中的FD:X→Y,在X的分量中寻找相同的行，然后将这些行中Y的分量改为相同的符号，如果其中有aj，则将bij改变aj，若其中无aj，则改为bij。（3）反复重复（2），如果发现某一行变成了a1,a2……ak，则分解的ρ具有对F的无损连接性，否则ρ具有损连接性。（判断）例：设关系模式R=(A,B,C}且F={A→B,C→B},分别判断下列分解是否具有无损连接性。(1)p1={AB,BC}(2)p2={AC,BC}(3)p3={AC,AB}解（1）构造一个表对于A→B,A列中无相同的行；对于C→B,C列中无相同的行；无法修改且也无全部为aj的行。p1不具有无损连接性。RiABCABBCa1b21a2a2b13a3（2）构造一个表查：C→B；C列中有相同的行，于是将第一行的B改为a2,则此时，立即发现第一行为a1,a2,a3所以不再检查其他依赖，则可判定p2具有无损联接性。若按前例：r1=r2=S=r1⋈r2=RiABCACBCa1b21b12a2a3a3RiABCACBCa1b21a2a2a3a3Aca1a2a1c1c2c2BCb1b1C1c2ABca1a2a1b1b1b1c1c2c2(3)构造一个表查：A→B；发现A列中有两行相等，把B列第一行b12也改为相应的a2,则在第一行出现a1,a2,a3，于是具有无损连接性。可使用简便列表法：其思想与原列表一样，只是bij不填入表中，使其留空位，只将ai填入表中，然后按算法改变表中的元素，如：上例（3）定理：算法1能正确的判定一个分解是否具有无损连接性。RiABCACABa1a1b12a2a3b23RiABCACABa1a1a2a2a3无损连接分解的判断的推导法：对于ρ只包含两个关系子模式的分解，有更简单的方法可检验ρ的无损连接性。定理：设ρ={R1,R2}是R的一个分解，F是R上函数依赖集，则对于F+来说，ρ具有无损连接性的充要条件是(R1∩R2)→(R1－R2)或(R1∩R2)→(R2－R1)。

注意：依赖的成立不仅在F中成立，而且也可以在F+中成立。例：设有关系模式R(U,V,W,X,Y,Z),其依赖集F={U→V,W→Z,Y→U,WY→X}

判断下列分解是否具有无损联接性(1)ρ1={WZ,VY,WXY,UV}(2)ρ2={UVY,WXYZ}解:(1)构造ρ1无损联接判定表RiUVWXYZWZb11b12a3b14b15a6VYb21a2b23b24a5b26WXYb31b32a3a4a5b36UVa1a2b43b44b45b46UVWXYZWZa3a6VYa2a5WXYa3a4a5a6UVa1a2由U→V可知U中无相同的行,故V不能修改W→Z;将b36改为a6(∵W中有相同行a3)Y→U;∵Y列中有相同的行a5,

∴将U列中的b31改为b21

WY

→X;WY两列中无相同的行,

故X不能修改。∴由化简的判定表可知ρ1不具有无损联接性。修改：有a的行，b都修改为a；都是b的行，都修改为下标相同的b。(2)判断ρ2的无损联接性可用两种方法：构造判定表法和推导法a、构造判定表法UVWXYZUVYa1a2b13b14a5b16WXYZb21b22a3a4a5a6UVWXYZUVYa1a2b13b14a5b16WXYZa1a2a3a4a5a6考察F：U→V；V列不能修改(∵U列中无相同行)

W→Z；Z列不能修改(∵W列中无相同行)Y→U；Y列有相同行a5,则U列中将b21改为a1WY→X；Y中有相同行，但W无相同行

∴X列不能修改。∴判定表为：ρ2分解为无损连接。注意：要求反复修改。b、推导法(它被分解成两个关系)∵(UVY)∩(WXYZ)=Y又∵(UVY)-(WXYZ)=UV(WXYZ)-(UVY)=WXZ

∴(UVY)∩(WXYZ)→((UVY)-(WXYZ))即Y→UV不在F中,但在F+中即用公理推出：∵Y+→YUV，∴

Y→UV∴根据定理：ρ2分解为无损连接。三、保持依赖的分解定义：设F是关系模式R(U)的函数依赖集,ZU,F在Z上的一个投影用

Z(F)表示，定义为：

Z(F)={|}定义：设ρ={R1,R2,…,Rk}是关系模式R的一个分解，F是R的一个FD集。若F+=()+

，则称分解ρ保持函数依赖集F，其中：∏R1(F)∪∏R2(F)∪…∪∏RK(F)

=即：分解前的F和分解后的F等价。（或称ρ具有依赖保持性）例：R(A,B,C),F={A→B,C→B}

当有一分解：ρ={AB,AC}（具有无损连接性）

但，

A,B(F)∪

A,C(F)={A→B}，并不等价于F，∴ρ不保持函数依赖性。说明：直接按保持函数依赖性的定义去论证一个分解是否保持原FD集是不现实的，因为需要计算F+的时间是指数级的。

比较可行的方法：逐个验证F中每个FD是否为∪

Ri(F)所逻辑蕴涵。这种方法计算的复杂性是多项式时间级。总之：保持函数依赖性的论证是困难的。实质上他是要求两个函数依赖集的等价问题。

ki=1例：设关系模式R（A，B，C，D，E，G），其上成立的FD集F={A→B，C→G，E→A，CE→D}，R上一个分解：ρ={R1(ABE)，R2(CDEG)}，现判断ρ是否保持函数依赖。解：计算分解的R1和R2分别在F上的投影为：∏R1(F)={A→B，E→A}和∏R2(F)={C→G，CE→D}∏R1(F)∪∏R2(F)={A→B，E→A}∪{C→G，CE→D}，显然，F中的每个FD被（∏R1(F)∪∏R2(F)）逻辑蕴涵。因此，ρ具有保持FD性。分解不保持FD性带来两个问题：

1）破坏原来成立且被丢失的FD，导致语义出错。

2）造成无约束地对数据插入或修改，使数据出错。注:(1)保持函数依赖与无损连接分解这两个要求在性质上有些差异，前者决定分解的好坏,而后者决定能否分解.不保持函数依赖的分解则会产生异常操作,有损分解是无实用意义的。(2)关系模式的分解主要准则：①首先满足无损连接分解要求。②既满足无损连接分解要求,又满足保持依赖要求。准则②比①理想,但分解要受到更多的限制。(3)只满足保持依赖而不满足无损连接分解的分解是存在的。如:R(A,B,C,D)设,则分解保持依赖,不满足无损分解的要求,这种分解前后的关系模式不等价,因而无实用价值。因此:在DB设计中,只满足保持依赖不宜作为关系分解的一个独立准则。本节小结:讨论关系模式的分解两个特性，实际上涉及到两个模式的等价问题，包括数据等价和依赖等价。数据等价是指两个模式中实例应表示同样的信息内容，这就用无损连接衡量。依赖等价是指两个模式应有相同的依赖集闭包。在依赖集闭包不变的情况下，数据的语义是不会出现差错的。

4.4关系模式的范式及规范化用什么标准衡量分解后的模式的好坏呢？满足特定函数依赖要求的模式称为范式。一．第一范式（1NF）与第二范式（2NF）1．1NF定义：如果一个关系模式R的每个具体关系r的每个属性值都是不可再分的最小数据单位，则称R为第一范式，简记1NF。部门号部门名

经理正经理副经理D1D2DN1DN2M1AM1M2AM2部门号部门名正经理副经理D1D2DN1DN2M1M2AM1AM2借书人书名日期张平T1T2T3D1D2D3李文化T2T4D4借书人书名日期张平张平张平李文化李文化T1T2T3T2T4D1D2D3D4D4如：r1(非1NF)r2(非1NF)1NF1NF改写：去掉组项改写：去掉重复组注：DB中关系一般要求至少是1NF2．2NF定义：满足1NF的关系模式R，如果它的所有非主属性完全函数依赖于任一侯选关键字（不部分依赖），则称R是第二范式，记为2NF。注：1）关系模式R中的每个侯选关键字都由单个属性构成，则R一定是2NF。关系模式R中的某个侯选关键字由多个属性构成，只要有一个非主属性部分函数依赖于该侯选关键字，则R一定不是2NF。

2）关系模式R中的属性都是主属性，无非主属性，则R必定是2NF。3）二元关系模式必定是2NF。例如：有关系student如下：SNOCNOCTITLENAMEGRADELOCAS2S3S4S4S5C1C2C1C3C4OSDBOSAICL王平高升王平杨杨高升7085867298D1D2D1D3D2存在插入异常：当新教师尚未任课，无法插该教师信息；存在删除异常：当学生毕业或退学教师信息被删除。根据语义：该关系的关键字（SNO，CNO）

冗余得到部分控制:教师的NAME和LOCA的取值与学生人数无关，仅与讲授课程的门数有关。

消除删除异常：学生降级或退学时,因删除仅在ST1上进行,不会丢失教师方面的信息；

插入异常没有解决。说明ST2中还存在其它的函数依赖。注意：存在非主属性对侯选关键字的部分函数依赖，是产生数据冗余和更新异常的重要原因之一。分解：消除部分FD：将有部分FD的属性分到不同的模式中：显然

成绩实体二、第三范式2NF关系并不能解决所有问题，尽管解决以上部分问题但：

例:

上例

：

CNOCTITLENAMELOCAC1C2C3C4OSDBAICL王平高升杨杨高升D1D2D3D2ST2存在原来的插入异常：有新教师报到，要将数据插入到ST2中，但未教课程（即CNO为空），而不能插入。存在新的删除异常：删除课程方面信息，则会删除教师的信息。存在新的冗余：一个教师讲多门课程，则他的的NAME和LOCA值会存储多次。原因是：在ST2中存在非主属性对关键字的传送函数依赖：CNO→NAME，NAME→LOCA,但NAMECNO即：CNO→LOCAt定义：如果关系模式R满足2NF，且它的任何一个非主属性都不传递依赖于任何的侯选关键字，则称R是第三范式，记为：3NF。例将ST2分解：消除传递依赖成为3NF

ST3(CNO,CTITLE,NAME)教课实体

ST4(NAME,LOCA)教师实体3NF关系可以解决大多数的异常问题，分解成3NF一般就可以了。但3NF还有特殊异常的情况。

注：1，关系模式R中的属性都是主属性，无非主属性，R必定是3NF。2，二元关系模式必定是3NF。

3，关系模式R是3NF，则R必定是2NF。反之不一定成立。注意：存在非主属性对侯选关键字的传递函数依赖，是产生数据冗余和更新异常的重要原因之二。。分解的过程，就是为解决更新异常和数据冗余，将关系中不同实体分开的过程。三．BC范式（BCNF）3NF的关系存在稀少特殊的异常问题：如

SNOCTITLENAMES1S1S2S3S4英语数学物理英语英语王平沈阳高飞袁志王平S每个学生可选多门课程，每门课有多个教师，但每个教师只教一门课。∴S的候选关键字为：（SNO，CTITLE）和（SNO,NAME）即S中无非主属性，也不存在非主属性对关键字传递依赖。∴S∈3NFS1(NAME,CTITLE)S2(SNO,NAME)

消除了主属性部分函数依赖于侯选关键字。分解S：存在插入异常：一个新课程和指导教师的数据要插入S中时必须至少有一个学生选修该课程且该指导教师被分配给他时才行，否则SNO为空而不能插入。删除异常：学生退学或改变所学课程时，会丢失课程或指导教师信息。另外，更换某课程的指导教师，且很多选修该课时，修改很麻烦。原因：在S中存在主属性部分函数依赖于侯选关键字：因为：NAME→CTITLE,SNOCTITLE，则:（SNO,NAME）→CTITLEp注：存在主属性部分（或传递）函数依赖于侯选关键字，也是产生数据冗余和更新异常的重要原因之三。定义：设F为模式R的依赖集，如果F中所有依赖X→A的左部(即X中)都包含了R一个候选关键字，则称R是Boyce—Codd范式,简记：BCNF。简言之：若在R上成立的F中，每一个决定因素都包含候选关键字，则R为BCNF。例：R(X,Y,Z),且F={Y→Z,XZ→Y}

R的侯选关键字是：XY和XZ ，所以，R是3NF,但不是BCNF

因为，F中Y→Z，Y没有包含侯选关键字。实质说明F中蕴涵着主属性部分依赖侯选关键字：由F中的FD推出的XY→Z和Y→Z说明XY→Z。p注：1）是BCNF的模式也必定是3NF，反之不一定。

2）二元关系模式必定是BCNF。

3）都是主属性的模式并非是BCNF。因为BCNF定义不仅排除了非主属性不能部分或传递依赖任何侯选关键字，而且也排除了主属性对不包含该主属性的侯选关键字的部分或传递FD。可见BCNF高于3NF。4种范式的关系：1NF

2NF

3NF

BCNF规范化关系：非规范关系1NF2NF3NFBCNF→4NF→5NF消去重复组组项消去非主属性对侯选关键字的部分依赖消除非主属性对侯选关键字的传递依赖消去所有的部分和传递依赖(包括主属性对侯选关键字的部分和传递依赖)部分和传递函数依赖是产生数据冗余和更新异常的根本原因，消除它们的方法是分解，消除它们的过程称为规范化。分解的实质是将模式中相对独立的信息或不同实体分离的过程。六、模式设计的原则

模式分解={R1,R2,…,Rk}的特性:（1）Ri应有某种范式性质（1NF~BCNF）（2）ρ具有无损连接性：r=⋈（3）ρ具有保持依赖性:F+=(∪)+（4）ρ具有最小性，模式最少，模式中属性总数应最少。

Ki=1好的模式设计原则；表达性原则；分解前后DB模式等价：即数据等价和依赖等价，分别用无损连接和保持依赖来衡量。分离性：指属性间的“独立联系”，应该用不同的关系模式表达，分离就是消除操作异常和减少冗余。最小冗余性：分解后模式少，属性总数少，主要是节省存储空间，提高对关系的操作效率。Ki=1综合题例本章主要有两类题型：1.已知R和其上的FD集F,求解：R的侯选关键字。证明R是几范式。根据F将R分解为3NF或BCNF，等。2.已知R和R的当前值r，求解上面各类问题。例1：设有关系模式R(F,G,H,I,J),R的FD集F={F→I,J→I,I→G,GH→I,IH→F}(1)求R所有候选关键字(2)判断ρ={FG，FJ，JH，IGH，FH}是否为无损的连接分解?

解:(1)考察F：J，H是L类属性，∴候选关键字至少包含J和H又∵J+=JI，H+=H则(JH)+=JHIGF，∴JH是R唯一的候选关键字。

(2)P的无损联接判定如下：

FGHIJFGa1a2FJa1a2a5JHa1a2a3a4a5IGHa1a2a3a4FHa1a2a3a4考察F中：F→I:将F相同中对应I中b24,b54改为：b14;J→I:将J相同中对应I中b34改为b14;I→G:将I相