6第6章-关系数据库模式设计PPT优秀课件

1、 关系数据库模式关系数据库模式 ？ 图1.14 数据库系统的体系结构 用户用户A1A1用户用户A1A1 局部逻辑结构局部逻辑结构 概念级概念级DBDB 全局逻辑结构全局逻辑结构 存储级存储级DB 存储组织结构存储组织结构 DBMS OS 用户级用户级DB 用户用户A1A1用户用户A1A1 学生关系（学号，姓名，性别，出生年月，籍贯，专业代码，班级）学生关系（学号，姓名，性别，出生年月，籍贯，专业代码，班级） 专业关系（专业代码，专业名称）专业关系（专业代码，专业名称） 课程关系（课程号，课程名，学时数）课程关系（课程号，课程名，学时数） 设置关系（专业代码，课程代码）设置关系（专业代码，课程代

2、码） 学习关系（学号，课程号，分数）学习关系（学号，课程号，分数） 教师关系（教工号，教员姓名，教员性别，教员出生年月，教研室，电话）教师关系（教工号，教员姓名，教员性别，教员出生年月，教研室，电话） 讲授关系（教工号，课程号）讲授关系（教工号，课程号） 关系数据库模式：关系数据库模式： 关系数据库的模式设计问题，是数据库应用关系数据库的模式设计问题，是数据库应用 系统设计中的核心问题之一。系统设计中的核心问题之一。 本章中，支撑关系数据库模式设计的函数依本章中，支撑关系数据库模式设计的函数依 赖和规范化理论，是关系数据库设计的重要理论赖和规范化理论，是关系数据库设计的重要理论 基础，也是本课

3、程学习的主要难点内容。基础，也是本课程学习的主要难点内容。 Question 关系数据库模式的设计有哪几种方法呢？关系数据库模式的设计有哪几种方法呢？ 1 1、E-RE-R模型方法：画出反映用户组织中相互关模型方法：画出反映用户组织中相互关 联的数据及其之间联系的联的数据及其之间联系的E-RE-R图，再将图，再将E-RE-R模型转换模型转换 成关系模型对应的关系模式。成关系模型对应的关系模式。 2 2、属性表方法：收集、整理和归纳用户组织、属性表方法：收集、整理和归纳用户组织 进行信息管理的各种表格，然后把每个表格转换成进行信息管理的各种表格，然后把每个表格转换成 一个关系模式。一个关系模式。

4、 由表由表6.1可直接得到如下关系模式：可直接得到如下关系模式： 学生学籍关系（学号，姓名，性别，出生年月，学生学籍关系（学号，姓名，性别，出生年月， 籍贯，班级，所属专业）籍贯，班级，所属专业） 考试成绩关系（学号，姓名，课程编号，课程名称，考试成绩关系（学号，姓名，课程编号，课程名称， 成绩，所属专业）成绩，所属专业） 教员信息关系（教员编号，教员名称，性别，教员信息关系（教员编号，教员名称，性别， 出生年月，职称，教研室名称）出生年月，职称，教研室名称） 由表由表6.1可直接得到如下关系模式：可直接得到如下关系模式： 学生学籍关系（学号，姓名，性别，出生年月，学生学籍关系（学号，姓名，性

5、别，出生年月， 籍贯，班级，所属专业）籍贯，班级，所属专业） 考试成绩关系（学号，姓名，课程编号，课程名称，考试成绩关系（学号，姓名，课程编号，课程名称， 成绩，所属专业）成绩，所属专业） 教员信息关系（教员编号，教员名称，性别，教员信息关系（教员编号，教员名称，性别， 出生年月，职称，教研室名称）出生年月，职称，教研室名称） 至少存在有至少存在有2种种 由一些属性值决定教研室名由一些属性值决定教研室名 称属性值的数据依赖关系。称属性值的数据依赖关系。 ),(FDOMDUR ( (教工号教工号, ,姓名姓名, ,职称职称, ,教研室，教研室， 课程号课程号, ,课程名课程名, ,学时学时) )

6、 数据之间存在着一定的数据依赖关系，其实质即数据之间存在着一定的数据依赖关系，其实质即 是函数依赖。是函数依赖。 进行关系模式分解。进行关系模式分解。 教员任课教员任课( (教工号教工号, ,姓名姓名, ,职称职称, ,教研室，课程号教研室，课程号, ,课程名课程名, ,学时学时) ) 定义定义6.16.1 设有关系模式设有关系模式R(AR(A1 1,A,A2 2, ,A,An n) )和属性集和属性集 U=AU=A1 1,A,A2 2, ,A,An n 的子集的子集X X、Y Y。如果对于任一具体关。如果对于任一具体关 系系r r的任何两个元组的任何两个元组u u和和v v，只要，只要uX=

7、vXuX=vX，就有，就有 uY=vYuY=vY，则称，则称X X函数地决定函数地决定Y Y，或，或Y Y函数依赖函数依赖X X，记，记 为为X XY Y。 例如：例如： 由上面的定义和例子说明：由上面的定义和例子说明： 函数依赖描述了每个关系中主键属性与非主函数依赖描述了每个关系中主键属性与非主 键属性之间的关系。对于关系键属性之间的关系。对于关系和和 XYXY来说，属性子集来说，属性子集X X中包括，且仅仅包括了关中包括，且仅仅包括了关 系系R R的主键属性，且对于关系的任何属性子集的主键属性，且对于关系的任何属性子集Y Y， 一定成立一定成立XYXY。 对于对于XYXY，可能存在，可能存

8、在Y Y X X、 两两 种情况。种情况。 YX 若有若有X XY Y，且，且 ，称，称X XY Y为非平凡函为非平凡函 数依赖数依赖; ; 若有若有X XY Y，且，且Y Y X X，称，称X XY Y为平凡函数依赖。为平凡函数依赖。 YX 若若X XY Y，则称，则称X X为决定因素。为决定因素。 若若Y Y不依赖于不依赖于X X，则记作，则记作X Y X Y 。 若同时有若同时有X XY Y和和Y YX X成立，则记为成立，则记为X YX Y。 S S（S#S#，SNAMESNAME，SSEXSSEX，SBIRTHINSBIRTHIN，PLACEOFB, SCODE#PLACEOFB,

9、SCODE#，CLASSCLASS， SNOSNAMESNOSNAME，SSEXSSEX，SBIRTHINSBIRTHIN，PLACEOFB, SCODEPLACEOFB, SCODE，CLASSCLASS） SSSS（SCODE#SCODE#，SSNAMESSNAME，SCODE#SSNAMESCODE#SSNAME） C C（C#C#，CNAMECNAME，CLASSH CLASSH ，C#CNAMEC#CNAME，CLASSH CLASSH ） CSCS（SCODE#SCODE#，C#C#，SCODE#, C# SCODE#, C#SCODE#, C# SCODE#, C#） SCSC（

10、S#S#，C#C#，GRADE GRADE ， S# S#，C# GRADE C# GRADE ） T T（T#T#，TNAMETNAME，TSEXTSEX，TBIRTHINTBIRTHIN，TITLEOFTITLEOF，TRSECTIONTRSECTION，TELTEL， TNOTNAMETNOTNAME，TSEXTSEX，TBIRTHINTBIRTHIN，TITLEOFTITLEOF，TRSECTIONTRSECTION，TELTEL） TEACHTEACH（ T# T#，C#C#， T# T#，C# T#C# T#，C#C#） 定义定义5.25.2 设有关系模式设有关系模式R(UR(U，

11、F)F)，X X、Y Y是属性是属性 集集U=AU=A1 1,A,A2 2, ,A,An n 的子集，如果从的子集，如果从 中的函数依赖中的函数依赖 能够推导出能够推导出X XY Y，则称，则称F F逻辑蕴涵逻辑蕴涵X XY Y，或称，或称X XY Y 是是F F的逻辑蕴涵。的逻辑蕴涵。 所有被所有被F F逻辑蕴涵的函数依赖组成的依赖集称为逻辑蕴涵的函数依赖组成的依赖集称为 F F的闭包，记为的闭包，记为F F+ +。 F F+ +中的元素是函数依赖；中的元素是函数依赖； 如果能计算出如果能计算出F F+ +，就可以很方便地判断，就可以很方便地判断 某个函数依赖是否被某个函数依赖是否被F F+

12、 +逻辑蕴涵。逻辑蕴涵。 F 举例：举例： 能够唯一地标识一个关系中不同元组的一个能够唯一地标识一个关系中不同元组的一个 属性集合；属性集合； 该属性集中不含有多余的属性。该属性集中不含有多余的属性。 设有关系模式设有关系模式R(AR(A 1 1 ,A,A 2 2 , ,A,A n n ) )和属性集和属性集 U=AU=A1 1,A,A2 2, ,A,An n 的子集的子集X X、Y Y，F F是是R R的的函数依赖集。的的函数依赖集。 如果：如果： XA XA1 1A A2 2A An n属于属于F F+ +； 不存在不存在X X的真子集的真子集X X，使，使X XAA1 1A A2 2A

13、An nFF+ +， 则称则称X X是是R R的一个候选键。的一个候选键。 举例举例 在课程关系在课程关系 中，有中，有 依赖集依赖集 F=C# F=C# CNAMECNAME，CLASSHCLASSH ，判断候选键。，判断候选键。 因为因为 F F中的唯一的函数依赖的决定因素中的唯一的函数依赖的决定因素C#C#已已 经是单个属性了，所以经是单个属性了，所以C#C#是唯一的候选建。当然是唯一的候选建。当然 也就是主键了。也就是主键了。 由前述内容可知，对于关系模式由前述内容可知，对于关系模式 来说，关来说，关 系的主键实质上是由其依赖集系的主键实质上是由其依赖集 中的函数依赖的决定中的函数依赖

14、的决定 因素确定的。因素确定的。 ),(FUR F ),(FUR F FXYXY F F F 作用作用：用于从给定的函数依赖集中推导出被用于从给定的函数依赖集中推导出被 其蕴涵的函数依赖。其蕴涵的函数依赖。 条件：条件： 合并规则合并规则：若若X XY Y且且X XZ Z，则，则X XYZYZ 分解规则分解规则：若若X XY Y，且，且Z Z Y Y，则，则X XZ Z 伪传递规则伪传递规则：若若X XY Y且且WYWYZ Z，则，则WXWXZ Z 1 1、合并规则：、合并规则：若若X XY Y且且X XZ Z，则，则X XYZYZ 证明：证明： 由条件由条件XYXY，并增广律可得，并增广律可

15、得XXYXXY。 由条件由条件XZXZ，并增广律可得，并增广律可得XYYZXYYZ。 利用传递律，由利用传递律，由XXYXXY和和XYYZXYYZ，可得，可得 XYZXYZ。 2 2、分解规则、分解规则：若若X XY Y，且，且Z Z Y Y，则，则X XZ Z 证明：证明： 已知有已知有XYXY。 由条件由条件Z Z Y Y，并自反律可得，并自反律可得YZYZ。 利用传递律，由利用传递律，由XYXY和和YZYZ，可得，可得ZZZZ。 3 3、伪传递规则、伪传递规则：若若X XY Y且且WYWYZ Z，则，则WXWXZ Z 证明：证明： 由条件由条件XYXY，并增广律可得，并增广律可得WXWY

16、WXWY。 利用传递律，和已知条件利用传递律，和已知条件WYZWYZ，可得，可得 WXZWXZ。 对于关系模式对于关系模式(CITY(CITY，STST，ZIP)ZIP)，依赖集，依赖集 候选键为候选键为CITYCITY，STST和和 STST，ZIPZIP。证明有。证明有: :ST ZIPST ZIPCITY,ST,ZIPCITY,ST,ZIP 和和CITY,STCITY,STCITY,ST,ZIPCITY,ST,ZIP。现证明前者。现证明前者。 如果如果A Ai i(i=1,2(i=1,2,n),n)是关系模式是关系模式R R 的属性的属性, ,则则X XA A1 1A A2 2A An

17、n成立的充分必要条件是成立的充分必要条件是 X XA Ai i(i=1,(i=1,n),n)均成立。均成立。 充分性证明：充分性证明：由条件推出结论；由条件推出结论； 必要性证明：必要性证明：假设结论成立，推出条件成立。假设结论成立，推出条件成立。 已知关系模式已知关系模式R(A,B,C)R(A,B,C)上有函数依赖集上有函数依赖集 F=AF=AB,BB,BCC，求，求X X分别等于分别等于A A、B B、C C时的时的X X+ +。 解：解： 设有关系模式设有关系模式R(UR(U，F)F)和属性集和属性集U=AU=A1 1， A A2 2，A An n 的子集的子集X X、Y Y。则。则X

18、XY Y能用阿姆斯特朗能用阿姆斯特朗 公理从公理从F F导出的充分必要条件是导出的充分必要条件是。 从给定的属性集从给定的属性集X X出发（出发（设设X XX X） 如果发现如果发现X X包含了包含了F F中的某个函数依赖左中的某个函数依赖左 边的属性，就把该依赖右边的属性添加到边的属性，就把该依赖右边的属性添加到X X中。中。 即对于即对于F F中的所有中的所有V VW W，若有，若有V V X X，则有，则有 X X=X=XW W。 循环第步的过程不断扩充循环第步的过程不断扩充X X，直到该集，直到该集 合再也无法扩展时，得到的结果就是合再也无法扩展时，得到的结果就是X X 。 。 输入：

19、输入：关系模式关系模式R R的全部属性集的全部属性集U,UU,U上的函数依赖上的函数依赖 集集F F，U U的子集的子集X X。 输出：输出：X X关于关于F F的闭包的闭包X X 。 。 方法：方法：（1 1）X X(0) (0)=X =X。 （2 2）从）从F F中找出满足条件中找出满足条件V V X X(i) (i)的所有函数依赖 的所有函数依赖 VWVW，并把所有的，并把所有的VWVW中的属性中的属性W W组成的集合记为组成的集合记为Z Z； 也即从也即从F F中找出那些其决定因素是中找出那些其决定因素是X X(i) (i)的子集的函数依 的子集的函数依 赖，并由这些函数依赖的被决定因

20、素组成一个集合，赖，并由这些函数依赖的被决定因素组成一个集合， 设其（被记为）设其（被记为）Z Z。 （3 3）若）若Z Z X X(i) (i)，则转（ ，则转（5 5）。）。 （4 4）否则，）否则，X X(i+1) (i+1)=X =X(i) (i)Z Z，并转（ ，并转（2 2）。）。 （5 5）停止计算，输出）停止计算，输出X X(i) (i)，即为 ，即为X X+ +。 例例6.46.4 已知有函数依赖集已知有函数依赖集 F=ABC, BCD, F=ABC, BCD, ACDB,DEG,BECACDB,DEG,BEC，属性集，属性集U=A,B,C,D,E,GU=A,B,C,D,E,

21、G， 且且X=BDX=BD，求，求X X 。 。 解：解： 输入：输入：关系模式关系模式R R的全部属性集的全部属性集U,UU,U上的函数依赖上的函数依赖 集集F F，U U的子集的子集X X。 输出：输出：X X关于关于F F的闭包的闭包X X 。 。 方法：方法：（1 1）X X(0) (0)=X =X。 （2 2）从）从F F中找出满足条件中找出满足条件V V X X(i) (i)的所有函数依赖 的所有函数依赖 VWVW，并把所有的，并把所有的VWVW中的属性中的属性W W组成的集合记为组成的集合记为Z Z； 也即从也即从F F中找出那些其决定因素是中找出那些其决定因素是X X(i) (

22、i)的子集的函数依 的子集的函数依 赖，并由这些函数依赖的被决定因素组成一个集合，赖，并由这些函数依赖的被决定因素组成一个集合， 设其（被记为）设其（被记为）Z Z。 （3 3）若）若Z Z X X(i) (i)，则转（ ，则转（5 5）。）。 （4 4）否则，）否则，X X(i+1) (i+1)=X =X(i) (i)Z Z，并转（ ，并转（2 2）。）。 （5 5）停止计算，输出）停止计算，输出X X(i) (i)，即为 ，即为X X+ +。 U=A,B,C,D,E,G F=ABC, BCD,ACDB,DEG,BEC X=BD 定义定义6.56.5 定理定理6.46.4 根据集合运算规则根

23、据集合运算规则 推论推论6.46.4 每一个函数依赖集都被其右端只每一个函数依赖集都被其右端只 有一个属性的函数依赖组成的依赖集所覆盖。有一个属性的函数依赖组成的依赖集所覆盖。 推论推论6.46.4证明的主要理论根据：证明的主要理论根据：分解规则与分解规则与 合并过则。合并过则。 满足下列条件的函数依赖集满足下列条件的函数依赖集F F称为称为 最小函数依赖集。最小函数依赖集。 F F中每一个函数依赖的右端都是单个属性；中每一个函数依赖的右端都是单个属性； 对对F F中任何函数依赖中任何函数依赖X XA A，F-XF-XAA不等不等 价于价于F;F; 对对F F中的任何函数依赖中的任何函数依赖X

24、 XA A和和X X的任何真子的任何真子 集集Z Z，(F-X(F-XA)ZA)ZAA不等价于不等价于F F。 用分解规则将用分解规则将F F中的所有函数依赖分解成右端中的所有函数依赖分解成右端 为单个属性的函数依赖；为单个属性的函数依赖； 去掉去掉F F中冗余的函数依赖，即对于中冗余的函数依赖，即对于F F中任一函中任一函 数依赖数依赖X XY Y： 设设G = F-XG = F-XYY； 求求X X关于关于G G的闭包的闭包X XG G+ +； 看看X XG G+ +是否包含是否包含Y Y。如果。如果X XG G+ +包含包含Y Y，则在，则在G G中逻辑中逻辑 蕴涵蕴涵X XY Y，说明

25、，说明X XY Y是多余的函数依赖，从而可得到是多余的函数依赖，从而可得到 较小的函数依赖集较小的函数依赖集F=GF=G；如果；如果X XG G+ +不包含不包含Y Y，则保留，则保留X XY Y。 按上述方法逐个考察按上述方法逐个考察F F中的每一个函数依赖中的每一个函数依赖, ,直直 到其中所有函数依赖都考察完为止。到其中所有函数依赖都考察完为止。 注注： 去掉去掉 F F 中函数依赖左端多余的属性，即对于中函数依赖左端多余的属性，即对于F F中中 左端左端的函数依赖（的函数依赖（XYXYA A），要判断），要判断X X或或Y Y是是 不是多余的属性。不是多余的属性。当要判断当要判断Y Y

26、是否是多余的属性时是否是多余的属性时： 设设G = (F-XYG = (F-XYA)XA)XAA； 求求XYXY关于关于G G的闭包，（的闭包，（XY)XY)G G+ +； 如果如果 (XY) (XY)G G+ +包含包含A A，则说明，则说明 Y Y是多余的属性，是多余的属性， 从而可得到较小的函数依赖集从而可得到较小的函数依赖集F=GF=G；如果；如果(XY)(XY)G G+ +不包含不包含A A， 则说明则说明XYXYA A不被不被G G逻辑隐含逻辑隐含，说明说明 Y Y不是多余的属性。不是多余的属性。 或者或者 求求X X关于关于F F的闭包，的闭包， （X)X)F F+ + ； 如果

27、如果（X)X)F F+ +包含包含A A，则，则Y Y是多余属性是多余属性 当当Y Y不是多余属性时，要接着用类似的方法判断不是多余属性时，要接着用类似的方法判断X X 是不是多余的属性（是不是多余的属性（ ）。）。 如果如果X X和和Y Y都不是多余的属性时，则保留该函数依都不是多余的属性时，则保留该函数依 赖赖XYXYA A。 接着按上述方法逐个考察接着按上述方法逐个考察F F中左端是非单属性的中左端是非单属性的 其他函数依赖，直到其中的所有左端是非单属性的函数其他函数依赖，直到其中的所有左端是非单属性的函数 依赖都考察完为止。依赖都考察完为止。 求函数依赖集求函数依赖集F F的最小函数依

28、赖集，其中的最小函数依赖集，其中: : 求函数依赖集求函数依赖集F F的最小函数依赖集。的最小函数依赖集。 即试着去掉即试着去掉F1F1中的每中的每 一个函数依赖，看它是否被一个函数依赖，看它是否被F1F1中剩余的函数依赖蕴含。中剩余的函数依赖蕴含。 对于对于ABABC C，求，求ABAB关于关于F F1 1-AB-ABCC的闭包。的闭包。 显然，对于显然，对于(AB)(AB)(0) (0)=AB =AB，在，在F F1 1-AB-ABCC中不存在决中不存在决 定因素是定因素是ABAB的子集的函数依赖，也即有的子集的函数依赖，也即有(AB)(AB)+ +=AB=AB，且，且 C (AB)C (

29、AB)+ +，所以，所以ABABC C不多余。不多余。 F1= 求函数依赖集求函数依赖集F F的最小函数依赖集。的最小函数依赖集。 对于对于ACDACDB B，求，求ACDACD关于关于F F1 1-ACD-ACDB B 的闭包。的闭包。 由于对于由于对于(ACD)(ACD)+ +=ABCDEG=ABCDEG，且，且B B (ACD)(ACD)+ +=ABCDEG,=ABCDEG, 所以所以ACDACDB B是多余的。是多余的。 按照上述思路依次考察按照上述思路依次考察F F1 1中的每个函数依赖，可中的每个函数依赖，可 得：得： F1= 求函数依赖集求函数依赖集F F的最小函数依赖集。的最小

30、函数依赖集。 解：解： ABABC C，C CA A，BCBCD D， D DE E，D DG G，BEBEC C， CGCGB B，CECEG G F21= ABABC C，C CA A，BCBCD D， ACDACDB B，D DE E，D DG G， BEBEC C，CGCGD D，CECEG G F22= 求函数依赖集求函数依赖集F F的最小函数依赖集。的最小函数依赖集。 F Fmin min= = 或或 F Fmin min= = ABABC C，C CA A，BCBCD D， D DE E，D DG G，BEBEC C CGCGB B，CECEG G ABABC C，C CA A，

31、BCBCD D， CDCDB B，D DE E，D DG G， BEBEC C，CGCGD D，CECEG G 本章的本章的6.26.2节所述，为了消除某些关系节所述，为了消除某些关系 模式可能存在的数据冗余、插入异常、删除异模式可能存在的数据冗余、插入异常、删除异 常和修改异常，就需要对这些关系模式进行分常和修改异常，就需要对这些关系模式进行分 解。解。 设设U Ui i是属性集是属性集U U的一个子集，则函数的一个子集，则函数 依赖集合依赖集合XY|XYXY|XY F F+ +XYXY U Ui i 的一个覆盖的一个覆盖F Fi i， 称为称为F F在在U Ui i上的投影。上的投影。 定

32、义定义6.76.7的含义和要说明的问题：的含义和要说明的问题： 对于属性集对于属性集U U的子集的子集U Ui i，存在一个与其对应的依赖，存在一个与其对应的依赖 子集子集F Fi i，且由，且由F Fi i中的每个函数依赖中的每个函数依赖XYXY的决定因素的决定因素X X和和 被决定因素被决定因素Y Y组成的属性子集组成的属性子集XYXY均是均是U Ui i的子集。的子集。 设有关系模式设有关系模式R(UR(U，F)F)和和 U=A1,A2,U=A1,A2,An,An的子集的子集Z Z，把，把F F+ +中所有满足中所有满足XYXY Z Z 的函数依赖的函数依赖XYXY组成的集合，称为依赖集

33、组成的集合，称为依赖集F F在属性在属性 集集Z Z上的投影，记为上的投影，记为z z(F)(F)。 由定义由定义5.85.8知，显然有：知，显然有： z z(F)(F)XY|XYXY|XY F F+ +，且，且XYXY ZZ 所以定义所以定义5.85.8和定义和定义5.75.7本质上是相同的。本质上是相同的。 设有关系模式设有关系模式R(U,F)R(U,F)，如果，如果U=UU=U1 1UU2 2 UUk k，并且对于任意的，并且对于任意的i,j(1i,jk)i,j(1i,jk)，不成，不成 立立U Ui i U Uj j，且，且F Fi i是是F F在在U Ui i上的投影，则称：上的投影

34、，则称： =R =R1 1(U(U1 1,F,F1 1) )，R R2 2(U(U2 2,F,F2 2) )，R Rk k(U(Uk k,F,Fk k) 是关系模式是关系模式R(U,F)R(U,F)的一个分解。的一个分解。 例例6.6 6.6 设有关系模式设有关系模式R(U,F)R(U,F)，U=S#,SD,SMU=S#,SD,SM， F=S#SD,SDSMF=S#SD,SDSM，并设关系，并设关系R R有如下表的当前值有如下表的当前值 r r。 下面采用三种不同方法对关系下面采用三种不同方法对关系R R进行分解。进行分解。 F=S#SD,SDSMF=S#SD,SDSM 设：设：11R1(S#

35、,)R1(S#,)，R2(SD,)R2(SD,)，R3(SM,)R3(SM,) 即有，即有，F Fi i= = 和和 R Ri i=i i(R(U) (R(U) 对于已知关系对于已知关系r r在在i i(R(U)(R(U)上的投影，有：上的投影，有： r1=S1,S2,S3 r1=S1,S2,S3 r2=D1,D2,D3 r2=D1,D2,D3 r3=M1,M2 r3=M1,M2 S1 D1 M1， S2 D1 M1， S3 D1 M1， S1 D1 M2， S2 D1 M2， S3 D1 M2， S1 D2 M1， S2 D2 M1， S3 D2 M1， S1 D2 M2， S2 D2 M2

36、， S3 D2 M2， S1 D3 M1， S2 D3 M1， S3 D3 M1， S1 D3 M2， S2 D3 M2， S3 D3 M2 对关系模式的分解，理应要求分解后的各关系能恢对关系模式的分解，理应要求分解后的各关系能恢 复原关系的原值，一般采用自然联接方法恢复可得：复原关系的原值，一般采用自然联接方法恢复可得： r1r1 r2r2 r3rr3r r1 r2 r3=r1 r1 r2 r3=r1r2r2r3r3 联接结果为：联接结果为： 比较关系比较关系R R原来的当前值：原来的当前值： 和向和向R1R1、R2 R2 和和 R3 R3投影后，再联接恢复的值：投影后，再联接恢复的值： S

37、1 D1 M1， S2 D1 M1， S3 D1 M1， S1 D1 M2， S2 D1 M2， S3 D1 M2， S1 D2 M1， S2 D2 M1， S3 D2 M1， S1 D2 M2， S2 D2 M2， S3 D2 M2， S1 D3 M1， S2 D3 M1， S3 D3 M1， S1 D3 M2， S2 D3 M2， S3 D3 M2 设设:2=R1(S#,SD,S#:2=R1(S#,SD,S# SD),R2(S#,SM,S#SM)SD),R2(S#,SM,S#SM) 因为有：因为有： S#， S# SD，SD, S#S#， S# SDS#，SDSD, = S#SD， S#

38、SDSD， S#S# SD，S# SDS# SD 1 F S#， S# SM，SM, S#S#， S# SMS#，SMSM, = S#SM， S# SMSM， S#S# SM，S# SMS# SM 2 F 分析可知，原分析可知，原F F中的中的SDSM SDSM 均不在上面均不在上面2 2个闭包中，即：个闭包中，即： F1F2F1F2不等于不等于F F，但可以证明成立：，但可以证明成立： r1 r2 = r r1 r2 = r F=S#SD,SDSM 设设: :2=R1(S#,SD,S#SD),2=R1(S#,SD,S#SD), R2(SD,SM,SDSM) R2(SD,SM,SDSM) 因为

39、有：因为有： r1=(S1,D1),(S2,D2),(S3,D3) r1=(S1,D1),(S2,D2),(S3,D3)； F1 F1S#SD S#SD r2=(D1,M1),(D2,M1),(D3,M2) r2=(D1,M1),(D2,M1),(D3,M2)； F2 F2SDSMSDSM 可以证明成立：可以证明成立： r1 r2=r r1 r2=r 和和 F1F2 = F F1F2 = F 定义5.10 设有关系模式设有关系模式R(U,F)R(U,F)，=（R R1 1,R,R2 2, , ,R,Rk k）是）是R R的一个分解。如果对于的一个分解。如果对于R R的任一满足的任一满足F F的

40、的 关系关系r r，成立：，成立： r= r=R1 R1(r) (r) R2 R2(r) (r) Rk Rk(r) (r) 则称分解则称分解是无损联接分解。也称该分解是无损联接分解。也称该分解是保持是保持 无损的分解。无损的分解。 判断一个分解的无损联接性判断一个分解的无损联接性 关系模式关系模式R(A1,R(A1,An),An)，函数依赖集，函数依赖集F F， R R的一个分解的一个分解(R(R1 1,R,R2 2, ,R,Rk k) )。 是否为无损联接的判断。是否为无损联接的判断。 判断一个分解的无损联接性判断一个分解的无损联接性 构造一个构造一个k k行行n n列列表表S S。其中，第

41、。其中，第i i行对应于行对应于 关系模式关系模式R R分解后的模式分解后的模式R Ri i，第，第j j列对应于关系模式列对应于关系模式 R R的属性的属性A Aj j。表中第。表中第i i行第行第j j列位置的元素填入方法列位置的元素填入方法 为：如果为：如果A Aj j在在R Ri i中，则在第中，则在第i i行第行第j j列的位置上填上列的位置上填上 符号符号a aj j, ,否则填上符号否则填上符号b bij ij。 。 对于对于F F中的所有函数依赖中的所有函数依赖XYXY，在表中寻找，在表中寻找 在在X X的各个属性上都分别相同的行，若至少存在两个的各个属性上都分别相同的行，若至

42、少存在两个 或多个这样的行，则将这些行上对应的或多个这样的行，则将这些行上对应的Y Y属性上的元属性上的元 素值，修改成具有相同符号的元素值，修改方法为：素值，修改成具有相同符号的元素值，修改方法为： 当这些行的当这些行的Y Y属性上的某一行上都为属性上的某一行上都为a aj j（j j为为Y Y 属性对应的那些列的列序号，且属性对应的那些列的列序号，且j=1,2,j=1,2,n,n）时，）时， 则把该行的则把该行的Y Y属性上的其它元素都修改成属性上的其它元素都修改成a aj j； 当这些行的当这些行的Y Y属性列中没有这样的属性列中没有这样的a aj j时，则以时，则以 Y Y属性列中下标

43、较小的属性列中下标较小的b bij ij为基准，把这些行的 为基准，把这些行的Y Y属性属性 列上的其它元素都修改成列上的其它元素都修改成b bij ij。 。 按按(2)(2)逐个考察逐个考察F F中的每一个函数依赖，如中的每一个函数依赖，如 果发现某一行变成了果发现某一行变成了a a1 1，a a2 2，a an n，则分解，则分解具有具有 无损联接性；如果直到检验完无损联接性；如果直到检验完F F中的所有函数依赖也中的所有函数依赖也 没有发现有这样的行，表也不再变化，则分解没有发现有这样的行，表也不再变化，则分解不不 具有无损联接性。具有无损联接性。 设设R(ABCDE)R(ABCDE)

44、，F=AC,BC,CD,DEC,CEA,F=AC,BC,CD,DEC,CEA, 分解分解=R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE),=R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE),检验检验 分解分解是否具有无损联接性。是否具有无损联接性。 R(ABCDE)R(ABCDE)， F=AC,BC,CD,DEC,CEA, F=AC,BC,CD,DEC,CEA, =R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)=R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE) 解：解：第一步，构造表第一步，构造表S S

45、。 第二步：第二步： 根据函数依赖根据函数依赖ACAC修正表修正表S S。 第二步：第二步： 根据函数依赖根据函数依赖BCBC修正表修正表S S。 第二步：第二步： 根据函数依赖根据函数依赖CDCD修正表修正表S S。 第二步：第二步： 根据函数依赖根据函数依赖DECDEC修正表修正表S S。 第二步：第二步： 根据函数依赖根据函数依赖CEACEA修正表修正表S S。 第三步：通过判断，给出结论。第三步：通过判断，给出结论。 第三步：通过判断，给出结论。第三步：通过判断，给出结论。 表中的第三行都变成表中的第三行都变成a aj j了，所以分解了，所以分解具有无损具有无损 联接性。联接性。 设有

46、关系模式设有关系模式R(U,F)R(U,F)，=(R1=(R1，R2)R2) 是是R R的一个分解，当且仅当的一个分解，当且仅当: : (R1R2)( (R1R2)()F)F+ + 或或 (R2R1)(R2R1)()F)F+ + 时，时，具有无损联接性。具有无损联接性。 设有关系模式设有关系模式R(A,B,C)R(A,B,C)，函数依赖集，函数依赖集 F=ABF=AB，CBCB，分解，分解=R1,R2=R1,R2，其中，其中R1=ABR1=AB， R2=BCR2=BC。检验分解。检验分解是否具有无损联接性。是否具有无损联接性。 解：解： 在例在例5.65.6中，已知有关系模式中，已知有关系模式

47、 (S#(S#，SDSD，SM)SM)，函数依赖集，函数依赖集=S#SD=S#SD，SDSMSDSM。 且对于其中的方法且对于其中的方法(3)(3)，已知有分解，已知有分解=(S#,SD)=(S#,SD)， (SD,SM)(SD,SM)，且已指出分解是无损联接分解，下面，且已指出分解是无损联接分解，下面 进行验证。进行验证。 解：解： 对于对于关系模式关系模式R(U,F)R(U,F)，保持无损性讨论的是，保持无损性讨论的是 R(U)R(U)被分解成多个是被分解成多个是R Ri i时的信息保持问题。时的信息保持问题。 对于对于R(F)R(F)，同样存在分解成多个，同样存在分解成多个R Ri i时

48、，对应的时，对应的 R(FR(Fi i) )是否成立，以及能否保持原来是否成立，以及能否保持原来F F的依赖性问题。的依赖性问题。 设有关系模式设有关系模式R(U,F)R(U,F)，= （R1,R2,R1,R2,Rk,Rk）是）是R R的一个分解。如果所有函数依的一个分解。如果所有函数依 赖集赖集Ri Ri(F)(i=1,2, (F)(i=1,2,，k k）的并集逻辑蕴含）的并集逻辑蕴含F F中的中的 每一个函数依赖，则称分解每一个函数依赖，则称分解具有依赖保持性，也具有依赖保持性，也 即分解即分解保持依赖集保持依赖集F F。即：。即： k i R FF i 1 | )( 对对中的每一个中的每

49、一个R Ri i求求Ri Ri(F) (F) 求求 对对F F中每一个函数依赖中每一个函数依赖XYXY， 判断能否由判断能否由 导出，如果均能导出，则分解导出，如果均能导出，则分解具有依赖保具有依赖保 持性；否则分解持性；否则分解不具有依赖保持性。不具有依赖保持性。 k i R F i 1 )( k i R F i 1 )( 例例6.11 6.11 已知有关系模式已知有关系模式 R(S#,SD,SM) R(S#,SD,SM)和函数依赖集和函数依赖集 F=S#SD,SDSM F=S#SD,SDSM，且知有分解，且知有分解: : 3=R1(S#,SD,S#SD),R2(SD,SM,SDS3=R1(

50、S#,SD,S#SD),R2(SD,SM,SDS M)M)。验证分解。验证分解33是保持依赖的分解。是保持依赖的分解。 F #)()( 21 SMSDSDSFF RR 因为 ,#SMSDSDS 3 所以， 具有保持依赖性。 例例6.12 6.12 已知有关系模式已知有关系模式R(S#,SD,SM)R(S#,SD,SM)和函数依赖集和函数依赖集 F=S#SD,SDSMF=S#SD,SDSM，且知有分解，且知有分解 2=R1(S#,SD,S#SD),R2(S#,SM,S#SM)2=R1(S#,SD,S#SD),R2(S#,SM,S#SM)。 验证分解验证分解22具有无损联接性，但不具有保持依赖性。

51、具有无损联接性，但不具有保持依赖性。 因为因为 (R1R2)(R1-R2) (R1R2)(R1-R2) (S#,SD S#,SM)(S#,SD-S#,SM)(S#,SD S#,SM)(S#,SD-S#,SM) S#SD F S#SD F 所以分解具有无损联接性。所以分解具有无损联接性。 例例6.12 6.12 已知有关系模式已知有关系模式R(S#,SD,SM)R(S#,SD,SM)和函数依赖集和函数依赖集 F=S#SD,SDSMF=S#SD,SDSM，且知有分解，且知有分解 2=R1(S#,SD,S#SD),R2(S#,SM,S#SM)2=R1(S#,SD,S#SD),R2(S#,SM,S#S

52、M)。 验证分解验证分解22具有无损联接性，但不具有保持依赖性。具有无损联接性，但不具有保持依赖性。 因为因为 R1(F)R2(F) R1(F)R2(F) S#SDS#SMS#SDS#SM S#SDS#SD，S#SMS#SM 显然，显然，(SDSM) S#SD(SDSM) S#SD，S#SMS#SM 也即，也即，R1(F)R1(F)和和R2(F)R2(F)的并集不逻辑蕴含中的函的并集不逻辑蕴含中的函 数依赖数依赖SDSMSDSM。所以分解。所以分解22不具有保持依赖性。不具有保持依赖性。 课堂练习课堂练习 设有设有R(ABC), =AC,BCR(ABC), =AC,BC，F=AB,BCF=AB

53、,BC；判；判 断该分解是否具有无损联接和保持函数依赖。断该分解是否具有无损联接和保持函数依赖。 对于给定的关系对于给定的关系S(U,F)S(U,F)，关系，关系S S的的 属性按其在函数依赖的左端和右端的出现分为属性按其在函数依赖的左端和右端的出现分为4 4类：类： 仅出现在仅出现在F F中的函数依赖左部的属性；中的函数依赖左部的属性； 仅出现在仅出现在F F中的函数依赖右部的属性；中的函数依赖右部的属性； 在在F F中函数依赖的左右两边均出现的中函数依赖的左右两边均出现的 属性。属性。 在在F F中函数依赖的左右两边均未出现中函数依赖的左右两边均未出现 的属性；的属性； 设有关系模式设有关

54、系模式R(UR(U，F)F)和属性集和属性集 U=AU=A1 1,A,A2 2, ,A,An n 的子集的子集X X： 若若X X是是L L类属性，则类属性，则X X必为必为R R的某一候选键的成员；的某一候选键的成员； 若若X X是是L L类属性，且类属性，且X X+ +包含了包含了R R的全部属性，则的全部属性，则X X必为必为R R 的唯一候选键；的唯一候选键； 若若X X是是R R类属性，则类属性，则X X不是任一候选键的成员；不是任一候选键的成员； 若若X X是是N N类属性，则类属性，则X X必包含在必包含在R R的某一候选键中；的某一候选键中； 若若X X是是R R的的N N类属

55、性和类属性和L L类属性组成的属性集，且类属性组成的属性集，且X X+ +包含包含 了了R R的全部属性，则的全部属性，则X X是是R R的唯一候选键。的唯一候选键。 设关系模式设关系模式R(U,F)R(U,F)的依赖集的依赖集F F已经为最已经为最 小依赖集小依赖集( (即即, ,蕴含依赖右端只有单个属性蕴含依赖右端只有单个属性) )，则关系模式，则关系模式 R R的函数依赖图的函数依赖图G G是一个有序二元组是一个有序二元组G=(R,F),G=(R,F),且：且： （1 1）U=AU=A1 1,A,A2 2, ,A,An n 是一个有限非空集，是一个有限非空集，A Ai i是是G G中的中

56、的 结点。结点。 （2 2）F F是是G G的一个非空边集，的一个非空边集，A Ai iA Aj j是是G G中的一条有向中的一条有向 边边(A(Ai i，A Aj j) )。 （3 3）若结点）若结点A Ai i与结点与结点A Aj j之间存在一条有向边之间存在一条有向边(A(Ai i,A,Aj j) )， 则该边称为则该边称为A Ai i的出边和的出边和A Aj j的入边。的入边。 （4 4）只有出边而无入边的结点称为原始点（表示）只有出边而无入边的结点称为原始点（表示L L类类 属性）；只有入边而无出边的结点称为终结点（表示属性）；只有入边而无出边的结点称为终结点（表示R R类类 属性）

57、；既有入边又有出边的结点称为途中点（表示属性）；既有入边又有出边的结点称为途中点（表示LRLR 类属性）；既无入边又无出边的结点称为孤立点（表示类属性）；既无入边又无出边的结点称为孤立点（表示N N 类属性）。类属性）。 （5 5）原始点和孤立点统称为关键点；关键点对应的）原始点和孤立点统称为关键点；关键点对应的 属性称为关键属性；其他结点不能到达的回路称为独立属性称为关键属性；其他结点不能到达的回路称为独立 回路。回路。 关系模式关系模式R(A1,A2,An)，R的函数依赖集的函数依赖集F； R的所有候选键。的所有候选键。 求求F的最小依赖集的最小依赖集Fmin； 构造函数依赖图；构造函数依

58、赖图； 从图中找出关键属性集从图中找出关键属性集X（X可为空）；可为空）； 查看查看G中有无独立回路，若无则中有无独立回路，若无则X即为即为R的唯一候选的唯一候选 键，转；键，转； 从各独立回路中各取一结点对应的属性与从各独立回路中各取一结点对应的属性与X组合成组合成 一候选键，并重复这一过程，取尽所有可能的组合，即为一候选键，并重复这一过程，取尽所有可能的组合，即为 R的全部候选键；的全部候选键； 输出候选键，算法结束。输出候选键，算法结束。 将将R R的所有属性分为的所有属性分为L L、R R、N N和和LRLR四类，并令四类，并令X X代表代表L L和和N N 类，类，Y Y代表代表LR

59、LR类；类； 求求X X 。若 。若X X 包含了 包含了R R的全部属性的全部属性, ,则则X X是是R R的唯一候选键，的唯一候选键， 转；否则，转；转；否则，转； 在在Y Y中取一属性中取一属性A A，求，求(XA)(XA) ，若它包含了 ，若它包含了R R的全部属性，的全部属性， 则则XAXA为为R R的一个候选键的一个候选键; ; 重复，直到重复，直到Y Y中的属性依次取完为止；中的属性依次取完为止； 从从Y Y中除去已成为主属性的属性中除去已成为主属性的属性A;A; 在剩余属性中依次取两个、三个、在剩余属性中依次取两个、三个、，将其记为集合，将其记为集合B B， 求求(XB)(XB

60、) ：若 ：若(XB)(XB) 包含了 包含了R R的全部属性，且自身不包含已求出的全部属性，且自身不包含已求出 的候选键，则的候选键，则XBXB为为R R的一个候选键；的一个候选键； 重复，直到重复，直到Y Y中的属性按方法的组合依次取完为止；中的属性按方法的组合依次取完为止； 输出候选键，算法结束。输出候选键，算法结束。 设有关系模式设有关系模式R(A,B,C,D,E)R(A,B,C,D,E)和和R R的函数依赖集的函数依赖集 F=A F=ABC,CDBC,CDE,BE,BD,ED,EAA，求，求R R的所有候选键。的所有候选键。 根据根据F F对对R R的所有属性进行分类：的所有属性进行