【教学课件】第10章数据依赖和关系模式的规范化.ppt

《【教学课件】第10章数据依赖和关系模式的规范化.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第10章数据依赖和关系模式的规范化.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1010章章 数据依赖和关系模式的数据依赖和关系模式的规范化规范化10.1 10.1 关系模式设计中的一些数据语义问题关系模式设计中的一些数据语义问题 数据的语义不但表现为完整性约束，对数据库数据的语义不但表现为完整性约束，对数据库的状态或状态的转换施加一定的限制，而且对关的状态或状态的转换施加一定的限制，而且对关系模式的设计也提出一定的要求。系模式的设计也提出一定的要求。属性间往往存在一定的依赖关系，而最基本的属性间往往存在一定的依赖关系，而最基本的依赖关系是函数依赖。所谓函数依赖是指一个或依赖关系是函数依赖。所谓函数依赖是指一个或一组属性的值可以决定其他属性的值。一组属性的值可以决定其

2、他属性的值。一般地讲，设，是关系的两个不同的属性组，一般地讲，设，是关系的两个不同的属性组，如果函数依赖于，或函数决定，则其依赖关如果函数依赖于，或函数决定，则其依赖关系可表示为系可表示为。设有一关系，具有下列属性：学号（设有一关系，具有下列属性：学号（S S）、课）、课程号（程号（C C）、成绩（）、成绩（G G）、任课教师姓名（）、任课教师姓名（TNTN）、教）、教师所在系名（师所在系名（D D）。这些数据具有下列语义：）。这些数据具有下列语义：（）学号是一个学生的标识，课程号是一门课程的标（）学号是一个学生的标识，课程号是一门课程的标识，这些标识与其代表的学生和课程分别一一对应；识，这些

3、标识与其代表的学生和课程分别一一对应；（）一位学生所修的每门课程都有一个成绩；（）一位学生所修的每门课程都有一个成绩；（）每门课程（注意：不是每种课程！同一种课，如（）每门课程（注意：不是每种课程！同一种课，如数学课，可以开好多门，每门课有一个课程号）只有数学课，可以开好多门，每门课有一个课程号）只有一位任课教师，但一位教师可以教多门课；一位任课教师，但一位教师可以教多门课；（）教师中没有重名，每位教师只属于一个系。（）教师中没有重名，每位教师只属于一个系。根据上述语义，可以确认下面函数依赖的集合：根据上述语义，可以确认下面函数依赖的集合：，从图可以看出，属性集，可以从图可以看出，属性集，可以

4、决定其他所有属性的值，而，的任何子集决定其他所有属性的值，而，的任何子集则不能，故，是这个关系的主键。这样的则不能，故，是这个关系的主键。这样的关系用来查询是很方便的。关系用来查询是很方便的。计算机系通知教师准备给学生补考，可以计算机系通知教师准备给学生补考，可以“查询图查询图10-10-1 1函数依赖计算机系所开课程的不及格学生的学号、不及函数依赖计算机系所开课程的不及格学生的学号、不及格课程号以及任课教师的姓名格课程号以及任课教师的姓名”.查询仅涉及一个关查询仅涉及一个关系，是一元查询，不须做连接运算，可以用下面的系，是一元查询，不须做连接运算，可以用下面的SQLSQL语语句来表达：句来表

5、达：SELECT S SELECT S，C，TN FROM R WHERE CSAND F;但是这样的关系也有问题，首先数据冗余太多，但是这样的关系也有问题，首先数据冗余太多，如一门课程的教师名须对选这门课的所有学生重复一如一门课程的教师名须对选这门课的所有学生重复一次；一个系名须对选该系所开课程的所有学生重复一次；一个系名须对选该系所开课程的所有学生重复一次。除冗余外，在进行增、删、改操作时，还会发生次。除冗余外，在进行增、删、改操作时，还会发生所谓更新异常现象所谓更新异常现象:（）由于冗余，在修改时往往会导致数据的不一（）由于冗余，在修改时往往会导致数据的不一致。例如，改变一门课程的任课教

6、师，或一门课改由致。例如，改变一门课程的任课教师，或一门课改由另一个系开出，则需要修改多个元组。如果部分修改，另一个系开出，则需要修改多个元组。如果部分修改，部分不修改，则会导致数据的不一致。这叫修改异常。部分不修改，则会导致数据的不一致。这叫修改异常。（）由于主属性不能为空值，如某系有位教师不教课，（）由于主属性不能为空值，如某系有位教师不教课，则这位教师的姓名及所属的系名就不能插入；同样，则这位教师的姓名及所属的系名就不能插入；同样，如果一位教师所开的课暂时无人选，或是列入计划而如果一位教师所开的课暂时无人选，或是列入计划而目前不开，则也无法插入。这叫插入异常。目前不开，则也无法插入。这叫

7、插入异常。（）如果所有学生都退选一门课，则有关这门课的其（）如果所有学生都退选一门课，则有关这门课的其他数据（任课教师名及所属系名）也将被删除。如果他数据（任课教师名及所属系名）也将被删除。如果一位教师因病暂时停开他所开的课，则有关这位教师一位教师因病暂时停开他所开的课，则有关这位教师的其他信息（所属系、可开课程）都将被删去。这叫的其他信息（所属系、可开课程）都将被删去。这叫删除异常。删除异常。在上例的关系中，包含了三方面的信息：学生各门课程在上例的关系中，包含了三方面的信息：学生各门课程的成绩，各门课程开课的教师以及各个教师所属的系。的成绩，各门课程开课的教师以及各个教师所属的系。上例中上例

8、中,所有这三方面的数据都集中在一个关系中，此所有这三方面的数据都集中在一个关系中，此关系的主键为属性集关系的主键为属性集S S，C C。（C C，TNTN）和（）和（TNTN，D D）本来可以作为独立的关系而存）本来可以作为独立的关系而存在，而今却不得不依附于其他关系。这就是说，必须对应在，而今却不得不依附于其他关系。这就是说，必须对应一个主键一个主键S S，C C的值，才能插入或存在一个（的值，才能插入或存在一个（C C，TNTN）或（）或（TNTN，D D）的值。这是关系结构带来的限制，不是现）的值。这是关系结构带来的限制，不是现实世界的真实反映。实世界的真实反映。解决这个问题的途径是把关

9、系分解，也就是进行解决这个问题的途径是把关系分解，也就是进行所谓关系规范化。例如，把上例的关系分解为下列三所谓关系规范化。例如，把上例的关系分解为下列三个关系：个关系：SCG（S，C，G）CTN（C，TN）TND（TN，D）这样的分解使关系的语义单纯化，使之符合这样的分解使关系的语义单纯化，使之符合“一地一地一事一事”的原则。但是分解以后，对某些查询必须进行的原则。但是分解以后，对某些查询必须进行开销很大的连接操作，影响数据库的性能。开销很大的连接操作，影响数据库的性能。关系的规范化主要是对关系进行必要的分解，但如关系的规范化主要是对关系进行必要的分解，但如何分解，分解后是否有损于原来的信息，

10、回答这些问何分解，分解后是否有损于原来的信息，回答这些问题需要理论的指导，下面将讨论这些问题。题需要理论的指导，下面将讨论这些问题。n表示一个关系的模式，表示一个关系的模式，U=A1,A2,An是是R的所有的所有属性的集合，属性的集合，F是是R中函数依赖的集合，中函数依赖的集合，r是是R所取的值，所取的值，即即R实有元组的集合。实有元组的集合。n定义定义10-1 设有一关系模式设有一关系模式R(A1,A2,An),X和和Y为其属为其属性的子集。设性的子集。设t1,t2是关系是关系R中的任意两个元组，如果中的任意两个元组，如果t1X=t2X,则则t1Y=t2Y。这时我们称。这时我们称Y函数依赖于

11、函数依赖于X，或，或X函数决定函数决定Y，X称为决定子（称为决定子（determinant）。）。一个函数依赖要能成立，不但要求关系的当前值都能一个函数依赖要能成立，不但要求关系的当前值都能满足函数依赖条件，而且还要求关系的任一可能值都能满满足函数依赖条件，而且还要求关系的任一可能值都能满足函数依赖条件。确认一个函数依赖，需要弄清数据的语足函数依赖条件。确认一个函数依赖，需要弄清数据的语义，而语义是现实世界的反映，不是主观的臆断。义，而语义是现实世界的反映，不是主观的臆断。如果为的子集，显然如果为的子集，显然成立，这称为平凡函成立，这称为平凡函数依赖（数依赖（trivial functiona

12、l dependencytrivial functional dependency）。平凡函数）。平凡函数依赖必然成立，它不反映新的语义。我们平常所指的函数依赖必然成立，它不反映新的语义。我们平常所指的函数依赖一般都指非平凡函数依赖（依赖一般都指非平凡函数依赖（nontrivial functional nontrivial functional dependencydependency）。）。如果不函数依赖于，则记做如果不函数依赖于，则记做 。如果如果且且，则与一一对应，可记做，则与一一对应，可记做 。定义定义10-2 10-2 设设X,YX,Y是某关系的不同属性集是某关系的不同属性集,如如

13、XYXY，且不，且不存在存在XX为为X X的子集，使的子集，使XYY，则称，则称Y Y完全函数依赖完全函数依赖(full functional dependency(full functional dependency）于）于X X，记做，记做X YX Y；否则称否则称Y Y部分函数依赖部分函数依赖p（partial functional partial functional dependency)dependency)于于X X，记做，记做X YX Y。在在10.110.1节的例子中节的例子中,S S,C,C是主键，故是主键，故S S,C,CTNTN，但，但C CTNTN，故，故S S，p

14、pf fC CTNTN，而，而S S，C CGG。定义定义10-310-3设设X,Y,ZX,Y,Z是某关系的不同的属性集，如果是某关系的不同的属性集，如果XY,Y X,YZ,XY,Y X,YZ,则称传递函数依赖（则称传递函数依赖（transitive transitive functional dependencyfunctional dependency）于）于X X。n定义定义10-4 10-4 设设F F是是R R的函数依赖集合，的函数依赖集合，XYXY是是R R的一个函的一个函数依赖。如果一个关系模式满足数依赖。如果一个关系模式满足F F，则必然满足，则必然满足XYXY，就称就称F F

15、逻辑蕴涵逻辑蕴涵XYXY，或表示为，或表示为F|=XYF|=XY。n定义定义10-5 10-5 函数依赖集合所逻辑蕴涵的函数依赖的全函数依赖集合所逻辑蕴涵的函数依赖的全体称为体称为F F的闭包（的闭包（closureclosure），记为），记为F F，即，即F FXYXYF|=XYF|=XY。为了从已知的函数依赖推导出其他函数依赖，为了从已知的函数依赖推导出其他函数依赖，ArmstrongArmstrong提出了一提出了一套推理规则，我们常称为套推理规则，我们常称为ArmstrongArmstrong公理（公理（Armstrong saxions Armstrong saxions）。）。其

16、推理规则可归结为如下三条其推理规则可归结为如下三条:A1 A1：自反律（：自反律（reflexivityreflexivity）如果如果，则，则成立。这是一个平凡函数依赖。成立。这是一个平凡函数依赖。A2A2：扩展律（：扩展律（augumentationaugumentation）如如果果成成立立，且且，则则成成立立。式式中中，和和是是和和的简写，以后将沿用此表示法。的简写，以后将沿用此表示法。A3A3：传递律（：传递律（transitivitytransitivity）如果如果，成立，则成立，则成立。成立。引理引理10-110-1ArmstrongArmstrong公理是正确的（公理是正确的

17、（soundsound），即如果），即如果F F成立，则由成立，则由F F根据根据ArmstrongArmstrong公理所推导的函数依赖总是公理所推导的函数依赖总是成立的。成立的。引理引理10-2 10-2 下列三条推理规则是正确的。下列三条推理规则是正确的。(1)(1)合并规则（合并规则（the union rulethe union rule），|=|=。(2)(2)伪伪传传递递规规则则（the the pseudo pseudo transitivity transitivity rulerule）：，|=|=。(3)(3)分解规则（分解规则（the decomposition rul

18、ethe decomposition rule）：如果）：如果且为的子集，则且为的子集，则成立。成立。定义定义10-610-6设为的子集，则属性集关于函数依设为的子集，则属性集关于函数依赖集的闭包赖集的闭包定义为定义为且且可由可由ArmstrongArmstrong公理导出。公理导出。引理引理10-3 10-3 能由能由ArmstrongArmstrong公理导出的充分必公理导出的充分必要条件是要条件是。定理定理10-110-1ArmstrongArmstrong公理是正确的、完备的公理是正确的、完备的(complete)(complete)算法算法10-110-1计算属性集关于的闭包。计算属

19、性集关于的闭包。输入：属性集为的子集，函数依赖集。输入：属性集为的子集，函数依赖集。输出：输出：。方法：按下列方法计算属性集序列方法：按下列方法计算属性集序列X X(0)(0),X,X(1)(1),(i)(i)(1)(1)初始化初始化X X()X X，i i。(2)(2)求属性集求属性集B=B=A|(A|(V)(V)(W)(VWFVW)(VWFVX X(i)(i)AWAW）。(3)X(3)X(i+1)(i+1)BXBX(i)(i)。(4)(4)判别判别X X(i+1)(i+1)X X(i)(i)。(5)(5)若不等，若不等，i ii i1 1，返回，返回(2)(2)；若相等，；若相等，X X+

20、=X=X(i)(i)，结束。，结束。【例例10-110-1】设设ABCABC，DEGDEG，CACA，BECBEC，BCDBCD，CGBDCGBD，ACDBACDB，CEAGCEAG，试试用用算算法法10-110-1计计算算(BD)(BD)+。解：令解：令(0)(0)BDBD。找找左左部部为为BDBD的的子子集集的的函函数数依依赖赖，只只有有。(1)(1)BDEGBDEGBDEG,BDEG,找找左左部部为为BDEGBDEG的的子子集集的的函函数数依依赖赖，有有DEGDEG，BECBEC。X X(2)(2)BDEG EGC BDEG EGC BCDEG BCDEG找左部为找左部为BCDEGBCD

21、EG的子集的函数依赖，有的子集的函数依赖，有DEGDEG，CACA，BECBEC，BCDBCD，CGBDCGBD，CEAGCEAG。X X(3)(3)BCDEG BCDEG ABCDEG=ABCDEGABCDEG=ABCDEG因因X X(3)(3)U U，一望可知不必再进行计算了，一望可知不必再进行计算了，(BD)(BD)+=ABCDEGABCDEG。可是在算法。可是在算法10-110-1中，还要迭代一次才能结束。中，还要迭代一次才能结束。定义定义10-710-7设设F F，G G为两个函数依赖集，如果为两个函数依赖集，如果F F+G G+，则称则称F F和和G G是等价的，也可称是等价的，也

22、可称F F覆盖（覆盖（covercover）G G，或，或G G覆盖覆盖F F；也可说；也可说F F和和G G互相覆盖。互相覆盖。引理引理10-410-4F FG G的充分必要条件是的充分必要条件是F FG G+且且G GF F+。引理引理10-5 10-5 任一函数依赖集任一函数依赖集F F总可以为一右部恒为单总可以为一右部恒为单属性的函数依赖集所覆盖属性的函数依赖集所覆盖.定义定义10-810-8函数依赖集如果满足下列条件，则称为极函数依赖集如果满足下列条件，则称为极小函数依赖集或最小覆盖。小函数依赖集或最小覆盖。(1)F (1)F中每个函数依赖的右部为单属性。中每个函数依赖的右部为单属性

23、。(2)F(2)F中中不不存存在在这这样样的的函函数数依依赖赖XAXA，使使得得F FXAXA与与F F等价。等价。(3)(3)在在 F F中中 也也 不不 存存 在在 这这 样样 的的 XAXA，使使 得得 F FXAXAZAZA与与F F等价，式中，等价，式中，Z Z为为X X的子集。的子集。定理定理10-210-2任一函数依赖集任一函数依赖集F F都与一最小函数依赖集都与一最小函数依赖集FF等价。等价。FF称为称为F F的最小覆盖。的最小覆盖。10.3 多值依赖 除了函数依赖外，关系的属性间还有其他一些依赖关除了函数依赖外，关系的属性间还有其他一些依赖关系，多值依赖（系，多值依赖（Mul

24、tiValued Dependency,MVDMultiValued Dependency,MVD）是其中）是其中之一。之一。在多值依赖（表示为在多值依赖（表示为，读做多值决定，读做多值决定，或多值依赖于）中，对于给定的值，其对应的是或多值依赖于）中，对于给定的值，其对应的是的一组数值（其个数可以从零到多个），而且这种对的一组数值（其个数可以从零到多个），而且这种对应关系，对于给定的值所对应的（）每应关系，对于给定的值所对应的（）每个值都能成立。个值都能成立。定义定义10-910-9设，是关系模式的属性集，如果对于设，是关系模式的属性集，如果对于的任何值，都有如下的性质：的任何值，都有如下的性

25、质：则称满足则称满足XYXY。与函数依赖一样，多值依赖也有一组公理：与函数依赖一样，多值依赖也有一组公理：互补律：互补律如果如果，则，则（）。（）。如如果果需需要要，可可用用（）表表示示多多值值依依赖赖，以强调其互补关系。以强调其互补关系。：扩展律（多值依赖）：扩展律（多值依赖）如果如果，而，而，则，则。A6A6：传递律（多值依赖）：传递律（多值依赖）如果如果，且，且，则，则（）。（）。下面两个公理与函数依赖和多值依赖都有关。下面两个公理与函数依赖和多值依赖都有关。A7A7：如如果果，则则，即即函函数数依依赖赖是是多多值值依依赖赖的的特特例。例。A8A8：如果：如果，而且对某个与不，而且对某个

26、与不相交的，有相交的，有，则，则。由前述公理，还可以推导出下列个多值依赖推理规则。由前述公理，还可以推导出下列个多值依赖推理规则。（）多值依赖合并规则（）多值依赖合并规则如果如果，则，则。（）多值依赖伪传递规则（）多值依赖伪传递规则如果如果，则，则（）。（）。（）混合伪传递规则（）混合伪传递规则如果如果，则，则（）。（）。（）多值依赖分解规则（）多值依赖分解规则如果如果，则，则（），），（）及（）及（）均成立。（）均成立。10.410.4连接依赖连接依赖 前面所讲的函数依赖和多值依赖都是数据语义对数据所前面所讲的函数依赖和多值依赖都是数据语义对数据所施加的某种限制。这些依赖关系可以统称为数据依

27、赖（施加的某种限制。这些依赖关系可以统称为数据依赖（Data Data Dependency,DDDependency,DD）。数据依赖不仅包含函数依赖和多值依）。数据依赖不仅包含函数依赖和多值依赖，还有其他一些依赖。赖，还有其他一些依赖。函数依赖实际表现为对属性值的约束，例如，王平是计函数依赖实际表现为对属性值的约束，例如，王平是计算机系的教师，若有函数依赖算机系的教师，若有函数依赖TNDTND（参看图（参看图10-110-1），则在），则在TNTN为王平的元组中，其对应的为王平的元组中，其对应的D D必为计算机系，不能为其他必为计算机系，不能为其他值。值。多值依赖实际上表示为对元组值的约束

28、，如在多值依赖实际上表示为对元组值的约束，如在图图10-310-3中，由于中，由于TSTSC C，如果出现元组，如果出现元组LiLi，No1 No1 physicsphysics及及LiLi，No2 chemistryNo2 chemistry，则必有元组，则必有元组LiLi，No2 physicsNo2 physics及及LiLi，No1 chemistryNo1 chemistry。推广这个概念，还可以发现其他依赖关系，连推广这个概念，还可以发现其他依赖关系，连接依赖（接依赖（Join Dependency,JDJoin Dependency,JD）就是其中之一。）就是其中之一。定义定义1

29、0-1010-10设设X X1 1，X X2 2，X Xn n是关系是关系R R的属性集的属性集U U的子的子集，且集，且XXi iU U。若对。若对R R的任一值，的任一值，RXRXi i 均成立，均成立，则称则称R R具有连接依赖，记为具有连接依赖，记为（X X1 1，X X2 2，X Xn n)。注：注：表示连接操作表示连接操作10.510.5关系模式的分解及其问题关系模式的分解及其问题 在在10.110.1节中讨论过由函数依赖所引起的更新异常问节中讨论过由函数依赖所引起的更新异常问题。同样，多值依赖和连接依赖也会引起类似的问题。题。同样，多值依赖和连接依赖也会引起类似的问题。解决这些问

30、题的途径，就是按照前面曾提到过的解决这些问题的途径，就是按照前面曾提到过的“一地一地一一事事”原则，对关系模式进行分解，使其语义单纯化。原则，对关系模式进行分解，使其语义单纯化。定义定义10-1110-11设有一关系模式设有一关系模式R(U)R(U)，若用一关系模式的集，若用一关系模式的集合合R R1 1(U(U1 1)，R R2 2(U(U2 2),R),Rk k(U(Uk k)来取代，其中，来取代，其中，U UUU，则称此关系模式的集合为的一个分解，用，则称此关系模式的集合为的一个分解，用 =R R1 1，R R2 2,R,Rk k表示。表示。定义定义10-1210-12F F在属性集在属

31、性集U Ui i（为的真子集）上的投影定（为的真子集）上的投影定义为义为i(F)XYXYXYFXYF+XYXY为为U Ui i的子集的子集定义定义10-1310-13设设R R1 1，R R2 2,R,Rn n是是R R的一个分解，的一个分解，r r是是R R的任一个值，如果满足条件的任一个值，如果满足条件r rU1U1(r)(r)U2U2(r)(r)UkUk(r)(r)则称则称是无损连接分解或简称无损分解。是无损连接分解或简称无损分解。定义定义10-1410-14设设=R R1 1，R R2 2,R,Rn n是是R R的一个分解，如的一个分解，如UiUi(F)|=(F)|=，则称分解，则称分

32、解保持函数依赖，或简称保持保持函数依赖，或简称保持依赖。依赖。关系模式经分解后与原来的关系等价。所谓关系模式经分解后与原来的关系等价。所谓“等价等价”不是不是“等同等同”，“等价等价”是指两者对数据的使用者是指两者对数据的使用者来说应是等价的，即对分解前后的数据，做同样内容来说应是等价的，即对分解前后的数据，做同样内容的查询，应产生同样的结果。这是对模式分解的最基的查询，应产生同样的结果。这是对模式分解的最基本的要求，否则，不能进行分解。本的要求，否则，不能进行分解。如果硬要进行分解的话，那就意味着分解前后的模如果硬要进行分解的话，那就意味着分解前后的模式代表着两个不同的现实世界。因此，无损分

33、解应是式代表着两个不同的现实世界。因此，无损分解应是关系模式分解时所必须满足的条件。不是任意的分解关系模式分解时所必须满足的条件。不是任意的分解都是无损的。都是无损的。关系分解还带来保持依赖的问题。不满足关系分解还带来保持依赖的问题。不满足保持依赖条件，并不意味着某些函数依赖真正保持依赖条件，并不意味着某些函数依赖真正丢失了，而是某些函数依赖的有关属性分散在丢失了，而是某些函数依赖的有关属性分散在不同的关系中，不能被的所有投影所蕴涵。不同的关系中，不能被的所有投影所蕴涵。不同关系的属性间的函数依赖关系并不是不可不同关系的属性间的函数依赖关系并不是不可能存在的，问题在于这种函数依赖所代表的语能存

34、在的，问题在于这种函数依赖所代表的语义约束不如在一个关系中容易检查，一般须在义约束不如在一个关系中容易检查，一般须在检查前对有关的关系做一次连接运算。此外，检查前对有关的关系做一次连接运算。此外，不保持依赖还会引起一些更新异常，这可以通不保持依赖还会引起一些更新异常，这可以通过下面的例子说明。过下面的例子说明。【例【例10-310-3】取图】取图10-110-1的一部分组成关系模式的一部分组成关系模式R R（C C，TNTN，D D），其），其函数依赖关系见图函数依赖关系见图10-610-6，即，即F FC CTNTN，TNDTND。C C为为所逻辑蕴涵，如图所逻辑蕴涵，如图10-610-6中

35、虚线所示。如果中虚线所示。如果R R分解为两个关系分解为两个关系R1R1（C C，TNTN），），R2R2（C C，D D），则由于是的主键，故），则由于是的主键，故R1R1和和R2R2中都含有。如前所述，这样的分解是无损分解。但函数依赖中都含有。如前所述，这样的分解是无损分解。但函数依赖TNTN不能被不能被TNTN，所逻辑蕴涵，故分解所逻辑蕴涵，故分解 R1R1，R2R2不保持依赖。不保持依赖。TNTN和分属于和分属于R1R1和和R2R2。R2 R2中某门课的系中某门课的系名名D D应是应是R1R1中教该门课的教师所在系。如果中教该门课的教师所在系。如果R1R1中的教师所在的系变中的教师所在

36、的系变了，则需要修改了，则需要修改R2R2中相应的属性的值。更有甚者，如果一位教中相应的属性的值。更有甚者，如果一位教师不教课，则无法表示这位教师所在系的信息。师不教课，则无法表示这位教师所在系的信息。综上所述，关系模式的分解主要有两种准则：综上所述，关系模式的分解主要有两种准则：（）只满足无损分解要求；（）只满足无损分解要求；（）既满足无损分解要求，又满足保持依赖要求。（）既满足无损分解要求，又满足保持依赖要求。准则（）要比准则（）理想，但分解要受到更准则（）要比准则（）理想，但分解要受到更多的限制。当然，只满足保持依赖，而不满足无损分多的限制。当然，只满足保持依赖，而不满足无损分解要求的分

37、解是存在的。解要求的分解是存在的。下下面面进进一一步步讨讨论论无无损损分分解解和和保保持持依依赖赖的的性性质质及及其其判判别方法。别方法。首先介绍一些记号。设首先介绍一些记号。设=R R1 1，R R2 2,R,Rn n是是R R的的一个分解一个分解,r,r为为R R的一个值，的一个值，Ri(r)(r)为为r r在在Ri的属性（即的属性（即U Ui）上的投影）上的投影,t,t为为r r中的一个元组中的一个元组,t,tRi tUtUi 是是t t在在Ri的的属性上的投影。定义属性上的投影。定义m为为m(r)=(r)=Ri(r)(r)引理引理10-610-6设设=R R1 1，R R2 2,R,R

38、n n是是R R的一个分解，的一个分解，r r为为R R的一个值，的一个值，riRi(r)(r)，则有，则有:（）（）r r是是m(r)(r)的子集；的子集；（）如果（）如果s=s=m(r),(r),则则RiRi(s)(s)ri;（）（）m m(r)=(r)=m(r).(r).【例【例10-410-4】设有两个关系模式】设有两个关系模式R1（AB）和和R2（BC），r r1 1，r r2 2为其值。若为其值。若r1a1b1,r2b1c1，b2c2，则，则s s r1 r2a1b1 c1，2 2(s)=(s)=b1c1为为r r2 2的子的子集。集。r r2 2中的元组中的元组b2c2由于在由于

39、在r1中找不到匹配对象而不出中找不到匹配对象而不出现在现在s s中。这些通过连接而被淘汰的元组称为不连接中。这些通过连接而被淘汰的元组称为不连接（danglingdangling）元组。在图）元组。在图10-610-6所示的关系所示的关系R(CR(C,TN,D),TN,D)中，如果一位教师不教课，则其所属的系也不能在此中，如果一位教师不教课，则其所属的系也不能在此关系中表示。如果分解为关系中表示。如果分解为R1(C,TN)和和R3(TN,D)两个两个关系，就可以解决此问题。实际上，对应不教课教师关系，就可以解决此问题。实际上，对应不教课教师的元组是以的元组是以R3中的不连接元组出现的。从中也可

40、看出，中的不连接元组出现的。从中也可看出，为什么通过分解可以消除更新异常。为什么通过分解可以消除更新异常。下面介绍无损分解的测试算法。下面介绍无损分解的测试算法。算法算法10-210-2检验一个分解是否无损分解。检验一个分解是否无损分解。输输入入：关关系系模模式式R(AR(A1 1,A,A2 2,A,An n）；R R上上的的函函数数依依赖赖集集F F；R R上的分解上的分解R R1 1,R,R2 2,R,Rk k。输出：输出：是否无损分解。是否无损分解。方方法法：建建立立knkn的的矩矩阵阵M M（见见图图10-710-7）,其其中中每每列列对对应应于于R R的一个属性，每行对应于的一个属性

41、，每行对应于中的一个关系模式。中的一个关系模式。矩阵各元素的值由下面的规则确定：矩阵各元素的值由下面的规则确定：对对中中的的每每一一函函数数依依赖赖反反复复进进行行下下面面的的检检查查和和处处理理，直直至至无无可可改改变变为为止止。检检查查中中的的属属性性所所对对应应的的列列，找找出出相相等等的的那那些些行行。如如果果找找到到相相等等的的两两个个行行（或或多多行行），就就把把对对应应行行中中的的属属性性所所对对应应的的符符号号改改成成一一致致，即即如如果果其其中中之之一一为为aj，则则其其他他的的也也改改成成aj ;如如果果这这两两个个符符号号为为bij和和l，则则将将它它们们统统一一成成bi

42、j和和l。如此进行到无可改变时，如果发现某一行变成了如此进行到无可改变时，如果发现某一行变成了a a1 1，a a2 2,a,an n，则，则是无损分解，否则，是无损分解，否则，不是无损分不是无损分解。解。【例例10-510-5】设设有有关关系系模模式式（ABCDEABCDE），R R1 1（ADAD）,R,R2 2（ABAB）,R,R3 3（BEBE）,R,R4 4（CDECDE）,R,R5 5（AEAE）是是R R的的一一个个分分解解。在在R R上上有有下下列列函函数数依依赖赖：，DEDE，CECE。试试判断判断是否为无损分解。是否为无损分解。解解：先先构构造造初初始始矩矩阵阵，如如图图1

43、0-8(a)10-8(a)所所示示。然然后后按按下下列列次次序序反反复检查和修改。复检查和修改。b b1313，b b2323，b b5353bb1313 b b1313，b b3333bb1313 a a4 4，b b2424，b b3434，b b5454aa4 4 DEDE a a3 3，b b1313aa3 3（该列其余行的（该列其余行的b b1313都须改成都须改成a a3 3，以保持它们的一致），以保持它们的一致）CE CE b b3131，b b4141,a,a1 1aa1 1 再进行下去，将无任何改动，检查和修改到此结束。再进行下去，将无任何改动，检查和修改到此结束。最后的示于

44、图最后的示于图10-810-8（c c）。从中可以看出，第三行都是，）。从中可以看出，第三行都是，故故是无损分解。是无损分解。定理定理10-310-3算法算法10-210-2可以正确判断一个分解是否无损分解。可以正确判断一个分解是否无损分解。定理定理10-410-4设设RR1 1(U(U1 1)，R R2 2(U(U2 2)是是R(U)R(U)的一个分解，则的一个分解，则为无损分解的充分必要条件为（为无损分解的充分必要条件为（U U1 1UU2 2）（U U1 1U U2 2）或）或（U U1 1UU2 2）（U U2 2U U1 1）。）。【例【例10-610-6】在图】在图10-610-6

45、所示的关系中，有所示的关系中，有R R（C C，TNTN，D D）F FC CTNTN，TNDTNDR R1 1（C C，TNTN）R R2 2（TNTN，D D）试证）试证RR1 1,R,R2 2 是是R R的无损分解。的无损分解。解解：U U1 1C C，TNTN，U U2 2TN,DTN,D，U U1 1UU2 2TNTN，U U1 1U U2 2CC,U,U2 2U U1 1DD。因因TNDTND，故（，故（U U1 1UU2 2）（U U2 2U U1 1）。）。上述两条件之一成立，故上述两条件之一成立，故是无损分解。是无损分解。下面介绍保持依赖的检验方法。下面介绍保持依赖的检验方法

46、。算法算法10-310-3检验一个分解是否保持依赖。检验一个分解是否保持依赖。输入：分解输入：分解R R1 1,R,R2 2,R,Rk k和函数依赖集和函数依赖集F F。输出：输出：是否保持是否保持F F。方法：令方法：令GUi（F）。为为了了检检验验G G是是否否覆覆盖盖F F，可可对对F F中中的的每每一一函函数数依依赖赖进行下列检查。进行下列检查。计计算算关关于于的的闭闭包包+，并并且且检检查查是是否否包包含含在在+中中。为为了了计计算算+，不不必必求求出出G G，可可以以分分别别地地、反复地计算反复地计算Ui（F）对对X X所增加的属性。所增加的属性。这可以用下面的算法：这可以用下面的

47、算法：WHILE WHILE 有改变有改变 DO DO FOR i FOR i to to do do:=:=（UUi i）+UUi i）UUi i是是中中与与R Ri i有有关关的的属属性性。（UUi i）+是是UUi i关关于于F F的的闭闭包包。（UUi i）+UUi i是是UiUi(F)(F)对对X X+所所增增加加的的属属性性。经经反反复复计计算算，直直至至不不变变为为止止。最最终终的的就就是是关关于于的的闭闭包包X X+。如如果果Y Y是是X X+子子集，则集，则GG+。如果对如果对F F中的所有函数依赖经检查都属于中的所有函数依赖经检查都属于G G+，则，则保持依赖，保持依赖，否

48、则否则不保持依赖。不保持依赖。【例例10-710-7】设设有有关关系系模模式式R(ABCD),FR(ABCD),FAB,BC,CD,DA,AB,BC,CD,DA,试试判判别分解别分解=R=R1 1(AB),R(AB),R2 2(BC),R(BC),R3 3(CD)(CD)是否保持依赖。是否保持依赖。解解：U1U1(F)(F)ABAB，U2U2(F)(F)BCBC，U3U3(F)(F)CDCD，F F中中的的前前三三个个函函数数依依赖赖已已明明显显地地在在中中，只只要要检检验验是是否否为为G G所蕴涵。所蕴涵。令令Z ZD D作为作为Z Z的初始值。的初始值。第一趟：第一趟：UU1 1D DA,

49、BA,B空集，不变空集，不变UU2 2D DB,CB,C空集，不变空集，不变UU3 3D DC,DC,DD DD D(D(D+C,D)C,D)D(A,B,C,DC,D)=C,DD(A,B,C,DC,D)=C,D第二趟：第二趟：UU1 1C,DC,DA,BA,B空集，不变空集，不变UU2 2C,DC,DB,CB,CC CC,DC,D（C+B,CB,C）C,DC,D（A,B,C,DA,B,C,DB,CB,C)B,C,DB,C,DUU3 3B,C,DB,C,DC,DC,DC,DC,D B,C,DB,C,D（C,D+C,D)C,D)B,C,D(A,B,C,DC,D)B,C,D(A,B,C,DC,D)B

50、,C,DB,C,D，不变，不变第三趟：第三趟：UU1 1B,C,DA,BB,C,DA,BBBB,C,D(B,C,D(B+A,B)A,B)B,C,D(A,B,C,DA,B)B,C,D(A,B,C,DA,B)）A,B,C,DA,B,C,D已等于全部属性的集合，不可能再变，故已等于全部属性的集合，不可能再变，故D+A,B,C,DA,B,C,D。因为因为A A是是A,B,C,DA,B,C,D的子集，故的子集，故属于属于G G+，即，即可保持依可保持依赖。请注意，两个属性虽然不同时出现在任何分解关系中，赖。请注意，两个属性虽然不同时出现在任何分解关系中，但但|=|=，故仍保持依赖。，故仍保持依赖。10.