第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），），它的码它的码是（是（C，T，B），），所以所以属于属于BCNF。 存在的问题：存在的问题：(1)插入异常：

3、插入异常：当某门当某门课程增加一名教员时，课程增加一名教员时，该门课程有多少本参该门课程有多少本参考书就必须插入多少考书就必须插入多少个元组；同样当某门个元组；同样当某门课程需要增加一本参课程需要增加一本参考书时，它有多少个考书时，它有多少个教员就必须插入多少教员就必须插入多少个元组。个元组。4普通物理学普通物理学光学原理光学原理物理习题集物理习题集普通物理学普通物理学光学原理光学原理物理习题集物理习题集数学分析数学分析微分方程微分方程高等代数高等代数数学分析数学分析微分方程微分方程高等代数高等代数李李 勇勇李李 勇勇李李 勇勇王王 军军王王 军军王王 军军李李 勇勇李李 勇勇李李 勇勇张张

4、平平张张 平平张张 平平 物物 理理物物 理理物物 理理物物 理理物物 理理物物 理理数数 学学数数 学学数数 学学数数 学学数数 学学数数 学学 参考书B教员T课程C存在的问题：存在的问题：(2)删除异常：删除异常：当删当删除一门课程的某个教除一门课程的某个教员或者某本参考书时，员或者某本参考书时，需要删除多个元组。需要删除多个元组。(3)更新异常：更新异常：当一当一门课程的教员或参考门课程的教员或参考书作出改变时，需要书作出改变时，需要修改多个元组。修改多个元组。(4)数据冗余：数据冗余：同一同一门课的教员与参考书门课的教员与参考书的信息被反复存储多的信息被反复存储多次。次。5【定义定义6

5、.9】 关系模式关系模式R(U)，X、Y、Z U， 并且并且Z = U X Y， 多值依赖多值依赖X Y 成立当且仅当对成立当且仅当对R(U) 的任一关系的任一关系r，给定的一对（，给定的一对（x，z）值有一组）值有一组y 的值，这组值仅仅决定于的值，这组值仅仅决定于x 值而与值而与z 值无关。值无关。 物物 理理,普通物理学普通物理学 李李 勇勇,王王 军军物物 理理,光学原理光学原理 李李 勇勇,王王 军军物物 理理,物理习题集物理习题集 李李 勇勇,王王 军军对于对于C的每一个值，的每一个值，T有一组值与之对应，而不论有一组值与之对应，而不论B取何值。取何值。若若XY而而Z=，则称，则称

6、XY为平凡的多值依赖，为平凡的多值依赖，否则称否则称XY为非平凡的多值依赖。为非平凡的多值依赖。6【形式化定义形式化定义】在在R（U）的任一关系）的任一关系r中，如果存中，如果存在元组在元组t、s ，使得，使得tX=sX，那么就必然存在元组，那么就必然存在元组 w，v r，（，（w，v可以与可以与s，t相同），使得相同），使得wX=vX=tX，而，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交换（即交换s，t元组的元组的Y值所得值所得的两个新元组必在的两个新元组必在r中），则中），则Y多值依赖于多值依赖于X，记为，记为XY。 这里，这里，X，Y是是U的子集，的子集，Z=U-X-Y。 t

7、 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 关系模式关系模式WSC（ W，S，C ）中，）中，W表示仓库，表示仓库，S表示保管员，表示保管员，C表示商品。表示商品。 假设，每个仓库有若干个保管员，有若干种商假设，每个仓库有若干个保管员，有若干种商品。每个保管员包管所在仓库的所有商品，每种商品。每个保管员包管所在仓库的所有商品

8、，每种商品被该仓库的所有保管员包管。品被该仓库的所有保管员包管。 存在是函数依赖：存在是函数依赖： W S W C81. 多值依赖多值依赖的的性质性质 （1）多值依赖具有对称性，多值依赖具有对称性，即即 若若XY，则，则XZ，其中，其中Z=UXY。 （2）多值依赖具有多值依赖具有传递传递性，性，即即 若若XY，则，则YZ，则，则XZ-Y 。 （3）函数依赖是多值依赖的特例，）函数依赖是多值依赖的特例，即即 若若XY， 则则XY。 若若XY，UXY=， 则称则称XY 为平凡的多为平凡的多值依赖值依赖 。（4） 若若XY，XZ，则，则XYZ 。（5）若若XY，XZ，则，则XYZ 。（6）若若XY，

9、XZ，则，则XY-Z ，XZ-Y 。92. 多值依赖多值依赖与函数依赖的与函数依赖的区别区别（1）XY的有效性与属性集范围有关的有效性与属性集范围有关XY在在U上成立上成立 XY在属性集在属性集W（XY W U）上成立。上成立。反之，反之，XY在属性集在属性集W（XY W U）上成立，但在）上成立，但在U上不一定成立。上不一定成立。若在若在R(U)上，上，XY在属性集在属性集W(XY W U)上成立，则上成立，则称称XY为为R(U) 的嵌入式多值依赖。的嵌入式多值依赖。XY 的的 有效性仅决定于有效性仅决定于X、Y 属性集上的值，它在任何属性集上的值，它在任何属性集属性集W（XY W U） 上

10、都成立。上都成立。（2）若）若XY 在在R(U) 上成立，则对于任何上成立，则对于任何Y Y， 均有均有XY 成立。成立。 若若XY在在R(U)上成立，则不能断言对于上成立，则不能断言对于Y Y，是，是否有否有XY 成立。成立。10【定义定义6.10】 关系模式关系模式R 1NF， 若若XY（Y X） 是非平凡的多值依赖，且是非平凡的多值依赖，且X 含有含有码，则称码，则称R 4NF。 如关系模式如关系模式CTB，CT，CB， 码为码为(C, T , B)，C不是候选码，所以不是候选码，所以CTB 4NF。 如果一门课如果一门课Ci 有有m 个个 教员，教员，n 本本 参考书，则关参考书，则关

11、系中分量为系中分量为Ci 的元组共有的元组共有mn 个，数据冗余非常个，数据冗余非常大。大。 规范化：规范化： 4NF的要求是：消除非平凡且非函数依赖的多值的要求是：消除非平凡且非函数依赖的多值依赖。依赖。 将将CTB 分解为分解为CT（C，T），），CB（C，B），）， 在分解后的关系中分量为在分解后的关系中分量为Ci 的元组共有的元组共有m + n 个。个。 116.3 数据依赖的蕴涵与公理系统数据依赖的蕴涵与公理系统1. 函数依赖的逻辑蕴含定义函数依赖的逻辑蕴含定义 已经讨论了函数依赖的类型及其对数据库模式已经讨论了函数依赖的类型及其对数据库模式设计的影响和处理方法；设计的影响和处理方法

12、； 关于关于“处理方法处理方法”即范式设计，事实上是由模即范式设计，事实上是由模式分解而得，而模式分解的理论与方法是以数据依式分解而得，而模式分解的理论与方法是以数据依赖理论为基础理论的，所以需要较全面的讨论数据赖理论为基础理论的，所以需要较全面的讨论数据依赖理论；依赖理论； 数据库专家数据库专家Armstrong等提出一组定义和推理规等提出一组定义和推理规则，并形成了一个有效而完备的理论体系，即则，并形成了一个有效而完备的理论体系，即Armstrong公理系统。公理系统。 数据依赖的公理系统是模式分解的理论基础。数据依赖的公理系统是模式分解的理论基础。12 函数依赖函数依赖F是很大的，如果依

13、靠语义分析方法是很大的，如果依靠语义分析方法找出一个关系模式的所有函数依赖，是一件很不找出一个关系模式的所有函数依赖，是一件很不容易的事。实际上，也是没有必要的，因为一组容易的事。实际上，也是没有必要的，因为一组函数依赖的存在，必定引起另外一组函数依赖的函数依赖的存在，必定引起另外一组函数依赖的出现。因此，出现。因此，可以用推理的方法，从一组已知的可以用推理的方法，从一组已知的函数依赖推导出另外一组函数依赖，而不必完全函数依赖推导出另外一组函数依赖，而不必完全用语义分析方法找出一个关系模式的所有函数依用语义分析方法找出一个关系模式的所有函数依赖赖。13【例例】关系模式关系模式 R=(A,B,C

14、)函数依赖集函数依赖集F=AB,BC, 则：必存在则：必存在AC。 这个例子说明：函数依赖集这个例子说明：函数依赖集F=AB,BC与与F=AB,BC ,AC之间存在着某种因果关之间存在着某种因果关系，即从系，即从F可以推导出可以推导出F，反之亦然。，反之亦然。 两个函数依赖集之间的这种互为因果关系称两个函数依赖集之间的这种互为因果关系称为逻辑蕴涵，即一个函数依赖集逻辑蕴涵另外一为逻辑蕴涵，即一个函数依赖集逻辑蕴涵另外一个函数依赖集。个函数依赖集。 F=AB,BC与与F=AB,BC ,AC相相互逻辑蕴涵。互逻辑蕴涵。14【定义定义6.11】对于满足一组函数依赖对于满足一组函数依赖F的关系模式的关

15、系模式RU,F,其任何一个关系其任何一个关系r,若函数依赖若函数依赖XY都成立都成立(即即r中任意两元组中任意两元组t,s,若若tX=sX,则则tY=sY),则称则称F逻辑蕴含逻辑蕴含XY，或称，或称XY 可从可从F中推出。中推出。【例例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逻辑蕴

16、涵逻辑蕴涵AC。15【例例2】给定给定U=X，Y，Z，W，函数依赖集，函数依赖集F=XY，YZ，给定下列的关系实例，给定下列的关系实例r如表如表1所示，显然，满足函数依赖集所示，显然，满足函数依赖集F。元组号元组号XYZWt1adbat2adbbt3bcbct4bcbdt5ceae 例例2中，可观察到中，可观察到r还满足还满足XZ，但在函数依，但在函数依赖集赖集F中没有中没有XZ。那么，就需要考虑。那么，就需要考虑r除满足除满足F之外，是否还会满足一些其它的函数依赖？之外，是否还会满足一些其它的函数依赖？ 16 在上面的例子中，在上面的例子中，r实例满足实例满足F外，还满足外，还满足F所不所不

17、包括的包括的XZ，这就产生一个问题，如何从，这就产生一个问题，如何从F=XY，YZ推导得出推导得出XZ ? 这需要一套规则这需要一套规则从给定的函数依赖集推出其蕴涵的函数依赖。从给定的函数依赖集推出其蕴涵的函数依赖。 一套推理规则：是模式分解算法的理论基础一套推理规则：是模式分解算法的理论基础用途：用途：l从一组函数依赖求得蕴含的函数依赖从一组函数依赖求得蕴含的函数依赖l这组推理规则是这组推理规则是l974年首先由年首先由Armstrong提出来的提出来的 172. Armstrong公理系统公理系统 若若U为关系模式为关系模式R的属性全集，的属性全集，F为为U上的一组上的一组函数依赖，设函数

18、依赖，设X、Y、Z、W均为均为R的子集，对的子集，对R(U,F)有以下的推理规则：有以下的推理规则：（1）A1(自反律自反律)：若：若Y X U ，则，则XY为为F所所蕴涵；蕴涵；（注意，由自反律所得到的函数依赖均是平（注意，由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于凡的函数依赖，自反律的使用并不依赖于F。 ）（2）A2(增广律增广律): 若若XY为为F所蕴涵，且所蕴涵，且 Z U，则则XZYZ为为F所蕴涵；所蕴涵； （YZ表示并集）表示并集） （3）A3(传递律传递律): 若若XY,YZ为为F所蕴涵，则所蕴涵，则XZ为为F所蕴涵。所蕴涵。18【定理定理6.l】Arms

19、trong推理规则是正确的。推理规则是正确的。证明：证明： (1) 设设Y X U 。 对对RU,F的任一关系的任一关系r中的中的任意两个元组任意两个元组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及及

20、YZ为为F所蕴含。所蕴含。 对对RU,F的任一关系的任一关系r中的任意两个元组中的任意两个元组t,s 。 若若tX=sX,由于由于XY,有有tY=sY； 再由再由YZ,有有tZ=sZ,所以所以XZ为为F所蕴含，传所蕴含，传递律得证。递律得证。 人们把自反律人们把自反律,传递律和增广律称为传递律和增广律称为Armstrong公公理系统。理系统。 20Armstrong公理的有效性及完备性公理的有效性及完备性A = f | 可用可用Armstrong公理从公理从F中导出的函数依赖中导出的函数依赖f B = f | 被被F所逻辑蕴涵的函数依赖所逻辑蕴涵的函数依赖f l有效性：用有效性：用Armstr

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

22、蕴涵。 22证明：证明： （1）推论）推论1显然成立。显然成立。 （2）推论）推论2的证明。的证明。由由XY，利用增广律可得，利用增广律可得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

23、 （分解规则）（分解规则）（4） AD, DE A E （传递律）（传递律）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 公理导出？公理导出？253. 函数依赖的闭包

24、理论函数依赖的闭包理论（1）函数依赖闭包、属性集闭包）函数依赖闭包、属性集闭包【定义定义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的闭包。的闭包。解：（解

25、：（1）若）若X=A A B,BC AC（传递律）（传递律） 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+。 于是，判定于

26、是，判定XY 是否能由是否能由F根据根据Armstrong公公理导出的问题，就转化为求出理导出的问题，就转化为求出XF+，判定，判定Y是否为是否为XF+的子集的问题。的子集的问题。 28【算法算法6.1】（求属性集（求属性集X(X U)关于关于U上的函数依赖上的函数依赖集集F的闭包的闭包XF+）l输入输入 ：X，Fl输出输出 ： 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) 若相等或若相等或

27、X(i)=U 则则X(i)就是就是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子集的那些函子集的那些函数依赖，

28、又得到数依赖，又得到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)，所

29、以再找出左部为，所以再找出左部为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 。324. 函数依赖集的覆盖问题函数依赖集的覆盖问题(1) 函数

30、依赖集的等价函数依赖集的等价 从蕴含从蕴含(或导出或导出)的概念出发，又引出了两个函的概念出发，又引出了两个函数依赖集的等价和最小依赖集的概念。数依赖集的等价和最小依赖集的概念。 【定义定义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+ 就行了。就行了。 因此引理因此引理6.3

31、给出了判断两个函数依赖集等价的给出了判断两个函数依赖集等价的可行算法。可行算法。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, CB, G = AC, BD, BC, CB,问

32、，问，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 G36（2） 最小函数依赖集最小函数依赖集 【定义定义6.15】 如果函数依赖集如果函数依赖集F满足下列条件，则满足下列条件，则称称F为一个极小函数依赖集。亦称为最小依赖集或为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。最小覆盖。 lF中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。 lF中不存在这样

33、的函数依赖中不存在这样的函数依赖XA，使得，使得 F与与F-XA等价。等价。 lF中不存在这样的函数依赖中不存在这样的函数依赖XA, X有真子集有真子集Z使使得得F-XAZA与与F等价。等价。37三个条件的作用：三个条件的作用：（1）单属性化：）单属性化：保证每个函数依赖保证每个函数依赖X A，A不不会是组合的属性会是组合的属性 。 （2）无冗余化：）无冗余化：保证保证F中没有重复的函数依赖。中没有重复的函数依赖。 （3）既约化：）既约化：保证每个函数依赖左部的属性最小保证每个函数依赖左部的属性最小化化 。 38【例例5】 考察考察6.l节中的关系模式节中的关系模式SU,F,其中：其中： U=

34、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均等价于一个极小均等价于一个极小函数依赖集函数依赖集Fm。此。此Fm称为称为F的最小依赖集。的最小依赖集。求函数依赖集求函数依赖集F的最小覆

35、盖的方法：的最小覆盖的方法：(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中各函数依赖中各函数依赖FDi：XA， 设设X=B1,B2,Bm， 检查检查Bi （i=l，2，m），

36、）， 若若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+，保留，保留ABBA，令，令G=F-BA BG+=BCA,ABG+，从，从F中去掉中去掉BAF = AB，BC，AC，CA BC，

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

38、G+，保留，保留ABBA，令，令G=F-BA BG+=B, A BG+，在，在F中保留中保留BAAC，令，令G=F-AC AG+=AB,C AG+，在，在F中保留中保留ACCA，令，令G=F-CA CG+=C,A CG+，在，在F中保留中保留CAF等价于等价于Fm243【说明说明】F的最小依赖集的最小依赖集Fm不一定是唯一的，不一定是唯一的，它和对各函数依赖它和对各函数依赖FDi 及及XA中中X各属性的处置各属性的处置顺序有关。顺序有关。44(1)判断判断CGB，G=F CGB= CA，AG，BA (CG)G+=A，C，G，B A，C，G检查检查 CA , G=F CA = AG，CGB，BA

39、 (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，AG，CGB，BA， 求最小覆盖求最小覆盖Fm。456.4 模式的分解模式的分解解决的问题：解决的问题：(1)什么叫模式的分解？什么叫模式的分解？(2)分解

40、后，原关系中的信息和语义分解后，原关系中的信息和语义(是否会丢失是否会丢失)？ 把低一级的关系模式分解为若干个高一级的关系把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的。模式的方法并不是唯一的。 只有能够保证分解后的关系模式与原关系模式等只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义。价，分解方法才有意义。46【定义定义6.16 】关系模式关系模式R的一个分解：的一个分解：= R1，R2，Rn其中：其中：（1）U=U1U2Un，（2）且不存在）且不存在 Ui Uj，1i，j n，Fi 为为 F在在 Ui 上上的投影。的投影。【定义定义6.17】 函数依赖集合函

41、数依赖集合XY | XY F+XY Ui 的一个覆盖的一个覆盖 Fi 叫作叫作 F 在属性在属性 Ui 上的投影。上的投影。47 例例: SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc SL2NF 存在问题存在问题插入异常插入异常删除异常删除异常冗余度大冗余度大修改复杂修改复杂分解方法分解方法可以有多种可以有多种SL Sno SdeptSloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B 48SN SD SO Sno Sdept Sloc 95001 CS A 95002 I

42、S B 95003 MA C 95004 PH 95005 分解后数据库丢失了许多信息分解后数据库丢失了许多信息例如无法查询例如无法查询95001学生所学生所在系或所在宿舍。如果分解后在系或所在宿舍。如果分解后的关系可以通过自然连接恢复的关系可以通过自然连接恢复为原来的关系，那么这种分解为原来的关系，那么这种分解就没有丢失信息。就没有丢失信息。希望在分解过程中不丢失希望在分解过程中不丢失信息，这个问题称为信息，这个问题称为无损连接无损连接或连接不失真或连接不失真。（1） SL分解为下面三个关系分解为下面三个关系模式：模式： SN(Sno) SD(Sdept) SO(Sloc)49NL DL S

43、no 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 Sloc50NLDL Sno Sloc Sdept 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个

44、元组个元组 无法知道无法知道95002、95004、95005 究竟是哪个系的学生。究竟是哪个系的学生。 元组增加了，信息丢失了。元组增加了，信息丢失了。51F1F2=SnoSloc, SdeptSlocF= SnoSdept,SdeptSloc,SnoSloc(F1F2)+=SnoSloc, SdeptSlocF+= SnoSdept,SdeptSloc,SnoSloc(F1F2)+ F+ ，说明分解后，有些函数依赖丢失，说明分解后，有些函数依赖丢失了。了。希望在分解过程中不丢失函数依赖，这个问希望在分解过程中不丢失函数依赖，这个问题称为分解的依赖保持性。题称为分解的依赖保持性。52ND N

45、L 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(Sno, Sloc) F2=Sno Sloc53NDNL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 CS A 95005 PH B 与与SL关系一样，因此关系一样，因此没有丢失信息没有丢失信息F

46、+= SnoSdept,SdeptSloc,SnoSloc(F1F2)+=SnoSdept, SnoSloc(F1F2)+ F+ ，说明分解后，说明分解后，有些函数依赖丢失了有些函数依赖丢失了。54ND DL Sno Sdept Sdept Sloc 95001 CS CS A 95002 IS IS B 95003 MA MA C 95004 IS PH B 95005 PH （4） 将将SL分解为下面二个关系模式：分解为下面二个关系模式： ND(Sno, Sdept) F1=Sno Sdept DL(Sdept, Sloc) F2=Sdept Sloc55NDDL Sno Sdept Sl

47、oc 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)+ = F+ ，说明分解后，说明分解后，函数依赖没有丢失。函数依赖没有丢失。566.4.1 三种模式分解的等价定义三种模式分解的等价定义（1）分解具有无损连接性）分解具有无损连接性（2） 分解要保持函数依赖分解要保持函数依赖（3）分解既要保持函数依赖，又要具有无损连接性）分解既要保

48、持函数依赖，又要具有无损连接性l如果一个分解具有无损连接性，则它能够保证不丢如果一个分解具有无损连接性，则它能够保证不丢失信息。失信息。l如果一个分解保持了函数依赖，则它可以减轻或解如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。决各种异常情况。l分解具有无损连接性和分解保持函数依赖是两个互分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖的分解也不一保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。定具有无损连接性。576.4.2 具有无损连接性的模式分解

49、具有无损连接性的模式分解【定义定义】关系模式关系模式R的一个分解的一个分解 = R1，R2， ，Rn若若R与与R1、R2、Rn自然连接的结果相等，则称自然连接的结果相等，则称关系模式关系模式R的这个分解的这个分解具有无损连接性（具有无损连接性（Lossless join） 具有无损连接性的分解保证不丢失信息。具有无损连接性的分解保证不丢失信息。 无损连接性不一定能解决插入异常、删除异常、无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题。修改复杂、数据冗余等问题。58连接不失真的检验连接不失真的检验关系模式关系模式R ,U = Ai ，(i=1,2,n) = R1 , R2,

50、, Rk是是R的的一个分解，一个分解，（1）构造一个）构造一个n列列k行的一个表，第行的一个表，第i行对应行对应Ri，第，第j列对应列对应Aj；RI AJA1A2AnR1R2Rk59连接不失真的检验连接不失真的检验（2）填表，第）填表，第i行第行第j列上填写列上填写aj；否则填写；否则填写bi,j（3）修改表：逐一扫描函数依赖，在）修改表：逐一扫描函数依赖，在x列上相同，列上相同，y上必定相上必定相同；同；（4）重复（）重复（3），直至，扫描完所有的函数依赖。），直至，扫描完所有的函数依赖。RI AJA1A2AnR1R2Rk60【例例1】U=A,B,C,D,E, F=ABC, CD,DE =(

51、A, B, C), (C, D), (D, E)RI AJABCDER1a1a2a3b14 a4b15 a5R2b21b22a3a4b25 a5R3b31b32b33a4a5 =(A, B, C), (C, D), (D, E)为无损分解。为无损分解。61分解分解1具有无损连接性，具有无损连接性， 分解分解2不具有无损连接性不具有无损连接性ABCa1a2a1a3ABACABCa1a2a2a3ABBC【例例2】R(A,B,C), F=AB, C B 分解分解1=(A,B) AB, (A,C) 分解分解2=(A,B) AB, (B,C) CB分析两种分解的无损连接性？分析两种分解的无损连接性？62

52、【定理定理6.5 】关系模式关系模式R(U)的一个分解，的一个分解， = R1 , R2, 如 果如 果 U1 U2 U1 U2 F+， 或， 或U1U2U2 U1F+，则，则 具有无损连接性。具有无损连接性。63【例例3】U=S#，SD，MN，C#，GF=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+该分解该分解 具有无损连接性。具有无损连接性。 如果两个关系模式之间的公共属性集至少包含如果两个关系模式之间的公共属

53、性集至少包含其中一个关系模式的码，则此分解具有无损连接其中一个关系模式的码，则此分解具有无损连接性。性。64【例例4】U=A，B，C F=AB，CB U1=A，B , F1=AB U2=B, C, F2=CB解：解： U1U2= B U1-U2= A , U2-U1= C BA, BC F+该分解该分解 不不具有无损连接性。具有无损连接性。656.4.3 保持函数依赖的模式分解保持函数依赖的模式分解【定义定义6.19】设关系模式设关系模式R被分解为若干个被分解为若干个关系模式关系模式R1，R2，Rn 若若F+ = ( Fi)+， 则称则称R 的分解的分解 = R1 , , Rn 保持函数依赖。

54、保持函数依赖。 即即F所逻辑蕴含的函数依赖一定也由分解得到所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖的某个关系模式中的函数依赖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 SlocF+= SnoSdept,SdeptSloc,SnoSl

55、oc(F1F2)+=SnoSdept, SdeptSloc,SnoSloc(F1F2)+ = F+ ，说明分解后，函数依赖没有丢失。，说明分解后，函数依赖没有丢失。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）第一种分解方

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

57、又保持了函数依赖；赖；ND(Sno, Sdept) ，NL(Sdept, Sloc) 69【例例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试问：分解相对于试问：

58、分解相对于F1和和F2是否无损分解？是否无损分解？71 几个命题几个命题（1）一个无损连接的分解不一定具有依赖保持性，）一个无损连接的分解不一定具有依赖保持性，反之亦然。反之亦然。（2）若要求模式分解保持函数依赖，则模式分离总）若要求模式分解保持函数依赖，则模式分离总能达到能达到3NF，但不一定能达到，但不一定能达到BCNF。（3）若要求分解既保持函数依赖，又具有无损连接）若要求分解既保持函数依赖，又具有无损连接性，则模式分离可以达到性，则模式分离可以达到3NF，但不一定能达到，但不一定能达到BCNF。（4）若要求分解具有无损连接性，则模式分离一定）若要求分解具有无损连接性，则模式分离一定可以

59、达到可以达到4NF。72补充：求解关系模式的候选码补充：求解关系模式的候选码属性分类：属性分类：L类：只出现在函数依赖的左边的属性类：只出现在函数依赖的左边的属性R类：只出现在函数依赖的右边的属性类：只出现在函数依赖的右边的属性N类：在函数依赖的两边均未出现的属性类：在函数依赖的两边均未出现的属性LR类：出现在函数依赖的两边的属性类：出现在函数依赖的两边的属性73一、快速求解候选码的方法一、快速求解候选码的方法【定理定理1】对于给定的关系模式对于给定的关系模式R及其函数依赖集及其函数依赖集F,若若X(XR)是是L类属性类属性,则则X必为必为R的任一候选码的任一候选码的成员。的成员。【推论推论1

60、】对于给定的关系模式对于给定的关系模式R及其函数依赖集及其函数依赖集F,若若X(XR)是是L类属性类属性,且且X+包含了包含了R的全部属的全部属性性,则则X必为必为R的唯一候选码。的唯一候选码。 74快速求解候选码的方法快速求解候选码的方法【定理定理2】对于给定的关系模式对于给定的关系模式R及其函数依赖集及其函数依赖集F,若若X(XR)是是R类属性类属性,则则X不在任何候选码中。不在任何候选码中。【定理定理3】设有关系模式设有关系模式R及其函数依赖集及其函数依赖集F,如果如果X是是R的的N类属性类属性,则则X必包含在必包含在R的任一候选码中。的任一候选码中。【推论推论2】对于给定的关系模式对于