第4章 关系规范化理论.pptx

《第4章 关系规范化理论.pptx》由会员分享，可在线阅读，更多相关《第4章 关系规范化理论.pptx（141页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4章章 关系规范化理论关系规范化理论 23:54:501主要内容主要内容4.1问题的提出的提出4.2 函数依函数依赖和范式和范式4.3 数据依数据依赖的公理系的公理系统4.4 关系模式的分解方法关系模式的分解方法223:54:50第一讲第一讲问题的提出函数依赖和范式23:54:5034.14.1问题的提出问题的提出4关系数据关系数据库的的规范化理范化理论如何构如何构造合适造合适的数据的数据模式？模式？如何如何优化不好化不好的关系的关系模式模式如何判如何判定关系定关系模式模式R的的优劣劣23:54:50概念回顾概念回顾关系：描述实体、属性、实体间的联系。从形式上看，它是一张二维表，是所涉及属

2、性的笛卡尔积的一个子集。关系模式：用来定义关系。关系数据库：基于关系模型的数据库，利用关系来描述现实世界。从形式上看，它由一组关系组成。关系数据库的模式：定义这组关系的关系模式的全体。23:54:505关系模式的形式化定义关系模式的形式化定义关系模式由五部分组成，即它是一个五元组：关系模式由五部分组成，即它是一个五元组：R(U,D,DOM,I，F)R：关系名关系名U：组成该关系的属性名集合组成该关系的属性名集合D：属性组属性组U中属性所来自的域中属性所来自的域DOM：属性向域的映象集合：属性向域的映象集合I：一组完整性约束条件一组完整性约束条件F：属性间数据的依赖关系集合属性间数据的依赖关系集

3、合23:54:506什么是数据依赖什么是数据依赖1.完整性约束的表现形式完整性约束的表现形式限定属性取值范围：例如学生成绩必须在限定属性取值范围：例如学生成绩必须在0-100之间之间定义属性定义属性值值间的相互关连（主要体现于值的间的相互关连（主要体现于值的相相等与否等与否），这就是数据依赖，它是数据库模式），这就是数据依赖，它是数据库模式设计的关键设计的关键23:54:507什么是数据依赖（续）什么是数据依赖（续）2.数据依赖数据依赖是通过一个关系中属性间值的相等与否体现出来是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系的数据间的相互关系是现实世界属性间相互联系的抽象是现实世界

4、属性间相互联系的抽象是数据内在的性质是数据内在的性质是是语义语义的体现的体现23:54:5084.14.1问题的提出问题的提出9数据依数据依赖：关系：关系中属性中属性间互相依互相依存、互相制存、互相制约的的关系。关系。函数依函数依赖、多、多值依依赖、连接依接依赖、分、分层依依赖和和相互依相互依赖函数依函数依赖极极为普普遍的存在于遍的存在于现实生活中生活中如：学生（学如：学生（学号，姓名，系号，姓名，系名）名）学号学号姓名姓名学号学号系名系名基本概念：基本概念：23:54:50四、关系模式的简化表示四、关系模式的简化表示关系模式关系模式R（U,D,DOM,I，F）简化为一个三元组：简化为一个三元

5、组：R（U,F）当且仅当当且仅当U上的一个关系上的一个关系r 满足满足F时，时，r称为关系称为关系模式模式 R（U,F）的一个）的一个关系关系23:54:5010泛关系模式实例泛关系模式实例如果把现实问题的所有属性组合成一个关系模式如果把现实问题的所有属性组合成一个关系模式R（U），则这个关系模式就称为泛关系模式。），则这个关系模式就称为泛关系模式。例：研究生管理系统包含的对象有：研究生的学例：研究生管理系统包含的对象有：研究生的学号、姓名、学院名称、院长、项目编号、项目名号、姓名、学院名称、院长、项目编号、项目名称、承担任务、导师姓名称、承担任务、导师姓名23:54:5011泛关系模式实例泛

6、关系模式实例研究生管理系统的语义：研究生管理系统的语义：学院中包含若干研究生，某个研究生只能属于固学院中包含若干研究生，某个研究生只能属于固定的一个学院；定的一个学院；学院的院长是主要负责人且只有一个；学院的院长是主要负责人且只有一个；每个研究生可以承担多个项目，每个项目可以由每个研究生可以承担多个项目，每个项目可以由多个研究生共同参与，研究生选定项目后要承担多个研究生共同参与，研究生选定项目后要承担相应的任务；相应的任务；每个研究生只能选择一个导师，一个导师可以带每个研究生只能选择一个导师，一个导师可以带若干名研究生。若干名研究生。23:54:501213U=学号、姓名、导师姓名学号、姓名、

7、导师姓名、学院名称、院长、项目编号、项目名称、承担、学院名称、院长、项目编号、项目名称、承担任务任务4.1.1 一个泛关系模式的实例学号学号项目目编号号学院名称学院名称院院长承担任承担任务项目名称目名称导师姓名姓名姓名姓名F=学号学号姓名，姓名，学号学号导师姓名，导师姓名，学号学号学院名称，学院名称学院名称，学院名称 院长院长，项目编号，项目编号项目名称项目名称,（学号，项目编号）（学号，项目编号）承担任务承担任务23:54:50学号学号姓名姓名学院名称学院名称院院长项 目目 编号号项目名称目名称承承 担担 任任务导 师 姓姓名名20082401周黎明计算机学院李 洲彤0042提升机稳定性研究

8、实验分析贺信维20082402李毅先计算机学院李 洲彤0042提升机稳定性研究系统设计张琦20082402李毅先计算机学院李 洲彤0052多维数据分析研究软件编码萨林20083401王鑫鑫数学学院吴 兆民0091定理证明自动化研究软件编码刘玉琴20083402何飞雨数学学院吴 兆民0083最大熵原理研究软件编码刘玉琴20083403杨宇奇数学学院吴 兆民0083最大熵原理研究实验分析实验分析刘坤鹏144.1.1 一个泛关系模式的实例问题：关系的主码是什么？问题：关系的主码是什么？23:54:50（1）项目名称（2）学院名称、院长缺点：1、冗余太大1）插入异常2）删除异常 3）修改异常2、操作异

9、常学号学号姓名姓名学院名称学院名称院院长项目目编号号项目名称目名称承担任承担任务导师姓名姓名20082401周黎明计算机学院李洲彤0042提升机稳定性研究实验分析贺信维20082402李毅先计算机学院李洲彤0042提升机稳定性研究系统设计张琦20082402李毅先计算机学院李洲彤0052多维数据分析研究软件编码萨林20083401王鑫鑫数学学院吴兆民0091定理证明自动化研究软件编码刘玉琴20083402何飞雨数学学院吴兆民0083最大熵原理研究软件编码刘玉琴20083403杨宇奇数学学院吴兆民0083最大熵原理研究实验分析实验分析刘坤鹏154.1.1 一个泛关系模式的实例23:54:50关系

10、模式S_D_P是不好的设计，需要改造。改造方法？关系模式分解4.1.2 4.1.2 改造泛关系模式改造泛关系模式S_D_PS_D_P23:54:5016第第1 1种分解方法种分解方法-消除项目信息的冗余消除项目信息的冗余S_D（学号，姓名，学院名称，院长，导师姓名）P（项目编号，项目名称）S_P（学号，项目编号，承担任务）17导师姓名姓名院院长学院名称学院名称学号学号姓名姓名项目目编号号项目名称目名称学号学号项目目编号号承担任承担任务4.1.2 改造泛关系模式S_D_P23:54:50第第1 1种分解方法种分解方法-消除项目信息的冗余消除项目信息的冗余S_D（学号，姓名，学院名称，院长，导师姓

11、名）P（项目编号，项目名称）S_P（学号，项目编号，承担任务）18优点2：解决学生和项目信息的更新异常4.1.2 改造泛关系模式S_D_P优点1：消除部分冗余数据 缺点：数据冗余与更新异常问题依然存在！23:54:50第第2 2种分解方法种分解方法S（学号，姓名，学院名称，导师姓名）P（项目编号，项目名称）S_MN（学号，院长）S_P（学号，项目编号，承担任务）19消除冗余数据，但丢失数据依赖关系 导师姓名姓名学院名称学院名称学号学号姓名姓名项目目编号号项目名称目名称学号学号项目目编号号承担任承担任务学号学号院院长23:54:50第第3 3种分解方法种分解方法 S（学号，姓名，学院名称，导师姓

12、名）P（项目编号，项目名称）D（学院名称，院长）T（承担任务）20消除了冗余数据，但消除了冗余数据，但丢失了信息。失了信息。导师姓名姓名学院名称学院名称学号学号姓名姓名项目目编号号项目名称目名称承担任承担任务学院名称学院名称院院长问题：如何：如何查询某个研究生在某个某个研究生在某个项目中承担了什么任目中承担了什么任务？23:54:50第第4 4种分解方法种分解方法 S（学号，姓名，学院名称、导师姓名）P（项目编号，项目名称）D（学院名称，院长）S_P（学号，项目编号，承担任务）21消除冗余，保持数据依赖，保证信息不丢失 导师姓名姓名学院名称学院名称学号学号姓名姓名项目目编号号项目名称目名称学号

13、学号项目目编号号承担任承担任务学院名称学院名称院院长23:54:504.1.3 4.1.3 存在问题的原因存在问题的原因数据内部的联系表现为同一关系模式中各个属性间的数据内部的联系表现为同一关系模式中各个属性间的依赖关系。即数据依赖依赖关系。即数据依赖对数据依赖的不恰当处理对数据依赖的不恰当处理是产生数据冗余和操作异常是产生数据冗余和操作异常的重要原因的重要原因.22一个关系中各一个关系中各属性之间属性之间可能可能是相互关联是相互关联的，而这种的，而这种关联有关联有“强强”有有“弱弱”，有直接关联，也有间接关，有直接关联，也有间接关联。联。不从语义上研究和考虑属性子集间的这种关联不从语义上研究

14、和考虑属性子集间的这种关联,简简单地将各种属性单地将各种属性随意地编排在一起随意地编排在一起，形成泛关系模，形成泛关系模式。式。23:54:50解决的方法解决的方法将关系模式进一步分解将关系模式中的属性按照一定的约束条件重新分组，争取“一个关系模式只描述一个独立的一个关系模式只描述一个独立的实体实体”，使得逻辑上独立的信息放在独立的关系模式中，即进行关系模式的规范化处理。2323:54:504.1.4 4.1.4 规范化理论的提出规范化理论的提出设计好的数据库模式的根本方法：设计好的数据库模式的根本方法：分析和掌握属性间的语义关联，再依据这些关联得到相应的设计方案不是任意一种关系模式设计方案都

15、是合适的、满足应用环境的需要的。2423:54:514.1.4 4.1.4 规范化理论的提出规范化理论的提出属性间的依赖关系（关联关系）属性间的依赖关系（关联关系）多对一多对一25函数依赖函数依赖 多值连接依赖关系多值连接依赖关系 连接依赖关系连接依赖关系一对多一对多将属性之间的关联分为若干等级，形成将属性之间的关联分为若干等级，形成“规范化规范化”理论理论23:54:514.1.4 4.1.4 规范化理论的提出规范化理论的提出“关系规范化关系规范化”理论包含两个核心的问题：理论包含两个核心的问题：一、如何判断关系模式中存在的问题。一、如何判断关系模式中存在的问题。通过分析关系模式中的数据依赖

16、关系，判断关系模式的“范式”级别，从而得到这种模式中可能存在的数据冗余和操作异常问题；二、如何解决关系模式中存在的问题，即对关系模、如何解决关系模式中存在的问题，即对关系模式进行分解。式进行分解。如何分解？“关系规范化”理论为解决这些问题提供了理论依据和相应的算法。2623:54:5127数据依赖包括：数据依赖包括：函数依赖、多值依赖、连接依赖、分层依赖、函数依赖、多值依赖、连接依赖、分层依赖、相互依赖相互依赖 4.2 函数依赖和范式函数依赖和范式函数依赖函数依赖是最常见、最重要的一种数据依赖是最常见、最重要的一种数据依赖23:54:51284.2.1函数依赖的概念：函数依赖的概念：属性或属性

17、组之间可能存在的依赖性。属性或属性组之间可能存在的依赖性。1、定义 定义定义4.14.1：设R(U)是属性集U上的关系模式。X，Y是U的子集。若对于R(U)的任意一个可能的关系r，r 中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作XY。4.2 函数依赖和范式函数依赖和范式23:54:5129或者说：或者说：设R(U)是一个关系模式，X，Y是U的子集，对于R中X的每一个值都有Y的唯一值与之对应，则称X函数确定Y或Y函数依赖于X，记作XY。或者说：或者说：关系模式R(U)的任一具体关系，属性集X在任意元组上的值能唯一决定属性集Y在该元组上的值，

18、则称X函数确定Y或Y函数依赖于X，记作XY。4.2.1函数依赖的概念函数依赖的概念23:54:51XY中X与Y是一对多还是多对一？例：例：U=学号、姓名、学院名称、院长、项目编号、学号、姓名、学院名称、院长、项目编号、项目名称、承担任务、导师姓名项目名称、承担任务、导师姓名问题：存在哪些事实关系？试给出其上的函数依赖。问题：存在哪些事实关系？试给出其上的函数依赖。并说明各个函数依赖的语义。并说明各个函数依赖的语义。F=学号学号姓名，姓名，学号学号导师姓名，导师姓名，学号学号-学院名称，学院名称，学院名称学院名称 院长院长，项目编号，项目编号项目名称项目名称,（学号，项（学号，项目编号）目编号）

19、承担任务承担任务4.2.1函数依赖的概念函数依赖的概念23:54:5130注意：注意：R上的函数依赖对于关系中的所有实体都必须满足，上的函数依赖对于关系中的所有实体都必须满足，即使有一个特例的存在，也认为这个函数依赖不即使有一个特例的存在，也认为这个函数依赖不成立。成立。函数依赖不是指关系模式函数依赖不是指关系模式R的某个或某些关系满足的某个或某些关系满足的条件，而是指的条件，而是指R的一切关系均要满足的约束条件。的一切关系均要满足的约束条件。4.2.1函数依赖的概念函数依赖的概念姓名姓名学院院长学院院长 是否成立是否成立？23:54:5131由定义可以导出下列概念：1.1.决定因素：决定因素

20、：若X Y，则X叫做决定因素 2.2.平凡的函数依赖：平凡的函数依赖：X Y，Y X，则称XY是平凡的函数依赖。3.3.非平凡的函数依赖非平凡的函数依赖:X Y，且X不包含Y，则称XY是非平凡的函数依赖。4.4.互相依赖：互相依赖：若XY，YX，则记作X Y。324.2.1函数依赖的概念函数依赖的概念5.5.若若Y Y不函数依赖于不函数依赖于X X，则记作X Y。23:54:51 定义定义4.2：完全函数依赖：完全函数依赖：在R(U)中，如果X Y，并且对于X的任何一个真子集X，都有X Y，则称Y对X完全函数依赖。记作：33FXY 定义定义4.3：部分函数依赖部分函数依赖 在R(U)中，如果X

21、 Y，并且对于X的一个真子集X，有X Y，则称Y对X部分函数依赖。记作：PXY定义定义4.44.4：传递函数依赖传递函数依赖 在R(U)中，如果X Y，(Y X)，Y X，Y Z，则称Z对X传递函数依赖。函数依赖的类型函数依赖的类型23:54:5134学院学院院长院长成绩成绩 学号学号课程号课程号课程名课程名4.2.1函数依赖的概念函数依赖的概念23:54:52354.2.1函数依赖的概念函数依赖的概念例：设车间考核职工完成生产定额关系WW(日期，工号，姓名，工种，超额，定额，车间，车间主任)F(工号姓名，工号工种，工种定额，工号车间，车间车间主任，日期、工号超额)23:54:5236工号日期

22、姓名超额车间主任车间定额工种函数依赖图：F(工号姓名，工号工种，工种定额，工号车间，车间车间主任，日期、工号超额)关系的主码：关系的主码：工号工号+日期日期23:54:5237分析：完全函数依赖完全函数依赖部分函数依赖部分函数依赖部分函数依赖部分函数依赖23:54:52定义4.5：设K为R(U，F)中的属性或属性组，若 ，则K为R的候选码候选码。38FKU主码：主码：若候选码多于一个，则选定其中的一个为主码。主属性：主属性：包含在任何一个侯选码中的属性。非主属性：非主属性：不包含在任何码中的属性。4.2.2 码的函数依赖定义码的函数依赖定义23:54:524.2.2 4.2.2 码的函数依赖定

23、义码的函数依赖定义例：关系例：关系（歌手，歌曲，听众）的候（歌手，歌曲，听众）的候选码是什么？选码是什么？全码全码：整个属性组是码。23:54:5239定义定义4.6:4.6:关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外码外码主码与外码提供了一个表示关系间联系的手段4.2.2 码的函数依赖定义码的函数依赖定义23:54:524041 一个低一级范式的关系模式，通过模式分解可一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，以转换为若干个高一级范式的关系模式的集合，这种过程就叫做规范化。这种过程就叫做规范化。1971E.F.Cod

24、d 提出范式概念1NF 2NF 3NF BCNF 4NF 5NF5NF 4NF BCNF 3NF 2NF 1NF 范式表示关系模式满足的某种级别。4.2.3范式范式1 1、第一范式、第一范式(1NF)(1NF)定义：满足关系的每一个分量是不可分的数据项这一条件的关系模式就属于第一范式(1NF)。42解决方法：用原子属性取代复合属性解决方法：用原子属性取代复合属性1 1、第一范式、第一范式(1NF)(1NF)学号学号项目目编号号000101020300020203学号学号项目目编号号000101000102000103000202000203问题：存在多值属性，不属于1NF解决方法：将多值属性拆

25、分（1）项目编号（2）学院名称、院长缺点：1、冗余太大1）插入异常2）删除异常 3）修改异常2、操作异常学号学号姓名姓名学院名称学院名称院院长项目目编号号项目名称目名称承担任承担任务导师姓名姓名20082401周黎明计算机学院李洲彤0042提升机稳定性研究实验分析贺信维20082402李毅先计算机学院李洲彤0042提升机稳定性研究系统设计张琦20082402李毅先计算机学院李洲彤0052多维数据分析研究软件编码萨林20083401王鑫鑫数学学院吴兆民0091定理证明自动化研究软件编码刘玉琴20083402何飞雨数学学院吴兆民0083最大熵原理研究软件编码刘玉琴20083403杨宇奇数学学院吴兆

26、民0083最大熵原理研究实验分析实验分析刘坤鹏441 1、第一范式、第一范式(1NF)(1NF)定义：若R1NF，且每一个非主属性完全函数依赖于码，则R2NF。452 2、第二范式、第二范式(2NF)(2NF)U=学号、姓名、学院名称、院长、项目编号、项目名称、承担任务、学号、姓名、学院名称、院长、项目编号、项目名称、承担任务、导师姓名导师姓名学号学号项目目编号号学院名称学院名称院院长承担任承担任务项目名称目名称导师姓名姓名姓名姓名存在非主属性对码存在非主属性对码的部分函数依赖的部分函数依赖462 2、第二范式、第二范式(2NF)(2NF)S_P（学号，项目编号，承担任务）导师姓名姓名院院长学

27、院名称学院名称学号学号姓名姓名项目目编号号项目名称目名称学号学号项目目编号号承担任承担任务S_D（学号，姓名，学院名称，院长，导师姓名）P（项目编号，项目名称）2NF2NF2NF关系关系S_D依然存在冗余和操作异常依然存在冗余和操作异常！473 3、第三范式、第三范式(3NF)(3NF)导师姓名姓名院院长学院名称学院名称学号学号姓名姓名3 3、第三范式、第三范式(3NF)(3NF)即：若即：若R 3NFR 3NF，且每一个非主属性既不部分依赖，且每一个非主属性既不部分依赖于码也不传递依赖于码。于码也不传递依赖于码。若若R 2NFR 2NF，且每一个非主属性不传递依赖于，且每一个非主属性不传递依

28、赖于码，则码，则R 3NFR 3NF。3 3、第三范式、第三范式(3NF)(3NF)导师姓名姓名学院名称学院名称学号学号姓名姓名院院长学院名称学院名称S（学号，姓名，学院名称，导师姓名）D（学院名称，院长）3NF3NFS_P（学号，项目编号，承担任务）P（项目编号，项目名称）3NF分解后的关系模式，减小分解后的关系模式，减小了冗余，消除了操作异常了冗余，消除了操作异常例：项目(编号，项目名称，负责人，职务，成员，任务情况)(假设:负责人无重名情况）50编号编号成员成员负责人负责人项目名称项目名称任务情况任务情况职务职务规范化举例规范化举例主码：（编号，成员）1NF问题：你能分析出关系模式存在的

29、问题吗？举例说明51任务（编号，成员，任务情况）任务（编号，成员，任务情况）项目（编号，项目名称，负责人，职务项目（编号，项目名称，负责人，职务）编号编号成员成员任务情况任务情况编号编号负责人负责人项目名称项目名称职务职务任务任务项目项目分解为分解为2NF结论：消除了非主属性对码的部分依赖结论：消除了非主属性对码的部分依赖规范化举例规范化举例52编号编号成成 员员任务情况任务情况任务任务编号编号负责人负责人项目名称项目名称项目项目负责人负责人职务职务负责人职务分解为分解为3NF结论：进一步消除了非主结论：进一步消除了非主属性对码的传递依赖属性对码的传递依赖规范化举例规范化举例53凡是满足3NF

30、的关系，一般都能获得满意的效果。但是某些情况下，3NF仍会出现问题。原因是没有对主属性与关键字之间给出任何限制，如果出现主属性部分或传递依赖于主属性部分或传递依赖于KEY，则也会使关系性能变坏3NF3NF存在问题吗？存在问题吗？544、BCNF(扩充的扩充的3NF)55一个满足BCNF的关系模式有:所有非主属性对每一个码都是完全函数依赖。所有非主属性对每一个码都是完全函数依赖。所有主属性对每一个不包含它的码也是完全函数依所有主属性对每一个不包含它的码也是完全函数依赖。赖。没有任何属性完全函数依赖于非码的任何一组属性。没有任何属性完全函数依赖于非码的任何一组属性。4、BCNF(扩充的扩充的3NF

31、)例：例：关系模式SJP（S，J，P）S：学生 学生选修课程有一定的名次 J：课程 每门课程中每一名次只有一个学生 P：名次 （名次没有并列）564、BCNF(扩充的扩充的3NF)函数依赖：（S，J）P 分析得知：SJP 3NF SJP BCNF（J，P）S例：例：关系模式STJ（S，T，J）S：学生 某一学生选定某门课，就对应一个固定教师 T：教师 每个教师只教一门课 J：课程 每门课有若干教师 函数依赖：（S，J）T，（S，T）J，TJ分析得知：STJ 3NF但是：STJ BCNF 因为：T J，而T不是码 STJ可以分解为：ST（S，T）TJ（T，J）574、BCNF(扩充的扩充的3NF

32、)判断题：（）若关系中所有的属性均为主属性，则关系至少可以达到NF？（）若关系为双目关系，则至少可以达到BCNF？（）若每个决定因素都是单属性，则至少可以达到NF？（4）若每个码都是单属性，则R至少可以达到2NF？593NF3NF与与BCNFBCNF的关系的关系 如果一个关系数据库中的所有关系模式都属于BCNF，那么在函数依赖范畴内，它已实现了模式的彻底分解，达到了最高的规范化程度，消除了插入异常和删除异常。如果关系模式RBCNF，必定有R3NF。如果R3NF，且R只有一个候选码，则R必属于BCNF。4.24.2规范化小结规范化小结消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖消

33、除非主属性对码的传递函数依赖消除非主属性对码的传递函数依赖消除主属性对码的部分和传递函数依赖消除主属性对码的部分和传递函数依赖1NF1NF2NF2NF3NF3NFBCNFBCNF消除消除决定决定因素因素非码非码的非的非平凡平凡函数函数依赖依赖关系模式规范化的基本步骤关系模式规范化的基本步骤规范化的基本思想规范化的基本思想消除不合适的数据依赖消除不合适的数据依赖使得各关系模式达到某种程度的使得各关系模式达到某种程度的“分离分离”采用采用“一事一地一事一地”的模式设计原则的模式设计原则 让一个关系描述一个概念、一个实体或者实体间的一种让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个

34、概念就把它联系。若多于一个概念就把它“分离分离”出去出去所谓规范化实质上是概念的单一化所谓规范化实质上是概念的单一化614.24.2规范化小结规范化小结62指出下列关系模式属于第几范式，并说明理由指出下列关系模式属于第几范式，并说明理由(1)R（X,Y,Z）FXY Z(2)R（X,Y,Z）FY Z,XZ Y(3)R（X,Y,Z）FY Z,Y X,X YZ课堂问答题课堂问答题4.3.1 函数依赖集的闭包函数依赖集的闭包4.3.2 函数依赖的推理规则函数依赖的推理规则4.3.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件4.3.4 Armstrong公理的正确性和完备性公理的正

35、确性和完备性4.3.5 函数依赖集的等价和最小函数依赖集函数依赖集的等价和最小函数依赖集634.3 数据依赖的公理系统数据依赖的公理系统1、函数依赖集、函数依赖集F的逻辑蕴含的逻辑蕴含定义：对于R(U,F)，如果XY不在F中，但是对于其任何一个关系r，XY都成立，则称F逻辑蕴含XY。或者说：或者说：XY可以由可以由F导出导出64例：关系模式R(U，F)其中U(A，B，C，D，E，F，G)F(AB，CD，ABE，FG)问：F是否逻辑蕴含AE4.3.1 函数依赖集的闭包函数依赖集的闭包2、F的闭包定义：在关系模式R(U，F)中为F及F所逻辑蕴含的函数依赖的全体叫做F的闭包。记为F+。F+=X Y|

36、F及能由F根据Armstrong公理导出65 所有被一个已知函数依赖集F及F逻辑蕴涵的那些函数依赖的集合为F的闭包（Closure），记为F+。4.3.1 函数依赖集的闭包函数依赖集的闭包1 1、ArmstrongArmstrong公理系统公理系统 对于关系模式R(U，F)，有公理公理1：自反律自反律(Reflexivity)(Reflexivity)若Y X U，则XY为F所蕴含。公理公理2：增广律增广律(Augmentation)(Augmentation)若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。公理公理3：传递律传递律(Transitivity)(Transitivity)若XY

37、，YZ为F所蕴含，则XZ为F所蕴含。66自反律、增广律、传递律是最基本的自反律、增广律、传递律是最基本的Armstrong公理。公理。4.3.2 函数依赖的推理规则函数依赖的推理规则公理公理4：合并规则合并规则 由XY，XZ，有XYZ。公理公理5：伪传递规则伪传递规则 由XY，WYZ，有XWZ公理公理6：分解规则分解规则 由XY及 Z Y，有XZ。67由自反律、增广律、传递律可以导出下面三条推理规则。由自反律、增广律、传递律可以导出下面三条推理规则。4.3.2 函数依赖的推理规则函数依赖的推理规则定理定理：Armstrong公理系统是有效的(正确性）、完备的。正确性正确性：指公理1、2、3是正

38、确的。有效性：有效性：指由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+。完备性：完备性：指F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。684.3.4 函数依赖的推理规则函数依赖的推理规则69定理定理4.1根据合并规则和分解规则可以得到：根据合并规则和分解规则可以得到：定理定理4.1 若若Ai(i=1,2,n)是关系模式是关系模式R的属性，的属性，所以所以XA1,A2,An成立的充分必要条件是成立的充分必要条件是XAi均成立。均成立。即：即：XA1A2An成立的充分必要条件是成立的充分必要条件是XAi成立（成立（i=1,2,n）。）。4.3.

39、2 函数依赖的推理规则函数依赖的推理规则70例：关系模式R(U，F)其中U(A，B，C，D，E，F，G)F(AB，CD，ABE，FG)问：F是否逻辑蕴含AE解：解：AB （已知）AAB（增广率）ABE （已知）AE （传递率）4.3.2 函数依赖的推理规则函数依赖的推理规则71例：证明：对R（A，B，C，G，H，I），FAB，AC，CGH，CGI，BH，存在：AH，CGHI，AGI求证：1.由于AB，BH，依传递律，可得AH2.由于CGH，CGI，依合成规则，可得 CGHI3.由于AC，CGI，依伪传递律，可得AGI。也可另证为：由AC，依增广律，得AGCG，又CGI，依传递律，得：AGI4.

40、3.2 函数依赖的推理规则函数依赖的推理规则如何判定属性如何判定属性X X是否为关系是否为关系R R的超码的超码？例：R=A,B,C,G.H,I),F=AB,AC,CGH,CGI,BHAG是否为R的超码？方法1：设计算法求AG可以函数确定的属性集方法2：求F+，找出所有左部为AG的函数依赖，将函数依赖的右部合并。1、X关于函数依赖集F的闭包定义：设F为属性集U上的一组函数依赖，X U，XF+=A|XA能由F根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F的闭包734.3.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件【例】设关系模式R（A、B、C）的函数依

41、赖集为F=A B,B C，分别求A、B、C的闭包。74解：1.求A的闭包若X=A，AB，BC（已知）AC （传递律）AA （自反律）XF+=A，B，C4.3.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件【例】设关系模式R（A、B、C）的函数依赖集为F=A B,B C，分别求A、B、C的闭包。75解：2.求B的闭包 若X=B，BB BC XF+=B，C4.3.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件【例】设关系模式R（A、B、C）的函数依赖集为F=A B,B C，分别求A、B、C的闭包。76解：3.求C的闭包若X=C，CC XF+=C4.3.3 属

42、性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件772.F逻辑蕴涵的充要条件逻辑蕴涵的充要条件定理定理4.2：设F为属性集U上的一组函数依赖，X,Y U，XY能由F根据Armstrong公理导出的充分必要条件是Y XF+。4.3.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件判定判定XY是否能由是否能由F根据根据Armstrong公理导出的问题，公理导出的问题，可以转化为可以转化为求出求出XF+，判定Y是否为XF+的问题。4.3.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件3、求属性集闭包XF+的算法算法：输入：X，F 输出：XF+(1)令

43、X(0)=X，i=0(2)求B,B=A|(V)(W)(VWFVX(i)AW)(3)X(i+1)=BX(i)(4)判断X(i+1)=X(i)吗？(5)若相等或X(i)=U则X(i)就是XF+，算法终止。(6)若否，则i=i+1，返回第(2)步。例例1：已知关系模式R(U，F)，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB求(AB)F+。解：1：X(0)=AB 2：计算X(1)=X(0)C D=ABCD 3：求X(2)=X(1)E B=ABCDE 4：由于X(2)已经等于全部属性集合所以 (AB)F+=ABCDE79找出左部为找出左部为A，B或或AB的函数依赖的函数依赖4.3

44、.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件例例2：已知关系模式R(U，F)，其中U=A，B，C，D，E，F，G，H；F=AD，ABE，BHE，CDH，EC。令X=AE，求X+。解：1：X(0)=AE 2：X(1)=X(0)D C=ACDE 3：X(2)=X(1)D H C=ACDEH 4：X(3)=ACDEH不变，即X(3)=X(2)所以 X+=(AE)+=ACDEH804.3.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件81例3：R（U，F），其中UA，B，C，D，E，I，FAD，ABC，BIC，EDI，CE，求(AC)解：（1）令XAC，则X

45、（0）AC;（2）在F中找出左边是AC子集的函数依赖：AD，CE；（3）X（1）X（0）DEACDE；（4）很明显X（1）X（0）；（5）在F中找左边是ACDE子集的函数依赖：EDI；（6）X（2）X（1）I=ACDEI；（7）虽然X（2）X（1），但是F中未用过的函数依赖的左边属性已没有X（2）的子集，所以停止计算，输出（AC）X（2）ACDEI。4.3.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件对于属性闭包算法的终止条件，下列四种方法是对于属性闭包算法的终止条件，下列四种方法是等价的：等价的：1 X(i+1)=X(i)2 当发现X(i)包含了全部属性时；3 在F中的

46、函数依赖的右部属性中，再也找不到X(i)中未出现过的属性。4 在F中未用过的函数依赖的左部属性中已没有X(i)的子集。824.3.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件83 对对于于给给定定的的关关系系R（A1，A2，An）和和函函数数依依赖集赖集F，可将其属性分为，可将其属性分为4类：类：nL类类 仅出现在仅出现在F的函数依赖左部的属性的函数依赖左部的属性nR类类 仅出现在仅出现在F的函数依赖右部的属性的函数依赖右部的属性nN类类 在在F的函数依赖左右两边均未出现的属性的函数依赖左右两边均未出现的属性nLR类类 在在F的函数依赖左右两边均出现的属性的函数依赖左右两

47、边均出现的属性码值理论码值理论84 定理定理4.3：对于给定的关系模式：对于给定的关系模式R及其函数依赖集及其函数依赖集F，若，若X（X R）是）是L类属性，则类属性，则X一定是一定是R的候选码的的候选码的成员。成员。定理定理4.4：对于给定的关系模式对于给定的关系模式R及其函数依赖集及其函数依赖集F，若，若X（X R）是）是N类属性，则类属性，则X一定是一定是R的候选码的候选码的成员。的成员。4.3.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件求候选码的相关定理求候选码的相关定理85定理定理4.6：对于给定的关系模式：对于给定的关系模式R及其函数依赖集及其函数依赖集F，

48、若，若X（X R）是）是LR类属性，则类属性，则X可能可能是是R的候选的候选码的成员。码的成员。定理定理4.5：对于给定的关系模式对于给定的关系模式R及其函数依赖集及其函数依赖集F，若，若X（X R）是）是R类属性，则类属性，则X必必不在不在任何候选任何候选码中。码中。4.3.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件求候选码的相关定理求候选码的相关定理多属性依赖集候选关键字求解算法多属性依赖集候选关键字求解算法1.将R的所有属性分为L、R、N和LR两类，令X代表L和N类，Y代表LR类2.2.求求X+。若。若X+包含了包含了R的全部属性，则的全部属性，则X为为R的惟一候

49、的惟一候选关键字，转选关键字，转5；否则转；否则转33.在Y中取一属性A，求（XA）+。若它包含R的全部属性，则转4；否则，调换一属性反复进行这一过程，直到试完所有Y中的属性。4.4.如果已找出所有候选关键字，则转如果已找出所有候选关键字，则转5；否则在；否则在Y中依中依次取两个、三个、次取两个、三个、，求它们的属性闭包，直到，求它们的属性闭包，直到其闭包包含其闭包包含R的全部属性的全部属性5.停止，输出结果864.3.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件87设有关系模式R（A，B，C，D，E，P），R的函数依赖集为：F=AD,ED,DB,BC D,DC A,求R

50、的候选码。例例1：因因为为 C，E是是L类类属属性性，P是是N类类属属性性，所所以以CEP包包含在所有候选码中；含在所有候选码中；因为因为 （CEP）ABCDEP；所以所以 CEP是是R的唯一候选码。的唯一候选码。4.3.3 属性集闭包与属性集闭包与F逻辑蕴涵的充要条件逻辑蕴涵的充要条件例例4设有关系模式设有关系模式R（A，B，C，D，E），其上的函），其上的函数依赖集数依赖集:F=ABC,CDE,BD,EA求求1.计算计算B+2.求出求出R的所有候选关键字的所有候选关键字88典型例题等价定义：等价定义：如果如果G+=F+，则称，则称F与与G等价，记为等价，记为F=G。89定理4.7 F+=G