1、掌握为什么不合适的关系模式会带来插入异常、删除异常、 存储异常、修改困难等严重问题 2、深刻理解函数依赖、多值依赖等有关概念

Presentation on theme: "1、掌握为什么不合适的关系模式会带来插入异常、删除异常、 存储异常、修改困难等严重问题 2、深刻理解函数依赖、多值依赖等有关概念"— Presentation transcript:

1 1、掌握为什么不合适的关系模式会带来插入异常、删除异常、 存储异常、修改困难等严重问题 2、深刻理解函数依赖、多值依赖等有关概念
本章要求： 1、掌握为什么不合适的关系模式会带来插入异常、删除异常、 存储异常、修改困难等严重问题 2、深刻理解函数依赖、多值依赖等有关概念 3、掌握关系的1NF、2NF、3NF、BCNF、4NF的概念和特征 4、掌握函数依赖的Armstrong公理系统、求属性集的闭包算法 以及求极小函数依赖集的方法等 5、掌握模式分解的无损连接性和保持函数依赖性以及分解算法 本章内容： §1 为什么需要对关系模式规范化？ 请选择内容 §2 数据依赖 §3 关系的范式 §4 函数依赖的Armstrong公理系统 返回 §5 关系模式的分解 2018/11/19 数据库系统

2 一个基本的问题：给出一组数据，如何构造一个合适的数据模式？
§1 问题的提出 一个基本的问题：给出一组数据，如何构造一个合适的数据模式？ 例如：对关系模型，给了一组数据，应该构造几个关系？每个关系由哪些属性组成？…… 这就是数据库逻辑设计问题 网状、层次模型的数据库设计，主要凭设计者的经验直观地选择和确定实体集、属性以及实体间的联系。哪些实体应该合并或分解以及如何合并和分解、每个实体中应该包括哪些属性为宜、属性间的联系如何确定和处理等一系列问题的解决是没有什么固定规则和理论可循的。 2018/11/19 数据库系统

3 关系数据库的设计是借助近代数学工具而提出来的，形成了一整套定义、公理、定理及各种实用算法，产生了确定、评价关系数据库模式的好方法。
关系数据库的规范化理论 ——数据库逻辑设计的有力工具 这就是本章的主题 要考虑的几个问题：  为什么要规范化？  怎样规范化？  规范化到什么程度后最合适？ 本节首先用一个例子来说明对关系模式为什么要规范化， 不经过规范化会产生什么样的结果。 2018/11/19 数据库系统

4 例：假设车间考核职工完成生产定额的关系模式如下： W（工号，日期，姓名，工种，定额，超额，车间，车间主任）
比如设某工号某年月超额完成定额的20%，其记录的内容为： （1001，98年11月，张三，车工，180，20%，金工车间，李四） 该关系的主键为？ 工号  日期 该关系模式存在以下四个严重问题： （1）数据冗余大 对同一个人来说，其姓名、工种、车间、车间主任等多次重复 …… …… 1001，98年08月，张三，车工，，，金工车间，李四 1001，98年09月，张三，车工，，，金工车间，李四 1001，98年10月，张三，车工，，，金工车间，李四 1001，98年11月，张三，车工，，，金工车间，李四 2018/11/19 数据库系统

5 （1005，NULL，天然，车工，NULL，NULL，金工车间，李四）
（2）插入异常 应该存储的信息无法存储 若新调来一个职工并将他分配到某个车间，根据上述关系模式，在对该职工统计工作之前，他的信息是装不进数据库中的。因为他的日期值是空值，而日期是主键的属性之一，不允许为空。 （1005，NULL，天然，车工，NULL，NULL，金工车间，李四） （3）删除异常 不该删除的信息被删除 若想删除某人的所有定额完成情况，则该职工的其他信息也都被删除。 比如在98年底要删除97年以前的所有定额完成信息，则98年由于种种原因未参加现实工作的职工的所有信息全部被删除。 2018/11/19 数据库系统

6 若某车间换了主任，则该车间所有职工的上述记录都要修改； 又如某人换了车间，则其工种、车间、车间主任等信息都要修改。
（4）修改困难，容易造成数据的不一致性 （也称更新异常） 若某车间换了主任，则该车间所有职工的上述记录都要修改； 又如某人换了车间，则其工种、车间、车间主任等信息都要修改。 修改工作量大； 即使漏改一处都会造成数据的不一致性； 上例充分说明对关系模式若随意设计，其后果是严重的。 本章将要讨论产生上述问题的原因以及解决办法，即如何改造一个不好的关系模式。这就是规范化理论要解决的主要问题。 2018/11/19 数据库系统

7 原因何在？规律何在？ 比如，对于上述关系模式，若分解成下面三个关系，则前面提到的几个问题将全部或部分地得到解决：
职工关系（工号，姓名，工种，车间号） 车间关系（车间号，车间名，车间主任） 定额关系（工号，日期，定额，超额，车间号） 原因何在？规律何在？ 本节开头 本章开头 下一节 2018/11/19 数据库系统

8 数据模型中我们讨论了实体间的联系，同时提到实体内部属性间也有联系。事实上上一节中的问题都是由于属性间的联系引起的。
§2 数据依赖 数据模型中我们讨论了实体间的联系，同时提到实体内部属性间也有联系。事实上上一节中的问题都是由于属性间的联系引起的。 一、数据依赖 1、属性间的联系： 也是1:1，1:n，m:n三种  1:1联系：设A、B为某实体集中的两个属性的值集，如 果对于A中的任一值，B中至多有一个值与之 对应，且反之亦然。 如：车间--主任  1:n联系：设A、B为某实体集中的两个属性的值集，如 果对于A中的任一值，B中有多个值（包括0个） 与之对应；而对于B中的任一值，A中至多有 一个值与之对应。 如：队长--学号 2018/11/19 数据库系统

9  m:n联系：设A、B为某实体集中的两个属性的值集， 如果对于A中的任一值，B中有多个值（包 括0个）与之对应，且反之亦然。
如：学号--课程号 实体间的联系表示实体之间相互依赖又相互制约的关系； 属性间的联系表示属性之间相互依赖又相互制约的关系。 2、数据依赖 通过一个关系中属性间值的相互关联（主要体现于值的相等与否）体现出来的数据间的相互联系。 （是数据内在的性质，语义的体现） 函数依赖 两类最重要的数据依赖 多值依赖 2018/11/19 数据库系统

10 对关系模式 R<U, F>，当且仅当U上的一个关系r满足F时，称r为关系模式 R<U, F>的一个关系。
二、关系的形式化定义 1、关系的两个主要方面 语法：属性的描述 语义：数据依赖 2、关系模式： R <U，D，dom，F> 关系名 属性组 U上的一组数据依赖 3、关系： 对关系模式 R<U, F>，当且仅当U上的一个关系r满足F时，称r为关系模式 R<U, F>的一个关系。 2018/11/19 数据库系统

11 不严格地讲，函数依赖指的是一组属性值唯一决定另一组属性值的这种数据依赖。
三、函数依赖 不严格地讲，函数依赖指的是一组属性值唯一决定另一组属性值的这种数据依赖。 如学生关系中，当学号确定后，其姓名也就唯一确定了。 选课关系中，当学号和课程号确定后，其成绩也就唯一确定了。 1、函数依赖（Functional Dependency，缩写FD）： 设 R(U)是属性集U上的关系模式，X、Y是U的子集。若对于R中的任意关系 r，对于 r中的任意两个元组u、v都有 u[X]=v[X]  u[Y]=v[Y] 成立，则称X函数决定Y，或称Y函数依赖于X，记作XY。称X为决定因素。 2018/11/19 数据库系统

12 例：对学生关系 S（S#，SN，SD，SA），有 S# SN， S# SD， S# SA
对选课关系 SC（S#，C#，G），有（S#，C# ） G 说明：  函数依赖类似于变量间的单值函数关系（一个自变量只能对应一个 函数值），因此也称为单值函数依赖；  若XY且YX ，则记作 XY；  若Y不函数依赖于X，则记作 X Y 函数依赖是指关系模式R的任一关系都要满足的约束条件 2018/11/19 数据库系统

13 （1）若X、Y之间是“1:1联系”, 则存在函数依赖XY和 YX, 即XY.
2、函数依赖与属性间的联系之关系 （1）若X、Y之间是“1:1联系”, 则存在函数依赖XY和 YX, 即XY. （2）若X、Y之间是“m:1联系”, 则存在函数依赖关系XY。 （3）若X、Y之间是“m:n联系”, 则X、Y之间不存在函数 依赖关系。 3、函数依赖分类 （1）非平凡的函数依赖： XY，但Y X。 （2）平凡的函数依赖： XY，但Y  X。 （3）完全函数依赖：XY，且对任意的X’ X，都有 记作 X Y f Y。 X’ 如在 SC（S#，C#，G）中，（S#，C#） G， G， C# G，因此（S#，C#） f G。 但S# 2018/11/19 数据库系统

14 （4）部分函数依赖： XY，但Y不完全函数依赖于X。
p 如在 S（S#，SN，SD，SA）中，因为 S#SD， （S#，SN） SD p 所以 （5）传递函数依赖：若XY，Y X，YZ， 且Z（XY）= ，则称Z对X是传递函数依赖。 例如，在学生关系模式 S（S#，SN，SD，SA）中，增加属性SL（系的位置），则 S#SD，SDSL，SD S#，所以 S# SL。 传递 2018/11/19 数据库系统

15 1、例子：设学校中一门课由多位教员讲授，他们使用相同 的参考书，比如： “物理”，教员为汪洋、大海，参考书为《普通物理学》、 《光学原理》、
四、多值依赖 （教材P178） 1、例子：设学校中一门课由多位教员讲授，他们使用相同 的参考书，比如： “物理”，教员为汪洋、大海，参考书为《普通物理学》、 《光学原理》、 《物理习题集》； “数学”，教员为大海、白云，参考书为《数学分析》、 《微分方程》、 《高等代数》； “计算”，教员为蓝天、白云，参考书为《数学分析》、 …… …… 2018/11/19 数据库系统

16 用模式为 TEACH（C，T，B）的关系表示上述数据：
该关系模式中，任何两个属性都不能函数决定第三个属性。 物理 汪洋 普通物理学 物理 汪洋 光学原理 物理 汪洋 物理习题集 物理 大海 普通物理学 物理 大海 光学原理 物理 大海 物理习题集 数学 大海 数学分析 数学 大海 微分方程 数学 大海 高等代数 数学 白云 数学分析 数学 白云 微分方程 数学 白云 高等代数 计算 白云 数学分析 …… …… …… 该关系模式存在 冗余大、增删不方便 等问题。 没有函数依赖， 需要另行分析 2018/11/19 数据库系统

17 课程C 教员T 参考书B 在该关系模式中，对于一个（物理，普通物理学），有一组教员{汪洋，大海}，而对于另一个（物理，光学原理），对应的教员仍是{汪洋，大海}。因此，所对应的教员只与课程的值有关而与参考书的值无关。 物理 汪洋 普通物理学 物理 汪洋 光学原理 物理 汪洋 物理习题集 物理 大海 普通物理学 物理 大海 光学原理 物理 大海 物理习题集 数学 大海 数学分析 数学 大海 微分方程 数学 大海 高等代数 数学 白云 数学分析 数学 白云 微分方程 数学 白云 高等代数 计算 白云 数学分析 …… …… …… 这是产生问题的原因吗？ 2018/11/19 数据库系统

18 2、多值依赖（MultiValued Dependency，缩写为MVD）
设 R(U)是属性集U上的关系模式，X、Y、Z是U的子集，且Z=UXY，多值依赖XY成立当且仅当对R(U)的任一关系r，任给的一对（x，z）值有一组Y的值，这组值仅仅取决于x值而与z值无关。 称X多值决定Y或Y多值依赖于X。 课程C 教员T 参考书B 物理 汪洋 普通物理学 物理 汪洋 光学原理 物理 汪洋 物理习题集 物理 大海 普通物理学 物理 大海 光学原理 物理 大海 物理习题集 数学 大海 数学分析 数学 大海 微分方程 数学 大海 高等代数 数学 白云 数学分析 计算 白云 数学分析 …… …… …… 例如，在关系模式TEACH中 有 CT 直观上看，若XY， 则X的一个值唯一决定一组 Y值，且这组值与X、Y之外 的属性值无关 2018/11/19 数据库系统

19 交换s、t的Y值 所得新元组仍在r中 s[Y] s[Z] t[Y] t[Z] w[Y] w[Z] v[Y] v[Z]
多值依赖的另一等价定义： 多值依赖XY成立当且仅当对R(U)的任一关系r，若存在元组s、t使得s[X]=t[X]，则必存在元组w、vr（w、v可以与s、t相同），使得w[X]=v[X]=t[X]，而w[Y]=t[Y]，w[Z]=s[Z]，v[Y]=s[Y]，v[Z]=t[Z]。 X Y Z s 交换s、t的Y值 所得新元组仍在r中 s[Y] s[Z] t t[Y] t[Z] 左图直观显示， x决定一组y值， 这组值与z无关 w w[Y] w[Z] v v[Y] v[Z] 2018/11/19 数据库系统

20 汪洋 大海 物理 普通物理学 光学原理 物理习题集 大海 白云 完全二分图 数学 数学分析 微分方程 高等代数
由前面例子，可看出X、Y、Z之间有下述关系： 汪洋 大海 物理 普通物理学 光学原理 物理习题集 大海 白云 完全二分图 数学 数学分析 微分方程 高等代数 2018/11/19 数据库系统

21 （1）对称性：若 XY， Z=UXY，则 XZ。 （2）函数依赖可看成是多值依赖的特例：若 XY，则 XY
3、多值依赖的性质： （1）对称性：若 XY， Z=UXY，则 XZ。 （2）函数依赖可看成是多值依赖的特例：若 XY，则 XY （3）若U=XY（表示X  Y），则 XY显然成立。 （这种多值依赖无任何实际意义，故称为 平凡的多值依赖 ） 4、多值依赖与函数依赖的区别 （1）函数依赖XY的有效性仅取决于X、Y，与X、Y之外的属性无关： XY在 （R）上成立 XY在 （R）上成立 XY W 其中W满足 XY  W  U（U是关系模式R的属性集）。 X Y Z R（U）： X是否函数决定Y 与这一部分属性无关 W 2018/11/19 数据库系统

22 多值依赖XY的有效性与X、Y之外的属性范围有关： 若XY在U上成立，则在W（ XY  W  U）上也成立， 但反之不然。
可缩小范围但不一定能扩大范围 X Y Z R（U）： X是否多值决定Y 与这一部分属性密切相关 W XY在U上成立 X Y R（W）： 反之 不成立 XY在W上也成立 W 2018/11/19 数据库系统

23 例如，在前面的例子中，若增加属性“教室”（R），则在
XY在W上成立， 不一定有 XY在U上也成立 例如，在前面的例子中，若增加属性“教室”（R），则在 {C，T，B，R}上CT不再成立。因为若汪洋在一号教室上物理课，大海在二号教室上物理课，关系中会有下述两个元组： C T R 物理 汪洋 普通物理学 一号教室 …… …… 物理 大海 普通物理学 二号教室 但交换汪洋和大海 后的两个元组不存在 W （2）对函数依赖，若XY，则对Y的任意子集Y’，都有XY’ 对多值依赖，没有上述性质。 XY成立 即 不能保证 XY’成立 2018/11/19 数据库系统

24 从函数依赖的角度给关键字一个形式化的定义。 比以前的直观定义 准确、严谨 1、候选关键字和主关键字：
例： 在U上C {T，R}， 但C T不成立，因 为交换汪洋和大海后 的两个元组不存在 C T R 物理 汪洋 普通物理学 一号教室 …… …… 物理 大海 普通物理学 二号教室 五、关键字 从函数依赖的角度给关键字一个形式化的定义。 比以前的直观定义 准确、严谨 1、候选关键字和主关键字： 设K是R<U, F>中的属性或属性组合， 若 K U，则称K为U的候选关键字（候选码）； f 若候选关键字多于一个，则选定其中的一个作为主关键字（主键、主码）。 2018/11/19 数据库系统

25 例：借书证关系 C（CARD#，S#，SN，SD） CARD#、S#都是候选关键字 通常选择CARD#作为主键  K能唯一确定 一个元组
2、外键（外部码） 若R<U, F>中的属性或属性组合X不是R的关键字，但X是另一个关系的关键字，则称X是R的外键。 主键与外键提供了一个表示关系间联系的手段 3、全键（All-key，全码） 若R<U, F>的整个属性组是关键字，即U U，则称U是全键。 f 2018/11/19 数据库系统

26 一般来讲，全键是没有什么实际意义的。主键包含的属性应尽可能少为好。 演奏者 作品 听众
例：关系模式 R（P，W，A） 注意： 一般来讲，全键是没有什么实际意义的。主键包含的属性应尽可能少为好。 演奏者 作品 听众 （P，W，A）是R的全键。 4、主属性和非主属性 主属性： 包含在某个候选关键字中的属性 非主属性：不包含在任何侯选关键字中的属性 例：SC（S#，C#，G）中， （S#，C#）是关键字，故S#，C#是主属性 G不包含在任何关键字中 ，故G是非主属性。 2018/11/19 数据库系统

27  如何根据关系模式属性间的数据依赖情况来判断它是否具有某些不合适的性质？  如何将具有不合适性质的关系模式转换为更合适的形式？
§3 关系的范式 本节讨论下述问题：  如何根据关系模式属性间的数据依赖情况来判断它是否具有某些不合适的性质？  如何将具有不合适性质的关系模式转换为更合适的形式？ 一、规范化 1、范式（Normal Form） 按关系模式所具有的数据依赖性质对关系模式的分类。也就是关系的规范化程度。 满足不同程度要求的为不同范式。 2、规范化 把一个低一级范式的关系模式通过模式分解转化为若干个高一级的关系模式的过程。 2018/11/19 数据库系统

28 1、定义：关系的每个分量必须是不可再分的数据项。 记作R1NF。（每个属性必须是原子的） 2、说明：
 属性不可再分（不允许出现嵌套的属性定义） 这两个表 都可变为 规范关系  属性下的值不可再分（不允许出现多个值）  这是对关系的最起码的要求，但远远不够。 （满足1NF的关系称为规范关系） 例：借书表 例：职工情况表 借书人 所借书名 借书日期 张三 B1 B2 B3 D1 D2 D3 李四 B5 职工 号 部门 …… 工 资 基本工资 奖金 2018/11/19 数据库系统

29 3、仅属于1NF的关系模式可能会产生的问题： 例：车间考核职工完成生产定额的关系模式：
W（工号，日期，姓名，工种，定额，超额，车间，车间主任） 主属性 非主属性 显然W 1NF，但第一节中我们已讨论知它有 四个严重问题 四个严重问题 因此仅是第一范式的关系模式完全不能满足需要。 分析出现问题的原因： 数据冗余 插入异常 删除异常 修改困难 工号函数决定非主属性姓名、工种、车间、车间主任。因此，关键字（工号，日期）部分函数决定这些属性。 这显然是产生冗余的一个主要原因。 三、第二范式（2NF） 1、定义：若 R1NF，且每一非主属性都完全函数依赖于R的 码，则称R是第二范式，记作R 2NF。 2018/11/19 数据库系统

30 对关系模式S_L_C,同样存在数据冗余大、插入异常、 删除异常、修改困难等问题。（产生问题的原因同W）
2、属于1NF但不属于2NF的例子：  关系模式W（工号，日期，姓名，工种，定额，超额，车间，车间主任）  关系模式S_L_C（S#，SD，SL，C#，G） 学生宿舍楼，且每个系学生只住一栋楼 关键字：（S#，C#） 函数依赖： （S#，C#） G f S# SD 完全 S# SD，SD SL， G 传递 S# SL （S#，C#） SD （S#，C#） SL C# 部分 SL p p 关键字 对关系模式S_L_C,同样存在数据冗余大、插入异常、 删除异常、修改困难等问题。（产生问题的原因同W） 2018/11/19 数据库系统

31 ? 3、解决办法：用投影分解 消除非主属性对关键字的部分函数依赖转换为2NF G S# C# G SD SL S# C# 关键字 部分 SC
分解之后，与S_L_C相比， SC和S_L性质如何? ? 2018/11/19 数据库系统

32 分解前 S_L_C（S#，SD，SL，C#，G）
分解后 SC（S#，C#，G） S_L（S#，SD，SL） 分解之后，与S_L_C相比：  数据冗余减小 （原来伴随学生所学的每门课都要存储一遍SD、SL的值）；  没选课的学生信息可以存储；  删除选课记录不会误删学生其他信息；  冗余数据的减少使得修改变得容易些。 S_L还有问题吗? 1NF的上述四个问题得到了部分解决 2018/11/19 数据库系统

33 若一个系刚成立但尚无学生，该系名称等无法存储
4、仅属于2NF的关系模式可能会产生的问题 S_L（S#，SD，SL） （1）数据冗余 数据冗余仍然较大：SL的值重复严重 （2）插入异常 若一个系刚成立但尚无学生，该系名称等无法存储 （3）删除异常 若一个系的学生全部毕业，删除全部学生数据的同时把该系的数据（如系名等）也都删除了 （4）修改困难 可能的原因： 存在传递函数依赖 S#SL 数据冗余大势必造成修改困难 （这可以说是个必然联系） 2018/11/19 数据库系统

34 若R3NF ， 则R中不存在码X、属性组Y和非主属性Z（Z  Y）使得X→Y（ Y → X），Y → Z成立
1、定义；若关系模式 R<U, F>1NF，并且R中不存在码X、属性组Y和非主属性Z（Z  Y）使得X→Y（ Y → X），Y → Z成立，则称 R3NF。 2、定理：若 R3NF，则 R2NF。 分析 要证R2NF R的每一非主属性都完全函数依赖于码 不存在任何非主属性部分函数依赖于码 希望推出 由3NF的定义， 若R3NF ， 则R中不存在码X、属性组Y和非主属性Z（Z  Y）使得X→Y（ Y → X），Y → Z成立 只需证：若存在非主属性部分函数依赖于码 R3NF 2018/11/19 数据库系统

35 四、第三范式（3NF） 1、定义；若关系模式 R<U, F>1NF，并且R中不存在码X、属性组Y和非主属性Z（Z  Y）使得X→Y（ Y → X），Y → Z成立，则称 R3NF。 2、定理：若 R3NF，则 R2NF。 只需证：若存在非主属性部分函数依赖于码 R3NF 设A是R的一个非主属性，K是R的码，且 K p A 证明 则存在 K’ K，使得K’A。故有 K K’ ，K’A。 因为一个候选关键字不可能函数依赖于它的真子集， 所以有 K’ K. 又因为A是非主属性，K是码，且K’ K，故 A  K’。 证毕！ 所以R  3NF。 要找Y，满足 KY，Y K，YA 2018/11/19 数据库系统

36 若 R2NF，并且R中不存在任何非主属性传递函数依 赖于R的码，则称R3NF。
3、说明  根据以上证明，也可这样定义3NF： 若 R2NF，并且R中不存在任何非主属性传递函数依 赖于R的码，则称R3NF。  若R<U, F>中U是全键，则一定有 R3NF。 4、属于2NF但不属于3NF的例子：  关系模式S_L（S#，SD，SL） SD SL S# 传递 5、解决办法：用投影分解 消除非主属性对关键字的传递函数依赖，转换为3NF 如将S_L分解为: S_D（S#，SD） D_L（SD，SL） SD SL S# SD 2018/11/19 数据库系统

37 由上可知，部分函数依赖和传递函数依赖是产生异常的两个重要原因。
6、仅属于3NF的关系模式可能会产生的问题 由上可知，部分函数依赖和传递函数依赖是产生异常的两个重要原因。 3NF中不存在非主属性对于关键字的部分函数依赖和传递函数依赖，因此具有较好的性质。 通常设计关系模式时至少应该是属于3NF的。 虽说3NF是广泛使用的一种关系范式，但3NF仍然存在某些“异常”。 每个教师只教一门课，每门课有若干教师，学生选定某门课就对应固定的教师。 例：关系模式 R（S，T，J） 学生 教师 课程 2018/11/19 数据库系统

38 问题 S T J 例：关系模式 R（S，T，J） 学生1 教师1 课程1 …… 函数依赖：（S，J） T; 学生K 教师1 课程1
学生1 教师1 课程1 …… 学生K 教师1 课程1 学生L 教师2 课程1 学生M 教师2 课程1 学生1 教师3 课程2 学生K 教师3 课程2 函数依赖：（S，J） T; （S，T） J；T J 候选关键字：（S，J）；（S，T） R中无非主属性，显然R3NF。 问题 J 重复，产生冗余， 带来可能的不一致性等问题 因为这是关键字 可能的原因： R中存在部分函数依赖 （S，T）  J。 也是传递函数依赖 （S，T） 2018/11/19 数据库系统

39 唉，还是有问题！ 由例子可以看出，虽然3NF消除了一大类 数据冗余问题（冗余也是产生异常操作的直接
原因），但这种数据冗余是非主属性下的冗余。 3NF并没有涉及主属性下的数据冗余问题。 唉，还是有问题！ 2018/11/19 数据库系统

40 五、Boyce-Codd范式（BCNF） 1、定义：若R  1NF，且对任何非平凡的函数依赖XY， X必包含码。则R  BCNF。
2、另一种等价的定义： 若 R1NF，并且R中不存 在任何属性传递函数依赖于R的某个码，则称R BCNF。 即每一决定因素都包含码 证明 （1）定义等价定义 即要证：若对任何非平凡的函数依赖XY，X必包含码， 则R中不存在任何属性传递函数依赖于R的某个码。 反证法：假设R中存在属性Z传递函数依赖于码X， 则必存在属性组Y，使得 X Y，Y X，Y  Z。 显然Y不是码，也不包含码，矛盾。 2018/11/19 数据库系统

41 仍用反证法：假设存在非平凡函数依赖XY，X不包含码，
（2）等价定义定义 仍用反证法：假设存在非平凡函数依赖XY，X不包含码， 设X’是一关键字，则X’ X, X X’，因此 X’ Y， 矛盾。 传递 证毕 3、说明 若 R1NF，并且R中不存在任何非主属性传递函数依赖于R的某个码，则称 R3NF。  若R BCNF，则R 3NF。 （也称BCNF为修正的3NF）  BCNF又消除了主属性对码的部分函数依赖和传递函数依赖。  从完全函数依赖的观点看，属于BCNF的关系模式满足：  所有非主属性对每一个码都是完全函数依赖；  所有主属性对每一个不包含它的码也是完全函数依赖；  没有任何属性完全函数依赖不是码的任何一组属性。 2018/11/19 数据库系统

42  在函数依赖的范畴内,BCNF已做到彻底的分离，消除了插 入异常、删除异常（3NF的“不彻底性”在于可能存在主
属性对关键字的部分函数依赖和传递函数依赖）。 4、属于3NF但不属于BCNF的例子：  关系模式 R（S，T，J） 码：（S，T）；（S，J） 函数依赖：（S，J） T；（S，T） J；T J 因为J部分函数依赖于码（S，T），或T是决定因素，但T不包含码。故R不属于BCNF。 5、解决办法：用投影分解 消除主属性对码的部分或传递函数依赖，转换为BCNF。 将R（S，T，J）分解为： R1（S，T） R2（T，J） 2018/11/19 数据库系统

43 6、仅属于BCNF的关系模式可能会产生的问题 以前面讨论过的关系模式 TEACH（C，T，B）为例
课程 教员 参考书 物理 汪洋 普通物理学 物理 汪洋 光学原理 物理 汪洋 物理习题集 物理 大海 普通物理学 物理 大海 光学原理 物理 大海 物理习题集 数学 大海 数学分析 数学 大海 微分方程 数学 大海 高等代数 数学 白云 数学分析 数学 白云 微分方程 数学 白云 高等代数 …… …… …… TEACH的关键字是 （C，T，B），即全键。 因此 TEACHBCNF 问题：冗余大， 增、删不便 原因：存在多值依赖 2018/11/19 数据库系统

44 1、定义：设R  1NF，若对于R的每个非平凡的多值依赖 XY（Y X），X都包含码，那么称 R  4NF。
2、定理：若 R  4NF，则 R  BCNF。 3、属于BCNF但不属于4NF的例子：  关系模式 TEACH（C，T，B） （存在非平凡多值依赖CT，而C不是关键字） 全码 4、解决办法：用投影分解 消除不合适的多值依赖，转换为4NF 对于TEACH（C，T，B）分解为： C-T（C，T） C-B（C，B） 2018/11/19 数据库系统

45 解决 数据冗余、插入异常、删除异常、修改困难 等问题
七、范式小结 1、规范化的目的 解决 数据冗余、插入异常、删除异常、修改困难 等问题 2、规范化的基本思想 逐步消除不合适的数据依赖，让一个关系描述一个概念、一个实体或实体间的一种联系。即“一事一地”的模式设计原则。 2018/11/19 数据库系统

46 3、范式 1NF 消除非主属性对码的部分函数依赖 消除决定因素非码的非平凡函数依赖 2NF 消除非主属性对码的传递函数依赖 3NF
消除主属性对码的部分和传递函数依赖 BCNF 消除非平凡且非函数依赖的多值依赖 4NF …… 2018/11/19 数据库系统

47 对关系模式分解，把一个低一级关系模式分解成若干个高一级的关系模式。
范式间的关系： 4、规范化的过程 对关系模式分解，把一个低一级关系模式分解成若干个高一级的关系模式。 1NF 2NF 3NF BCNF 4NF 5NF 5、规范化与操作效率 片面追求高级的模式，会使数据库操作效率降低 本节开头 本章开头 下一节 2018/11/19 数据库系统

48 上一节给出了范式的定义，并用例子说明了如何确定一个关系模式属于第几范式以及如何把低一级的模式分解成高一级的模式，但都是直观的方法。
§4 函数依赖的Armstrong公理系统 上一节给出了范式的定义，并用例子说明了如何确定一个关系模式属于第几范式以及如何把低一级的模式分解成高一级的模式，但都是直观的方法。 本节及下节将从理论上探讨： 如何确定一个关系模式的极小函数依赖集？ 如何分解关系模式？ 一、Armstrong公理系统 模式分解算法的理论基础 问题：对于给定的一组函数依赖，如何判断其它函数依赖是否成立？或者说哪些函数依赖是不独立的？如：对关系模式R有：AB，BC。 问：AC是否成立？ 2018/11/19 数据库系统

49 即对R的任一关系r，对r中的任意两元组t、s， 若t[X]=s[X]，则t[Y]=s[Y]
1、逻辑蕴涵 设F是关系模式R<U, F>的函数依赖集，X、Y是R的属性子集。如果在R<U, F>上函数依赖XY成立，则称F逻辑蕴涵XY。 即对R的任一关系r，对r中的任意两元组t、s， 若t[X]=s[X]，则t[Y]=s[Y] 下面将会看到（我们的本意也是如此），可以用下述方式来表述逻辑蕴涵： 若从F中的函数依赖能够推出XY，则F逻辑蕴涵XY。 2、Armstrong公理 对关系模式R<U, F>，有如下的推理规则： A1、自反律（Reflexivity）：若YXU，则XY为F所蕴涵。 简写：若YX，则XY 2018/11/19 数据库系统

50 决定每一部分必决定全部 决定全部必决定部分
A2、增广律（Augmentation）：若XY为F所蕴涵，且ZU， 则XZYZ为F所蕴涵。 简写：若XY，则XZYZ A3、传递律（Transitivity）：若XY和YZ为F所蕴涵， 则XZ为F所蕴涵。 简写：若XY、Y  Z，则XZ 证明很简单，自己看书P184 决定每一部分必决定全部 3、Armstrong公理的正确性 定理： Armstrong推理规则是正确的。 4、Armstrong公理的推论 （1）合并规则：由XY， XZ，有XYZ。 （2）分解规则：由XY及ZY，有XZ。 （3）伪传递规则：由XY， WYZ，有XWZ。 决定全部必决定部分 2018/11/19 数据库系统

51 （1）合并规则：由XY， XZ，有XYZ。
证明 （1）合并规则：由XY， XZ，有XYZ。 因为 XZ，由增广律有 XYYZ， 因为 XY，由增广律有 XXXY， 由传递律有 XXYZ 又因为 XXX （自反律），所以 XYZ（传递律）。 （2）分解规则：由XY及ZY，有XZ。 因为ZY，所以YZ（自反律）， 由XY、 YZ，又有XZ（传递律）。 Armstrong公理 若YX，则 XY 若XY，则 XZYZ 若XY、Y  Z，则XZ 伪传递规则的证明作为习题自己证。 根据合并规则和分解规则，可以得出一个重要的结论： 定理：XA1 A2 …Ak的充要条件是XAi（i=1，2，…，k）。 2018/11/19 数据库系统

52 有了上述推理规则，对一个给定的函数依赖集F，我们自然希望知道哪些函数依赖可由F推出，哪些不能由F推出，由F能推出的函数依赖有多少等。
二、函数依赖集的闭包 有了上述推理规则，对一个给定的函数依赖集F，我们自然希望知道哪些函数依赖可由F推出，哪些不能由F推出，由F能推出的函数依赖有多少等。 1、闭包的定义：在关系模式R<U, F>中F所逻辑蕴涵的函数 依赖的全体称为F的闭包。记作F+。 例：设关系模式R<U, F>,其中U={X，Y，Z}，F={XY， YZ}，则F的闭包F+为： X XY XZ XYZ Y YZ Z XX XYX XZX XYZX YY YZY ZZ XY XYY ZXY XYZY YZ YZZ XZ XYZ XZZ XYZZ YYZ YZYZ XXY XYXY XZXY XYZXY XXZ XYXZ XZXZ XYZXZ XYZ XYYZ XZYZ XYZYZ XXYZ XYXYZ XZXYZ XYZXYZ 2018/11/19 数据库系统

53 难 2、求函数依赖集的闭包问题是NP完全问题 3、属性集的闭包
设关系模式 R<U, F>，X U，X关于函数依赖集F的闭包为： X + F ={ A | XA能由F根据Armstrong公理推出} 函数依赖集的闭包是一个（更大的）函数依赖集 属性集的闭包 是一个（更大的）属性集合 设F为属性集U上的一组函数依赖，X，Y  U， XY能由F根据Armstrong公理导出的充分必要条件是Y 。 X + F 于是判定XY能否由F根据Armstrong公理导出的问题，就转化为求出 ，判定Y是否为 的子集的问题。 X + F 2018/11/19 数据库系统

54 分析：根据定义，要求所有这样的属性A：XA能由F经数次使用Armstrong公理推出。
4、求闭包 X + F 的算法 Armstrong公理 若YX，则 XY 若XY，则 XZYZ 若XY、Y Z，则XZ 分析：根据定义，要求所有这样的属性A：XA能由F经数次使用Armstrong公理推出。 A应具备何种特征？ 分析Armstrong公理的形式可以看出，A应该属于X，或A属于F中某个函数依赖的右部，而该函数依赖的左部属性应是属于X的闭包。 算法思想：采用逐步扩张X的策略求X的闭包。方法是：扫描F，找出左部属性属于当前X的闭包的函数依赖，将右部属性加入当前X的闭包。经若干次扩张，直到当前闭包集不再扩大为止。 2018/11/19 数据库系统

55 计算时在F中寻找未用过的 左部是X(i)的子集的函数依赖
算法 计算时在F中寻找未用过的 左部是X(i)的子集的函数依赖 输入：X，U，F； 输出：X关于F的闭包 X + F （1）初始：令X(0)=X, i=0; （2）迭代：求B={A | (V)(W) (VWF  VX(i)  AW)}； X(i+1)=BX(i); （3）判断： X(i+1)=X(i)？ 若相等或X（i）=U，转下一步； 否则，用i+1取代i，转第（2）步继续迭代； （4）结束：X(i)就是 ，算法终止. X + F 每次迭代都添加属性到当前闭包(不增加时算法就结束)故至多迭代|U|－|X|次算法终止 2018/11/19 数据库系统

56 例：设F={ ACPE，PGA，BCE，AP，GAB， GCA，PABG，AEGB，DPH }， X=BG， 求
+ F 左部 右部 迭代号 AC PG B A GA GC PAB AE DP 3 AC PE PE A CE P B G GB H 求解过程 4 PG A 初始：X(0) = X = BG 第1次迭代: 找左部为B、G或BG的 函数依赖，将其右部属性放入闭包 B CE 1 A P 3 X(1) = X(0)  CE = BCEG 第2次迭代: GA B 3 2 GC A 4 X(2) = X(1)  A = ABCEG 第3次迭代: PAB G 3 AE GB X(3) = X(2)  PEBG = ABCEGP 第4次迭代: X(4)与X(3)相同，算法结束， X(4)=ABCEGP就是BG的闭包 X(4) = X(3)  AG = ABCEGP 2018/11/19 数据库系统

57 又如，若关系模式为 R(A1，A2，A3)，F={A1A2， A2A3}， 则当 X=A1 时，X的闭包为 A1A2A3；
留作习题 思考：对关系模式R<U, F>, 若 = U， 问X有何性质？ X + F 求X的闭包算法的正确性 我们不做证明。 2018/11/19 数据库系统

58 ？ 三、Armstrong公理系统的有效性和完备性
函数依赖集F的闭包F+是F所逻辑蕴涵的函数依赖的全体。关于逻辑蕴涵，我们已经建立了一套推理规则（ Armstrong公理系统），因此自然要问：  由F出发根据Armstrong公理能推出的函数依赖是否一定是F逻辑蕴涵的，即是否一定在F+中？  F+中的每一个函数依赖，即F逻辑蕴涵的每一个函数依赖，是否一定可以根据Armstrong公理推出？ ？ F+ = { 由F出发根据Armstrong公理能推出的函数依赖的全体 } 2018/11/19 数据库系统

59 1、何谓有效性？何谓完备性？ Armstrong公理的有效性：
有效性就是正确性， Armstrong公理的正确性就是由该公理系统推出的函数依赖都是正确的。而正确性的标准就是只要F中的函数依赖为真，则由公理推出的函数依赖也为真。换句话说，由F出发根据Armstrong公理能推出的函数依赖一定在F+中 Armstrong公理的完备性： 完备性就是要讨论用公理能否推出所有的函数依赖。因为如果存在F逻辑蕴涵的函数依赖不能用公理推出，则说明这些公理不够用，是不完全的，还必须补充新的公理。因此，完备性就是指F+中的每一个函数依赖，一定可以根据Armstrong公理推出 2018/11/19 数据库系统

60 公理的正确性保证了推出的所有函数依赖都是正确的； 公理的完备性保证了可以推出所有的函数依赖。
2、 Armstrong公理的有效性 回忆一下Armstrong公理系统（自反律、传递律和增广律）以及前面讨论过的定理“ Armstrong推理规则是正确的”，可证Armstrong公理系统是有效的。 3、 Armstrong公理的完备性 要证完备性，必须解决如何判断 一个函数依赖是否可由F出发根据Armstrong公理推出 如果能方便地求出F+，将有助于解决上述问题，但计算F+是NP完全问题。 前面已经给出求属性集的闭包的有效算法。对一个函数依赖XY，X的闭包对我们要解决的问题有何帮助？ 2018/11/19 数据库系统

61 引理：对关系模式R<U, F>，X、Y U， X Y能由F根据Armstrong公理推出 Y X + F 证明 充分性：
反之是否成立？ 引理：对关系模式R<U, F>，X、Y U， X Y能由F根据Armstrong公理推出 Y X + F 证明 充分性： 设Y=B1B2…Bk，Bi  X + F ，（i=1，2，…，k） 根据属性闭包的定义可得 XBi（i=1，2，…，k）都可由F根据Armstrong公理推出， 再由合并规则可得 XB1B2…Bk， 即 XY可由F根据Armstrong公理推出， 必要性： 此处证明从略，留作习题 2018/11/19 数据库系统

62 定理： Armstrong公理系统是完备的。
分析 欲证 XY不为F所蕴涵， 只需证： 存在符合关系模式 R<U, F>的一个关系r，函数依赖XY在r上不成立 因此，需要构造一个关系r： r的属性集是U，且r满足F中的所有函数依赖，但XY在r上不成立 根据定义，需证： 对F+中的每一个函数依赖，必定可由F用Armstrong公理推出 再由F+的定义，需证： 对F所蕴涵的每个函数依赖，必定可由F用Armstrong公理推出 因此，只需证明： 若存在函数依赖 XY不能由Armstrong公理推出，则它不为F所蕴涵 关键是证明这两点 2018/11/19 数据库系统

63 关系r只有两个元组， 在X的闭包上分量值相等
欲构造关系r，使得XY在r上不成立，最简单的情形是： r X Y Z 1 1 表示相等 表示不相等 但这样构造的r显然不合要求，因为r不一定满足F中的所有函数依赖。 属性集的闭包在Armstrong公理可推导的意义下具有封闭性，我们这里要讨论的就是Armstrong公理的完备性。所以 构造r时利用X的闭包更为合理： X + F X + F U– 关系r只有两个元组， 在X的闭包上分量值相等 关系r 11…1 11…1 00…0 2018/11/19 数据库系统

64 关系r X X X X 证明 假设函数依赖 XY不能由Armstrong公理推出 根据前面引理易证
（1）先证F中的函数依赖和X的闭包有下述关系： 若VW是F中的函数依赖，且 V X + F ，则W  （2）再证前面构造的关系 r 是 R<U, F>的关系，即满足F中的全部函数依赖 设VW 是F中的任一函数依赖， 要证VW在r上成立。 分两种情情形： W 11…1 X + F U– 关系r 00…0 第一种情形：V X + F 根据第（1）步结论，有W  X + F W的值在仅有的两个元组上相等，因此必有若t[V]=s[V]则t[W]=s[W]， 所以此时VW在r上成立。 2018/11/19 数据库系统

65 关系r X X X X X X + U– F + 第二种情形：V F 1 A + 此时存在属性AV，但A F
第二种情形：V X + F A 此时存在属性AV，但A X + F r中仅有的两个元组在属性A上的值不等， 所以在r中不存在两个元组t、s满足t[V]=s[V]， 因此“若t[V]=s[V]，则t[W]=s[W]”在关系r上恒成立，故VW在r上成立。 V 综上可知F的任一函数依赖在r上成立，即r是 R<U, F>的关系 （3）最后证明函数依赖XY在r上不成立 由假设， XY不能由Armstrong公理推出，根据引理有Y X + F 所以有Y的子集Y’满足Y’ X + F U– ，故对r中仅有的两元组t、s，有 X + F 但由于X t[Y’]s[Y’]，进而有t[Y]s[Y]。 ，所以有t[X]=s[X]， 因此得XY在r上不成立。即XY必不为F所蕴涵。 证毕 2018/11/19 数据库系统

66 定义：设F和G都是关系模式R上的两个函数依赖集，如果F+ = G+，则称F与G等价（或称F覆盖G，或G覆盖F）。
四、函数依赖集的等价和极小依赖集 1、函数依赖集的等价（覆盖）： 定义：设F和G都是关系模式R上的两个函数依赖集，如果F+ = G+，则称F与G等价（或称F覆盖G，或G覆盖F）。 等价具有自反性、对称性、传递性，即是一等价关系。 定理：F+ = G+ 的充要条件是 FG+和 G F+ 。 证明：必要性显然。因为FF+、G G+成立， 若 F+ = G+，则必有FG+、G F+成立。 即F可由G推出 G也可由F推出 充分性：要证当FG+、G F+时，有F+ = G+成立。 先证对任意的XYF+，有XYG+。这样就有F+ G+。 因为XYF+，所以Y X + F 。 2018/11/19 数据库系统

67 对本定理也可先证命题：（1）若F  G，则F+  G+； （2）F+ =（F+）+。
X + F G+ X + G+ 所以Y ，从而得XY（G+）+=G+。 于是证得F+ G+。 证毕 同理可证 G+ F+，所以 F+ = G+。 对本定理也可先证命题：（1）若F  G，则F+  G+； （2）F+ =（F+）+。 然后有：F  G+  F+ （G+）+ = G+； G  F+  G+ （F+）+ = F+； F+ = G+ 2、极小（最小）函数依赖集 根据分解与合并规则，可以证明下述引理： 引理：每个函数依赖集F都与一个右部只有单个属性的函数 依赖所构成的函数依赖集G等价。 2018/11/19 数据库系统

68 设F2中的函数依赖形如 XA1A2…Ak，k2。 令F3是将F2中所有函数依赖分解成形如 XAi 的函数依赖全体，
F = F1  F2 右边是一个以上属性的函数依赖子集 右边是单属性的函数依赖子集 设F2中的函数依赖形如 XA1A2…Ak，k2。 令F3是将F2中所有函数依赖分解成形如 XAi 的函数依赖全体， G = F1  F3，要证明F与G等价 对G中任一个形如 XAi F3，由于F中存在XA1A2…Ak，ik，根据分解规则可推出 XAi，所以 XAiF+，而F1  F  F+。 故GF+。 根据合并规则，同理可证 FG+。 根据前面的引理，有F与G等价。 证毕 2018/11/19 数据库系统

69 定义：若函数依赖集F满足下列条件，则称F为极小（函数） 依赖集，亦称最小（函数）依赖集、最小覆盖：
（2）对F中的任一个函数依赖XA， 都有F与F{XA}不等价； （3）对F中的任一个函数依赖XA， 都有F与（F{XA}） {ZA}不等价， 其中Z是X的任一真子集。 右部都是单属性 不存在多余的函数依赖 每个函数依赖的左部 没有多余的属性 例：关系模式 S<U, F>，U ={ S#，SD，MN，CN，G }， F ={ S#SD，SDMN，（S#，CN）G }， 则F是最小覆盖。 设函数依赖集F’ ={ S#SD，S#MN， SDMN， （S#，CN）G ，（S#，SD）SD }， 则F’不是最小覆盖。 2018/11/19 数据库系统

70 定理：每一个函数依赖集F均等价于一个极小函数依赖集Fm。
3、如何求极小函数依赖集 定理：每一个函数依赖集F均等价于一个极小函数依赖集Fm。 证明 对F极小化处理 （1）分解：将F中右部多于一个属性的函数依赖分解成单属性函数依赖。 逐一检查F中各函数依赖FDi：XY，若Y=A1A2…Ak，k2，则用{XAi | i=1，2， …k }取代XY。 这样每个函数依赖的右部都为单属性，由引理知该函数依赖集与F等价。 （2）去多余依赖： 对经第一步处理后的F，逐一检查F中各函数依赖 XA， 令G=F－{XA}，若A ，则从F中去掉XA。 X + G 2018/11/19 数据库系统

71 此处我们考虑XA 是否多余，即F是否与G等价。 因为G是F的子集，且只比F少一个函数依赖XA，所以
+ G A  F与G等价 XA可由G推出 （3）去左部多余属性： 对经第二步处理后的F，逐一检查F中各函数依赖 XA， 设X=B1B2…Bm，逐一考察Bi，若 A（X－Bi） ，则以X－Bi + F 取代X。这样得到的函数依赖集仍与F等价，且去掉了左部多余 的属性。 F 与（ F－{XA}） {（ X－Bi）A }等价 （X－Bi）A 可由F推出 A（X－Bi） + F 证毕 2018/11/19 数据库系统

72 说明  此定理表明：任一函数依赖集都可极小化。定理的证明过程就是“极小化处理”过程，也就是求一个函数依赖集的极小依赖集的方法。
 F的极小依赖集不一定唯一（例子见P187）。当以不同的顺序考察各函数依赖时，得到的极小函数依赖集可能不同。 2018/11/19 数据库系统

73 BCD，CGBD， ACDB， CEAG F = DEG， CGBD， CEAG
ABC， DEG， CA， BEC， BCD，CGBD， ACDB， CEAG F = DEG， CGBD， CEAG 解：（1）分解右部为单属性 ABC， DE， CA， BEC， DG， BCD，CGB，ACDB，CEA， CGD， CEG G = （2）去掉G中多余的函数依赖 具体做法是：从G的第一个依赖开始，依次判别是否多余。设处理到函数依赖 XY，从函数依赖集中先去掉它，求X关于此函数依赖集的闭包，再判属性Y是否属于该闭包。若是，则去掉XY；否则，保留。然后处理下一个。 2018/11/19 数据库系统

74 ABC，DE，DG，CA，BEC， BCD， CGB，CGD，ACDB，CEA， CEG G =
求AB关于G－{ABC}的闭包，根据求闭包的算法，仍为 {A，B}，而 C{A，B}，所以不能去掉ABC； 同样可判DE, DG, CA, BEC, BCD也不能去掉； 求CG关于G－{CGB}的闭包，得ABCDEG，B在其中， 故去掉CGB； 对G－{CGB}继续进行，可得CGD，ACDB保留， CEA去掉， CEG保留。 问：CGB如何由H推出？ CG CCG ACG ACCG ACD B 最后得： ABC，DE，DG，CA，BEC，BCD， CGD，ACDB， CEG H = 2018/11/19 数据库系统

75 具体做法是：依次检查左部为多属性的函数依赖，对每一个这样的函数依赖，检查其中是否有多余属性：若XBA，求X关于H的闭包，看它是否包含A。
ABC，DE，DG，CA， BEC， BCD，CGD，ACDB，CEG H = BEC， ABC， BCD，CGD，ACDB，CEG 看ABC，因为A关于H的闭包为{A}，B关于H的闭包为{B}，它们都不包含C，故ABC无多余属性； 同样可得BEC，BCD，CGD，CEG中无多余属性； 看ACDB，因为 AC关于H的闭包为{A，C}， AD关于H的闭包为{A，D，E，G}， CD关于H的闭包为{A，B，C，D，E，G}， 不含B A多余 不含B 包含B 2018/11/19 数据库系统

76 ABC， DE， DG， CA， BEC， BCD，CGD，ACDB，CEG H =
因此在H中把 ACDB 换成 CDB： ABC， DE， DG， CA， BEC， BCD，CGD，ACDB，CEG H = F的极小依赖集为： ABC， DE， DG， CA， BEC， BCD，CGD，CDB，CEG Fm = F还有另一个极小依赖集为： ABC， DE， DG， CA， BEC，BCD，CGB，CEG Fm2 = 本节开头 本章开头 下一节 2018/11/19 数据库系统

77  = { R1<U1, F1>， R2<U2, F2>，…， Rn<Un, Fn> }
§5 关系模式的分解 一、模式分解的有关概念 1、分解的定义：对关系模式 R<U, F>，若模式集合  = { R1<U1, F1>， R2<U2, F2>，…， Rn<Un, Fn> } 满足  U = U1  U2  … Un，且 Ui  Uj，1 ij n，  Fi是F在Ui上的投影。 函数依赖集合 { XY  XYF+  XYUi }的一个覆盖 例：设模式为R<U, F>，其中U={S#，SD，MN}， F={S#SD，SDMN}，考虑下面几种分解： （1）U1 = { S# }， U2 = { SD }，U3 = { MN } F1 = ， F2 = ， F3 =   = { R1<U1, F1>， R2<U2, F2>，R3<U3, F3> }是R的一 个分解。 2018/11/19 数据库系统

78 （2）U1 = { S#，SD }， U2 = { S#，MN } F1 = { S#SD }，
参考前面的例子：设关系模式为R<U, F>，其中U={X，Y，Z}， F={XY，YZ}， F的闭包F+为： X XY XZ XYZ Y YZ Z XX XYX XZX XYZX YY YZY ZZ XY XYY XZY XYZY YZ YZZ XZ XYZ XZZ XYZZ YYZ YZYZ XXY XYXY XZXY XYZXY XXZ XYXZ XZXZ XYZXZ XYZ XYYZ XZYZ XYZYZ XXYZ XYXYZ XZXYZ XYZXYZ XY 2018/11/19 数据库系统

79 （2）U1 = { S#，SD }， U2 = { S#，MN } F1 = { S#SD }， F2 = { S#MN }
 = { R1<U1, F1>， R2<U2, F2> }也是R的一个分解。 参考前面的例子：设关系模式为R<U, F>，其中U={X，Y，Z}， F={XY，YZ}， F的闭包F+为： X XY XZ XYZ Y YZ Z XX XYX XZX XYZX YY YZY ZZ XY XYY XZY XYZY YZ YZZ XZ XYZ XZZ XYZZ YYZ YZYZ XXY XYXY XZXY XYZXY XXZ XYXZ XZXZ XYZXZ XYZ XYYZ XZYZ XYZYZ XXYZ XYXYZ XZXYZ XYZXYZ XZ 2018/11/19 数据库系统

80 信息丢失 （3）U1 = { S#，SD }， U2 = { SD，MN } F1 = { S#SD }， F2 = { SDMN }
 = { R1<U1, F1>， R2<U2, F2> }也是R的一个分解。 2、分解可能会带来的问题 问题：关系r分解为r1、r2、r3三个关系，但根据这三个关系，无法回答诸如“S1是哪个系的学生？”、“D1系的系主任是谁？”等许多提问。 （1）分析第一种情形： U1 = { S# }，U2 = { SD }，U3 = { MN } F1 = ， F2 = ， F3 =  设关系r为： S# SD MN r1为： S# r2为： SD r3为： MN S1 D1 张五 S2 D1 张五 S3 D2 李四 S4 D3 王一 S1 S2 S3 S4 D1 D2 D3 张五 李四 王一 信息丢失 2018/11/19 数据库系统

81 分解后的关系应该能够恢复成原来的形式，这是最基本的要求。恢复通常由自然连接来实现。
r1、r2、r3自然连接的结果与r相比元组增加了，但信息丢失了。 分解不能丢失信息，这就是“无损连接性”的概念 （2）分析第二种情形： U1 = { S#，SD }， U2 = { S#，MN } F1 = { S#SD }， F2 = { S#MN } 对此分解，可正确恢复出原来的关系。但原关系模式的数据冗余、插入异常、删除异常的问题仍然存在。 分析原因，原来具有的函数依赖SDMN现在没有了。 分解应该“保持函数依赖” 2018/11/19 数据库系统

82 对此分解，通过自然连接可正确恢复，且原来的函数依赖都保持。
（3）分析第三种情形： U1 = { S#，SD }， U2 = { SD，MN } F1 = { S#SD }， F2 = { SDMN } 对此分解，通过自然连接可正确恢复，且原来的函数依赖都保持。 3、分解准则 分解后的模式应和原来的模式“等价”。 根据以上分析，可提出以下不同标准：  分解具有“无损连接性”（Lossless join）  分解要“保持函数依赖”（Preserve dependency）  分解既要“保持函数依赖”，又要具有“无损连接性” 本节讨论：  何谓“无损连接性”和“保持函数依赖”？  分离程度如何？  如何分解？ 2018/11/19 数据库系统

83 r = （r）  （r） …  （r） 二、分解的无损连接性和保持函数依赖性 1、无损连接性的形式化定义:
设 = { R1<U1, F1>， R2<U2, F2>，…， Rk<Uk, Fk> }是R<U, F>的一个分解。若对R的任何一个关系r都有 r = （r）  （r） …  （r） U1 U2 Uk 成立，则称具有无损连接性，简称为无损分解。 例：设关系模式 R（A，B，C）， 分解为R1（A，B）、R2（B，C）。 又设其中一个关系为： 不是无损分解 r1= （r） A,B r2 = （r） B,C r r2  r r A B C A B C a1 b1 c1 a2 b1 c2 a1 b1 c2 A B a1 b1 a2 b1 B C b1 c1 b1 c2 a1 b1 c1 a1 b1 c2 a2 b1 c1 a2 b1 c2 多一个元组 a2 b1 c1 2018/11/19 数据库系统

84 例: 设模式为R<U, F>，其中U={S#，SD，MN}， F={S#SD，SDMN}，
分解为：U1 = { S#，SD }，U2 = { S#，MN } F1 = { S#SD }， F2 = { S#MN } r1= （r） S#,SD r2 = （r） S#,MN r r2 ＝ r 设关系r为： S# SD MN S# SD S1 D1 S2 D1 S3 D2 S4 D3 S# MN S1 张五 S2 张五 S3 李四 S4 王一 S# SD MN S1 D1 张五 S2 D1 张五 S3 D2 李四 S4 D3 王一 S1 D1 张五 S2 D1 张五 S3 D2 李四 S4 D3 王一 不行！ 此时是否可以说这是一个无损分解？ 如何判断是否为无损分解？ 2018/11/19 数据库系统

85 输入： R<U, F>的一个分解 ={ R1(U1,F1), …, Rk(Uk,Fk) }， U={A1，A2，…，An}，
2、无损连接性判定算法 输入： R<U, F>的一个分解 ={ R1(U1,F1), …, Rk(Uk,Fk) }， U={A1，A2，…，An}， F={FD1，FD2，…，FDp}为最小覆盖，FDi：XiAli； 输出： 是否为无损连接的判定结果；  构造一个k行n列的表：第i行对应关系模式Ri，第j列对应属性Aj；若AjUi，则在第i行第j列处写入aj；否则写入bij。  逐个检查F中的每一个函数依赖，并修改表中的元素： 对每个FDi ：XiAli，在Xi对应的列中寻找符号相同的行，并将这些行中Ali对应的列全改为相同的符号。修改规则为：若其中有ali，则全改为ali；否则全改为bmli，m是这些行中行号的最小值。（若某个btli被改动，则该列中凡是btli的符号都要作同样的修改。） 2018/11/19 数据库系统

86 设模式为R<U, F>,U={ A, B, C, D, E },F ={ ABC, CD, DE },
 判别：若某一行变成a1，a2 ，…an，则算法终止（此时 为无损分解）；否则，比较本次扫描前后的表有无变化，若有，重复第步；若无，算法终止（此时 不是无损分解） 无损连接判定举例： 设模式为R<U, F>,U={ A, B, C, D, E },F ={ ABC, CD, DE }, 分解为 R1(A, B, C)、R2(C, D)、R3(D, E)。 算法第二步：扫描F，修改表 算法第一步：构造初始表 对ABC，看A、B对应的第1、2两列有无相同的行。没有，不做处理。 对CD，看C对应的第3列有无相同的行 A B C D E R1 R2 R3 b14 b15 b21 b b25 b31 b32 b33 a1 a2 a3 a3 a4 a4 a5 a3 a4 a4 a5 第1、2行相同，将D列的b14改为a4。 对DE，进行同样处理。 a3 a4 a4 a5 算法第三步：判断 表中第一行为a1、a2、a3、a4、a5，算法终止，R1、R2、R3是R的无损分解 a4 a5 2018/11/19 数据库系统

87 其函数依赖集合F={AB，CF，EA，CED}，
例：设有关系模式 R（A, B, C, D, E, F )， 其函数依赖集合F={AB，CF，EA，CED}， 分解为  = { R1(C, F), R2(B, E), R3(E, C, D), R4(A, B) } 解: （1）构造表 （2）修改表，第一次扫描F  AB：无修改 A B C D E F  CF： b36改为a6 R1(C,F) R2(B,E) R3(E,C,D) R4(A, B) b11 b12 a3 b14 b15 a6 b21 a2 b23 b24 a5 b26 b31 b32 a3 a4 a5 b36 a1 a2 b43 b44 b45 b46  EA： b31改为b21 b21 a2 a6  CED：无修改 （3）第二次扫描F  AB：b32改为a2 其余无修改 （4）第三次扫描: 表无变化, 算法终止 （5）判断：不是无损分解 2018/11/19 数据库系统

88 定理：为无损连接分解的充分必要条件是： 算法终止时，表中有一行为a1，a2，，an。
3、算法的正确性： 定理：为无损连接分解的充分必要条件是： 算法终止时，表中有一行为a1，a2，，an。 证明略 4、分解为两个关系模式时的简单判定法 例：设关系模式为R<U, F>, U={ A, B, C }, F ={ AB, CB }, 分别检查下列分解的无损连接性： （1） 1 = { R1(A, B), R2(B, C) } (2) 2 = { R1(A, C), R2(B, C) } A B C R1(A, B) R2(B, C) A B C R1(A, C) R2(B, C) a1 a2 a2 a3 b13 b21 a1 a2 a3 b12 b21 a3 a2 对AB，表无修改 对CB，表无修改 对AB，表无修改 对CB，修改b12为a2 2018/11/19 数据库系统

89 定理：设 = { R1<U1, F1>, R2<U2, F2> }是R<U, F>的一个分解。
那么是无损分解的充分必要条件是 U1U2  U1－U2  F+ 或 U1U2  U2－U1  F+ (U1－U2)  (U1U2) F + (U2－U1)  (U1U2) F + 即 或 证明略 看上例：关系模式为R<U, F>, U={ A, B, C }, F ={ AB, CB }, (1) 1 = { R1(A, B), R2(B, C) } (2) 2 = { R1(A, C), R2(B, C) } U1U2  U1－U2 为： B  A U1U2  U2－U1 为： B  C U1U2  U1－U2 为： C  A U1U2  U2－U1 为： C  B 因为 B = {B} + F 因为CB  F，所以 不包含A，也不包含C， 所以BA和BC不为F所蕴涵 2是无损分解 1不是无损分解 2018/11/19 数据库系统

90 的一个分解，若 F = （F1F2Fk），则称保持函数依赖。 +
5、保持函数依赖性的形式化定义: 设 = { R1<U1, F1>, R2<U2, F2>, …, Rk<Uk, Fk> }是R<U, F> 的一个分解，若 F = （F1F2Fk），则称保持函数依赖。 + 判别定理：F+ = G+ 的充要条件是 FG+和 G F+ 。 6、说明  一个无损连接分解 不一定是 一个保持函数依赖的分解  一个保持函数依赖的分解 不一定是 一个无损连接分解 例：关系模式为R<U, F>, U={ A, B, C }, F ={ AB, CB }, (1) 1 = { R1(A, B), R2(B, C) } (2) 2 = { R1(A, C), R2(B, C) } 有损连接 无损连接 其 F1={AB}，F2={CB } 其 F1=，F2={CB } 保持函数依赖 不保持函数依赖 2018/11/19 数据库系统

91 2、转换为3NF的保持函数依赖的分解算法——合成法
直 观 的 想 法 最 重 要 三、模式分解的算法 1、模式分解的分离程度 保持函数依赖 3NF 具有无损连接性 4NF 保持函数依赖 具有无损连接性 3NF 2、转换为3NF的保持函数依赖的分解算法——合成法 若要将一个关系模式的极小函数依赖集中的每一个函数依赖都要保留下来，最简单的方法就是把每一个函数依赖的左右部属性组成一个模式。 如假设 F = {AB，AC，CD}，则可考虑分解为：  = { R1(A, B), R2(A, C), R3(C, D) } 但AB，AC左部相同，分解成两个模式是否有必要呢？ 算法思想： 考虑合并 （左部相同的函数依赖放在一起考虑） 2018/11/19 数据库系统

92 算法5.3：把一个关系模式分解为3NF，且使它保持函数依赖 输入：关系模式 R<U, F>;
输出：R的一个分解 ={R1,R2,…Rk}，每个Ri均为3NF，且保持函数依赖 （1）极小化：对F进行极小化处理（处理后的函数依赖集仍记为F）； （2）分离无关属性：把U中不出现在F中的属性组成一个关系模式，从U中去掉这些属性（剩余的属性仍记为U）； （3）判是否需分解：若有XAF，且XA=U，则 ={R}，算法终止； （4）分解：对F分组：左部相同的为一组, 设为Fi’，每组所包含的全部属性形成一个属性集Ui。若有UiUj（ij），去掉Ui。设最后保留下来U1，U2，…，Uk，则  ={ R1(U1), R2(U2), … Rk(Uk) }，算法终止。 2018/11/19 数据库系统

93 例1：设关系模式 R（A，B，C，G，H，R，S，T）， F = { CT，CSG，HTR，HRC，HSR }
求：(a)R的一个侯选关键字； (b)将R分解为3NF，并且保持函数依赖性。 (a)求关键字：设X为候选关键字，则必有X =U。 F + 解 －X只能取F中函数依赖右部的属性， X + F 而 要等于U， 至少应有ABHS X。 求ABHS关于F的闭包有：(ABHS) = ABHSRCTG=U F + 所以ABHS是一个候选关键字。 (b)分解R：(1) 先对F极小化：F已是最小依赖集。 (2) 分离无关属性：AB未在F中出现，分离出去。 (3) 判是否需分解：需要。 (4) 分解：按左部相同的原则分组。 则  ={ R1(A,B), R2(C,T),R3(C,S,G), R4(H,T,R), R5(H, R, C), R6(H,S,R) }为一个保持函数依赖且达到3NF 的分解。 2018/11/19 数据库系统

94 例2：设有关系模式 R（A，B，C，D，E），R的一个函数依 赖集为F = { AD，AB，ED，DB，BCD，DCA }，
（a）求R的候选关键字； （b）将R分解为3NF，并且保持函数依赖性。 （a）求关键字：设X为候选关键字，则必有X =ABCDE。 + F 解 X + F －X只能取F中函数依赖右部的属性，要使 而 等于 ABCDE，必须有CEX。 再求CE关于F的闭包，得（CE） = CEDBA。 + F 所以CE是一个候选关键字。 若此时还不等于 R的属性集U， 怎么办？ （b）分解R: （1）先对F极小化： ①分解右部为单属性：不需要； ②去掉多余函数依赖：AB多余； 2018/11/19 数据库系统

95 例2：设有关系模式 R（A，B，C，D，E），R的一个函数依 赖集为F = { AD，AB，ED，DB，BCD，DCA }，
（a）求R的候选关键字； （b）将R分解为3NF，并且保持函数依赖性。 ③去掉左部多余属性：没有。 所以极小函数依赖集为： F = { AD，ED，DB，BCD，DCA } （2）分离无关属性：没有。 （3）判是否需分解：需要。 （4）分解： {AD，ED，DB，BCD，DCA}  ={R1( E, D)，R2(B, C, D)，R3(D, C, A) } 2018/11/19 数据库系统

96 例3：设有关系模式 R(A，B，C，D)，R的一个函数依赖集为 F = { AB，BC，CD，DA }，
试将R分解为3NF，并且保持函数依赖性。 解 （1）先对F极小化：F就是最小依赖集。 （2）分离无关属性：没有。 （3）判是否需分解：需要。 （4）分解：  ={R1(A, B)，R2(B, C)，R3(C, D)，R4(D, A)} 算法的正确性： 按算法5.3得到的关系模式R的分解 ={R1,R2,…Rk}满足： 每个Ri均为3NF，且保持函数依赖。 2018/11/19 数据库系统

97 Fi’系由F按左部相同的原则分组而得。 非主属性Am传递依赖于侯选关键字X
（b）证每个 Ri<Ui, Fi> 均为3NF（Fi是F在Ui上的投影）： 设F是R的最小依赖集，Fi’是分解算法中得到Ri的那组函数依赖， 要证不存在非主属性对关键字的传递函数依赖。 设 Fi ’={ XA1, XA2, … XAn }，Ui ={X, A1, …An }， 则X一定是Ri的候选关键字。 反证法：假设Ri不是3NF，则Ui中存在非主属性Am(1mn) 和属性组合Y使得AmY，XY、YAmFi , 而YX Fi 。 + Fi’系由F按左部相同的原则分组而得。 非主属性Am传递依赖于侯选关键字X 下面证 XAm在F中多余，从而与F是最小依赖集矛盾。 令G=F－{ XAm }，欲证 XAmG 。 + 2018/11/19 数据库系统

98 因为Y是Ui的子集，且不包含Am，所以 Y X ， 因此XYG 。 + G
要证 XAmG ，只需再证YAmG 。 + 因为YAmFi ，所以AmY 。 + F 若YAmG ，则在求Y 的算法中，只有使用XAm才能 将Am引入。 + F 根据求闭包的算法，存在j使得XY ，故得YXF ， (j) + 与YX Fi 相矛盾， + 所以YAmG 成立。 + 证毕 说明：因为保持函数依赖的分解可能不是无损连接的分解，而不具有无损连接性就会丢失信息，所以这样的分解是没有意义的。因此单单算法5.3没有实用价值，但它是下一算法的基础。 2018/11/19 数据库系统

99 2、转换为3NF既保持函数依赖又具有无损连接性的分解算法
在算法5.3分解的基础上，增加一个模式，该模式以 原模式的一个关键字作为属性组，使该模式起到正确连接其它 各模式的作用。 算法思想: 例如，对 R(A，B，C，D)，其最小依赖集F={AB，CD}， 按算法5.3得到的分解是 1 ={AB，CD}， 不具有无损连接性。 R的关键字是AC，分解成2 ={AB, CD, AC}就具有无损连接性。 输入：关系模式R<U, F>； 输出：R的一个分解 ={R1,R2,…Rp}，每个Ri均为3NF， 且  既保持函数依赖又具有无损连接性； 算法5.4: （1）用算法5.3将R分解为  ={ R1(U1), R2(U2), … Rk(Uk) }； （2）求R的一个关键字X； （3）若X是某个Ui的子集，输出  = ； 否则， 输出 =   { R （X）} ；算法结束。 * 2018/11/19 数据库系统

100 算法的正确性：按算法5.4得到的关系模式R的分解 ={R1, R2, …Rp}满足：
每个Ri均为3NF，且 既保持函数依赖又具有无损连接性。 证明；（a）  保持函数依赖显然成立。 （b）证每个 Ri均为3NF： 算法5.3保证R 之外的Ri都为3NF；R 中没有非主属性，因此也为3NF。 * （c） 证为无损分解： 分析：增加 R 的目的就是为了达到无损连接， 按照无损连接判定算法，R 所对应的行应该成为全a。 * R 不一定在中，但中必存在某关系模式的属性组T包含X， * R * 为简单起见，不妨设T就是X， 就在中。 按照无损连接判定算法，在构造初始判定表时，对 所对应的行， R * X对应的列全为a， 设 U－X={A1，A2，…As}，欲证经有限步执行判定算法， 该行中A1，A2，…As所对应的列也被改为全a。 2018/11/19 数据库系统

101 YiAiF，且YiX =XA1A2 … A(i–1)。
因为X是关键字，故X =U. + F 属性 U－X A1 … Ai … As X 模式 所以在求X的闭包时，A1、 A2、…As将进入X的闭包， 不妨设进入的次序就是A1、 A2、…As，则根据求闭包的 算法，会产生序列： … … … R （X） * aaa…aaaa b b…b b … b … … … R1(Y1A1) baa…abba a b…b b … b a … … … Ri(YiAi) bab…babb b a…a b … b a … … … Rs(YsAs) aab…abaa a b…b a … a a XX X X =U (2) (1) (i) … … … 满足 YiAiF，且YiX =XA1A2 … A(i–1)。 (i–1) 不失一般性，可设R1(Y1A1)、 R2(Y2A2)、 … Rs(YsAs)在中， 初始判定表如右上角所示。 2018/11/19 数据库系统

102 U－X A1 … Ai … As a a a … a a … a a a a
证按无损判定算法， 对应的行中A1，A2，…As所对应的列被改为全a。 R * 用归纳法： 当s=1时，有Y1A1F，故R1 所在的行中Y1对应的列全a； U－X A1 … Ai … As X … … … R （X） * R1(Y1A1) Ri(YiAi) Rp(YpAp) 属性 模式 a b…b a … a aaa…aaaa baa…abba bab…babb aab…abaa b b…b b … b a b…b b … b b a…a b … b a (0) 因为Y1X =X，而R 所在 * a a … a a … a 行中X对应的列全a，所以至少这 两行中Y1对应的列全a，故相等。 a a 考察A1对应的列： 因R1行对应的为a，故R 行A1 列也改为a。 * a 假设s=i–1时，R 所在行A1、A2、A(i–1)对应列能够全改为a。 * 当s=i时，有YiAiF，且YiX =XA1A2 … A(i–1) 。 (i–1) 与s=1时的同样道理，根据Ri行的Ai列为a，可将R 行Ai列也改为a。 * 根据归纳法原理，结论成立。 证毕 2018/11/19 数据库系统 YiAiF，且YiX =XA1A2 … A(i–1) 。 (i–1)

103 3、转换为BCNF的无损连接分解——分解法 按自顶向下的方式，从关系模式R<U, F>开始，选择
不是BCNF的模式将其一分为二，直到都为BCNF。（二叉分解） 算法思想: 输入：关系模式R<U, F>； 输出：R的一个分解 ={R1,R2,…Rk}，每个Ri均为 BCNF，且 具有无损连接性； 算法5.5: （1）初始：令={R<U, F>}。 （2）检查：检查各关系模式是否都是BCNF。若是，算法终止。 （3）分解：设中Ri<Ui, Fi>不是BCNF， 正确性证明自己看 则存在XAFi （AX），X不是Ri的关键字； + 对Ri作无损分解：={S1，S2} Ui－X A Ui－X－A 因X不是Ri的关键字，故XA是Ui的真子集， 且容易验证，是Ri的一个无损分解。 X S1<XA> S2<X(Ui－X－A)> a…a a bbb … bb a…a b aaa … aa 以代Ri，返回第(2)步。 a 2018/11/19 数据库系统

104 定理：设关系模式为R<U, D>，其中D为R中函数依赖和多值依赖的集合， 则 XY成立
4、转换为4NF的无损连接分解 定理：设关系模式为R<U, D>，其中D为R中函数依赖和多值依赖的集合， 则 XY成立 R的分解  ={ R1<XY>，R2 <XZ> }具有无损连接性， 其中Z=U－X－Y。 证明：充分性。要证 若 是无损连接，则XY成立。 多值依赖的定义： 多值依赖XY成立当且仅当对R(U)的任一关系r，若存在元组s、t 使得s[X]=t[X]，则必存在元组w、vr（w、v可以与s、t相同），使得 w[X]=v[X]=t[X]，而w[Y]=t[Y]，w[Z]=s[Z]，v[Y]=s[Y]，v[Z]=t[Z]。 交换s、t的Y值 所得新元组仍在r中 2018/11/19 数据库系统

105 t[Z] s[Z] s[Y] t[Y] t[Z] s[Z] s[Y] t[Y]
4、转换为4NF的无损连接分解 定理：设关系模式为R<U, D>，其中D为R中函数依赖和多值依赖的集合， 则 XY成立 R的分解  ={ R1<XY>，R2 <XZ> }具有无损连接性， 其中Z=U－X－Y。 证明：充分性。要证 若 是无损连接，则XY成立。 欲证：对R的任一关系r，若t、sr，且t[X]=s[X]，则存在u、vr使得 u[X]=v[X]=t[X]，而u[Y]=t[Y]，u[Z]=s[Z]，v[Y]=s[Y]，v[Z]=t[Z]。 因为 是无损连接，对R的任一关系r，有 r =  （r）  （r）。 XY XZ 若t、sr，且t[X]=s[X]，  （r） XY  （r） XZ 关系r： t s X Z t[Z] s[Z] t s X Y Z s[Y] t[Y] t[Z] s[Z] t s X Y s[Y] t[Y] 2018/11/19 数据库系统

106 s[Y] t[Y] t[Z] s[Z] t[Y] s[Y] t[Z] s[Z]
 （r） XY XZ t s X Y s[Y] t[Y] X Z t[Z] s[Z] 若t、sr，且t[X]=s[X]， 令 u = t[X]•t[Y]•s[Z]， v = s[X]•s[Y]•t[Z]， 则 u、vr满足u[X]=v[X]=t[X]， 而u[Y]=t[Y]，u[Z]=s[Z]， v[Y]=s[Y]，v[Z]=t[Z]。 所以 XY成立。 X Y Z t[Y] s[Y] t[Z] s[Z] s 必要性。要证 若XY成立，则 是无损连接。 t 欲证：对R的任一关系r，有 r =  （r）  （r）。 XY XZ u 而 r   （r）  （r）显然成立， XY XZ v 故只需证 r  （r）  （r） XY XZ （自己证） r =  （r）  （r） XY XZ 证毕 2018/11/19 数据库系统

107 说明：上述定理是在函数依赖和多值依赖的范畴内讨论问题，因此需要 建立一套新的公理系统来保证“逻辑蕴涵”和“导出”仍是等价的。
幸运的是，只要简单扩充Armstrong公理系统（增加关于多值依赖的 公理），该公理系统仍是有效的和完备的。 转换为4NF的无损连接分解算法: 以算法5.5作为第一步，规范化到4NF时方法也同算法5.5 （二叉分解）。 输入：关系模式R<U, D>； 输出：R的一个分解 ={R1,R2,…Rk}，每个Ri均为4NF， 且 具有无损连接性； 算法5.6: （1）用算法5.5先将R分解到BCNF，且具有无损连接性。 （2）对其中没达到4NF的模式，根据前面定理分解，直到所有模式都 为4NF时为止。 2018/11/19 数据库系统

108 作业： X 本节开头 本章开头 P196 习题 2、3、12 补充：
1、设F={ ACPE，PGA，BCE，AP，GAB，GCA， PABG，AEGB，DPH }， X=AG， 求 X + F 2、设有关系模式 R（ABCDE），R的函数依赖集为 F={AC，BC，CD，DEC，CEA}， （1）设 ={ R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE) } 是R的一个分解。试判断是否为无损分解。 （2）给出R的一个既保持函数依赖又具有无损连接的3NF分解。 本节开头 本章开头 2018/11/19 数据库系统