第6章关系数据理论20142

1、1 第第6章章 关系数据理论关系数据理论 2 课课 程程 C教教 员员 T参参 考考 书书 B 物理物理 数学数学 计算数学计算数学 李李 勇勇 王王 军军 李李 勇勇 张张 平平 张张 平平 周周 峰峰 普通物理学普通物理学 光学原理光学原理 物理习题集物理习题集 数学分析数学分析 微分方程微分方程 高等代数高等代数 数学分析数学分析 6.2.7 多值依赖多值依赖 例例: 学校中某一门课程由多个教师讲授，他们使用相同的学校中某一门课程由多个教师讲授，他们使用相同的 一套参考书。一套参考书。 关系模式关系模式Teaching(C, T, B) 课程课程C、教师、教师T 和和 参考书参考书B 3

2、 普通物理学普通物理学 光学原理光学原理 物理习题集物理习题集 普通物理学普通物理学 光学原理光学原理 物理习题集物理习题集 数学分析数学分析 微分方程微分方程 高等代数高等代数 数学分析数学分析 微分方程微分方程 高等代数高等代数 李李 勇勇 李李 勇勇 李李 勇勇 王王 军军 王王 军军 王王 军军 李李 勇勇 李李 勇勇 李李 勇勇 张张 平平 张张 平平 张张 平平 物物 理理 物物 理理 物物 理理 物物 理理 物物 理理 物物 理理 数数 学学 数数 学学 数数 学学 数数 学学 数数 学学 数数 学学 参考书B教员T课程C 关系模式关系模式TEACHING （C，T，B），），它

3、的码它的码 是（是（C，T，B），），所以所以 属于属于BCNF。 存在的问题：存在的问题： (1)插入异常：插入异常：当某门当某门 课程增加一名教员时，课程增加一名教员时， 该门课程有多少本参该门课程有多少本参 考书就必须插入多少考书就必须插入多少 个元组；同样当某门个元组；同样当某门 课程需要增加一本参课程需要增加一本参 考书时，它有多少个考书时，它有多少个 教员就必须插入多少教员就必须插入多少 个元组。个元组。 4 普通物理学普通物理学 光学原理光学原理 物理习题集物理习题集 普通物理学普通物理学 光学原理光学原理 物理习题集物理习题集 数学分析数学分析 微分方程微分方程 高等代数高等代

4、数 数学分析数学分析 微分方程微分方程 高等代数高等代数 李李 勇勇 李李 勇勇 李李 勇勇 王王 军军 王王 军军 王王 军军 李李 勇勇 李李 勇勇 李李 勇勇 张张 平平 张张 平平 张张 平平 物物 理理 物物 理理 物物 理理 物物 理理 物物 理理 物物 理理 数数 学学 数数 学学 数数 学学 数数 学学 数数 学学 数数 学学 参考书B教员T课程C 存在的问题：存在的问题： (2)删除异常：删除异常：当删当删 除一门课程的某个教除一门课程的某个教 员或者某本参考书时，员或者某本参考书时， 需要删除多个元组。需要删除多个元组。 (3)更新异常：更新异常：当一当一 门课程的教员或参

5、考门课程的教员或参考 书作出改变时，需要书作出改变时，需要 修改多个元组。修改多个元组。 (4)数据冗余：数据冗余：同一同一 门课的教员与参考书门课的教员与参考书 的信息被反复存储多的信息被反复存储多 次。次。 5 【定义定义6.9】 关系模式关系模式R(U)，X、Y、Z U， 并且并且Z = U X Y， 多值依赖多值依赖X Y 成立当且仅当对成立当且仅当对 R(U) 的任一关系的任一关系r，给定的一对（，给定的一对（x，z）值有一组）值有一组y 的值，这组值仅仅决定于的值，这组值仅仅决定于x 值而与值而与z 值无关。值无关。 物物 理理,普通物理学普通物理学 李李 勇勇,王王 军军 物物

6、理理,光学原理光学原理 李李 勇勇,王王 军军 物物 理理,物理习题集物理习题集 李李 勇勇,王王 军军 对于对于C的每一个值，的每一个值，T有一组值与之对应，而不论有一组值与之对应，而不论B 取何值。取何值。 若若XY而而Z=，则称则称XY为平凡的多值依赖，为平凡的多值依赖， 否则称否则称XY为非平凡的多值依赖。为非平凡的多值依赖。 6 【形式化定义形式化定义】在在R（U）的任一关系）的任一关系r中，如果存中，如果存 在元组在元组t、s ，使得，使得tX=sX，那么就必然存在元组，那么就必然存在元组 w，v r，（，（w，v可以与可以与s，t相同），使得相同），使得 wX=vX=tX，而，而

7、wY=tY，wZ=sZ， vY=sY，vZ=tZ（即交换（即交换s，t元组的元组的Y值所得值所得 的两个新元组必在的两个新元组必在r中），则中），则Y多值依赖于多值依赖于X，记为，记为 XY。 这里，这里，X，Y是是U的子集，的子集，Z=U-X-Y。 t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2 若若(C, T, B)满足满足CT， 含有元组含有元组t1=(C1, T1, B1)， t2=(C1, T2, B2)，则也一定含有元组，则也一定含有元组t3=(C1, T1, B2)， t4=(C1, T2, B1)。 7 例如：例如：P179 关系模式关系模式WS

8、C（ W，S，C ）中，）中，W表示仓库，表示仓库， S表示保管员，表示保管员，C表示商品。表示商品。 假设，每个仓库有若干个保管员，有若干种商假设，每个仓库有若干个保管员，有若干种商 品。每个保管员包管所在仓库的所有商品，每种商品。每个保管员包管所在仓库的所有商品，每种商 品被该仓库的所有保管员包管。品被该仓库的所有保管员包管。 存在是函数依赖：存在是函数依赖： W S W C 8 1. 多值依赖多值依赖的的性质性质 （1）多值依赖具有对称性，多值依赖具有对称性，即即 若若XY，则，则XZ，其中，其中Z=UXY。 （2）多值依赖具有多值依赖具有传递传递性，性，即即 若若XY，则，则YZ，则，

9、则XZ-Y 。 （3）函数依赖是多值依赖的特例，）函数依赖是多值依赖的特例，即即 若若XY， 则则XY。 若若XY，UXY=， 则称则称XY 为平凡的多为平凡的多 值依赖值依赖 。 （4） 若若XY，XZ，则，则XYZ 。 （5）若若XY，XZ，则，则XYZ 。 （6）若若XY，XZ，则，则XY-Z ， XZ-Y 。 9 2. 多值依赖多值依赖与函数依赖的与函数依赖的区别区别 （1）XY的有效性与属性集范围有关的有效性与属性集范围有关 XY在在U上成立上成立 XY在属性集在属性集W（XY W U） 上成立。上成立。 反之，反之，XY在属性集在属性集W（XY W U）上成立，但在）上成立，但在U

10、 上不一定成立。上不一定成立。 若在若在R(U)上，上，XY在属性集在属性集W(XY W U)上成立，则上成立，则 称称XY为为R(U) 的嵌入式多值依赖。的嵌入式多值依赖。 XY 的的 有效性仅决定于有效性仅决定于X、Y 属性集上的值，它在任何属性集上的值，它在任何 属性集属性集W（XY W U） 上都成立。上都成立。 （2）若）若XY 在在R(U) 上成立，则对于任何上成立，则对于任何Y Y， 均有均有 XY 成立。成立。 若若XY在在R(U)上成立，则不能断言对于上成立，则不能断言对于Y Y，是，是 否有否有XY 成立。成立。 10 【定义定义6.10】 关系模式关系模式R 1NF， 若

11、若 XY（Y X） 是非平凡的多值依赖，且是非平凡的多值依赖，且X 含有含有 码，则称码，则称R 4NF。 如关系模式如关系模式CTB，CT，CB， 码为码为(C, T , B)，C不是候选码，所以不是候选码，所以CTB 4NF。 如果一门课如果一门课Ci 有有m 个个 教员，教员，n 本本 参考书，则关参考书，则关 系中分量为系中分量为Ci 的元组共有的元组共有mn 个，数据冗余非常个，数据冗余非常 大。大。 规范化：规范化： 4NF的要求是：消除非平凡且非函数依赖的多值的要求是：消除非平凡且非函数依赖的多值 依赖。依赖。 将将CTB 分解为分解为CT（C，T），），CB（C，B），）， 在

12、分解后的关系中分量为在分解后的关系中分量为Ci 的元组共有的元组共有m + n 个。个。 11 6.3 数据依赖的蕴涵与公理系统数据依赖的蕴涵与公理系统 1. 函数依赖的逻辑蕴含定义函数依赖的逻辑蕴含定义 已经讨论了函数依赖的类型及其对数据库模式已经讨论了函数依赖的类型及其对数据库模式 设计的影响和处理方法；设计的影响和处理方法； 关于关于“处理方法处理方法”即范式设计，事实上是由模即范式设计，事实上是由模 式分解而得，而模式分解的理论与方法是以数据依式分解而得，而模式分解的理论与方法是以数据依 赖理论为基础理论的，所以需要较全面的讨论数据赖理论为基础理论的，所以需要较全面的讨论数据 依赖理论

13、；依赖理论； 数据库专家数据库专家Armstrong等提出一组定义和推理规等提出一组定义和推理规 则，并形成了一个有效而完备的理论体系，即则，并形成了一个有效而完备的理论体系，即 Armstrong公理系统。公理系统。 数据依赖的公理系统是模式分解的理论基础。数据依赖的公理系统是模式分解的理论基础。 12 函数依赖函数依赖F是很大的，如果依靠语义分析方法是很大的，如果依靠语义分析方法 找出一个关系模式的所有函数依赖，是一件很不找出一个关系模式的所有函数依赖，是一件很不 容易的事。实际上，也是没有必要的，因为一组容易的事。实际上，也是没有必要的，因为一组 函数依赖的存在，必定引起另外一组函数依赖

14、的函数依赖的存在，必定引起另外一组函数依赖的 出现。因此，出现。因此，可以用推理的方法，从一组已知的可以用推理的方法，从一组已知的 函数依赖推导出另外一组函数依赖，而不必完全函数依赖推导出另外一组函数依赖，而不必完全 用语义分析方法找出一个关系模式的所有函数依用语义分析方法找出一个关系模式的所有函数依 赖赖。 13 【例例】关系模式关系模式 R=(A,B,C) 函数依赖集函数依赖集F=AB,BC, 则：必存在则：必存在AC。 这个例子说明：函数依赖集这个例子说明：函数依赖集F=AB,BC 与与F=AB,BC ,AC之间存在着某种因果关之间存在着某种因果关 系，即从系，即从F可以推导出可以推导出

15、F，反之亦然。，反之亦然。 两个函数依赖集之间的这种互为因果关系称两个函数依赖集之间的这种互为因果关系称 为逻辑蕴涵，即一个函数依赖集逻辑蕴涵另外一为逻辑蕴涵，即一个函数依赖集逻辑蕴涵另外一 个函数依赖集。个函数依赖集。 F=AB,BC与与F=AB,BC ,AC相相 互逻辑蕴涵。互逻辑蕴涵。 14 【定义定义6.11】对于满足一组函数依赖对于满足一组函数依赖F的关系模式的关系模式R U,F,其任何一个关系其任何一个关系r,若函数依赖若函数依赖XY都成立都成立 (即即r中任意两元组中任意两元组t,s,若若tX=sX,则则tY=sY),则称则称 F逻辑蕴含逻辑蕴含XY，或称，或称XY 可从可从F中

16、推出。中推出。 【例例1】关系模式关系模式 R=(A,B,C),函数依赖集函数依赖集 F=AB,BC, 则：则：F逻辑蕴涵逻辑蕴涵AC。 证：设证：设u,v为为r中任意两个元组：若中任意两个元组：若AC不成立，不成立， 则有则有uA=vA,而而uCvC 而而AB, BC,知知 uA=vA, uB=vB, uC=vC,即若即若uA=vA则则uC=vC，和假设矛，和假设矛 盾。故盾。故F逻辑蕴涵逻辑蕴涵AC。 15 【例例2】给定给定U=X，Y，Z，W，函数依赖集，函数依赖集 F=XY，YZ，给定下列的关系实例，给定下列的关系实例r如表如表1 所示，显然，满足函数依赖集所示，显然，满足函数依赖集F

17、。 元组号元组号XYZW t1adba t2adbb t3bcbc t4bcbd t5ceae 例例2中，可观察到中，可观察到r还满足还满足XZ，但在函数依，但在函数依 赖集赖集F中没有中没有XZ。那么，就需要考虑。那么，就需要考虑r除满足除满足F 之外，是否还会满足一些其它的函数依赖？之外，是否还会满足一些其它的函数依赖？ 16 在上面的例子中，在上面的例子中，r实例满足实例满足F外，还满足外，还满足F所不所不 包括的包括的XZ，这就产生一个问题，如何从，这就产生一个问题，如何从 F=XY，YZ推导得出推导得出XZ ? 这需要一套规则这需要一套规则 从给定的函数依赖集推出其蕴涵的函数依赖。从

18、给定的函数依赖集推出其蕴涵的函数依赖。 一套推理规则：是模式分解算法的理论基础一套推理规则：是模式分解算法的理论基础 用途：用途： l从一组函数依赖求得蕴含的函数依赖从一组函数依赖求得蕴含的函数依赖 l这组推理规则是这组推理规则是l974年首先由年首先由Armstrong提出来的提出来的 17 2. Armstrong公理系统公理系统 若若U为关系模式为关系模式R的属性全集，的属性全集，F为为U上的一组上的一组 函数依赖，设函数依赖，设X、Y、Z、W均为均为R的子集，对的子集，对 R(U,F)有以下的推理规则：有以下的推理规则： （1）A1(自反律自反律)：若：若Y X U ，则，则XY为为F

19、所所 蕴涵；蕴涵；（注意，由自反律所得到的函数依赖均是平（注意，由自反律所得到的函数依赖均是平 凡的函数依赖，自反律的使用并不依赖于凡的函数依赖，自反律的使用并不依赖于F。 ） （2）A2(增广律增广律): 若若XY为为F所蕴涵，且所蕴涵，且 Z U， 则则XZYZ为为F所蕴涵；所蕴涵； （YZ表示并集）表示并集） （3）A3(传递律传递律): 若若XY,YZ为为F所蕴涵，则所蕴涵，则 XZ为为F所蕴涵。所蕴涵。 18 【定理定理6.l】Armstrong推理规则是正确的。推理规则是正确的。 证明：证明： (1) 设设Y X U 。 对对RU,F的任一关系的任一关系r中的中的 任意两个元组任意

20、两个元组t，s： 若若tX=sX，由于，由于Y X，有，有 tY=sY, 所以所以XY成立，自反律得证。成立，自反律得证。 (2) 设设XY为为F所蕴含所蕴含,且且Z U。 设设RU,F的任一关系的任一关系r中任意的两个元组中任意的两个元组t,s； 若若tXZ=sXZ，则有，则有tX=sX和和tZ=sZ； 由由XY,于是有于是有tY=sY，所以，所以tYZ=sYZ，所，所 以以XZYZ为为F所蕴含，增广律得证。所蕴含，增广律得证。 19 (3) 设设XY及及YZ为为F所蕴含。所蕴含。 对对RU,F的任一关系的任一关系r中的任意两个元组中的任意两个元组t,s 。 若若tX=sX,由于由于XY,有

21、有tY=sY； 再由再由YZ,有有tZ=sZ,所以所以XZ为为F所蕴含，传所蕴含，传 递律得证。递律得证。 人们把自反律人们把自反律,传递律和增广律称为传递律和增广律称为Armstrong公公 理系统。理系统。 20 Armstrong公理的有效性及完备性公理的有效性及完备性 A = f | 可用可用Armstrong公理从公理从F中导出的函数依赖中导出的函数依赖f B = f | 被被F所逻辑蕴涵的函数依赖所逻辑蕴涵的函数依赖f l有效性：用有效性：用Armstrong公理从公理从F中导出的函数依赖中导出的函数依赖 必为必为F所蕴涵。所蕴涵。 A B l完备性：完备性：F所蕴涵的函数依赖都能

22、用所蕴涵的函数依赖都能用Armstrong公公 理从理从F中导出。中导出。 B A 21 由由A1、A2和和A3推理规则，可以得到下面推理规则，可以得到下面3条推条推 理规则：理规则： （1）合并规则：）合并规则：若若XY,XZ为为F所蕴涵，则所蕴涵，则 XYZ为为F所蕴涵；所蕴涵； （2）伪传递规则：）伪传递规则：若若XY，WYZ为为F所蕴涵所蕴涵, 则则XWZ为为F所蕴涵；所蕴涵； （3）分解性规则）分解性规则: 若若XY，Z Y 为为F所蕴涵，则所蕴涵，则 XZ为为F所蕴涵。所蕴涵。 22 证明：证明： （1）推论）推论1显然成立。显然成立。 （2）推论）推论2的证明。的证明。 由由XY

23、，利用增广律可得，利用增广律可得XWYW。由。由YWZ， 利用传递律得到利用传递律得到XWZ。 （3）推论）推论3的证明。的证明。 由由Z Y，利用自返律得到，利用自返律得到YZ。由。由XY，利用，利用 传递律得到传递律得到XZ。 23 【例例3】 R, U = (A, B, C, D, E), F = ABCD, AB, DE, 求证，求证， AE。 证明：证明： （1） AB， AAB（增广律）（增广律） （2） AAB,ABCD, A CD （传递律）（传递律） （3） ACD, A C , AD （分解规则）（分解规则） （4） AD, DE A E （传递律）（传递律） 24 根据合

24、并规则和分解规则，很容易得到这样一根据合并规则和分解规则，很容易得到这样一 个重要事实：个重要事实： 【引理引理6.1】X A1A2Ak成立的充分必要条件是成立的充分必要条件是 X Ai成立（成立（i1，2，k）。）。 【例例4】R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH, A H？CG HI？AG I？ 问题：问题：有没有一般性的算法判定有没有一般性的算法判定XY是否能由是否能由F 根据根据Armstrong 公理导出？公理导出？ 25 3. 函数依赖的闭包理论函数依赖的闭包理论 （1）函数依赖闭包、属性集闭包）函数依赖闭包、属性集

25、闭包 【定义定义6.12】在关系模式在关系模式R（U，F）中为）中为F所逻辑所逻辑 蕴涵的函数依赖的全体称为蕴涵的函数依赖的全体称为F的闭包，记作的闭包，记作F+。 【定义定义6.13】设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X U， XF+ = A | XA能由能由F根据根据Armstrong公理导公理导 出出，XF+ 称为属性集称为属性集X关于函数依赖集关于函数依赖集F的闭包。的闭包。 26 【例例5】 R, U = (A, B, C), F = AB,BC, 分别求分别求A、B、C的闭包。的闭包。 解：（解：（1）若）若X=A A B,BC AC（传递律）（传递律）

26、AA XF+ =A,B,C （2）若）若X=B BB,BC, XF+ =B,C （3）若）若X=C CC XF+ =C 可见，计算属性集闭包要比直接计算函数依赖可见，计算属性集闭包要比直接计算函数依赖 集闭包简单的多。能否通过计算属性集闭包来计算集闭包简单的多。能否通过计算属性集闭包来计算 函数依赖集闭包？函数依赖集闭包？可行可行 27 【引理引理6.2】设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X U ，Y U，XY能由能由F根据根据Armstrong公理导公理导 出的充分必要条件是出的充分必要条件是Y XF+。 于是，判定于是，判定XY 是否能由是否能由F根据根据Arms

27、trong公公 理导出的问题，就转化为求出理导出的问题，就转化为求出XF+，判定，判定Y是否为是否为 XF+的子集的问题。的子集的问题。 28 【算法算法6.1】（求属性集（求属性集X(X U)关于关于U上的函数依赖上的函数依赖 集集F的闭包的闭包XF+） l输入输入 ：X，F l输出输出 ： XF+ l步骤：步骤： (l) 令令X(0)=X，i=0 (2) 求求B，这里，这里B = A |( V)( W)(VW F V X（i）A W)； X(i)AW)； (3) X(i+1)=BX(i) (4) 判断判断X(i+1)=x(i)吗吗? (5) 若相等或若相等或X(i)=U 则则X(i)就是就

28、是XF+，算法终止。，算法终止。 (6) 若否，则若否，则i=i+l，返回第，返回第(2)步。步。 29 【例例1】U=A,B,C,D,E；F=ABC，BD，CE， ECB，ACB。计算。计算 (AB)F+ 。 解：解： 由算法由算法6.1，设，设X(0)=AB； 计算计算X(1)； 逐一的扫描逐一的扫描F集合中各个函数依赖集合中各个函数依赖,找左部为找左部为 A、B或或AB的函数依赖。得到两个：的函数依赖。得到两个：ABC，BD。 于是于是X(1)=ABCD=ABCD。 因为因为X(0)X(1)，所以再找出左部为，所以再找出左部为ABCD子集的那些函子集的那些函 数依赖，又得到数依赖，又得到

29、CE，ACB，于是，于是 X(2)=X(1)BE=ABCDE。 因为因为X(2)已等于全部属性集合已等于全部属性集合,所以所以(AB)F+=ABCDE 。 30 【例例2】 U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH, 计算计算 (AG)F+ 。 解：解： 由算法由算法6.1，设，设X(0)=AG； 计算计算X(1)； 逐一的扫描逐一的扫描F集合中各个函数依赖集合中各个函数依赖,找左部为找左部为A、G、 AG的函数依赖。得到两个：的函数依赖。得到两个：AB，AC。于是。于是X(1)=AG BC=AGBC; 因为因为X(1)X(0)，所以再找

30、出左部为，所以再找出左部为AGBC子集的那些函数依子集的那些函数依 赖，又得到赖，又得到CGH, CGI , BH，于是，于是 X(2)=X(1)HI=AGBCHI; 因为因为X(2)已等于全部属性集合已等于全部属性集合,所以所以(AG)F+=AGBCHI 。 31 【例例3】 U = (A, B, C, D, E,G), F = ABC, CA, BCD, ACDB, DEG , BEC , CGBD, CEAG , 计算计算 (BD)F+ 。 解：解： X(3)已等于全部属性集合已等于全部属性集合,所以所以(BD)F+=ABCDEG 。 32 4. 函数依赖集的覆盖问题函数依赖集的覆盖问题

31、 (1) 函数依赖集的等价函数依赖集的等价 从蕴含从蕴含(或导出或导出)的概念出发，又引出了两个函的概念出发，又引出了两个函 数依赖集的等价和最小依赖集的概念。数依赖集的等价和最小依赖集的概念。 【定义定义6.14】 如果如果G+=F+，就说函数依赖集，就说函数依赖集F覆盖覆盖 G(F是是G的覆盖，或的覆盖，或G是是F的覆盖的覆盖)，或，或F与与G等价。等价。 引理引理6.3： F+=G+ 的充分必要条件是的充分必要条件是F G+ ,和和G F+ 。 33 要判定要判定F G+，只须逐一对，只须逐一对F中的函数依赖中的函数依赖 XY，考察，考察 Y 是否属于是否属于XG+ 就行了。就行了。 因

32、此引理因此引理6.3 给出了判断两个函数依赖集等价的给出了判断两个函数依赖集等价的 可行算法。可行算法。 34 【例例4】U = (A, B, C, D), F = AB, BC, CD, CB, G = AC, BD, BC, CB,问，问，F与与G 是否等价。是否等价。 解：解： (1) AB，AG+=ACBD,B AG+, ABG+ (2) BC，BG+=BDC,C BG+, BCG+ (3) CD，CG+=CBD,D CG+, CDG+ (4) CB，CG+=CBD,B CG+, CBG+ F G+ 35 【例例4】U = (A, B, C, D), F = AB, BC, CD, C

33、B, G = AC, BD, BC, CB,问，问，F与与G 是否等价。是否等价。 同理：同理： (1) AC，AF+=ABCD,C AF+, ACF+ (2) BD，BF+=BCD,D BF+, BDF+ (3) BC，BF+=BCD,C BG+, BCF+ (4) CB，CF+=CDB,B CF+, CBF+ G F+ F G 36 （2） 最小函数依赖集最小函数依赖集 【定义定义6.15】 如果函数依赖集如果函数依赖集F满足下列条件，则满足下列条件，则 称称F为一个极小函数依赖集。亦称为最小依赖集或为一个极小函数依赖集。亦称为最小依赖集或 最小覆盖。最小覆盖。 lF中任一函数依赖的右部仅

34、含有一个属性。中任一函数依赖的右部仅含有一个属性。 lF中不存在这样的函数依赖中不存在这样的函数依赖XA，使得，使得 F与与F-XA等价。等价。 lF中不存在这样的函数依赖中不存在这样的函数依赖XA, X有真子集有真子集Z使使 得得F-XAZA与与F等价。等价。 37 三个条件的作用：三个条件的作用： （1）单属性化：）单属性化：保证每个函数依赖保证每个函数依赖X A，A不不 会是组合的属性会是组合的属性 。 （2）无冗余化：）无冗余化：保证保证F中没有重复的函数依赖。中没有重复的函数依赖。 （3）既约化：）既约化：保证每个函数依赖左部的属性最小保证每个函数依赖左部的属性最小 化化 。 38

35、【例例5】 考察考察6.l节中的关系模式节中的关系模式SU,F,其中：其中： U=SNO，SDEPT，MN，CNAME，G, F=SNOSDEPT，SDEPTMN，(SNO,CNAME)G 设设F=SNOSDEPT，SNOMN，SDEPTMN， (SNO，CNAME)G，(SNO，SDEPT)SDEPT 根据定义根据定义6.15可以验证可以验证F是最小覆盖，而是最小覆盖，而F不是。不是。 因为因为F-SNOMN与与F 等价等价, F-(SNO,SDEPT)SDEPT与与F 等价。等价。 39 【定理定理6.3】 每一个函数依赖集每一个函数依赖集F均等价于一个极小均等价于一个极小 函数依赖集函数

36、依赖集Fm。此。此Fm称为称为F的最小依赖集。的最小依赖集。 求函数依赖集求函数依赖集F的最小覆盖的方法：的最小覆盖的方法： (1) 检查检查F中每个函数依赖中每个函数依赖FDi：XA， 若若A=A1,A2, ,Ak，k 2，根据分解原则，根据分解原则， 用用 XAj |j=1，2， k 来取代来取代XA。 (2) 检查检查F中每个函数依赖中每个函数依赖FDi：XA， 令令G=F-XA， 若若A XG+， 则从则从F中去掉此函数依赖。中去掉此函数依赖。 由于由于F与与G =F-XA等价的充要条件是等价的充要条件是A XG+ 因此因此F变换前后是等价的。变换前后是等价的。 40 (3)检查检查F

37、中各函数依赖中各函数依赖FDi：XA， 设设X=B1,B2,Bm， 检查检查Bi （i=l，2，m），）， 若若A (X-Bi) F+ ， 则以则以X-Bi 替换替换X。 由于由于F与与F-XAZA等价的充要条件是等价的充要条件是 A ZF+ ，其中，其中Z=X-Bi 因此因此F变换前后是等价的。变换前后是等价的。 41 【例例6】 F = AB，BA，BC，AC，CA Fm1= AB，BC，CA Fm2= AB，BA，AC，CA (1) F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。 (2) AB，令，令G=F-AB AG+=AC, B AG+，保留，保留AB B

38、A，令，令G=F-BA BG+=BCA,ABG+，从，从F中去掉中去掉BA F = AB，BC，AC，CA BC，令，令G=F-BC BG+=B,C BG+，在，在F中保留中保留BC AC，令，令G=F-AC AG+=ABC,CAG+，从，从F中去掉中去掉AC F = AB，BC，CA CA，令，令G=F-CA CG+=C,C CG+，在，在F中保留中保留CA F等价于等价于Fm1 42 【例例6】 F = AB，BA，BC，AC，CA Fm2= AB，BA，AC，CA (1) F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。 (2) BC，令，令G=F-BC BG+

39、=BAC,CBG+，从，从F中去掉中去掉BC F = AB，BA，AC，CA AB，令，令G=F-AB AG+=AC,B AG+，保留，保留AB BA，令，令G=F-BA BG+=B, A BG+，在，在F中保留中保留BA AC，令，令G=F-AC AG+=AB,C AG+，在，在F中保留中保留AC CA，令，令G=F-CA CG+=C,A CG+，在，在F中保留中保留CA F等价于等价于Fm2 43 【说明说明】F的最小依赖集的最小依赖集Fm不一定是唯一的，不一定是唯一的， 它和对各函数依赖它和对各函数依赖FDi 及及XA中中X各属性的处置各属性的处置 顺序有关。顺序有关。 44 (1)判断

40、判断CGB，G=F CGB= CA，AG，BA (CG)G+=A，C，G，B A，C，G 检查检查 CA , G=F CA = AG，CGB，BA (C)G+= C A C 检查检查 AG , G=F AG = CA，CGB ，BA (A)G+= A G A 检查检查 BA , G=F BA = CA，AG，CGB (B)G+= B A B (2)检查检查 CGB (CG-C)F+ =(G)F+ = G B G 检查检查 CGB (CG-G)F+ =(C)F+ = CAGB BCAGB 所以：所以： 以以C 代替代替CG 最后，最后，Fm = CA，AG，CB，BA 例如：例如：F = CA，

41、AG，CGB，BA， 求最小覆盖求最小覆盖 Fm。 45 6.4 模式的分解模式的分解 解决的问题：解决的问题： (1)什么叫模式的分解？什么叫模式的分解？ (2)分解后，原关系中的信息和语义分解后，原关系中的信息和语义(是否会丢失是否会丢失)？ 把低一级的关系模式分解为若干个高一级的关系把低一级的关系模式分解为若干个高一级的关系 模式的方法并不是唯一的。模式的方法并不是唯一的。 只有能够保证分解后的关系模式与原关系模式等只有能够保证分解后的关系模式与原关系模式等 价，分解方法才有意义。价，分解方法才有意义。 46 【定义定义6.16 】关系模式关系模式R的一个分解：的一个分解： = R1，R

42、2，Rn 其中：其中： （1）U=U1U2Un， （2）且不存在）且不存在 Ui Uj，1i，j n，Fi 为为 F在在 Ui 上上 的投影。的投影。 【定义定义6.17】 函数依赖集合函数依赖集合XY | XY F+XY Ui 的一个覆盖的一个覆盖 Fi 叫作叫作 F 在属性在属性 Ui 上的投影。上的投影。 47 例例: SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc SL2NF 存在问题存在问题 插入异常插入异常 删除异常删除异常 冗余度大冗余度大 修改复杂修改复杂 分解方法分解方法 可以有多种可以有多种 SL Sno SdeptSl

43、oc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B 48 SN SD SO Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 PH 95005 分解后数据库丢失了许多信息分解后数据库丢失了许多信息 例如无法查询例如无法查询95001学生所学生所 在系或所在宿舍。如果分解后在系或所在宿舍。如果分解后 的关系可以通过自然连接恢复的关系可以通过自然连接恢复 为原来的关系，那么这种分解为原来的关系，那么这种分解 就没有丢失信息。就没有丢失信息。 希望在分解过程中不丢失希望在分解过程

44、中不丢失 信息，这个问题称为信息，这个问题称为无损连接无损连接 或连接不失真或连接不失真。 （1） SL分解为下面三个关系分解为下面三个关系 模式：模式： SN(Sno) SD(Sdept) SO(Sloc) 49 NL DL Sno Sloc Sdept Sloc 95001 A CS A 95002 B IS B 95003 C MA C 95004 B PH B 95005 B （2） SL分解为下面二个关系模式：分解为下面二个关系模式： NL(Sno, Sloc) F1=Sno Sloc DL(Sdept, Sloc) F2=Sdept Sloc 50 NLDL Sno Sloc Sd

45、ept 95001 A CS 95002 B IS 95002 B PH 95003 C MA 95004 B IS 95004 B PH 95005 B IS 95005 B PH NL DL比原来的比原来的SL关系多了关系多了3个元组个元组 无法知道无法知道95002、95004、95005 究竟是哪个系的学生。究竟是哪个系的学生。 元组增加了，信息丢失了。元组增加了，信息丢失了。 51 F1F2=SnoSloc, SdeptSloc F= SnoSdept,SdeptSloc,SnoSloc (F1F2)+=SnoSloc, SdeptSloc F+= SnoSdept,SdeptSlo

46、c,SnoSloc (F1F2)+ F+ ，说明分解后，有些函数依赖丢失，说明分解后，有些函数依赖丢失 了。了。 希望在分解过程中不丢失函数依赖，这个问希望在分解过程中不丢失函数依赖，这个问 题称为分解的依赖保持性。题称为分解的依赖保持性。 52 ND NL Sno Sdept Sno Sloc 95001 CS 95001 A 95002 IS 95002 B 95003 MA 95003 C 95004 IS 95004 B 95005 PH 95005 B （3） 将将SL分解为下面二个关系模式：分解为下面二个关系模式： ND(Sno, Sdept) F1=Sno Sdept NL(Sn

47、o, Sloc) F2=Sno Sloc 53 NDNL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 CS A 95005 PH B 与与SL关系一样，因此关系一样，因此没有丢失信息没有丢失信息 F+= SnoSdept,SdeptSloc,SnoSloc (F1F2)+=SnoSdept, SnoSloc (F1F2)+ F+ ，说明分解后，说明分解后，有些函数依赖丢失了有些函数依赖丢失了。 54 ND DL Sno Sdept Sdept Sloc 95001 CS CS A 95002 IS IS B 95003 MA MA

48、 C 95004 IS PH B 95005 PH （4） 将将SL分解为下面二个关系模式：分解为下面二个关系模式： ND(Sno, Sdept) F1=Sno Sdept DL(Sdept, Sloc) F2=Sdept Sloc 55 NDDL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 CS A 95005 PH B 与与SL关系一样，因此关系一样，因此没有丢失信息没有丢失信息 F+= SnoSdept,SdeptSloc,SnoSloc (F1F2)+=SnoSdept, SdeptSloc,SnoSloc (F1F2)+

49、 = F+ ，说明分解后，说明分解后，函数依赖没有丢失。函数依赖没有丢失。 56 6.4.1 三种模式分解的等价定义三种模式分解的等价定义 （1）分解具有无损连接性）分解具有无损连接性 （2） 分解要保持函数依赖分解要保持函数依赖 （3）分解既要保持函数依赖，又要具有无损连接性）分解既要保持函数依赖，又要具有无损连接性 l如果一个分解具有无损连接性，则它能够保证不丢如果一个分解具有无损连接性，则它能够保证不丢 失信息。失信息。 l如果一个分解保持了函数依赖，则它可以减轻或解如果一个分解保持了函数依赖，则它可以减轻或解 决各种异常情况。决各种异常情况。 l分解具有无损连接性和分解保持函数依赖是两

50、个互分解具有无损连接性和分解保持函数依赖是两个互 相独立的标准。具有无损连接性的分解不一定能够相独立的标准。具有无损连接性的分解不一定能够 保持函数依赖。同样，保持函数依赖的分解也不一保持函数依赖。同样，保持函数依赖的分解也不一 定具有无损连接性。定具有无损连接性。 57 6.4.2 具有无损连接性的模式分解具有无损连接性的模式分解 【定义定义】关系模式关系模式R的一个分解的一个分解 = R1， R2， ，Rn 若若R与与R1、R2、Rn自然连接的结果相等，则称自然连接的结果相等，则称 关系模式关系模式R的这个分解的这个分解具有无损连接性（具有无损连接性（Lossless join） 具有无损

51、连接性的分解保证不丢失信息。具有无损连接性的分解保证不丢失信息。 无损连接性不一定能解决插入异常、删除异常、无损连接性不一定能解决插入异常、删除异常、 修改复杂、数据冗余等问题。修改复杂、数据冗余等问题。 58 连接不失真的检验连接不失真的检验 关系模式关系模式R ,U = Ai ，(i=1,2,n) = R1 , R2, , Rk是是R的的 一个分解，一个分解， （1）构造一个）构造一个n列列k行的一个表，第行的一个表，第i行对应行对应Ri，第，第j列对应列对应Aj； RI AJA1A2An R1 R2 Rk 59 连接不失真的检验连接不失真的检验 （2）填表，第）填表，第i行第行第j列上填

52、写列上填写aj；否则填写；否则填写bi,j （3）修改表：逐一扫描函数依赖，在）修改表：逐一扫描函数依赖，在x列上相同，列上相同，y上必定相上必定相 同；同； （4）重复（）重复（3），直至，扫描完所有的函数依赖。），直至，扫描完所有的函数依赖。 RI AJA1A2An R1 R2 Rk 60 【例例1】U=A,B,C,D,E, F=ABC, CD,DE =(A, B, C), (C, D), (D, E) RI AJ ABCDE R1 a1a2a3b14 a4b15 a5 R2 b21b22a3a4b25 a5 R3 b31b32b33a4a5 =(A, B, C), (C, D), (D,

53、 E)为无损分解。为无损分解。 61 分解分解1具有无损连接性，具有无损连接性， 分解分解2不具有无损连接性不具有无损连接性 ABC a1a2 a1a3 AB AC ABC a1a2 a2a3 AB BC 【例例2】R(A,B,C), F=AB, C B 分解分解1=(A,B) AB, (A,C) 分解分解2=(A,B) AB, (B,C) CB 分析两种分解的无损连接性？分析两种分解的无损连接性？ 62 【定理定理6.5 】关系模式关系模式R(U)的一个分解，的一个分解， = R1 , R2, 如 果如 果 U 1 U 2 U 1 U 2 F + ， 或， 或 U1U2U2 U1F+，则，则

54、 具有无损连接性。具有无损连接性。 63 【例例3】U=S#，SD，MN，C#，G F=S#SD，S#MN，SDMN，(S#,C#)G U1=S#，SD , F1=S#SD U2=S#, MN, C#, G, F2=S#MN, (S#,C#)G 解：解： U1U2= S# U1-U2= SD U1U2U1 U2F+ 该分解该分解 具有无损连接性。具有无损连接性。 如果两个关系模式之间的公共属性集至少包含如果两个关系模式之间的公共属性集至少包含 其中一个关系模式的码，则此分解具有无损连接其中一个关系模式的码，则此分解具有无损连接 性。性。 64 【例例4】U=A，B，C F=AB，CB U1=A

55、，B , F1=AB U2=B, C, F2=CB 解：解： U1U2= B U1-U2= A , U2-U1= C BA, BC F+ 该分解该分解 不不具有无损连接性。具有无损连接性。 65 6.4.3 保持函数依赖的模式分解保持函数依赖的模式分解 【定义定义6.19】设关系模式设关系模式R被分解为若干个被分解为若干个 关系模式关系模式R1，R2，Rn 若若F+ = ( Fi)+， 则称则称R 的分解的分解 = R1 , , Rn 保持函数依赖。保持函数依赖。 即即F所逻辑蕴含的函数依赖一定也由分解得到所逻辑蕴含的函数依赖一定也由分解得到 的某个关系模式中的函数依赖的某个关系模式中的函数依

56、赖Fi所逻辑蕴含，则所逻辑蕴含，则 称关系模式称关系模式R的这个分解是保持函数依赖的的这个分解是保持函数依赖的 （Preserve dependency）。）。 66 【例例1】 SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc 分解：分解： ND(Sno, Sdept) F1=Sno Sdept NL(Sdept, Sloc) F2=Sdept Sloc F+= SnoSdept,SdeptSloc,SnoSloc (F1F2)+=SnoSdept, SdeptSloc,SnoSloc (F1F2)+ = F+ ，说明分解后，函数依赖没有丢

57、失。，说明分解后，函数依赖没有丢失。 67 【例例2】 R(A,B,C), F=AB, C B 分解分解1=(A,B) AB, (A,C) 分解分解2=(A,B) AB), (B,C) CB 分析两种分解的依赖保持性？分析两种分解的依赖保持性？ 分解分解1：只有：只有AB，显然，分解，显然，分解1不具有依赖保不具有依赖保 持性持性 分解分解2：保留了所有函数依赖，具有依赖保持性：保留了所有函数依赖，具有依赖保持性 68 【例如例如】 SL（Sno， Sdept， Sloc） 第一种分解方法既不具有无损连接性，也未保持函数第一种分解方法既不具有无损连接性，也未保持函数 依赖，它不是原关系模式的一

58、个等价分解；依赖，它不是原关系模式的一个等价分解；SN(Sno)， SD(Sdept)，SO(Sloc) 第二种分解方法没有保持函数依赖，也不具有无损连第二种分解方法没有保持函数依赖，也不具有无损连 接性；接性；NL(Sno, Sloc)，DL(Sdept, Sloc) 第三种分解方法具有无损连接性，但未保持函数依赖；第三种分解方法具有无损连接性，但未保持函数依赖； ND(Sno, Sdept)，NL(Sno, Sloc) 第四种分解方法既具有无损连接性，又保持了函数依第四种分解方法既具有无损连接性，又保持了函数依 赖；赖；ND(Sno, Sdept) ，NL(Sdept, Sloc) 69

59、【例例3】U=A，B，C F=AB，CB U1=A，B , F1=AB U2=A, C, F2=AC 解：解： U1U2= A U1-U2= B , U2-U1= C U1U2- U1-U2 F+ 即：即：AB F+ 该分解该分解 具有无损连接性。具有无损连接性。 (F1F2)+=AB ,AC (F1F2)+ F+ ，说明分解后，不具有依赖保持性。，说明分解后，不具有依赖保持性。 70 【例例4】U=A，B，C，D R1=A，B， R2=B，C， R3=C，D F1=BC，CD F2=AB，CD 试问：分解相对于试问：分解相对于F1和和F2是否无损分解？是否无损分解？ 71 几个命题几个命题

60、（1）一个无损连接的分解不一定具有依赖保持性，）一个无损连接的分解不一定具有依赖保持性， 反之亦然。反之亦然。 （2）若要求模式分解保持函数依赖，则模式分离总）若要求模式分解保持函数依赖，则模式分离总 能达到能达到3NF，但不一定能达到，但不一定能达到BCNF。 （3）若要求分解既保持函数依赖，又具有无损连接）若要求分解既保持函数依赖，又具有无损连接 性，则模式分离可以达到性，则模式分离可以达到3NF，但不一定能达到，但不一定能达到 BCNF。 （4）若要求分解具有无损连接性，则模式分离一定）若要求分解具有无损连接性，则模式分离一定 可以达到可以达到4NF。 72 补充：求解关系模式的候选码补