关系数据库的规范化理论课件.ppt

1、第四章第四章 关系数据库的规范化理论关系数据库的规范化理论本章内容本章内容n1、问题的提出、问题的提出n2、函数依赖、函数依赖n3、 关系范式关系范式n4、 函数依赖理论函数依赖理论n5、 关系分解原则关系分解原则4.1 问题的提出问题的提出学号学号姓名姓名年龄年龄性别性别系名系名系主任系主任课程名课程名成绩成绩011121王强王强19男男计算机计算机王金喜王金喜操作系统操作系统87011132李琳李琳18女女信息信息刘成刘成数据结构数据结构90020923刘过刘过19男男信息信息刘成刘成C语言语言97021206张克张克20男男数学数学刘国民刘国民高等数学高等数学88021511吴雯吴雯18

2、女女计算机计算机王金喜王金喜软件工程软件工程76出现的问题：出现的问题：1、数据冗余、数据冗余2、修改异常、修改异常3、插入异常、插入异常4、删除异常、删除异常例：教学关系例：教学关系S1实例实例出现问题的原因出现问题的原因：有太多相互之间相联系的属性保存在了同一个关系模有太多相互之间相联系的属性保存在了同一个关系模式中，这就造成因一种信息被捆绑在其他信息上而产式中，这就造成因一种信息被捆绑在其他信息上而产生的信息之间相互依附存储的问题生的信息之间相互依附存储的问题数据依赖数据依赖n解决问题的方法解决问题的方法：将相互之间有太多依赖关系的属性分别存放在不将相互之间有太多依赖关系的属性分别存放在

3、不同的关系中。同的关系中。n分解后的三个关系分解后的三个关系学号学号姓名姓名年龄年龄性别性别系名系名011121王强王强19男男计算机计算机011132李琳李琳18女女信息信息020923刘过刘过19男男信息信息021206张克张克20男男数学数学021511吴雯吴雯18女女计算机计算机系名系名系主任系主任计算机计算机王金喜王金喜信息信息刘成刘成信息信息刘成刘成数学数学刘国民刘国民计算机计算机王金喜王金喜学号学号课程名课程名成绩成绩011121操作系统操作系统87011132数据结构数据结构90020923C语言语言97021206高等数学高等数学88021511软件工程软件工程76学生学生

4、S1系系 S2选修选修 S34.2关系模式的函数依赖关系模式的函数依赖n4.2.1 函数依赖的相关定义函数依赖的相关定义n（1）函数依赖）函数依赖n定义定义4.1 设一个关系为设一个关系为R（U），），X、Y是属性集是属性集U的子集。若对于元组的子集。若对于元组中中X上的每个值都有上的每个值都有Y上的一个唯一值与之对应，上的一个唯一值与之对应， 则称则称X和和Y具有函数具有函数依赖关系，并称依赖关系，并称X函数决定函数决定Y，或称，或称Y函数依赖于函数依赖于X，记作，记作XY，称，称X为为决定因素决定因素。（同书上的概念。（同书上的概念p106)n例例1：设一个职工关系为（：设一个职工关系为（

5、职工号职工号，姓名，性别，年龄，职称），姓名，性别，年龄，职称） 职工号职工号为决该函数依赖的决定因素为决该函数依赖的决定因素 例例2： U=（学号，姓名，性别，班级，系，课程号，成绩）（学号，姓名，性别，班级，系，课程号，成绩） 则其函数依赖情况是：则其函数依赖情况是： F学号学号姓名，学号姓名，学号性别，学号性别，学号班级，学号班级，学号系，班级系，班级系，系，（学号，课程号）（学号，课程号）成绩成绩 注意：几点说明注意：几点说明4.2.2 函数依赖的类型函数依赖的类型n（1）平凡函数依赖与非平凡函数依赖）平凡函数依赖与非平凡函数依赖n定义定义4.3 对于函数依赖对于函数依赖XY,如果满足

6、如果满足 ，则称，则称此函数依赖为非平凡函数依赖，此函数依赖为非平凡函数依赖， 否则称之为平凡函数否则称之为平凡函数依赖。依赖。n例如：例如：学号学号姓名，学号姓名，学号性别，（学号，课程号）性别，（学号，课程号）成绩成绩 等都是非平凡函数依赖。等都是非平凡函数依赖。n例如：例如： （学号，课程号）（学号，课程号）学号，（学号，课程号）学号，（学号，课程号）课程号课程号 是平凡函数依赖是平凡函数依赖n对于任一关系模式，平凡函数依赖必然是成立的。对于任一关系模式，平凡函数依赖必然是成立的。n通常讨论的都是非平凡函数依赖。通常讨论的都是非平凡函数依赖。YXYXn（2）完全函数依赖与部分函数依赖）完

7、全函数依赖与部分函数依赖n定义定义4.4 对于函数依赖对于函数依赖XY，若，若Y函数依赖于函数依赖于X，但不依赖于，但不依赖于X的任的任意一个真子集意一个真子集 ，则称，则称Y完全函数依赖于完全函数依赖于X。记作：。记作：n n例：（学号，课程号）例：（学号，课程号） 成绩成绩 n定义定义4.4 若若Y函数依赖于函数依赖于X，但并非完全依赖于，但并非完全依赖于X，则称，则称Y部分函数依赖于部分函数依赖于X，或称，或称Y函数依赖于函数依赖于X的某个真子集。的某个真子集。n记作：记作：n例：（学号，课程号）例：（学号，课程号）姓名姓名n（学号，课程号）（学号，课程号） 姓名，而对于每个学生都有唯一

8、的学号值，所姓名，而对于每个学生都有唯一的学号值，所以以 学号学号姓名。因此（学号，课程号）姓名。因此（学号，课程号） 姓名姓名 是部分函数依赖。是部分函数依赖。XXFXY PXY P F n（3）传递函数依赖）传递函数依赖n定义定义4.5 如果如果XY，（，（ ），）， ， YZ，则称，则称Z传递依赖于传递依赖于X。记作：记作：n例：学号例：学号班级，班级班级，班级系，学号系，学号 系系n例：有以下班级关系：例：有以下班级关系：n班级（班级（班号班号，专业名，系名，人数，入学年份），专业名，系名，人数，入学年份）n其中，主码是班号。其中，主码是班号。 n经分析，有：班号经分析，有：班号专业名

9、，班号专业名，班号人数，班号人数，班号入入学年份，专业名学年份，专业名系名。系名。n又因为：班号又因为：班号专业名，专业名专业名，专业名 班号，专业名班号，专业名系名，所以有：班号系名，所以有：班号 系名。系名。YXYXTXZ T T FKU 4.2.3 关键字的相关定义关键字的相关定义n1、关键字、关键字n定义：在关系模式R（U）中，若 ，且满足 ，则称K为R的候选键或候选关键字。n2、候选关键字、主关键字、候选关键字、主关键字n3、主属性、非主属性、主属性集、非主、主属性、非主属性、主属性集、非主属性集属性集KU4.2.4 函数依赖的推理规则n1、函数依赖的逻辑蕴涵n2、Armstrong

10、 公理系统n3、函数依赖推理规则的完备性n4、闭包的计算n4.2 函数依赖理论函数依赖理论n一个关系模式可能存在很多个函数依赖，它们构一个关系模式可能存在很多个函数依赖，它们构成了该关系模式的函数依赖集。成了该关系模式的函数依赖集。n该集合是很大的该集合是很大的,如果仅依靠语义分析的方法去找如果仅依靠语义分析的方法去找出一个关系模式的所有函数依赖是一件很不出一个关系模式的所有函数依赖是一件很不 容易容易的事情，实际上也没有必要。的事情，实际上也没有必要。n1,逻辑蕴涵：用推理的方法，从一个已知的函数依逻辑蕴涵：用推理的方法，从一个已知的函数依赖集去推导出另一个函数依赖集，这样两个函数赖集去推导

11、出另一个函数依赖集，这样两个函数依赖集之间的互为因果关系称之为逻辑蕴涵。依赖集之间的互为因果关系称之为逻辑蕴涵。n因此，我们给出一个函数依赖集闭包的定义。因此，我们给出一个函数依赖集闭包的定义。n定义：所有被一个已知函数依赖集（定义：所有被一个已知函数依赖集（F）逻辑蕴涵的那些函数依赖的集合称为逻辑蕴涵的那些函数依赖的集合称为F的的闭包。闭包。nP109n如何由一个已知函数依赖集找出它的闭如何由一个已知函数依赖集找出它的闭包呢？包呢？1974年，年，Armstrong提出了用提出了用推理方法计算闭包的一套规则，具体包推理方法计算闭包的一套规则，具体包括三个推理规则和三条推论，及一定的括三个推理

12、规则和三条推论，及一定的算法。算法。n函数依赖的一些常用规则：函数依赖的一些常用规则：n自反性：自反性：n增广性增广性n传递性传递性n合并规则合并规则n分解规则分解规则n伪传递性伪传递性P109p110n实际上计算推导出函数依赖集的闭包是实际上计算推导出函数依赖集的闭包是一件非常繁琐复杂的事情，所以引入的一件非常繁琐复杂的事情，所以引入的属性集闭包属性集闭包的概念。的概念。 定义定义4.9 设设F是属性集合是属性集合U上的一个函数依赖集，上的一个函数依赖集，X U，称，称 为属性集为属性集X关于关于F的闭包。的闭包。P110引理引理4.2 设设F是属性集是属性集U上的函数依赖集，上的函数依赖集

13、，X，Y是是U的子集，则的子集，则XY能由能由F根据根据Armstrong公理导出公理导出的充分必要条件是的充分必要条件是 。ArmstrongFAXU,A|AXF公理导出根据能由 XYn求属性集X关于函数依赖集F的闭包的算法nP1114.2.6函数依赖集的等价与覆盖每个函数依赖集至少存在一个最小依赖集，但并不唯一。最小函数依赖集的定义最小函数依赖集的计算方法函数依赖集极小化的作用n定理定理4.7 4.7 每个函数依赖集每个函数依赖集F F都有最小覆盖。都有最小覆盖。n定义：设一个关系为定义：设一个关系为R（U），），X 和和Y为为U的子集，若的子集，若X Y，并且为完全非平凡函数依赖，同时，

14、并且为完全非平凡函数依赖，同时Y为单属性，为单属性，则称则称X Y为为R的的最小函数依赖最小函数依赖。由。由R中所有最小函数中所有最小函数依赖构成依赖构成R的的最小函数依赖集最小函数依赖集，其中不含有冗余的传，其中不含有冗余的传递函数依赖。递函数依赖。n最小函数依赖集的计算方法最小函数依赖集的计算方法 P113n最小函数依赖集的计算方法：n1、 F Fminmin中任一函数依赖的右部都是单个属性，故先把F中的函数依赖的右部化为单属性的形式。n2、 F Fminmin中不存在冗余的FD（即不存在这样的FD：X X A A，使得，使得 F F XXAA与与F F等价；故消去等价；故消去冗余的冗余的

15、FD。n3、消去左边冗余的属性：对对F F中的任一函数依中的任一函数依赖赖X X A A，若，若Z Z X X，则，则(F(F XXA)A) ZZAA与与F F不等价。不等价。n每一个函数依赖集至少存在一个最小函数依赖每一个函数依赖集至少存在一个最小函数依赖集，但并不一定唯一。集，但并不一定唯一。4.3 关系范式关系范式n分解前后模式的好坏，是用什么标准来衡量呢？分解前后模式的好坏，是用什么标准来衡量呢？n 关系模式的规范化标准（范式）关系模式的规范化标准（范式）n关系规范化的条件可以分为几级，每一级称为一个范关系规范化的条件可以分为几级，每一级称为一个范式，记为式，记为XNF。nNF（Nor

16、mal Form），范式），范式即关系模式满足的即关系模式满足的条件。条件。n范式的概念范式的概念4.3.1 范式的定义及规范化范式的定义及规范化n1、第一范式（、第一范式（1NF）n定义：如果一个关系模式定义：如果一个关系模式R的每个属性的值都是不可再的每个属性的值都是不可再分的基本数据项，则称分的基本数据项，则称R属于第一范式。属于第一范式。n2、第二范式（、第二范式（2NF）n定义：如果一个关系模式定义：如果一个关系模式R属于属于1NF，且它的任一非主，且它的任一非主属性都完全函数依赖于任一候选关键字，则称属性都完全函数依赖于任一候选关键字，则称R满足第满足第二范式。二范式。n2NF不允

17、许关系模式中的非主属性部分函数依赖于关键字。不允许关系模式中的非主属性部分函数依赖于关键字。n例：书例：书P122n分析可知：部分依赖必然带来数据冗余和操作异常。分析可知：部分依赖必然带来数据冗余和操作异常。n如何消除部分依赖，使一个只满足如何消除部分依赖，使一个只满足1NF的关系模式变为属于的关系模式变为属于2NF的的关系模式关系模式？n通过模式分解，使任一非主属性都完全函数依赖于它通过模式分解，使任一非主属性都完全函数依赖于它的任一候选关键字。的任一候选关键字。n对于一个关系对于一个关系R（U），假定），假定W、X、Y、Z是是U的互不的互不相交的属性子集，其中（相交的属性子集，其中（W、X

18、）是主码，且）是主码，且X Y，（W，X）Z，Z中不包含依赖于中不包含依赖于X的属性，则把的属性，则把R（U）分解为两个关系）分解为两个关系R1（X，Y）和）和R2（W，X，Z）后就取消了后就取消了Y对（对（W，X）的部分依赖。）的部分依赖。F n3、第三范式（、第三范式（3NF）n定义：如果一个关系模式定义：如果一个关系模式R属于属于1NF，且每一个非主，且每一个非主属性不传递依赖于任一候选关键字，则称属性不传递依赖于任一候选关键字，则称R满足第三满足第三范式。范式。n消除关系的传递函数依赖也是消除关系的传递函数依赖也是通过关系分解通过关系分解的方法来实现的。的方法来实现的。n设一个关系设一

19、个关系R（U），假定），假定X、Y、Z 、W是是U的互不相交的属性的互不相交的属性子集，其中子集，其中 X是主码，是主码，YZ是直接函数依赖（也可能包含部分函是直接函数依赖（也可能包含部分函数依赖），数依赖）， XZ 是传递函数依赖，则把是传递函数依赖，则把 R（U）分解为两个关）分解为两个关系系R1（Y，Z）和）和R2（X，Y，W），其中），其中Y是是R1的主码，的主码，R2的的外码，这样就消除了外码，这样就消除了Z对对X的传递依赖。的传递依赖。n4、Boyce-Codd范式（范式（BCNF）n定义：设有关系模式定义：设有关系模式R及其函数依赖集及其函数依赖集F，X和和A是是R的的属性集会，

20、且属性集会，且 。如果只要。如果只要R满足满足X A，X就必就必包含包含R的一个候选关键字，则称的一个候选关键字，则称R满足满足BCNF。n或：若一个关系为或：若一个关系为R（U），它是满足），它是满足1NF的，当的，当R中中不存在任何属性对候选码的传递函数依赖时，则称不存在任何属性对候选码的传递函数依赖时，则称R是符合是符合BCNF的。的。n或：若或：若R中的所有属性都完全直接依赖于候选码，或中的所有属性都完全直接依赖于候选码，或说说R的的所有函数依赖所有函数依赖的决定因素都是候选码。的决定因素都是候选码。n没有任何属性完全函数依赖于非码的任何一组属性。没有任何属性完全函数依赖于非码的任何一

21、组属性。A Xn定理定理 如果一个关系模式如果一个关系模式R BCNF，则它必满足，则它必满足3NF。反之，不一定成立。反之，不一定成立。n3NF和和BCNF是在函数依赖的条件下对模式分解所能达是在函数依赖的条件下对模式分解所能达到的分离程度的测度。到的分离程度的测度。n一个模式中的关系模式如果都属于一个模式中的关系模式如果都属于BCNF，那么在函，那么在函数依赖范畴内，它已实现了彻底的分离，已消除了插数依赖范畴内，它已实现了彻底的分离，已消除了插入和删除的异常。入和删除的异常。n3NF的的“不彻底不彻底”性表现在可能存在主属性对码的部性表现在可能存在主属性对码的部分依赖和传递依赖。分依赖和传

22、递依赖。n4.3.2 关系规范化小结关系规范化小结n规范化的基本思想是规范化的基本思想是逐步消除数据依赖中不适逐步消除数据依赖中不适合的部分，使各关系模式达到某种程度的合的部分，使各关系模式达到某种程度的“分分离离”，即，即“一事一地一事一地”的模式设计原则。尽量的模式设计原则。尽量让一个关系描述一个概念、一个实体或一种联让一个关系描述一个概念、一个实体或一种联系。系。n若有多于一个概念的，就把它若有多于一个概念的，就把它“分解分解”出去。出去。因此，所谓因此，所谓规范化实质上是概念的单一化规范化实质上是概念的单一化。n4.3. 2关系模式规范化步骤n4.4 关系分解原则关系分解原则研究函数依

23、赖规范化理论以及研究函数依赖规范化理论以及Armstrong公理等的目的是为了更公理等的目的是为了更有效地规范关系模式。有效地规范关系模式。n通过关系模式的分解，使之满足某种规范化条通过关系模式的分解，使之满足某种规范化条件。件。n但是分解处理中又会涉及一些新问题：但是分解处理中又会涉及一些新问题：n书上的例子：书上的例子：n假设有一个成绩关系（学号，课程，教师，成绩），如表5-1所示，成绩关系的函数依赖集F 如下：n（学号，课程） 教师，成绩教师，成绩n（学号，教师）（学号，教师） 课程，成绩课程，成绩n教师教师课程课程n表表5-1 学号课程教师成绩010205数据库张静96010338数据

24、库张静88020308数据库张静90010205C语言刘天民92n分解：n表5-2和5-3 学号课程成绩010205数据库96010338数据库88020308数据库90010205C语言92 学号教师010205张静010338张静020308张静010205刘天民当需查询某位教师上什么课，就要对M和N两个关系以学号为公共属性进行自然连接.?n模式分解要遵循两个原则：模式分解要遵循两个原则：n（1）无损连接）无损连接:当对关系模式当对关系模式R 进行分解时，进行分解时，R的元组将分别在相应属性集进行投影而产生的元组将分别在相应属性集进行投影而产生新的关系，如果对新的关系进行自然连接得到新的关系，如果对新的关系进行自然连接得到的元组的集合与原关系完全一致，则称无损连的元组的集合与原关系完全一致，则称无损连接接 。n无损连接反映了模式分解的数据等价原则。无损连接反映了模式分解的数据等价原则。n（2）保持依赖：分解前后总的函数依赖集应）保持依赖：分解前后总的函数依赖集应保持一致。保持一致。n无损连接反映了模式分解的依赖等价原则。无损连接反映了模式分解的依赖等价原则。