数据库系统原理课件2

数据库系统原理数据库系统原理第二篇设计篇第二篇设计篇设计篇第四章数据库设计概述与需求分析第五章概念数据库设计第六章逻辑数据库设计第七章物理数据库设计第六章逻辑数据库设计设计篇第四章数据库设计概述与需求分析第六章逻辑数据库逻辑数据库设计的任务：第六章逻辑数据库设计把概念数据库设计阶段产生的概念数据库模式变换为逻辑数据库模式。逻辑数据库设计的任务：第六章逻辑数据库设计把概念数据库设计逻辑数据库设计的目标是：第六章逻辑数据库设计①满足用户的完整性和安全性要求；②动态关系至少具有第三规范形式，静态关系至少具有第一规范形式；③能够在逻辑级上高效率地支持各种数据库事务的运行；④存储空间利用率高。逻辑数据库设计的目标是：第六章逻辑数据库设计逻辑数据库设计的步骤是：第六章逻辑数据库设计①形成初始关系数据库模式；②关系模式规范化；③关系模式优化；④定义关系上的完整性和安全性约束；⑤子模式定义；⑥性能估计。逻辑数据库设计的步骤是：第六章逻辑数据库设计6.1形成初始关系数据库模式6.2关系数据库设计理论6.3关系模式规范化方法6.4关系模式的优化6.5完整性和安全性约束的定义6.6逻辑数据库的性能估计6.1形成初始关系数据库模式第六章逻辑数据库设计6.1形成初始关系数据库模式6.1形成初始关系数据库初始关系数据库模式是指直接由概念数据库模式生成的关系数据库模式。初始关系数据库模式生成的目的是把概念数据库模式的实体、实体间联系等模型结构变换为关系模式。6.1形成初始关系数据库模式初始关系数据库模式是指直接由概念数据库模式生成的关系数据库模由概念数据库模式生成初始关系数据库模式的方法:普通实体型的变换弱实体的变换多值属性的变换实体间联系的变换确定函数依赖集6.1形成初始关系数据库模式由概念数据库模式生成初始关系数据库模式的方法:6.1形成初普通实体型的变换为概念数据库模式中的每个普通实体型Ｅ建立一个关系Ｓ。Ｓ包含Ｅ的所有简单属性和Ｅ的复合属性的简单子属性。Ｅ的键是Ｓ的主键。6.1形成初始关系数据库模式普通实体型的变换6.1形成初始关系数据库模式普通实体型的变换例6.1形成初始关系数据库模式普通实体型的变换6.1形成初始关系数据库模式弱实体的变换设Ｗ是概念数据库模式中以实体型Ｅ为识别实体型的弱实体。建立一个与Ｗ对应的关系Ｒ；Ｗ的所有简单属性和复合属性的简单子属性映射为Ｒ的属性；E的键属性也是R的属性；Ｒ的键由Ｅ的键和Ｗ的部分键组合而成；Ｅ对应的关系的键是Ｒ的外部键。6.1形成初始关系数据库模式弱实体的变换6.1形成初始关系数据库模式弱实体的变换例6.1形成初始关系数据库模式弱实体的变换6.1形成初始关系数据库模式多值属性的变换设实体型Ｅ具有多值属性，Ｓ是Ｅ对应的关系。为E的每个多值属性A建立一个关系Ｔ，用Ｔ表示Ａ。如果A是简单属性，Ｔ的属性为Ａ与Ｓ的主键Ｋ。Ａ和Ｋ形成Ｔ的主键。如果Ａ是复合属性，Ｔ包含Ａ的简单子属性和S的键Ｋ。Ａ的简单子属性和Ｋ形成Ｔ的键。Ｓ关系中忽略属性Ａ。对联系R的多值属性类似处理6.1形成初始关系数据库模式多值属性的变换6.1形成初始关系数据库模式多值属性的变换例6.1形成初始关系数据库模式S(K,F)T1(K,B,C)T2(K,D)多值属性的变换6.1形成初始关系数据库模式S(K,F)实体间联系的变换1:1联系的变换设R是实体型E1和E2之间的1:1联系，S和T是E1和E2对应的关系。方法1：通过在S或T中增加有关信息来表示联系R①T(或S)的主键作为外部键添入S(或T)；②R的简单属性和复合属性的简单子属性作为简单属性添入S(或T)。注意：如果S和T中至少一个具有关于R的全域关联约束，则应选择具有这种约束的关系型表示R。如果S和T都具有全域关联约束，而且S和T与其他联系无关，则把S和T合并为一个关系型来表示R。6.1形成初始关系数据库模式实体间联系的变换6.1形成初始关系数据库模式实体间联系的变换1:1联系的变换设R是实体型E1和E2之间的1:1联系，S和T是E1和E2对应的关系。方法2：建立一个单独的关系W表示R①T和S的主键作为键添入W；②R的简单属性和复合属性的简单子属性作为简单属性添入W。6.1形成初始关系数据库模式实体间联系的变换6.1形成初始关系数据库模式实体间联系的变换1:1联系的变换例6.1形成初始关系数据库模式职工产品负责11职工号姓名产品名产品号实体间联系的变换6.1形成初始关系数据库模式职工产品负责实体间联系的变换1:n联系的变换设R是从实体型E1到实体型E2的1:N联系，S和T是E1和E2对应的关系。方法1：不需建立新关系。由于T的每个实体至多与S的一个实体对应，因此用T来表示R①S的主键作为外部键添入T;②R的简单属性和复合属性的简单子属性作为简单属性添入T。方法2：建立一个单独的关系W表示R，同1:1联系。6.1形成初始关系数据库模式实体间联系的变换6.1形成初始关系数据库模式实体间联系的变换1:n联系的变换例：教师和系6.1形成初始关系数据库模式实体间联系的变换6.1形成初始关系数据库模式实体间联系的变换m:n联系的变换设R是从实体型E1到实体型E2的M:N联系，S和T是E1和E2对应的关系。建立一个新关系W来表示R。S和T的主键添入W，既作为外部键，也组合起来作为W的主键。W还需要包含R的简单属性和复合属性的简单子属性。6.1形成初始关系数据库模式实体间联系的变换6.1形成初始关系数据库模式实体间联系的变换m:n联系的变换例：学生选课6.1形成初始关系数据库模式实体间联系的变换6.1形成初始关系数据库模式实体间联系的变换n元联系的变换设R是关联实体型E1、E2、...、En的n元联系。类似于M:N联系的表示方法：需建立一个关系T，用T来表示R。所有Ei的主键都是T的外部键，也组合起来作为T的主键。T还包含R的简单属性和复合属性的简单子属性。6.1形成初始关系数据库模式实体间联系的变换6.1形成初始关系数据库模式确定函数依赖集通过前面的步骤，初始关系数据库模式已经形成。最后，对初始关系数据库模式中的每个关系模式进行深入地分析，与用户协商，确定每个初始关系的函数依赖集，使用关系数据库设计理论，对关系模式进行规范化处理。6.1形成初始关系数据库模式确定函数依赖集6.1形成初始关系数据库模式形成初始关系数据库模式举例6.1形成初始关系数据库模式形成初始关系数据库模式6.1形成初始关系数据库模式6.1形成初始关系数据库模式6.2关系数据库设计理论6.3关系模式规范化方法6.4关系模式的优化6.5完整性和安全性约束的定义6.6逻辑数据库的性能估计6.2关系数据库设计理论第六章逻辑数据库设计6.1形成初始关系数据库模式6.2关系数据库设计理论6.2.1问题的提出初始关系模式不是逻辑设计的最终结果，其中某些关系模式可能存在由属性间的函数依赖引起的冗余问题、插入问题、更新问题和删除问题。6.2关系数据库设计理论6.2.1问题的提出6.2关系数据库设计理论6.2.1问题的提出6.2关系数据库设计理论有一个描述学生的关系模式：U＝{S#,SD,MN,CN,G}例：学生的学号(S#)、姓名(SN)、系(SD)之间存在函数依赖:S#→SN,S#→SD现实世界的已知事实：F={S#→SD,SD→MN,(S#,CN)→G}存在的问题：插入异常删除异常数据冗余和更新问题需要用关系模式的规范化方法消除初始逻辑数据库模式中存在的问题6.2.1问题的提出6.2关系数据库设计理论例：需要用关6.2.2函数依赖定义1：设R是一个关系模式，U是R的属性集合，X和Y是U的子集。对于R的任意实例ｒ，ｒ中任意两个元组t1和t2，如果t1[X]=t2[X]，则t1[Y]=t2[Y]，我们称X函数地确定Y，或Y函数依赖于X，记作X→Y。6.2关系数据库设计理论只能根据数据的语义来确定函数依赖。6.2.2函数依赖6.2关系数据库设计理论只能根据数据6.2.2函数依赖如果X→Y而且Y不是X的子集，则称X→Y是非平凡函数依赖。若不特别声明，我们总是讨论非平凡函数依赖。如果X→Y，我们称X为这个函数依赖的决定属性集。6.2关系数据库设计理论6.2.2函数依赖6.2关系数据库设计理论6.2.2函数依赖6.2关系数据库设计理论定义2：设R是一个具有属性集合U的关系模式，如果X→Y，并且对于X的任何一个真子集Z，Z→Y都不成立，则称Y完全函数依赖于X。若X→Y，但Y不完全函数依赖于X，则称Y部分函数依赖于X。6.2.2函数依赖6.2关系数据库设计理论定义2：6.2.2函数依赖6.2关系数据库设计理论定义3：设Ｒ是一个具有属性集合Ｕ的关系模式，XＵ,YＵ,ZＵ，Y→X不成立，Z-X、Z-Y和Y-X不空。如果X→Y，Y→Z，则称Z传递地函数依赖于X。6.2.2函数依赖6.2关系数据库设计理论定义3：6.2.2函数依赖定义4：设Ｒ是一个具有属性集合Ｕ的关系模式,ＫＵ。如果Ｋ满足下列两个条件，则称Ｋ是Ｒ的一个候选键：(1)Ｋ→Ｕ。(2)不存在Ｋ的真子集Ｚ使得Ｚ→Ｕ。候选键可以唯一地识别关系的元组。一个关系模式中可能具有多个候选键，指定其中的一个作为识别关系元组的主键。包含在任何一个候选键中的属性称为键属性。不包含在任何候选键中的属性称为非键属性。在最简单的情况下，候选键只包含一个属性。在最复杂的情况下，候选键包含关系模式的所有属性，称为全键。6.2关系数据库设计理论6.2.2函数依赖6.2关系数据库设计理论6.2.2函数依赖定义5：设Ｘ是关系模式Ｒ的属性子集合。如果Ｘ是另一个关系模式的候选键，则称Ｘ是Ｒ的外部键。6.2关系数据库设计理论6.2.2函数依赖6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论在关系模式的规范化处理过程中，只知道一个给定的函数依赖集合是不够的。还需要知道由给定的函数依赖集合所蕴涵的所有函数依赖的集合。为了能够从给定的函数依赖集合推导出这个集合蕴涵的所有函数依赖，我们需要一个有效而完备的公理系统。Armstrong公理系统就是这样一个系统。6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论定义6：设R是一个具有属性集合Ｕ的关系模式，F是R上的函数依赖集合。如果对于R的任意一个使F成立的关系实例ｒ，函数依赖X→Y都成立，则称F逻辑地蕴含X→Y。6.2.3函数依赖的公理系统6.2关系数据库设计理论定6.2.3函数依赖的公理系统Armstrong公理系统设Ｒ是一个具有属性集合Ｕ的关系模式，Ｆ是Ｒ的一个函数依赖集合。Armstrong公理系统包含如下三条推理规则：6.2关系数据库设计理论自反律：若ＹＸＵ，则Ｆ蕴含Ｘ→Ｙ。增广律：若Ｆ蕴含Ｘ→Ｙ，ＺＵ，则Ｆ蕴含ＸＺ→ＹＺ。传递律：若Ｆ蕴含Ｘ→Ｙ和Ｙ→Ｚ，则Ｆ蕴含Ｘ→Ｚ。6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统定理1：Armstrong推理规则是正确的。证明：6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统三条推论合并规则如果Ｘ→Ｙ，Ｘ→Ｚ，则Ｘ→ＹＺ。伪传递规则如果Ｘ→Ｙ，ＹＷ→Ｚ，则ＸＷ→Ｚ。分解规则如果Ｘ→Ｙ，ＺＹ，则Ｘ→Ｚ。6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统定理2：合并规则、伪传递规则和分解规则是正确的。证明：6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统引理1：X→A1A2...Ak成立的充分必要条件是对于1≤i≤k，X→Ai成立。证明：?6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统定义7：设Ｒ是一个具有属性集合Ｕ的关系模式，F是给定的函数依赖集合。由F逻辑蕴含的所有函数依赖称为F的闭包，记为F+。6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统Armstrong公理系统是有效而且完备的吗？Armstrong公理的有效性是指由F出发根据Armstrong公理推导出来的每个函数依赖一定在F+中；Armstrong公理的完备性指的是F+中的每一个函数依赖一定可以由F出发根据Armstrong公理推导出来。Armstrong公理的有效性已经在定理1中证明。6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统为了证明Armstrong公理的完备性，首先需要解决如何判定一个函数依赖是否可以由F根据Armstron公理推导出来。6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统定义8：设F为属性集Ｕ上的一组函数依赖，XＵ。X+＝{A｜X→A能由F根据Armstrong公理导出}称为属性集X关于函数依赖集F的闭包。例:关系模式R(A1,A2,A3)的函数依赖集F为{A1→A2，A2→A3}6.2关系数据库设计理论(1)若X=A1,X+=(2)若X=A2,X+= (3)若X=A3,X+={A1,A2,A3}{A2,A3}{A3}6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统引理2设F为属性集Ｕ上的函数依赖，X、YＵ，X→Y能由F根据Armstrong公理导出的充分必要条件是YX+。证：6.2关系数据库设计理论引理2把判定X→Y是否能由F根据Armstrong公理导出的问题转化为求出X+6.2.3函数依赖的公理系统6.2关系数据库设计理论引6.2.3函数依赖的公理系统算法1计算X+输入:X，F输出:X+方法：1.X(1):=空集合；X(0):=X;2.B:={A|V→W∈F，VX(0)，A∈W｝；3.X(1):=B∪X(0);4.IFX(1)≠X(0)THENX(0):=X(1);GOTO２；ELSEX+:=X(1)ENDIF.6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统算法1计算X+例：Ｕ＝{A,B,C,D,E}，Ｆ＝{AB→C,AC→B，B→D，C→E，EC→B}，求(AB)+。6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统定理3算法1正确地计算出了X关于F的闭包X+。证：算法的终止性算法的正确性6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统定理4Armstrong公理系统是有效而且完备的。证：Armstrong公理的有效性已由定理1证明；现只需证明完备性（Armstrong公理的完备性指的是F+中的每一个函数依赖一定可以由F出发根据Armstrong公理推导出来）。6.2关系数据库设计理论证明完备性的逆否命题：如果函数依赖X→Y不能由Ｆ根据Armstrong公理导出，它必然不为Ｆ蕴含。由F出发经Armstrong公理导出的函数依赖集合为F+6.2.3函数依赖的公理系统6.2关系数据库设计理论由6.2.3函数依赖的公理系统两个概念 定义9：设G和F是两个函数依赖集。如果G+=F+则称F与G等价。引理3设G和F是两个函数依赖集。F与G等价的充分必要条件是FG+且GF+。证明：引理3给出了一个判断两个函数依赖集等价的算法。6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统两个概念 定义10：函数依赖集F称为极小(或最小)函数依赖集如果F满足下列条件:(1)F中任一函数依赖的右部仅含有一个属性；(2)F中不存在这样的函数依赖X→A，使得F与F－{X→A}等价；(3)F中不存在这样的函数依赖X→A：X包括真子集Z使得(F－{X→A})∪{Z→A}与F等价。定理5每一个函数依赖集F都等价于一个极小函数依赖集。构造性证明6.2关系数据库设计理论6.2.3函数依赖的公理系统6.2关系数据库设计理论6.2.3函数依赖的公理系统极小函数依赖集不唯一例：6.2关系数据库设计理论F1＝{Ａ→Ｂ，Ｂ→Ｃ，Ｃ→Ａ}F2＝{Ａ→Ｂ，Ｂ→Ａ，Ａ→Ｃ，Ｃ→Ａ}F＝{Ａ→Ｂ，Ｂ→Ａ，Ｂ→Ｃ，Ａ→Ｃ，Ｃ→Ａ}的最小函数依赖集为F＝{Ａ→Ｂ，Ｂ→Ｃ，Ｂ→Ａ，Ａ→Ｃ，Ｃ→Ａ}的最小函数依赖集为6.2.3函数依赖的公理系统6.2关系数据库设计理论F6.2.4关系模式的规范形式以函数依赖为基础讨论关系模式的规范形式(范式)。关系模式的范式主要有四种第一范式（1NF）第二范式（2NF）第三范式（3NF）BC范式（BCNF）满足这些范式条件的关系模式可以在不同程度上避免本节开始提到的冗余问题、插入问题、更新问题和删除问题。6.2关系数据库设计理论6.2.4关系模式的规范形式6.2关系数据库设计理论6.2.4关系模式的规范形式把一个给定关系模式转化为某种范式的过程称为关系模式的规范化过程，简称为规范化。6.2关系数据库设计理论6.2.4关系模式的规范形式6.2关系数据库设计理论6.2.4关系模式的规范形式关系模式范式的基本概念定义11：第一范式(1NF)设Ｒ是一个关系模式。如果Ｒ的每个属性的值域都是不可分的简单数据项的集合，则称这个关系模式为第一范式关系模式，记作1NF。在任何一个关系数据库系统中，第一范式都是一个最起码的要求。在以后的讨论中，我们假定所有关系模式都是1NF。6.2关系数据库设计理论6.2.4关系模式的规范形式6.2关系数据库设计理论6.2.4关系模式的规范形式关系模式范式的基本概念定义12：第二范式(2NF)若关系模式Ｒ是1NF，而且每一个非主属性都完全函数依赖于Ｒ的键，则Ｒ称为第二范式关系模式，记作2NF。6.2关系数据库设计理论例：非2NF的关系U＝{S#,SD,MN,C#,G}存在的问题分解：消除对主属性的部分依赖SC(S#,C#,G)，SSS(S#,SD,MN)6.2.4关系模式的规范形式6.2关系数据库设计理论例6.2.4关系模式的规范形式关系模式范式的基本概念定义13：第三范式(3NF)如果关系模式Ｒ是2NF,而且它的任何一个非键属性都不传递地依赖于任何候选键，则Ｒ称为第三范式关系模式，记作3NF。6.2关系数据库设计理论例：关系模式SC(S#,C#,G)没有传递函数依赖，是3NF。存在的问题分解：消除对主属性的传递依赖SSD(S#,SD)，SSL(SD,MN)都是3NF。例：关系模式SSS(S#,SD,MN)中，从S#→SD、SDS#和SD→MN可知S#传递地确定MN。于是，SSS存在非键属性对候选键的传递依赖，不是3NF。6.2.4关系模式的规范形式6.2关系数据库设计理论6.2.4关系模式的规范形式关系模式范式的基本概念定义14：BCNF范式(BoyceCoddNormalForm)设关系模式R是1NF。如果对于R的每个函数依赖X→Y，则X必为候选键，则R是BCNF范式。每个BCNF关系模式都具有如下三个性质：①所有非键属性都完全函数依赖于每个候选键。②所有键属性都完全函数依赖于每个不包含它的候选键。③没有任何属性完全函数依赖于非键的任何一组属性。6.2关系数据库设计理论6.2.4关系模式的规范形式6.2关系数据库设计理论6.2.4关系模式的规范形式关系模式范式的基本概念6.2关系数据库设计理论BCNF3NF?6.2.4关系模式的规范形式6.2关系数据库设计理论B6.2.4关系模式的规范形式关系模式范式的基本概念例：关系模式SJP(S,J,P)；S表示学生，J表示课程，P表示名次。每个学生每门课程都有一个确定的名次，每门课程中每一名次只有一个学生。由这些语义得到下面的函数依赖：{S,J}→P和{J,P}→S。{S,J}与{J,P}都是候选键。这个关系模式中显然没有属性对候选键的传递依赖或部分依赖。SPJ是3NF，同时也是BCNF。6.2关系数据库设计理论6.2.4关系模式的规范形式6.2关系数据库设计理论6.2.4关系模式的规范形式关系模式范式的基本概念例：关系模式STJ(S,T,J)；S表示学生，T表示教师，J表示课程。每一教师只教一门课，每门课由若干教师教。某一学生选定某门课，就确定了一个固定的教师。由这些语义得到下面的函数依赖：{S,J}→T，{S,T}→J，T→J。(S,J)和(S,T)都是候选键。STJ是3NF，因为没有任何非键属性传递或部分依赖于任何候选键。但STJ不是BCNF，因为T是决定属性，而T不是候选键。6.2关系数据库设计理论6.2.4关系模式的规范形式6.2关系数据库设计理论6.2.4关系模式的规范形式关系模式范式的基本概念如果一个关系数据库的所有关系模式都属于BCNF，那么在函数依赖范畴内，它已达到了最高的规范化程度，已消除了插入和删除的异常。6.2关系数据库设计理论6.2.4关系模式的规范形式6.2关系数据库设计理论6.2.5多值依赖与第四范式6.2关系数据库设计理论例：设学校中某一门课程由多个教员讲授，他们使用相同的一套参考书。用关系模式TEACH(C,T,B)来表示教员T、课程C和参考书B之间的关系。属于BCNF的关系模式是否就很完美了呢？6.2.5多值依赖与第四范式6.2关系数据库设计理论例6.2.5多值依赖与第四范式6.2关系数据库设计理论问题的原因：存在多值依赖！对关系模式TEACH的分析：候选键：（C,T,B）（T,B）BCNF存在的问题：数据冗余！6.2.5多值依赖与第四范式6.2关系数据库设计理论问题6.2.5多值依赖与第四范式定义15：设Ｒ是一个具有属性集合Ｕ的关系模式，Ｘ、Ｙ和Ｚ是Ｕ的子集，并且Ｚ＝Ｕ－Ｘ－Ｙ，多值依赖Ｘ→→Ｙ成立当且仅当对Ｒ的任一关系ｒ，ｒ在（Ｘ，Ｚ）上的每个值对应一组Ｙ的值，这组值仅仅决定于Ｘ值而与Ｚ值无关。6.2关系数据库设计理论6.2.5多值依赖与第四范式6.2关系数据库设计理论6.2.5多值依赖与第四范式例：在TEACH关系实例中，每个(C,B)上的值对应一组T值，而且这种对应与Ｂ无关。例如，尽管与(C,B)对应的两个元组(化学，有机化学)和(化学，无机化学)在B属性上的值不同(一个是“有机化学”，一个是“无机化学”)，它们都对应T的同一组值{张强，王微}。因此，T多值依赖于C，即C→→T。6.2关系数据库设计理论6.2.5多值依赖与第四范式6.2关系数据库设计理论6.2.5多值依赖与第四范式例：在关系模式WSC(W,S,C)中，W表示仓库，S表示保管员，C表示商品。假设每个仓库有多个保管员和多种商品。每个保管员保管所在库的所有商品，每种商品被所有保管员保管。按照WSC的语义，对于W的每个值Wi，Ｓ有一个完整的集合与之对应而不问C取何值。故W→→S。由C与S的完全对称性，有W→→C成立。6.2关系数据库设计理论6.2.5多值依赖与第四范式6.2关系数据库设计理论6.2.5多值依赖与第四范式与函数依赖类似，可以定义多值依赖集合D的闭包D+。我们也有一组完备有效的多值依赖推理规则，可以用来推导出D+中的所有多值依赖。6.2关系数据库设计理论6.2.5多值依赖与第四范式6.2关系数据库设计理论6.2.5多值依赖与第四范式多值依赖的公理A1自反律若ＹＸ，则Ｘ→Ｙ。A2增广律若Ｘ→Ｙ，则ＸＺ→ＹＺ。A3传递律若Ｘ→Ｙ和Ｙ→Ｚ，则Ｘ→Ｚ。A4对称律若Ｘ→→Ｙ，则Ｘ→→Ｕ－Ｘ－Ｙ。A5多值增广率若Ｘ→→Ｙ，ＶＷ，则ＷＸ→→ＶＹ。A6多值传递律若Ｘ→→Ｙ，Ｙ→→Ｚ，则Ｘ→→Ｚ－Ｙ。A7替代律若Ｘ→Ｙ，则Ｘ→→Ｙ。A8聚集律若Ｘ→→Ｙ，ＺＹ，Ｗ∩Ｙ＝，Ｗ→Ｚ，则Ｘ→Ｚ。6.2关系数据库设计理论6.2.5多值依赖与第四范式6.2关系数据库设计理论6.2.5多值依赖与第四范式定理6多值依赖公理是有效的和完备的。6.2关系数据库设计理论6.2.5多值依赖与第四范式6.2关系数据库设计理论6.2.5多值依赖与第四范式上述八条公理的推理规则：(1)多值合并律：若Ｘ→→Ｙ，Ｘ→→Ｚ，则Ｘ→→ＹＺ。(2)多值伪传递律：若Ｘ→→Ｙ，ＷＹ→→Ｚ，则ＷＸ→→（Ｚ－ＷＹ）。(3)多值分解律：若Ｘ→→Ｙ，Ｘ→→Ｚ，则Ｘ→→Ｙ∩Ｚ，Ｘ→→Ｙ－Ｚ，Ｘ→→Ｚ－Ｙ。(4)混合伪传递律：若Ｘ→→Ｙ，ＸＹ→Ｚ，则Ｘ→（Ｚ－Ｙ）。6.2关系数据库设计理论6.2.5多值依赖与第四范式6.2关系数据库设计理论6.2.5多值依赖与第四范式定理7多值依赖的推理规则是正确的。6.2关系数据库设计理论6.2.5多值依赖与第四范式6.2关系数据库设计理论6.2.5多值依赖与第四范式定义16：设R是一个关系模式，D是R上的多值依赖集。如果对于R的每个多值依赖X→→Y(Y-X=非空集,XY未包含R的全部属性)，X都含有R的候选键，则R是第四范式关系模式，简记4NF。6.2关系数据库设计理论6.2.5多值依赖与第四范式6.2关系数据库设计理论6.2.5多值依赖与第四范式当D包含函数依赖时，如果关系模式R是4NF，则R必为BCNF，反之不然。例：关系模式WSC具有两个多值依赖W→→S和W→→C。WSC的唯一候选键是全键{W,S,C}。由于W不是候选键，WSC不是4NF，但是WSC是BCNF。WSC的关系可能具有相当大的数据冗余。例如，若某一仓库Wi有ｎ个保管员，存放m件物品，则对应关系中属性W的值为Wi的元组数是m×n。每个保管员重复存储m次，每种物品重复存储n次。可以通过把WSC分解为4NF关系模式的方法减少数据冗余。例如，我们可以把WSC分解为WS(W,S)和WC(W,C)两个关系模式。WS和WC都是4NF。6.2关系数据库设计理论6.2.5多值依赖与第四范式6.2关系数据库设计理论6.2.6连接依赖与第五范式定义17：设R、R1、...、Rn是关系模式，U、U1、...、Un分别是R、R1、...、Rn的属性集合，而且U＝U∪U1∪...∪Un。如果R的任意关系实例ｒ满足ｒ＝∏R1(ｒ)∏R2(ｒ)...∏Rn(ｒ) 则称R满足连接依赖,记作(R1,...,Rn)。在上述定义中，如果存在一个i使得Ri＝R，则对应的连接依赖称为平凡连接依赖。6.2关系数据库设计理论6.2.6连接依赖与第五范式6.2关系数据库设计理论6.2.6连接依赖与第五范式考虑关系模式R上的连接依赖(R1,R2)。这个连接依赖要求R的每个实例ｒ必须满足ｒ＝∏R1(ｒ)∏R2(ｒ)。设ｒ是R的由满足如下条件的两个元组t1和t2构成的关系实例t1[R1-R2]=(a1,a2,...,ai),t2[R1-R2]=(b1,b2,...,bi),t1[R1∩R2]=(ai+1,...,aj),t2[R1∩R2]=(ai+1,...,aj)，t1[R2-R1]=(aj+1,...,an),t2[R2-R1]=(bj+1,...,bn)。于是,t1[R1∩R2]=t2[R1∩R2],但是t1和t2在所有其他属性上具有不同的值。容易验证ｒ≠∏R1(ｒ)∏R2(ｒ)。于是,R不满足连接依赖(R1,R2)。6.2关系数据库设计理论6.2.6连接依赖与第五范式6.2关系数据库设计理论6.2.6连接依赖与第五范式定义18：设R、R1、R2、...、Rn是关系模式,Ri的属性集合包含在R的属性集合中，D是R上的函数依赖、多值依赖和连接依赖的集合。R称为满足D的第五范式，如果对于D+中的每个连接依赖(R1,R2,...,Rn)下面两条至少一条成立：(1)(R1,R2,...,Rn)是平凡连接依赖，(2)每个Ri都包含R的一个候选键。第五范式简称PJNF。可以证明,PJNF也是4NF。6.2关系数据库设计理论6.2.6连接依赖与第五范式6.2关系数据库设计理论6.1形成初始关系数据库模式6.2关系数据库设计理论6.3关系模式规范化方法6.4关系模式的优化6.5完整性和安全性约束的定义6.6逻辑数据库的性能估计6.3关系模式规范化方法第六章逻辑数据库设计6.1形成初始关系数据库模式6.3关系模式规范化方法关系模式的分类：静态关系：一旦数据已加载,用户只能在这个关系上运行查询操作,不再进行插入、删除和更新操作。动态关系：经常被更新、插入和删除。6.3关系模式规范化方法静态关系只需具有第一规范形式。动态关系必须至少具有第三规范形式。关系模式的分类：6.3关系模式规范化方法静态关系只需具有第关系模式规范化的主要方法：关系模式分解。把一个关系模式分解为几个子模式，使得这些子模式具有指定的规范化形式。关系模式分解中的重要问题是分解的无损连接性和函数依赖保持性。6.3关系模式规范化方法关系模式规范化的主要方法：关系模式分解。6.3关系模式规范例：关系模式R的属性集合U={S#,SD,MN},函数依赖集合F={S#→SD,SD→MN}。6.3关系模式规范化方法S#SDMNS1D1张红S2D1张红S3D2李微S4D3王力R的关系实例:该实例存在的问题:例：6.3关系模式规范化方法S#SDMNS1D1张红S2D6.3关系模式规范化方法例：关系模式R的属性集合U={S#,SD,MN},函数依赖集合F={S#→SD,SD→MN}。分解1：1＝{R1(S#)，R2(SD)，R3(MN)}S1S2S3S4D1D2D3张红李薇王力R1R2R36.3关系模式规范化方法例：分解1：1＝{R1(S#)，6.3关系模式规范化方法例：关系模式R的属性集合U={S#,SD,MN},函数依赖集合F={S#→SD,SD→MN}。分解2：2＝{R1(S#，SD)，R2(S#，MN)}R1R2S1D1S2D1S3D2S4D3S1张红S2张红S3李薇S4王力6.3关系模式规范化方法例：分解2：2＝{R1(S#，6.3关系模式规范化方法例：关系模式R的属性集合U={S#,SD,MN},函数依赖集合F={S#→SD,SD→MN}。分解2：3={R1(S#,SD)，R2(SD,MN)}R1R2S1D1S2D1S3D2S4D3D1张红D2李薇D3王力6.3关系模式规范化方法例：分解2：3={R1(S#6.3关系模式规范化方法定义6.3.1设R是具有属性集合U的关系模式。R的一个分解定义为={R1,R2,...,Rn},其中,Ri的属性集合是Ui，而且。6.3关系模式规范化方法定义6.3.1定义6.3.2设R是一个具有属性集合U和函数依赖集合F的关系模式，={R1,...,Rn}是R的一个分解。F在Ri的属性集合Ui上的投影是Fi={X→Y｜X→Y∈F+,X,Y∈Ui}。6.3关系模式规范化方法定义6.3.26.3关系模式规范化方法定义6.3.3设={R1,...,Rn}是关系模式R的一个分解，ｒ是R的一个关系。定义m(r)＝R1(r)R2(r)...Rn(r)，即m(r)是r在中各关系模式上投影的连接。6.3关系模式规范化方法定义6.3.36.3关系模式规范化方法引理6.3.1设R是一个关系模式，={R1,...,Rn}是R的一个分解，ｒ是R的一个关系实例，则：(1)rm(r)。(2)若ｓ＝m(r)，则Ri(ｒ)＝Ri(s)。(3)m(m(r))＝m(r)。证明：6.3关系模式规范化方法引理6.3.16.3关系模式规范化方法定义6.3.4设＝{R1,...,Rn}是R的一个分解。若对R的任何一个关系ｒ均有r=m(ｒ)成立，则称分解具有无损连接性。简称为无损连接分解。6.3关系模式规范化方法定义6.3.46.3关系模式规范化方法算法6.3.1判别一个分解的无损连接性。输入:关系模式R(A1,...,An),R的函数依赖集F,R的分解＝{R1,...,Rk}。输出:分解是否具有无损连接性。方法:108页6.3关系模式规范化方法算法6.3.1判别一个分解的无损连接性。6.3关系模式规无损连接分解例：关系模式R的属性集合U={A,B,C,D,E}函数依赖集F={A→C,B→C,C→D,DE→C,CE→A}分解={R1(A,D),R2(A,B),R3(B,E),R4(C,D,E),R5(A,E)}6.3关系模式规范化方法无损连接分解例：6.3关系模式规范化方法定理6.3.1关系R的分解具有无损连接性的充分必要条件是算法6.3.1终止时,矩阵S中有一行为(a1,a2,...,an)。6.3关系模式规范化方法定理6.3.1关系R的分解具有无损连接性的充分必要条件是当关系模式R被分解为两个子模式时,下述定理给出了一个判别无损连接性的简单方法。定理6.3.2设ρ={R1,R2}是关系模式R的一个分解,U1、U2和U分别是R1、R2和R的属性集合,F是R的函数依赖集合。ρ具有无损连接性的充分必要条件是U1∩U2→U1-U2∈F+或U1∩U2→U2-U1∈F+。6.3关系模式规范化方法当关系模式R被分解为两个子模式时,下述定理给出了一个判别无定义6.3.5设R是具有属性集合U和函数依赖集合F的关系模式,={R1,...,Rk}是R的一个分解，Ui是Ri的属性集合,Fi是F在Ui上的投影。如果,则称具有函数依赖保持性。6.3关系模式规范化方法定义6.3.56.3关系模式规范化方法算法6.3.2函数依赖保持性的判别算法输入:函数依赖集F,F1,F2,…,Fk,记。输出:是否F+=G+。方法:(1)FOR每个X→Y∈FDOIFY不属于X关于G的闭包THEN输出"F+≠G+",停止。ENDFOR；(2)输出“F+=G+”,停止。6.3关系模式规范化方法算法6.3.2函数依赖保持性的判别算法6.3关系模式规关系模式分解算法算法6.3.33NF分解算法1：只能保证函数依赖保持性的分解算法。见111页。定理6.3.3设关系模式R的分解={R1,...,Rk}是算法6.3.3的输出结果，G是F的最小函数依赖集，则具有函数依赖保持性，而且中每个关系模式都是3NF。6.3关系模式规范化方法关系模式分解算法6.3关系模式规范化方法关系模式分解算法算法6.3.43NF分解算法2：既能保证函数依赖保持性也能保证无损连接性的分解算法。见112页。定理6.3.4设关系模式R的分解={R1,...,Rn,RK}是算法6.3.4的输出结果，U是R的属性集合，则具有函数依赖保持性和无损连接性，而且中每个关系模式都是3NF。6.3关系模式规范化方法关系模式分解算法6.3关系模式规范化方法关系模式分解算法算法6.3.5BCNF分解算法：仅具有无损连接性。见112页。引理6.3.2设R1、R2、R3是关系模式,其属性集合分别为U1、U2、U3。则有(R1R2)R3=R1(R2R3)。6.3关系模式规范化方法关系模式分解算法6.3关系模式规范化方法关系模式分解算法引理6.3.3如果ρ={R1,R2,...,Rk}是R的一个无损连接分解，σ={S1,...,Sm}是Ri的一个无损连接分解,μρ，则(1)λ={R1,...,Ri-1,S1,...,Sm,Ri+1,...,Rk}是R的无损连接分解;(2)μ={R1,...,Rk,Rk+1,...,Rn}是R的无损连接分解。6.3关系模式规范化方法关系模式分解算法6.3关系模式规范化方法关系模式分解算法定理6.3