第六章 关系数据理论 内容出处： 1.Abraham Silberschatz《数据库系统概念》第七章.

Presentation on theme: "第六章 关系数据理论 内容出处： 1.Abraham Silberschatz《数据库系统概念》第七章."— Presentation transcript:

1 第六章 关系数据理论 内容出处： 1.Abraham Silberschatz《数据库系统概念》第七章

2 第六章 关系数据理论 教学目的 主要内容 教学方法 重点 难点
本章讨论如何进行关系数据库的逻辑设计。首先介绍函数依赖的概念，然后利用函数依赖和其他类型的依赖定义范式，并给出利用Armstrong公理系统确定范式级别的方法，最后介绍一些将关系模式分解为更高级范式的模式分解算法。 主要内容 关系模式的设计问题，函数依赖，范式，函数依赖的推理规则，模式分解 教学方法 课堂讲授加大作业中的数据库的逻辑设计 重点 函数依赖，范式及它们之间的关系，模式分解算法 难点 多值依赖， Armstrong公理系统的完备性证明

3 本章内容 关系模式的设计问题 函数依赖 范式 函数依赖的推理规则 模式分解

4 问题 数据库的逻辑设计问题 为什么研究关系数据理论？ 给出一组数据，如何构造一个适合于它们的数据模式？
关系数据理论是关系数据库逻辑设计的工具 关系模型有严格的数学理论基础 可以向其它数据模型转换

5 关系模式的设计问题 示例 设关系模式R(S#,C#,CName, TName) 属性分别为学生学号，选修课程号，课程名，教师姓名

6 关系模式的设计问题 信息的不可表示问题 信息的冗余问题 插入异常：新开课程(C1,Alg,Zhang)，尚无学生选修时，如何将其插入；
删除异常：删除学生信息时，课程信息会同时消除； 信息的冗余问题 数据冗余：对于多个学生选修的课程会多次重复； 更新异常(复杂)：若一门课程的信息，如授课教师，发生修改，则更新操作复杂且可能引入不一致；

7 关系模式的设计问题 解决办法：分解! SC(S#, C#) C(C#, CName, TName)

8 关系模式的设计问题 新问题：有关学生的关系模式 S(S# , SN , SD , DEAN , C# , G) 它存在哪些问题？ 原因何在？

9 关系模式的设计问题 概念回顾 问题：关系模式的形式描述？ 直观 抽象 关系：一张二维表 元组：表中一行 属性：表中一列
属性所对应的域---属性集 元组：属性集的笛卡尔积的一个元素 关系：元组的集合，即笛卡尔积的一个子集 关系模式：元组集合的结构上的描述（关系的集合） 问题：关系模式的形式描述？

10 关系模式的设计问题 关系模式的形式描述 关系模式由五部分组成，即关系模式是一个五元组： R（U，D，DOM，F） R：关系名
D：属性组U中属性所来自的域 DOM：属性到域的映射 F：属性间的数据依赖集合。它限定了组成关系的各个元组必须满足的完整性约束条件。

11 关系模式的设计问题 简化记法 存在上述逻辑设计问题的原因？ 关系规范化 将关系模式简记为R<U,F>
当且仅当U上的一个关系r满足F，r称为关系模式R<U，F>的一个关系 存在上述逻辑设计问题的原因？ 某些属性间存在某种数据依赖 关系规范化 用简单结构的关系取代复杂结构的关系，即逐步减少关系内部数据的依赖，以解决冗余、更新异常、插入异常和删除异常 方法 根据一个关系所具有的属性间依赖情况来判定它是否具有某些不合适的性质，若有，通过模式分解消除那些不合适的性质

12 对t , s  r，若t[X] = s[X]，则t[Y] = s[Y]，
函数依赖 函数依赖 设R(U)是属性集U上的关系模式，X , Y  U，r是R(U)上的任意一个关系，如果总有： 对t , s  r，若t[X] = s[X]，则t[Y] = s[Y]， 那么称“X函数决定Y”，或“Y函数依赖于X”，记作XY，称X为决定因素， 如S#  SN，（S#，C#） G 若X→Y，并且Y→X, 则记为X Y 若Y不函数依赖于X, 则记为 X Y

13 函数依赖 有几种等价的定义: X→Y ，for any t1, t2 in r(R), if t1 and t2 have the same X-value, then t1 and t2 also have the same Y-value. X → Y，there exist no t1, t2 in r(R) such that t1 and t2 have the same X-value but different Y-values. X → Y，for each X-value, there corresponds to a unique Y-value.

14 函数依赖 A B C D a1 b1 c1 d1 b2 d2 a2 c2 b3 d3 a3 d4 检验：A→C？C→A？AB→D？ 辨别：
满足依赖的关系：依赖在模式的某个关系实例上成立 模式上成立的依赖：依赖在模式的所有关系实例上都成立

15 练习 A B C 1 2 3 4 5 找出可能的函数依赖

16 思考：一个关系模式有n个属性，那么在它上面成立的所有可能的函数依赖有多少个？非平凡的函数依赖又有多少个？
平凡函数依赖 如果X  Y，但Y  X，则称其为非平凡的函数依赖，否则称为平凡的函数依赖 如（S#，SN） SN是平凡的函数依赖 思考：一个关系模式有n个属性，那么在它上面成立的所有可能的函数依赖有多少个？非平凡的函数依赖又有多少个？

17 函数依赖 部分函数依赖 在R(U)中，如果XY，且对于任意X的真子集X′，都有 ，则称Y完全函数依赖于X ，记作 否则称为Y部分函数依赖于X ，记作 S(S# , SN , SD , DEAN , C# , G) X′ Y X Y X Y （S#，C#） G （S#，C#） SN 练习：找出S中的另一部分函数依赖

18 函数依赖 传递函数依赖 X  Y，Y  Z，Y  X，且Z Y 在R(U)中，如果 则称Z传递函数依赖于X
S#  SD，SD  DEAN X  Y，Y  Z，Y  X，且Z Y 练习：给出一个具有传递函数依赖的关系模式例子

19 存在传递函数依赖的例子 示例 考虑为管理职工的工资信息而设计一个关系模式 职工 级别 工资 赵明 4 500 钱广 5 600 孙志 6
700 李开 周祥

20 函数依赖 候选码：设K为R< U , F >的属性(组)，若K U，则称K为R的候选码
超码：设K为R< U , F >的候选码， X为R< U , F >的属性(组)，若K X，则称X为R的超码 主码：若R(U , F)有多个候选码，则可以从中选定一个作为R的主码 主属性：包含在任一候选码中的属性，称作主属性 全码：关系模式的码由整个属性组构成

21 关系模式S(S# , SN , SD , DEAN , C# , G)
范例 关系模式S(S# , SN , SD , DEAN , C# , G) 主码：（S#，C#）函数依赖： （S#，C#） G S#  SN，（S#，C#） SN S#  SD，（S#，C#） SD SD  DEAN S# SN SD DEAN C# G

22 函数依赖的确定 函数依赖是语义范畴的概念。只能根据属性对现实世界的描述及在现实世界中的关系确定函数依赖，是一个断言，不能证明。如“name→age” 数据库设计者可以对现实世界作强制的规定。如规定不能重名。

23 范式 范式是对关系的不同数据依赖程度的要求，即符合某种级别的关系模式的集合，满足不同程度要求的为不同范式
通过模式分解将一个低级范式转换为若干个高级范式的过程称作规范化（概念的纯粹化） 1NF 2NF 3NF 4NF BCNF 5NF

24 1NF 定义 关系中每一分量不可再分。即不能以集合、序列等作为属性值 S# C# S1 C1 C2 C3 S# C# S1
对象－关系数据库 嵌套关系 传统数据库 平面关系

25 1NF 分量是否需要再分，与具体应用有关。如果用到值的一部分，则需要进一步分割 如果只是查询出生日期，则它满足1NF
如果比较两人的生肖呢？ 姓名 生日 王军 张立 李明 姓名 年 月日 王军 68 7.10 张立 69 李明 80 3.28

26 关系模式S(S# , SN , SD , DEAN , C# , G)
2NF 关系模式S(S# , SN , SD , DEAN , C# , G) 不良特性 插入异常：如果学生没有选课，关于他的个人信息及所在系的信息就无法插入 删除异常：如果删除学生的选课信息，则有关他的个人信息及所在系的信息也随之删除了 更新异常：如果学生转系，若他选修了k门课，则需要修改k次 数据冗余：如果一个学生选修了k门课，则有关他的所在系的信息重复

27 2NF 定义 若R1NF，且每个非主属性完全依赖于码，则称R2NF 消除非主属性对码的部分依赖 如S2NF，因为 （S#，C#） SN
（S#，C#） SD

28 2NF 改造 练习 非主属性有两种，一种完全依赖于码，一种部分依赖于码。 将S分解为： SC(S# , C# , G)
S_SD(S# , SN , SD , DEAN) 练习 关系模式R（A，B，C，D），码为AB，给出它的一个函数依赖集，使得R属于1NF而不属于2NF

29 3NF S_SD(S# , SN , SD , DEAN) 不良特性 插入异常：若系中没有学生，则与系有关的信息就无法插入
删除异常：如果学生全部毕业了，则在删除学生信息的同时与系有关的信息也随之删除了 更新异常：如果学生转系，不但要修改SD，还要修改DEAN，如果换系主任，则该系每个学生元组都要做相应修改 数据冗余：每个学生都存储了所在系的系主任的信息

30 3NF 定义 关系模式R< U , F >中，若不存在这样的码X，属性组Y及非主属性Z(Z Y)，使得下式成立，
XY , YZ , YX 则称R3NF 消除非主属性对码的传递依赖 如S_SD 3NF，因为有S#SD，SDDEAN

31 3NF 改造 练习 将S分解为 STUDENT(S# , SN , SD) DEPT(SD , DEAN)
关系模式R（A，B，C，D），码为AB，给出它的一个函数依赖集，使得R属于2NF而不属于3NF

32 （S#，C#） T#， 某学生选定一门课，就对应一位老师; （S#，T#），（S#，C#）为候选码。
BCNF 示例 STC(S# , T# , C#)， T#  C#， 每位老师只教授一门课; （S#，C#） T#， 某学生选定一门课，就对应一位老师; （S#，T#） C#; （S#，T#），（S#，C#）为候选码。 思考 STC  3NF ？

33 BCNF 不良特性 插入异常：如果没有学生选修某位老师的任课，则该老师担任课程的信息就无法插入
删除异常：删除学生选课信息，会删除掉老师的任课信息 更新异常：如果老师所教授的课程有所改动，则所有选修该老师课程的学生元组都要做改动 数据冗余：每位学生都存储了有关老师所教授的课程的信息 原因： 主属性对码的不良依赖

34 BCNF 定义 关系模式R< U , F >中，对于属性组X、Y，若 X  Y且Y X时,X必含有码，则R< U , F > BCNF 示例： STC  BCNF，因为T#  C#，而T不含有码 改造 将STC分解为（S#，T#），（T#，C#）

35 BCNF 若R∈BCNF 所有非主属性对每一个码都是完全函数依赖 所有的主属性对每一个不包含它的码，也是完全函数依赖
没有任何属性完全函数依赖于非码的任何一组属性 不存在任何属性对码的传递依赖或部分依赖

36 BCNF 思考 (S# , C# , ORDER)，表示学生选修课程的名次，有函数依赖(S#，C#) ORDER， (C#，ORDER)  S#，它属于BCNF吗？ 全码属于BCNF吗？

37 多值依赖 关系模式TEACH（C#，T#，B#），一门课程由多个教师讲授，一门课程使用相同的一套参考书。它的码是（C#，T#，B#），所以属于BCNF C# T# B# C1 T1 B1 B2 T2 C2 B3 B4 T3 C# T# B# C1 {T1,T2} {B1,B2} C2 {T1,T3} {B3,B4} 描述两个独立的一对多联系

38 多值依赖 不良特性 插入异常：当某门课程增加一名教员时，该门课程有多少本参考书就必须插入多少个元组；同样当某门课程需要增加一本参考书时，它有多少个教员就必须插入多少个元组 删除异常：当删除一门课程的某个教员或者某本参考书时，需要删除多个元组 更新异常：当一门课程的教员或参考书作出改变时，需要修改多个元组 数据冗余：同一门课的教员与参考书的信息被反复存储多次

39 多值依赖 定义 描述型：关系模式R(U)，X、Y、Z  U，并且Z = U – X – Y，多值依赖X  Y成立当且仅当对R(U)的任一关系r，给定的一对（X，Z）值有一组Y的值，这组值仅仅决定于X值而与z值无关。 如在关系模式TEACH中，对(C1 , B1)有一组T#值(T1 , T2)，对(C1 , B2)也有一组T#值(T1 , T2)，这组值仅取决于C#的取值，而与B#的取值无关。因此，T#多值依赖于C#，记作C#T#，同样有C#B#

40 多值依赖

41 多值依赖 形式化定义：关系模式R(U)，X、Y、ZU，Z=U–X– Y，对于R(U)的任一关系r，若存在元组t1，t2，使得t1[X] = t2[X]，那么就必然存在元组t3，t4，使得： t3[X] = t1[X] = t4[X] = t2[X] t3[Y] = t1[Y]， t4[Y] = t2[Y] t3[Z] = t2[Z]， t4[Z] = t1[Z] 则称Y多值依赖于X，记作X  Y 若(C#, T#, B#)满足C#T#，含有元组t1=(C1, T1, B1)，t2=(C1, T2, B2)， 则也一定含有元组t3=(C1, T2, B1)，t4=(C1, T1, B2)。

42 多值依赖

43 多值依赖 找出关系上所满足的多值依赖 CB？若使BC成立，需加入哪些元组？ t1 t2 t3 t4 t3 t4 A B C a1
t1.B t1.C t2.A t2.B t2.C t1.A B C A b1 c1 a1 c2 a2 t1 t2 t3 t4 t3 t4

44 多值依赖 性质 多值依赖具有对称性，即 若XY，则XZ，其中Z=U–X–Y 函数依赖是多值依赖的特例，即 若XY，则XY
若XY，U–X–Y=，则称XY为平凡的多值依赖

45 多值依赖 vs 函数依赖 区别 函数依赖规定某些元组不能出现在关系中，也称为相等产生依赖
多值依赖要求某种形式的其它元组必须在关系中，称为元组产生依赖 有效性范围 XY的有效性仅决定于X、Y属性集上的值，它在任何属性集W（XY  W  U）上都成立 若XY在R(U)上成立，则对于任何Y′ Y，均有XY′成立

46 多值依赖 vs 函数依赖 XY的有效性与属性集范围有关 XY在属性集W（XY  W  U）上成立，但在U上不一 定成立
XY在U上成立  XY在属性集W（XY  W  U） 上成立 若在R(U)上，XY在属性集W(XY  W  U)上成立， 则称XY为R(U)的嵌入式多值依赖 若XY在R(U)上成立，则不能断言对于Y′ Y，是 否有XY′成立

47 多值依赖 vs 函数依赖 AB在{ABC} {ABCD} A B C D a1 b1 c1 d1 d2 b2 c2 ABC AB

48 AB在{ABC}上成立，而在{ABCD}上不成立
多值依赖 vs 函数依赖 A B C D a1 b1 c1 d1 c2 b2 d2 AB在{ABC}上成立，而在{ABCD}上不成立 A B C D a1 b1 c1 d1 d2 b2 c2 ABC 成立AB不成立

49 4NF 定义 关系模式R< U , F >  1NF，若XY（YX）是非平凡的多值依赖，X必含有码，则称R4NF
如关系模式CTB，C#T#，C#B#，码为(C#, T#, B#)，所以CTB4NF 如果一门课Ci有m个教员，n本参考书，则关系中分量为Ci的元组共有m×n个，数据冗余非常大 改造 将CTB分解为CT（C#，T#），CB（C#，B#），在分解后的关系中分量为Ci的元组共有m + n个

50 4NF 如果R ∈ 4NF 不允许有非平凡且非函数依赖的多值依赖 允许的非平凡多值依赖是函数依赖

51 思考 任何一个二目关系模式R（A，B）一定属于BCNF吗？一定属于4NF吗？ 一个全是主属性的关系模式一定可以达到第几范式？
一个全码的关系模式一定可以达到第几范式？

52 范式之间的关系 3NF  2NF 反证：若R3NF， 但R2NF，则按2NF定义，一定有非主属性部分依赖于码
设X为R的码，则存在X的真子集X′，以及非主属性Z（Z X′），使得X′Z 于是在R中存在码X，属性组X′，以及非主属性Z（Z X′) ，使得XX′，X′Z，X′X成立，这与R3NF矛盾。 所以R2NF

53 范式之间的关系 BCNF  3NF 反证：若RBCNF， 但R3NF，则按3NF定义，一定有非主属性对码的传递依赖，于是存在：
R的码X ，属性组Y，以及非主属性Z（Z Y），使得XY， Y Z，YX成立 。 由YZ，按BCNF定义，Y含有码，于是YX成立，这与YX矛盾。 所以R3NF。

54 范式之间的关系 1NF 2NF 3NF BCNF 4NF 消除非主属性对码的部分函数依赖 消除非主属性对码的传递函数依赖
消除主属性对码的部分函数依赖 BCNF 消除非平凡的多值依赖 4NF

55 数据库的逻辑设计 Suppliers（Sname，Saddress，Item，Price） “不好”的关系模式会存在问题 原因
不可表示：插入异常、删除异常 冗余：数据冗余、更新复杂 原因 属性间存在某种数据依赖 范式：对关系的数据依赖程度的要求 怎样找出所有的数据依赖并确定范式和码？ Armstrong公理系统（推理规则） 怎样消除不合适的数据依赖？ 模式分解 分解的无损连接和保持依赖性

56 Armstrong公理、属性集的闭包、函数依赖的推导、候选码的计算、函数依赖集的等价和最小覆盖、
不良的模式设计 不良的数据依赖 范式 范式的判定 模式分解 各种异常 部分函数依赖、传递函数依赖、多值依赖 1NF、2NF、3NF、BCNF、4NF Armstrong公理、属性集的闭包、函数依赖的推导、候选码的计算、函数依赖集的等价和最小覆盖、 模式分解的定义、保持 函数依赖分解和保持无损连接分解的判定和分解算法 良好的模式设计

57 函数依赖的推理规则 如何判断关系模式的范式级别？ 如何求关系模式的候选码？ 问题
给定一组函数依赖，是否能导出另外一些函数依赖，或另外的函数依赖是否成立。 如FD={A  B，B  C}，A  C是否成立？

58 函数依赖的推理规则 逻辑蕴涵 Armstrong公理系统 闭包的计算 候选码的计算 函数依赖的等价和覆盖

59 逻辑蕴涵 定义 关系模式R，F是其函数依赖，X，Y是其属性子集，如果从F的函数依赖能够推出XY，则称F逻辑蕴涵XY，记作F├ XY 被F所逻辑蕴涵的函数依赖的全体所构成的集合称作F的闭包，记作F+ = {XY | F├ XY} 示例 R(X, Y), F = {XY} F+ = {X， XX， XY， XXY， Y， YY XY ，XYX，XYY，XYXY}

60 Armstrong公理系统 推理规则系统 Armstrong公理 正确的、完备的推理规则集 公理、定理、推论（如欧几里德几何）
若X，Y，Z是属性集，则下列规则成立： 自反律(reflexivity)：若Y  X， 则X  Y 增广律(augmentation)：若X  Y ，则XZ  YZ 传递律(transitivity)：若XY，YZ，则XZ 欧几里德几何的五条公理： 1、任意两个点可以通过一条直线连接。 2、任意线段能无限延伸成一条直线。 3、给定任意线段，可以以其一个端点作为圆心，该线段作为半径作一个圆。 4、所有直角都全等。 5、若两条直线都与第三条直线相交，并且在同一边的内角之和小于两个直角，则这两条直线在这一边必定相交。

61 Armstrong公理系统 Armstrong公理的正确性及完备性 A = { f | 可用Armstrong公理从F中导出的函数依赖f}
B = {f | 被F所逻辑蕴涵的函数依赖f} 正确性：用Armstrong公理从F中导出的函数依赖必为F所蕴涵 A  B 完备性：F所蕴涵的函数依赖都能用Armstrong公理从F中导出 B  A

62 按函数依赖定义r是R<U, F>上的任一关系，t，s  r
Armstrong公理系统 关于Armstrong公理正确性 按函数依赖定义r是R<U, F>上的任一关系，t，s  r 自反律：若Y  X， 则X  Y } t[X] = s[X] YX t[Y] = s[Y] X  Y

63 Armstrong公理系统 } 增广律：若X  Y ，则XZ  YZ t[XZ] = s[XZ] t[X] = s[X] XY
t[Y] = s[Y] t[Z] = s[Z] t[YZ] = s[YZ] XZYZ

64 Armstrong公理系统 } 传递律：若XY，YZ，则XZ X  Y t[X] = s[X] t[Y] = s[Y]
t[Z] = s[Z] X  Z

65 Armstrong公理系统 由Armstrong公理导出的推理规则 合并律(union rule) 若X  Y，X  Z，则X  YZ
分解律(decomposition rule) 若X  YZ ，则X  Y，X  Z 伪传递律(pseudotransitivity rule) 若X  Y，WY  Z，则WX  Z

66 Armstrong公理系统 } 合并律：若X  Y，X  Z，则X  YZ X  Y 增广律 X  XY X  Z
XY  YZ 传递律 X  YZ

67 Armstrong公理系统 } 分解律:若X  YZ ，则X  Y，X  Z Y  YZ YZ  Y Z  YZ YZ  Z
自反律 YZ  Y YZ  Z X  YZ 传递律 X  Y X  Z

68 Armstrong公理系统 } 伪传递律:若X  Y，WY  Z，则WX  Z X  Y 增广律 WX  WY WY  Z

69 Armstrong公理系统 示例 R< U, F >, U = (A, B, C, G, H, I),
F = {AB, AC, CGH, CGI, BH} A H？ CG  HI？ AG  I？

70 XA1 A2 Ak成立  XAi成立(i=1, 2,  ,k)
Armstrong公理系统 引理一 XA1 A2 Ak成立  XAi成立(i=1, 2,  ,k) 证明： 由合并律  由分解律  属性集的闭包 为判定X是否为码，需要计算由X所确定的属性集，为此引入属性集的闭包 设F为属性集U上的一组函数依赖，X  U， = {A | XA能由F根据Armstrong公理导出} 称 为属性集X关于函数依赖集F的闭包

71 Armstrong公理系统 示例 属性集U={A，B，C}， 函数依赖集F={A  B，B  C} 则 C+ = C B+ = BC
A+ = ABC

72 XY能由Armstrong公理导出  Y 
引理二 XY能由Armstrong公理导出  Y  Y  对Y中任意属性A，有XA } 引理一 XY 必要性： 若Y  充分性： Y中有属性A  XA不能由F导出 } 引理一 XY也不能由F导出 F逻辑蕴涵XY 矛盾

73 Armstrong公理系统 Armstrong公理完备性的证明 r（ U  ） t 11…1 00…0 s 11…1 11…1
证明：（构造性证明）用反证法 如果XY不能用Armstrong公理系统从F中导出，则 XY不为F所蕴含 由引理二， 构造R(U)上的关系r如下： 下面证明: 1. r满足F; 2. r不满足XY Y  ，Y  ≠ ， U  ≠  r（ U  ） t … …0 s … …1

74 Armstrong公理系统 } （1）r满足F 设VW是F的一个函数依赖，
t[V] = s[V] } X  W X  V V  W V  W  t[W] = s[W]  r满足函数依赖V  W，即r是R<U, F >上的关系

75 Armstrong公理系统 （2）r不满足XY Y ≠  ，所以Y中至少存在一个属性A
在r中有t[X] = s[X]，而t[A] ≠ s[A]， 所以t[Y] ≠ s[Y]，即XY不成立, 所以XY不为F所蕴含

76 闭包的计算 问题：有没有一般性的算法判定XY是否能由F根据Armstrong公理导出？
如果计算出F+，再判断XY是否属于F+，则由于F+的计算非常复杂，实际上是不可行的 由引理二，判定XY是否能由F根据Armstrong公理导出，可转化为求 ，判定Y 是否成立

77 闭包的计算 算法（求属性集的闭包） 算法会终止吗？ Input：X，F Output： := X; while ( 发生变化）do 开始：
for each 函数依赖 AB in F do begin if A  then :=  B end 开始：

78 闭包的计算 示例1 R< U, F >, U = (A, B, C, G, H, I), F = {AB, AC, CGH, CGI, BH},计算 所用依赖 AB AGB AC AGBC CGH AGBCH CGI AGBCHI = AGBCHI

79 闭包的计算 示例2 R< U, F >, U = (A, B, C, D, E), F = {ABC, BD, CE, CEB, ACB},计算 所用依赖 ABC ABC BD ABCD CE ABCDE = ABCDE

80 闭包的计算 示例3 R< U, F >, U = (A, B, C, D, E, G), F = {BEAG, CEA, AE, GD},计算 所用依赖 AE ABE BEAG ABEG GD ABEGD = ABEGD

81 闭包的计算 练习 R< U, F >, U = (C, T, H, R, S), F = {CT, HRC, HTR, HSR}，HR是码吗？HS呢？

82 候选码的计算 “发现一个问题是NP—完全问题，通常只是研究这个问题的开始。”
“······大多数指数级时间算法只是穷举搜索法的变种，而多项式时间算法通常只有在对问题的结构有了某些比较深入的了解之后才有可能给出······。”

83 候选码的计算 定义 定理 左部属性，只出现在F左边的属性 右部属性，只出现在F右边的属性 双部属性，出现在F两边的属性
左部属性一定出现在任何候选码中 右部属性一定不出现在任何候选码中 外部属性一定出现在任何候选码中

84 候选码的计算 U = (C,T,H,R,S) F = {C→T,HR→C,HT→R,HS→R} 给出R的所有候选码
出现在左边的属性：{C,H,T,R,S} 出现在右边的属性：{T,C,R} 左部属性：{HS} 右部属性：{} 双部属性：{T,C,R}

85 候选码的计算 U = {A，B，C，D，E} F = {AE→C,AC→D,CD→B,D→E} 给出R的所有候选码
出现在左边的属性：{A,E,C,D} 出现在右边的属性：{C,D,B,E} 左部属性：{A} 右部属性：{B} 双部属性：{C,D,E}

86 候选码的计算 Key-Finding(求一个候选码) 输入：关系模式<U, F>； 输出：一个候选码K
Begin K:=A1A2…An; For i=1 to n {求K-Ai相对于F的属性闭包(K-Ai)F+; if (K-Ai)F+ =U then K=K-Ai else then K=K; } return K; end.

87 All-Candidate Keys(求全部候选码)
候选码的计算 All-Candidate Keys(求全部候选码) 输入：关系模式R<U，F> 输出： R<U，F>的全部候选码 begin 1求关系模式R < U , F > 的最小函数依赖集F 2 分别计算出UL ,UR , UB  //UL 表示仅在函数依赖集中各依赖关系式左边出现的属性的集合;  //UR 表示仅在函数依赖集中各依赖关系式右边出现的属性的集合; //UB = U - UL - UR） 3 if UL ≠Φ then 计算UL的闭包 if UL+ = U then UL 为R 的唯一的候选码,算法结束. else if UL+≠U then goto 4 else if UL = Φ then goto 5. 4 将UL 依次与UB 中的属性组合, 判断该组合属性是否是候选码;找出所有的 候选码后,算法结束. 5  对UB 中的属性及属性组合依次进行判断;找出所有的候选码后,算法结束. end

88 函数依赖的等价和覆盖 讨论函数依赖集的等价性的目的 在关系上执行更新操作时必须保证不会破坏该关系所属的关系模式上的函数依赖
通过测试与给定函数依赖集有相同闭包的简化集来降低检测的开销

89 函数依赖的等价和覆盖 函数依赖集的等价性 最小覆盖 函数依赖集F，G，若F+= G+，则称F与G等价。
F+ = G+  F  G+，G  F+ 最小覆盖 满足下列条件的函数依赖集F称为最小覆盖，记作Fmin： 单属性化：F中任一函数依赖X  A，A必是单属性 既约化：F中不存在这样的函数依赖XA，在X中有真子集Z，使得F与F\{XA}{ZA}等价 无冗余化：F中不存在这样的函数依赖X  A，使得F与F\{XA}等价

90 函数依赖的等价和覆盖 算法—求解函数依赖集F的最小覆盖Fmin 1.单属性化：逐个检查F中各函数依赖FDi ：XY，
若Y=A1 A2  Ak ，k≥2，则用诸XAi 代替Y 2.既约化：逐个检查F中各函数依赖XA， 设X = B1Bm，逐个考查Bi， 若A  ，则以（X  Bi）取代X 3.无冗余化：逐个检查F中各函数依赖XA， 令G = F{XA}，若 X  A  ，则从F中去 掉该函数依赖

91 函数依赖的等价和覆盖 示例一 F = {AB，BA，AC，BC}，求Fmin
检查AB，G=F{AB}={BA，AC，BC} ={A，C}，B{A，C} 检查AC，G=F{AC}={AB，BA，BC} ={A，B，C}，C{A，B，C} 所以从F中删除AC， Fmin = {AB，BA，BC} 或者 Fmin = {AB，BA，AC}

92 函数依赖的等价和覆盖 示例二 F = {CA，AG，CGB，BA}，求Fmin 判断CGB， = = {G} B
= = {C，A，G，B} B  ，以C代替CG 删除冗余属性 CA 最后，Fmin = {AG，CB，BA}

93 模式分解 模式分解的定义 模式分解中的问题 无损连接分解 保持函数依赖的分解 关系模式的分解算法

94 模式分解的定义 模式分解 函数依赖集合Fi ={ XY | XYF+  XY  Ui}称为F在Ui上的投影
关系模式R<U , F>的一个分解是指  = {R1<U1,F1>, R2<U2 , F2>, … , Rn<Un , Fn>} 其中，U = Ui，并且没有Ui  Uj，1≤i,j≤n， Fi是F在Ui上的投影

95 模式分解的定义 分解的基本代数运算 投影 自然连接 分解的目标 无损连接分解 保持函数依赖 达到更高级范式

96 模式分解中存在的问题 R(A, B, C) ∏AB(R) ∏BC(R) ∏AB(R) ∏BC(R) 无损分解 R(A, B, C)
1 2 A B 1 2 B C 1 2 A B C 1 2 无损分解 R(A, B, C) ∏AB(R) ∏BC(R) ∏AB(R) ∏BC(R) A B C 1 2 A B 1 2 B C 1 2 A B C 1 2 有损分解

97 模式分解中存在的问题 = {A  B, B  C} A B C a1 b1 c1 a2 a3 b2 c2 a4 b3 A a1 a2
违反 B  C 插入

98 模式分解中存在的问题 = = A B C a1 b1 c1 b3 a2 a3 b2 c2 a4 A C a1 c1 a2 a3 c2 a4

99 无损连接分解 保持无损的模式分解 有损分解的例子 R(A, B, C) ∏AB(R) ∏BC(R) ∏AB(R) ∏BC(R) A B C
1 2 A B 1 2 B C 1 2 A B C 1 2

100 无损连接分解 无损连接分解 R(A, B, C) ∏AB(R) ∏BC(R) ∏AB(R) ∏BC(R) 定义（分解为两个关系模式）
关系模式R(U),U1，U2 U，U1 U2 = U，r是R上的一个关系, r1=∏U1(r)，r2=∏U2(r)，若r = r1 r2，则称(r1,r2)是r的一个无损连接分解。 注：r ∏U1(r) ∏U2(r) R(A, B, C) ∏AB(R) ∏BC(R) ∏AB(R) ∏BC(R) A B C 1 2 A B 1 2 B C 1 2 A B C 1 2

101 无损连接分解 定义 已知关系模式R<U,F>，设 ={ R1<U1,F1>,R2<U2,F2>,
…,Rn<Un,Fn>}是R<U,F>的一个分解，其中U = Ui 。 设r是R<U,F>的一个关系，m(r)= ∏Ri(r),若对于R<U,F>的任一个关系r，都有r = m(r)，则称是R<U , F>的一个无损连接分解

102 TB = {Cij | 若Aj  Ui , Cij = aj , 否则Cij = bij}
无损连接分解 算法：（判别一个分解的无损连接性） U={A1, A2, … , An}  = {R1<U1, F1> , R2<U2 , F2>, … , Rk<Uk , Fk>} ⒈建立一个n列k行的矩阵 TB = {Cij | 若Aj  Ui , Cij = aj , 否则Cij = bij} A1 A2 … An U1 Cij Uk

103 无损连接分解 ⒉对F中每一个函数依赖XY，若TB中存在元组t1，t2，使得t1[X]=t2[X]，t1[Y]≠t2[Y]，则对每一个Ai  Y: ①若t1[Ai],t2[Ai]中有一个等于aj,则另一个也 改为aj; ②若①不成立,则取t1[Ai]=t2[Ai]（t2的行号小 于t1）。

104 无损连接分解 ⒊反复执行⒉，直至： ①TB中出现一行为a1, a2 , … , an 的一行。
②TB不再发生变化，且没有一行为a1,… ,an。 4.若情况①发生，则为无损分解，否则为有损分解

105 无损连接分解 示例一：U={A,B,C,D,E}, F={ABC, CD,DE}

106 无损连接分解 示例二：U={A,B,C,D,E}, F={AC, BC, CD,DEC ,CEA}
 ={(A, D), (A, B), (B, E), (C, D, E), (A, E)} AC A B C D E AD a1 b12 b13 a4 b15 AB a2 b23 b24 b25 BE b31 b33 b34 a5 CDE b41 b42 a3 AE b32 b54 A B C D E AD a1 b12 b13 a4 b15 AB a2 b23 b24 b25 BE b31 b33 b34 a5 CDE b41 b42 a3 AE b32 b54 b13 b13

107 无损连接分解 BC CD 示例二：U={A,B,C,D,E}, F={AC, BC, CD,DEC ,CEA}
 ={(A, D), (A, B), (B, E), (C, D, E), (A, E)} BC CD A B C D E AD a1 b12 b13 a4 b15 AB a2 b24 b25 BE b31 b33 b34 a5 CDE b41 b42 a3 AE b32 b54 A B C D E AD a1 b12 b13 a4 b15 AB a2 b24 b25 BE b31 b34 a5 CDE b41 b42 a3 AE b32 b54 a4 b13 a4 a4

108 无损连接分解 DEC CEA 示例二：U={A,B,C,D,E}, F={AC, BC, CD,DEC ,CEA}
 ={(A, D), (A, B), (B, E), (C, D, E), (A, E)} DEC CEA A B C D E AD a1 b12 b13 a4 b15 AB a2 b25 BE b31 a5 CDE b41 b42 a3 AE b32 A B C D E AD a1 b12 b13 a4 b15 AB a2 b25 BE b31 a3 a5 CDE b41 b42 AE b32 a3 a1 a1 a3

109 无损连接分解 定理 关系模式R(U)的分解={R1，R2}，则是一个无损连接分解的充要条件是 R1∩R2R1R2（或R1∩R2R2R1）成立 R1∩R2 R1R2 R2R1 R1 a…a b…b R2 R1∩R2R1R2 R1∩R2 R1R2 R2R1 R1 a…a b…b R2

110 无损连接分解 R=ABC, F={A  B}, 1={R1(AB), R2(AC)}
R1∩R2 = A, R1－R2 = B, R2－R1 = C 由A  B ，得到1是无损连接分解 2={R1(AB), R2(BC)} R1∩R2 = B, R1－R2 = A, R2－R1 = C BA, BC均不成立，所以1不是无损连接分解

111 模式分解中的问题 实例1 表（职工，级别，工资）可以有两种分解途径， 分解一：（职工，工资），（工资，级别）
分解二：（职工，级别），（工资，级别） 不同行业机构的不同工资级别会有相同工资数额，因此按分解一，有可能导致同一职工对应不同的工资级别，从而丢失了有关职工工资级别的信息（丢失了函数依赖：职工级别） 姓名 级别 工资 ZHAO 4 500 QIAN 5 600 SUN 6 700 LI 7 姓名 工资 ZHAO 500 QIAN 600 SUN 700 LI 级别 工资 4 500 5 600 6 700 7 丢失函 数依赖

112 ∏Z(F) = {XY | XYF+  XY  Z}
保持函数依赖的分解 保持函数依赖的模式分解 Z是U的子集，函数依赖集合F在Z上的投影定义为 ∏Z(F) = {XY | XYF+  XY  Z} 设 = {R1, R2, …, Rn}是关系模式R<U, F>的一个分解，如果F+ = ( ∏Ri(F))+，则称是保持函数依赖的分解

113 保持函数依赖的分解 关系模式R<U, F> U = {CITY, ST, ZIP},
F = {(CITY, ST)  ZIP, ZIP  CITY}  = {R1 = {ST, ZIP}, R2 = {CITY, ZIP}} R1∩R2 ={ZIP}, R2－R1 ={CITY} ∵ R1∩R2  R2－R ∴分解是无损的 ∏R1(F) = {}， ∏R2(F) = {ZIP  CITY} ∏R1(F) ∪ ∏R2(F) = {ZIP  CITY} 丢失了函数依赖(CITY, ST)  ZIP

114 保持函数依赖的分解 违反了函数依赖(CITY, ST)  ZIP ST ZIP Haidian 100862 100971 ZIP
Beijing 100971 CITY ST ZIP Beijing Haidian 100862 100971 违反了函数依赖(CITY, ST)  ZIP

115 保持函数依赖的分解 如何判断分解保持函数依赖？ 回忆： F+ = ( Fi)+  F  ( Fi )+ 且 Fi  F+
如对于{ABC，{AB , BC}}的分解 {<AB, {AB}>，<AC, {AC}>} 思考：BC{AB， AC}+ ? 检验：C ？

116 练习 设关系模式R(ABCD)，在R上有两个相应的函数依赖集及分解：F =｛A→B，B→C, C→D｝，ρ=｛AB，ACD｝回答下列问题
ρ是否无损分解； ρ是否保持函数依赖； 确定ρ中每一模式的范式级别

117 练习 设关系模式R(ABCD)，在R上有两个相应的函数依赖集及分解：F =｛A→B，B→C, C→D｝,ρ=｛AB,AD,CD｝回答下列问题
ρ是否无损分解； ρ是否保持函数依赖； 确定ρ中每一模式的范式级别

118 关系模式的分解算法 算法：（达到BCNF无损连接分解算法） 给定关系模式R<U , F> ，
⒊设 中Ri<Ui , Fi>不属于BCNF， 则存在函数依赖XA ，且X不是Ri的码， 则XA是Ri的真子集，将Ri分解为={S1，S1}， 其中US1 = XA， US2 = Ui  {A} 以代替Ri ，返回到⒉

119 关系模式的分解算法 示例： U={S#，SD，MN，C#，G} F={S#SD，S#MN，SDMN，(S#,C#)G}
⒈U1={S#，SD} , F1={S#SD} U2={S#, MN, C#, G}, F2={S#MN, (S#,C#)G} ⒉U1 = {S#, SD}, F1={S#SD} U2 = {S#, MN}, F2={S#MN} U3 = {S#, C#, G}, F3 = {(S#,C#)G}

120 关系模式的分解算法 算法：（达到4NF无损连接分解算法） ⒈令 = {R<U , F>}
⒊设 中Ri<Ui , Fi>不属于4NF， 则存在非平凡多值依赖XA，X不是Ri的码， 则XA是Ri的真子集，将Ri分解为={S1，S1}， 其中US1 = XA， US2 = Ui  {A} 以代替Ri ，返回到⒉

121 关系模式的分解算法 示例 F={ABCG，BAC，CG} ⒈ U1={A，E，D} U2={A，B，C，G} ,
U={A，B，C，D，E，G} F={ABCG，BAC，CG} ⒈ U1={A，E，D} U2={A，B，C，G} , F2={ABCG，BAC，CG} ⒉ U1={A，E，D} U2={C，G} , F2={CG} U3={A，B，C}, F3={BAC}

122 关系模式的分解算法 示例 F={(S#，C#)T#, T#C#} 不属于BCNF，分解为 U1=(S#，T#)，
U=(S#，T#，C#)， F={(S#，C#)T#, T#C#} 不属于BCNF，分解为 U1=(S#，T#)， U2=(T#，C#)，F2={T#C#} 丢失了函数依赖(S#，C#)T#，原来一个学生选修一门课程时，只能对应一个老师；在新的关系模式下现在一个学生选修一门课程时，可能会对应多个老师。

123 关系模式的分解算法 结论：若要求分解保持函数依赖，那么分解后的模式总可以达到3NF，但不一定能达到BCNF
⒈求F的最小覆盖FC ⒉找出不在FC中出现的属性，将它们构成一个关系模式，并从U中去掉它们(剩余属性仍记为U) ⒊若有XA FC ，且XA=U，则={R}，算法终止

124 关系模式的分解算法 ⒋对FC按具有相同左部的原则进行分组（设为k组），每一组函数依赖所涉及的属性全体为Ui，令Fi为FC在Ui上的投影，则 = {R1<U1 ,F1> ,… , Rk<Uk , Fk>}是R<U , F>的一个保持函数依赖的分解，并且每个Ri<Ui , Fi> 3NF

125 关系模式的分解算法 示例 U={S#，SD，MN，C#，G} F={S#SD，S#MN，SDMN，(S#,C#)G}
⒈FC={S#SD，SDMN ，(S#,C#)G} ⒉分组 {(S#，SD)，S#SD} {(SD，MN)，SDMN} {(S#，C#，G)， (S#,C#)G}

126 关系模式的分解算法 示例：R（ABC；AC，BC） ⒈按保持无损连接分解 码为AB，分解为{AC；AC}，{AB}。
⒉按保持函数依赖分解 进行分组，{AC；AC}，{BC；BC} 分解是有损的 A B C 1 2 A B C 1 2 A C 1 2 B C 1 2

127 关系模式的分解算法 算法：（达到3NF且同时保持无损连接与函数依赖的分解）
设 = {R1<U1 , F1> , … , Rk<Uk , Fk>}是R<U , F>的一个保持函数依赖的3NF分解 设X为R<U , F>的码， 若有某个Ui，X  Ui，则即为所求， 否则令τ = ∪{R <X，FX>}，τ即为所求

128 The Pet Store: Sales Form
Sales(SaleID, Date, CustomerID, Name, Address, City, State, Zip, EmployeeID, Name, (AnimalID, Name, Category, Breed, DateOfBirth, Gender, Registration, Color, ListPrice, SalePrice), (ItemID, Description, Category, ListPrice, SalePrice, Quantity))

129 The Pet Store: Purchase Animals
AnimalOrder(OrderID, OrderDate, ReceiveDate, SupplierID, Name, Contact, Phone, Address, City, State, Zip, EmployeeID, Name, Phone, DateHired, (AnimalID, Name, Category, Breed, Gender, Registration, Cost), ShippingCost)

130 The Pet Store: Purchase Merchandise
MerchandiseOrder(PONumber, OrderDate, ReceiveDate, SupplierID, Name, Contact, Phone, Address, City, State, Zip, EmployeeID, Name, HomePhone, (ItemID, Description, Category, Price, Quantity, QuantityOnHand), ShippingCost)

131 Pet Store Normalization
Sale(SaleID, Date, CustomerID, EmployeeID) SaleAnimal(SaleID, AnimalID, SalePrice) SaleItem(SaleID, ItemID, SalePrice, Quantity) Customer(CustomerID, Name, Address, City, State, Zip) Employee(EmployeeID, Name) Animal(AnimalID, Name, Category, Breed, DateOfBirth, Gender, Registration, Color, ListPrice) Merchandise(ItemID, Description, Category, ListPrice) AnimalOrder(OrderID, OrderDate, ReceiveDate, SupplierID, EmpID, ShipCost) AnimalOrderItem(OrderID, AnimalID, Cost) Supplier(SupplierID, Name, Contact, Phone, Address, City, State, Zip) Employee(EmployeeID, Name, Phone, DateHired) Animal(AnimalID, Name, Category, Breed, Gender, Registration, Cost) MerchandiseOrder(PONumber, OrderDate, ReceiveDate, SID, EmpID, ShipCost) MerchandiseOrderItem(PONumber, ItemID, Quantity, Cost) Supplier(SupplierID, Name, Contact, Phone, Address, City, State, Zip) Employee(EmployeeID, Name, Phone) Merchandise(ItemID, Description, Category, QuantityOnHand)

132 Pet Store View Integration
Sale(SaleID, Date, CustomerID, EmployeeID) SaleAnimal(SaleID, AnimalID, SalePrice) SaleItem(SaleID, ItemID, SalePrice, Quantity) Customer(CustomerID, Name, Address, City, State, Zip) Employee(EmployeeID, Name, Phone, DateHired) Animal(AnimalID, Name, Category, Breed, DateOfBirth, Gender, Registration, Color, ListPrice, Cost) Merchandise(ItemID, Description, Category, ListPrice, QuantityOnHand) AnimalOrder(OrderID, OrderDate, ReceiveDate, SupplierID, EmpID, ShipCost) AnimalOrderItem(OrderID, AnimalID, Cost) Supplier(SupplierID, Name, Contact, Phone, Address, City, State, Zip) Animal(AnimalID, Name, Category, Breed, Gender, Registration, Cost) MerchandiseOrder(PONumber, OrderDate, ReceiveDate, SID, EmpID, ShipCost) MerchandiseOrderItem(PONumber, ItemID, Quantity, Cost) Employee(EmployeeID, Name, Phone) Merchandise(ItemID, Description, Category, QuantityOnHand)

133 Pet Store Class Diagram

134 本章总结 主要内容 学生应掌握的内容 关系模式的设计问题 函数依赖 范式 函数依赖的推理规则 模式分解
信息的冗余和信息的不可表示 函数依赖 完全函数依赖，部分函数依赖，传递函数依赖 范式 4NF  BCNF  3NF  2NF  1NF 函数依赖的推理规则 正确性，完备性 模式分解 分解的无损连接性和保持依赖性，分解算法 学生应掌握的内容 如何进行数据库的逻辑设计，怎样找出所有的数据依赖并确定范式和码？怎样消除不合适的数据依赖？