1、1 1 1第6 6章 关系数据库设计理论第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院2整体概述概述二点击此处输入相关文本内容概述一点击此处输入相关文本内容概述三点击此处输入相关文本内容第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院3 36.1 函数依赖第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院4 4函数依赖的定义 所谓函数依赖就是用形式化方法研究一个关系中各属性之间的语义关系。定义若关系R的任意两个元组在属性A1、A2、An上一致(即有相同分量值)，则这两个元组在属性B上也一致，则称属性A1A2An函数决定B，或称B函数依赖于A1A2An。
2、记为 A1A2An B第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院5 5 5函数依赖的定义tuAB若t和u在A上一致,则在B上一致第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院6 6例子 例如：学号 姓名 学号 性别 考虑：姓名 性别？关系：学生(学号,姓名，性别)中为何 学号 姓名 成立？如果两个元组具有相同学号，则两个元组指同一个学生，故具有相同姓名和性别。在一个关系中，不存在（键值）完全相同的元组。如果不存在两个元组具有相同学号，即每个元组各表示一个学生，则 学号 姓名 成立。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院7 7推论推论1
3、：当且仅当 A1A2An B1 A1A2An B2 A1A2An Bm 则 A1A2An B1B2 Bm推论2：A A第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院8 8例子关系Movies(title,year,length,genre,studioName,starName)中，存在哪些函数依赖？title year length genre studioName 考虑：title year starName?TitleYearLengthgenrestudioNamestarNameStar WarsStar WarsStar WarsGone with the Wind
4、Waynes WorldWaynes World1977197719771939199219921241241242319595sciFisciFisciFidramacomedycomedyFoxFoxFoxMGMParamountParamountCarrie FisherMark HamillHarrison FordVuvien LeighDana CarveyMike Meyers思考题：分析学生（学号，课号，成绩，系号，宿舍区）中的函数依赖。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院9 9怎样分析一个具体关系中的函数依赖 根据属性之间的语义关系分析函数依赖。应考
5、虑所有可能的属性组合。尽可能使函数依赖式的左面最小化，而右面最大化。注意：函数依赖是针对关系模式，而不是针对特定实例，故只从关系实例不能确切断定函数依赖。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院1010判断函数依赖的三种情形如果任意两元组在属性A上一致，在B上也一致，则有A B成立。如果任意两元组在属性A上一致，在B上不一致，则A B不成立。如果任意两元组在属性A上不可能一致，则不管在B上是否一致，有A B成立。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院1111函数依赖的定义部分函数依赖：若X Y，且存在X的真子集X，X Y，则称Y对X部分函数依赖。完
6、全函数依赖：若X Y，且Y对X不是部分函数依赖，则称Y对X是完全函数依赖。传递函数依赖：若XY，YZ，且YX，则称Z对X是传递函数依赖。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院1212关系的键定义：对于关系R，若属性集合A1,A2,An满足下列条件，则该属性集合是R的一个键key:1 A1,A2,An函数决定R中所有其他属性。(超键)2A1,A2,An的任何真子集都不能函数决定R中所有其他属性。(最小化)第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院1313函数依赖定义的键与E/R模型的键定义一致性 函数依赖所定义的键与E/R模型所定义的键完全一致。函数依
7、赖的定义是形式化的定义，而E/R模型键的定义是一种非形式化的语义说明。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院1414例子Movies关系的键是什么？title,year是键吗？为何title,year,starName是关系StarIn(title,year,starName)键？若有关系R(A,B,C)，已知A B在R上成立，则R的键是什么？第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院1515候选键与主键的关系一个关系中的所有的键，都称之为候选键。一个关系可能有多个键，但只选择其中之一作为主键。第6章 关系数据库设计理论 前一页 休息南京理工大学计算
8、机学院1616超键定义 包含键的属性集就称为超键(superkey)，它是“键的超集”的简写。每个键都是超键吗？是。关系模式StarIn(title,year,starName)的属性集title,year,starName是超键吗？一个关系的属性全集是超键吗？是。每个超键都是键吗？不是。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院1717从E/R图中发掘键一个关系模式中键的表示：每个关系只描述主键。下划线表示。E/R模型实体集的关系的键的确定来自实体集的关系的键码就是相应实体集的键属性。如 Movies(title,year,length,genre)第6章 关系数据库设计
9、理论 前一页 休息南京理工大学计算机学院1818从E/R图中发掘键来自E/R模型二元联系的关系R的键的确定 根据多重性分三种情况：多对多：相联系的两个实体集的键属性共同构成R的键。多对1：E1E2,E1的键属性作为R的键。通常该关系可合并到E1关系中。1对1：任意一端实体集的键都可作为R的键，但通常该关系可合并到E1或E2关系中。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院1919例子StarsIn(title,year,starName)Owns(title,year,studioName)，但我们通常关系Owns 的属性studioName合并到movies关系中：Mov
10、ies(title,year,length,genre,studioName)再如销售业务系统的例子。(见第1章最后给出的综合应用题)第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院2020作业P.40习题3.1.1、3.1.3第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院216.2 函数依赖规则第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院22函数依赖规则什么是函数依赖规则？在一个给定关系上，已知一组函数依赖作为前提条件。根据一组函数依赖规则，推断另一些函数依赖。为何需要它？这种计算和验证可有效减少冗余，得到良好的关系设计。第6章 关系数据库设计
11、理论 前一页 休息南京理工大学计算机学院2323例子已知 R(A,B,C)，及A B，B C，可证A C。证明：设(a,b1,c1)和(a,b2,c2)是R的元组 由A B 可知 b1=b2 记作 b 又由B C可知 c1=c2 从而A C第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院2424有哪些重要的函数依赖规则分解合并(Splitting/combining)规则平凡依赖(Trivial Dependance)规则传递(Transitivy)规则Armstrong公理第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院2525两个函数依赖集合之间有何关系设T是关
12、系R上的函数依赖集，若对R的所有实例，函数依赖X Y都成立，则称T“逻辑蕴含”X Y。(X Y可由T推导出来)设S是关系R上的另一函数依赖集，若对R的所有实例，S中的所有函数依赖均成立，则称函数依赖集S“蕴含于”函数依赖集T。(S可由T推导出来)若函数依赖集S“蕴含于”T，同时T“蕴含于”S，则函数依赖集S“等价于”函数依赖集T。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院2626蕴含和等价关系有何用处可用等价的更简单的函数依赖集代替复杂的函数依赖集。可在一个函数依赖集S中增加蕴含其中的其它函数依赖。可判断一个函数依赖是否蕴含于已知的函数依赖集。第6章 关系数据库设计理论 前
13、一页 休息南京理工大学计算机学院2727分解/合并规则(Splitting/Combining Rule)A1A2An B1B2Bm 等价于 A1A2An B1 A1A2An B2 A1A2An Bm第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院2828分解/合并规则(Splitting/Combining Rule)例如：关系Movies中，title year length genre studioName 等价于：title year length title year genre title year studioName注意：函数依赖的左面不能分解合并。例如：学号 课
14、号 成绩第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院2929平凡依赖(Trivial Dependance)对于函数依赖A1A2An B，若B是A中的某一个属性，则该函数依赖是“平凡的”。平凡依赖是恒真式。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院3030平凡依赖的一般定义 对于函数依赖A1A2An B1B2Bm若B是A的子集，则该依赖是“平凡的”；若B中至少有一个属性不在A中，则该依赖是“非平凡的”；若B中没有一个属性在A中，则该依赖是“完全非平凡的”。例如：title year year length是非平凡的；title year length是完全
15、非平凡的。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院3131平凡依赖规则 如果函数依赖式右边的属性中有一些出现在左面，那么可以将右边重复出现的属性删除。即：函数依赖A1A2An B1B2Bm等价于A1A2An C1C2Ck，其中：C是B中不在A中出现的属性。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院3232平凡依赖规则如果t和u在属性A上一致则它们必然在B上一致，所以在C上也一致。ACBut第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院3333计算属性的闭包已知S是关系R上的函数依赖集，则属性集A1,A2,An可函数决定的最大属性集合是什
16、么？这个集合被称做什么?如何计算这个集合？这种计算有何用途？第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院3434属性的闭包设S是关系R上的函数依赖集，A=A1,A2,An是R上的属性集，属性A在函数依赖集S下的闭包(closure)是这样一个属性集B，使对关系R的所有实例，函数依赖：A1A2An B 均成立。即A1A2An B“蕴含于”函数依赖集S。属性集A1,A2,An的闭包表示为 A1,A2,An+。A1,A2,An包含于A1,A2,An+若A1A2An X，则X B第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院3535如何计算属性的闭包 给定函数依赖集S
17、和属性集A=A1,A2,An，如何计算A+？1 将X初始化为A1,A2,An，闭包最小集合。2 遍历S中的每个函数依赖，对于每个依赖式：B1B2Bm C 如果B1、B2、Bm都在X中，而C不在X中，则把C加入X中。3 重复第2步，直到遍历完S中所有函数依赖，而没有新属性能加入到X中。4 最终属性集X即为属性集A在函数依赖集S下的闭包A+。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院3636例子 设有关系R(A,B,C,D,E,F)与函数依赖集 S：AB C，BC AD，D E，CF B 求：A,B+解：X(1)=A,B,由AB C，得：X(2)=A,B,C,由BC AD，得：
18、X(3)=A,B,C,D,由D E，得：X(4)=A,B,C,D,E=A,B+第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院3737属性闭包计算的用途 假设关系R上已有一个依赖集S，另有一个函数依赖A1A2An B，该依赖是否蕴含于S？判断方法：计算A1,A2,An+。若B在A1,A2,An+中，则函数依赖A1A2An B蕴含于S中。若B不在A1,A2,An+中，则函数依赖A1A2An B不蕴含于S中。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院3838属性闭包计算的用途 一般性结论：若关系R有函数依赖集S，当且仅当所有B1B2Bm都在A1,A2,An+中，则
19、A1A2An B1B2Bm蕴含于S中。思考题：上例关系R中，AB D 和D A是否蕴含于函数依赖集S中？第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院3939为什么闭包算法给出正确的函数依赖用归纳法证明基础 最基础的情况是没有进行任何计算。于是D必定是A1,A2,An中一员，则A1A2An D是平凡函数依赖。因此，R满足A1A2An D。归纳 假设当使用函数依赖B1B2Bm D时已把D加入到X。则由归纳法假设可知R满足A1A2An Bi (i=1,m)。换言之，R的任何两个元组在A1,A2,An上的取值相等时，它们在B1,B2,Bm上的取值也相等。由于R满足B1B2Bm D，还
20、可以得出这两个元组在D上取值也相等。因此，R满足A1A2An D。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院4040为什么闭包算法可找到所有得函数依赖实际上我们要证明至少有一个满足S中所有函数依赖集合，但不满足A1A2An B的关系实例存在。构造实例：A1,A2,An+Other Attrbutest:1111100000s:1111111111第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院4141属性的闭包与键之间关系 对于一个关系R，当且仅当A1,A2,An是R的超键时，A1,A2,An+是R的所有属性的集合。第6章 关系数据库设计理论 前一页 休息南京
21、理工大学计算机学院4242例子 已知关系模式R(A,B,C,D)有函数依赖AB C,C D,D A (a)求蕴含于给定函数依赖的所有完全非平凡函数依赖。(b)求R的所有键。(c)求R的所有超键(不包括键)。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院4343例子 解：(a)根据所有属性集合的闭包，计算所有可能的函数依赖。A+=A B+=B C+=C,D,A C AD D+=D,A A,B+=A,B,C,D AB CD A,C+=A,C,D AC D A,D+=A,D第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院4444例子B,C+=B,C,D,A BC ADB
22、,D+=B,D,A,C BD ACC,D+=C,D,ACD AA,B,C+=A,B,C,D ABC DA,B,D+=A,B,D,C ABD CA,C,D+=A,C,DB,C,D+=B,C,D,A BCD A第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院4545例子 (b)所有的键：A,B,B,C,B,D (c)所有的超键(不包括键)：A,B,C,A,B,D,B,C,D,A,B,C,D第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院4646传递规则 把两个函数依赖级联起来。具体来说：若A1A2An B1B2Bm和B1B2Bm C1C2Ck成立，则A1A2An C1C
23、2Ck成立(蕴含于前两个依赖中)。传递规则的证明 计算A1,A2,An的闭包，应包含B1B2Bm，再包含C1C2Ck。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院4747例子 关系MovieStudio(title,year,legth,genre,studioName,studioAddr)title,year studioName studioName studioAddr 则title,year studioAddr第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院4848函数依赖的闭包对于给定的关系模式R和函数依赖集F，所有能由F导出的函数依赖的全体称作F
24、的闭包，记作F+。通常我们更需要选择一个依赖集来表示所有依赖。对于一个关系，任何一个能导出所有依赖的依赖集，称为该关系的一个“基”base。对于同一个关系，可能有多个“基”。如果一个基的任何真子集都不能导出该关系的所有依赖集，则称该基为“最小”基。对于同一个关系，可能有多个“最小”基。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院4949例子 已知关系R(A,B,C)及函数依赖集 F:A B,A C,B A,B C,C A,C B 最小基有：A B,B A,B C,C B A B,B C,C A 等第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院5050最小函数依
25、赖集定义 设F是属性集U上的函数依赖集，如果Fmin是F的一个最小依赖集，那么Fmin应满足下列四个条件：Fmin+=F+；每个函数依赖的右边都是单属性；Fmin中没有冗余的函数依赖(即在F中不存在这样的函数依赖XY，使得F与F-|XY|等价)；每个函数依赖的左边没有冗余的属性(即F中不存在这样的函数依赖XY，X有真子集W使得F-|XY|WY|与F等价)；第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院5151求最小函数依赖集算法 根据分解规则，可得到一个与F等价的函数依赖集G，G中每个函数依赖的右边均为单属性。在G中的每个函数依赖中消除左边冗余的属性。在G中消除冗余的函数依赖。
26、第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院5252例子关系模式R(A,B,C,D,E,G)有函数依赖 BG C,BD E,DG C,DAG CB,AG B,B D求此模型的最小函数依赖集。求出关系模式的候选键。解Fmin=B E,DG C,AG B,B D所有的键：A,G第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院5353函数依赖的投影什么是投影？设R是一个含有函数依赖集合的关系，取关系R中部分指定的属性集，称之为“投影”。设有关系模式R(U)及函数依赖集F，若将R分解为S(U1)及T(U2)，则S上存在那些函数依赖？从函数依赖集推断而来。只包含S的属性。
27、第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院5454函数依赖投影的算法算法：对于S的属性集U中的每个属性子集X，计算X+，于是对于满足下列条件的每个属性B，函数X B 在S中成立：B是S的一个属性，B属于X+，而且 B不属于X。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院5555例子 已知关系R(A,B,C,D)及函数依赖集 F:A B,B C,C D 假设关系R投影到S(A,C,D)。A+=A,B,C,D C+=C,D 从而可得到关系S的函数依赖 F:A C,C D第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院5656Armstrong公理
28、 1 自反律(Reflexivity)。若B1,B2,Bm A1,A2,An，则 A1A2An B1B2Bm。(平凡)2 增长律(Augmentation)。若A1A2An B1B2Bm，则对于任意属性集C1,C2,Ck，有 A1A2An C1C2Ck B1B2Bm C1C2Ck3 传递律(Transitivity)。若A1A2An B1B2Bm和B1B2Bm C1C2Ck成立，则A1A2An C1C2Ck。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院5757作业P.47习题3.2.2、3.2.6、3.2.7、3.2.10第6章 关系数据库设计理论 前一页 休息南京理工大学计
29、算机学院58583.3 关系数据库模式设计第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院5959关系模式设计中为何出现冗余关系模式设计中可能出现各种冗余，即同一事实在多个元组中重复。造成冗余的原因通常是将同一个对象的单值和多值特征混合在同一个关系中。titleyearlengthgenreStudioNameStarNameStar Wars1977124SciFiFoxCarrie FisherStar Wars1977124SciFiFoxMark HamillStar Wars1977124SciFiFoxHarrison FordGone with the Wind19
30、39231dramaMGMEmilio EstevezWaynes World199295comedyParamountDana CarveyWaynes World199295comedyParamountMike Meyers第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院6060异常“异常”指什么？异常anomaly，即不符合规范，在操作数据库时，影响数据一致性。关系设计中主要有哪些异常？冗余。同一信息在多个元组中不必要的重复。浪费空间，增加更新操作的复杂度，影响数据一致性。修改异常。当修改了某个元组中的信息，而重复的信息可能未修改而破坏一致性。插入数据时，某些有用信息暂时
31、无法插入。删除异常。当删除某个元组时，可能删除其它信息；若需删除某个对象时，必须删除多个元组而不是一个元组。否则，破坏数据一致性。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院6161如何解决冗余问题按如下步骤解决冗余问题：分析关系模式设计缺陷可能导致的问题。引入“关系分解”，把一个关系模式(属性集)分解为更小的模式。介绍“Boyce-Codd 范式”(Boyce-Codd Normal Form,即BCNF)，给出关系模式所应满足的条件。如何通过分解关系模式保证满足BCNF。放宽BCNF条件，引入“3NF”。简单介绍1NF和2NF。第6章 关系数据库设计理论 前一页 休息南京
32、理工大学计算机学院6262关系分解什么是关系分解？给定一个关系RA1,A2,An，将R分解为两个关系SB1,B2,Bm和TC1,C2,Ck，使得1 A1,A2,An=B1,B2,BmC1,C2,Ck2 S中的元组是R的所有元组在B1,B2,Bm上的投影；T中的元组是R的所有元组在C1,C2,Ck上的投影。为何要进行关系分解？为了避免异常，用几个关系代替原有的关系，且保持数据一致性。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院6363例子 将关系模式Movies(title,year,length,filmtype,studioname,starname)分解为:Movies1
33、(title,year,length,genre,studioname)Movies2(title,year,starname)第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院6464例子titleyearlengthgenreStudioNameStar Wars1977124SciFiFoxGone with the Wind1939231dramaMGMWaynes World199295comedyParamounttitleyearStarNameStar Wars1977Carrie FisherStar Wars1977Mark HamillStar Wars197
34、7Harrison FordMighty Ducks1991Emilio EstevezWaynes World1992Dana CarveyWaynes World1992Mike Meyers第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院6565例子将关系模式 学生(学号,课号,成绩,系号,系主任)分解。学号课程号成绩系号系主任S1C1AD1M1S1C2AD1M1S1C3BD1M1S2C2BD1M1S3C1AD2M2S3C3AD2M2S4C1BD2M2S4C2AD2M2第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院6666例子学号课号成绩S1S1S1S2S3
35、S3S4S4C1C2C3C2C1C3C1C2AABBAABA学号系号系主任S1S2S3S4D1D1D2D2M1M1M2M2学生(学号,系号,系主任)选修(学号,课号,成绩)分解后的关系无异常。这些关系可连接(join)得到原有的关系元组，且不改变原有语义。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院6767问题对于一个给定的关系模式，如何判断是否存在异常？如何进行关系模式的分解？第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院6868什么是范式(Normal Form)关系模式所满足的不同程度的要求(规范形式)称之为范式。若关系模式R的每个分量均是不可再分的数据
36、项，则R满足第一范式，又记作：R 1NF。在第一范式的基础上，逐步加强条件，分别有2NF,3NF,BCNF,4NF,5NF。一个较低级别的关系模式，可通过分解的方式，转换成若干个较高级别的关系模式，这种过程叫做关系规范化。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院6969BC范式(BCNF,Boyce-Codd Normal Form)为何引入BC范式？BC范式是常用判断条件，满足该条件就能避免函数依赖引起的异常。BC范式如何定义？关系模式R满足BC范式，当且仅当 若非平凡函数依赖 A1A2An B1B2Bm 在关系R中成立，则A1,A2,An是R的超键。第6章 关系数据库
37、设计理论 前一页 休息南京理工大学计算机学院7070关系R满足BC范式的两种情形关系R中不存在非平凡函数依赖。(只有平凡函数依赖)每个非平凡函数依赖的左面包含某个键(即左面是超键)。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院7171关系R违背BC范式的唯一情形关系R中至少存在一个非平凡函数依赖，其左面不是超键。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院7272例子 学生(学号,课号,成绩,系号,系主任)是否满足BC范式？键：学号,课号 非平凡函数依赖：学号 系号,系主任 成立 而左面不是超键。分解后的 选修(学号,课号,成绩)和 学生(学号,系号,系主任
38、)是否满足BC范式？第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院7373判断BC范式的方法找出所有的Key。检查所有非平凡函数依赖。左面是否超键？第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院7474仅有两个属性的关系必是BC范式R(A,B)可分四种情况讨论：1 没有非平凡函数依赖。2 A B 成立，而B A不成立。A是唯一键，函数依赖式左面是键。3 B A 成立，而A B不成立。B是唯一键，函数依赖式左面是键。4 A B 成立，且B A成立，关系R有两个键：A和B，每个函数依赖式左面是键。注意：一个关系可能有多个键，而BC范式要求依赖式左面包含某个键，而不是
39、所有键。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院7575分解为BC范式分解关系有何条件？把一个关系模式分解成一个由若干个关系模式构成的集合，且这些关系模式应满足如下条件：1 每个关系模式都满足BCNF。2 分解后的元组能如实反映原有关系中的数据，即能从分解后的关系中准确重构原有关系。思考题：能否将所有关系分解为单目关系？第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院7676分解策略：消除违背BCNF的函数依赖1 找一个违背BCNF的非平凡函数依赖A1A2An B1B2Bm。2 把关系R分解成两个关系：R1(A1,A2,An,B1,B2,Bm)。R2(A1,
40、A2,An,所有其它属性)，若不满足BC范式，则再分解。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院7777例子 R(学号,课号,成绩,系号,系主任)不满足BCNF。1 非平凡函数依赖：学号 系号,系主任 成立2 R分解为：R1(学号,系号,系主任)R2(学号,课号,成绩)分解消除了部分属性对键的部分依赖。3 非平凡函数依赖：系号 系主任 成立4 R1继续分解为：R11(系号,系主任)R12(学号,系号)分解消除了部分属性对键的传递依赖。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院7878作业P.52习题3.3.1、3.3.2第6章 关系数据库设计理论 前一
41、页 休息南京理工大学计算机学院79793.4 分解的优劣第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院8080分解的三个性质1.消除异常2.信息的可恢复：能否从分解后的各个元祖中恢复原始关系？3.依赖的保持：如果FD的投影在分解后的关系上成立，能否确保分解后的关系用连接重构获取的原始关系仍然满足原来的FD？第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院8181从分解中恢复信息tuxwv投影连接连接投影如果确实能够重新获得R，则称该分解含有无损连接。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院8282从分解中恢复信息对属性集X，Y，Z，如果YZ在
42、关系R上成立，且R的属性集为XYZ，那么 R=XY(R)YZ(R)结论：如果依据算法3.20对一个关系进行分解，则原始关系可以通过自然连接来精确地恢复。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院8383分解若非基于函数依赖，则可能无法恢复成原关系设R为：ABC142235AB1422ABC114422223535BC2235分解为：R1(A,B)R2(B,C)连接R1,R2:P.53 习题3.3.4第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院8484无损连接的chase检验假设关系R被分解为若干关系，它们包含属性集分别为S1，S2，Sk。在R上成立的函数依
43、赖集合为F。当把关系R投影到这些分解关系上后，能否通过这些的自然连接来恢复？即 R=S1(R)S2(R)Sk(R)第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院8585无损连接的chase检验三个重要的性质自然连接满足结合律和交换律。R中的任意元祖都必然属于 R=S1(R)S2(R)Sk(R)推论：当F中的函数依赖对R成立时，R=S1(R)S2(R)Sk(R)当且仅当 连接的结果中每个元组都属于R。只需进行成员关系测试就可以验证分解是否包含无损连接 第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院8686无损连接的chase检验无损连接的chase检验仅仅是以一种
44、有条理的方式来判断是否可以根据F中的函数依赖来证明，所有属于 R=S1(R)S2(R)Sk(R)的元祖t也都是关系R的元组。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院8787无损连接的chase检验设有函数依赖 AB,BC,CDA 则有ABCDab1c1dab2cd2a3bcdABCDab1cdab1cd2abcd第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院8888为什么chase检验有效若chase过程找到一行与元组t相匹配，则连接是无损的。若所有可能的方式应用各函数依赖后，仍无法得到所有变量均不带下标的行，则连接是有损的。第6章 关系数据库设计理论 前
45、一页 休息南京理工大学计算机学院8989存在某些关系尽管不符合BCNF，但不能再分解关系Booking(movie,theater,city)表示电影的预定。其中一个元组(m,t,c)表示预定在城市c的影院t放映影片m。条件：一座城市有多个影院；每个影院对应唯一的城市。每个影院可放映多部影片；每部影片可在多个影院放映。同一个城市的两个影院不会预定同一部影片。故有函数依赖：theater city movie city theater有两个键:movie,city 和 movie,theater非平凡函数依赖：theater city违背BCNF。第6章 关系数据库设计理论 前一页 休息南京理工
46、大学计算机学院9090存在某些关系尽管不符合BCNF，但不能再分解能分解为 theater,city和 theater,movie而保持原有函数依赖吗？假设这两个关系的元组如下：theatercityGuildParkMenlo ParkMenlo ParktheatermovieGuildParkThe NetThe Net把两个关系连接起来，恢复为原有关系。theatercitymovieGuildParkMenlo ParkMenlo ParkThe NetThe Net函数依赖movie city theater不成立，违背原有的语义。关系Booking(movie,theater,c
47、ity)如果为了满足BC范式而分解的话，就不能保持原有的函数依赖。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院9191作业P.58习题3.4.1、3.4.2第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院92923.5 第三范式第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院9393第三范式定义定义 关系模式R满足3NF，当且仅当 若非平凡函数依赖A1A2An B在关系R中成立，则A1,A2,An是R的超键，或者B是某个键的组成部份（键属性）。根据定义，关系Booking(movie,theater,city)满足3NF。第6章 关系数据库设计理论
48、 前一页 休息南京理工大学计算机学院9494分解为第三范式的算法对于关系模式R和R上的函数依赖集F，先求出F的最小依赖集，然后再把最小依赖集中那些左部相同的函数依赖用合并规则合并起来；对最小依赖集中的每个函数依赖XY去构成一个模式XY；在构成的模式集中，如果每个模式都不包含R的候选键，那么把候选键作为一个模式放入模式集中。这样得到的模式集是关系模式R的一个分解，并且这个分解既是无损分解，又能保持函数依赖。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院9595第三范式结论一个关系模式总可以分解为满足3NF的模式，且所有的函数依赖都可得到保持。第6章 关系数据库设计理论 前一页 休
49、息南京理工大学计算机学院9696第一范式和第二范式第一范式(1NF)的条件是什么？每个元组的每个分量都是原子的(atomic)。第二范式(2NF)的条件是什么？在1NF的基础上，要求每个非键属性依赖于键的整体(直接或间接)，而不是键的部分属性，即不允许有非平凡函数依赖的右面是非键属性，而左面是某个键的真子集。第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院9797满足2NF的几种情形不存在非平凡函数依赖。存在非平凡函数依赖，且其右面是某个键的组成部分(键属性)。存在非平凡函数依赖，且其右面是非键属性，则其左面要么是超键，要么包含非键属性。第6章 关系数据库设计理论 前一页 休息南
50、京理工大学计算机学院9898例子1学生(学号,课号,成绩,系号,宿舍区)满足的最高范式是什么？仅满足1NF。为何不满足2NF？2Movies(title,year,length,filmType,studioName,starName)满足的最高范式是什么？仅满足1NF。为何不满足2NF？3MovieStudio(title,year,length,filmType,studioName,studioAddr)满足的最高范式是什么？仅满足2NF。为何不满足3NF？第6章 关系数据库设计理论 前一页 休息南京理工大学计算机学院9999范式等级满足范式条件：BCNF 3NF 2NF 1NF给定一个
