数据库原理与程序设计孙杰第6章逻辑数据库设计

1、第6章 逻辑数据库设计,生物医学软件工程,逻辑结构设计的任务把概念结构设计阶段设计好的ER图转化为与选用的DBMS产品所支持的数据模型相符合的逻辑结构。,本章概要,形成初始关系数据库模式 关系数据库设计理论 关系模式作规范化方法 关系模式的优化 定义关系完整性和安全性约束 逻辑数据库的性能估计,6.1 形成初始关系数据库模式,初始关系数据库模式是指使用简单方法直接由概念数据库模式生成的关系数据库模式。 从概念模式到初始关系模式的变换方法如下： 普通实体型变换为关系模式 R 弱实体型 W 变换为关系模式 R 实体型 E 的多值属性 A 变换为关系模式 T 实体型之间的联系型 R 的变换为关系模式

2、 W 超类/子类联系型变换为关系模式 范畴和共享子类的变换,一、普通实体型的变换,概念模式中的实体型 E 转换为关系 S，S 包含 E 的所有简单属性和复合属性的简单子属性，E 的键是 S 的主键。,关系T( 姓名, 证号, 工资, 邮编, 市, 区, 学校, 信箱, 课程, 教研室 ),二、弱实体的变换,概念模式中设 W 是以实体型 E 为识别实体型的弱实体，建立一个与W对应的关系 R。 规则：W 的所有简单属性和复合属性的简单子属性映射为 R 的属性；E 的键属性也是 R 的属性；R的键由E的键和W的部分键组成。 根据规则： R(父亲证号, 姓名, 性别, 区号, 房号, 床号),三、多值

3、属性的变换,具多值属性 A 的实体 E 变换为关系 S。 方法是为属性A建立关系 T。设 E 的键为k，则 T 的结构如下： 若A是简单属性，则T的属性为k, A； 若A是复合属性 (a1, a2)，则T的属性为 k, a1, a2 根据规则： S( 证号，姓名 ) T1 ( 证号，年，校，学衔 ) T2 ( 证号，任课编号 ),四、实体间联系的变换,实体联系型 R 变换为关系 W， 将联系相关是实体型A, B变换为关系 S, T; (1) 1:N的联系的变换(包括1:1) 方法1：取1方的键,添加到 N方,作为 N 方的外部键; R层次结构中的全体简单属性添加到N端。 方法2：构造关系W,至

4、少含两个属性,分别是A、B的键, R层次结构中的全体简单属性。 (2) M:N联系的变换 需要建立一个新关系W，将S和T的主键添入W，即将它们作为外部键，也将它们组合起来作为W的主键。W还需要包含R的简单属性和简单子属性。,五、超类/子类联系的变换,设超类实体型 C 的属性是 k, A1, , An，其中 k 是键。E1, Em是 C 的子类。 方法1：建立超类对应的关系，其属性是C的属性，k是键；建立子类Ei对应的关系，其属性是Ei的属性和k，k是键。要求各子类在k的投影是超类在k投影的子集。 方法2：建立子类Ei对应的关系，其属性是C和Ei的属性，k是键。适合于全域约束和正交约束的情况。

5、方法3：综合超子类所有属性建立关系，增添一个特殊属性t，用来说明元组所属的子类，k是键；适合于正交约束的情况。 方法4：综合超子类所有属性建立关系， k是键，增添m个特殊属性ti，用来说明元组是否属于子类Ei 。适合于子类相交的情况。,超类员工对应的关系：员工(证号,姓名,性别) 子类医师对应的关系：医师(证号,学位) 子类护士对应的关系：护士(证号,工龄),子类医师对应的关系：医师(证号,姓名,性别,学位) 子类护士对应的关系：护士(证号, 姓名,性别,工龄),建立关系：员工(证号,姓名,性别,学位,工龄,职务),可以用下边关系表示： 员工(证号,姓名,性别,课程,学时,业务,职位,a,b)

6、 a=1,表示该员工是教师；b1表示该员工是行政人员。,六、范畴和共享子类的变换,设C是E1, Em的范畴或共享子类， 若所有Ei有相同的键k，则用C的所有属性连同k建立一个关系L，k作为L的键。 若所有Ei有不同的键，则用C的所有属性及一个特殊属性k建立一个关系L，k作为L的键，并将k作为外部键加入到 E1,Em中。,转换方法1 教师(证号,姓名,课程,时数) 干部(证号,姓名,业务,职务) 工人(证号,姓名,工种,工龄) 住户(证号,房号,水费,电费) 转换方法2 教师(教号,姓名,课程,时数,编号) 干部(证号,姓名,业务,职务,编号) 工人(工号,姓名,工种,工龄,编号) 住户(编号,

7、房号,水费,电费),例：教务管理系统,七、确定函数依赖集,已形成初始关系数据库模式，但其中某些关系模式可能存在后边指出的冗余问题、插入问题、更新问题和删除问题。 需要对所产生的初始关系数据库模式进行后边介绍的规范化处理。,本章概要,形成初始关系数据库模式 关系数据库设计理论 关系模式作规范化方法 关系模式的优化 定义关系完整性和安全性约束 逻辑数据库的性能估计,6.2 关系数据库设计理论,一、问题的提出 考虑关系模式：学生(学号,系名,系主任,课名,成绩) 假定学校的教学环境有以下的基本情况： 一个系有多名学生，但一个学生属于并只属于某一个系； 一个系有且只有一名主任； 每个学生可选多门课程，

8、每门课程供多名学生选修； 每个学生修每门课程都有一个成绩。,这意味上述关系属性之间存在如下的决定关系：学号决定系名，系名决定系主任，(学号,课名)决定成绩。对决定关系进行形式化描述，就得出函数依赖概念。 上述关系模式有以下四个问题： 插入异常：系刚成立，没有学生，使系名和主任信息无法存入； 删除异常：全体学生毕业，资料删除，系名和主任信息随之删除； 数据冗余：主任数据重复存储，降低时空效率，增加维护复杂性; 数据更新：更新冗余数据容易引起数据不一致。,四个问题的产生原因是： 关系模式的属性之间存在较复杂的决定关系 解决方法： 对属性集合作适当分组，即后边介绍的规范化处理。,二、函数依赖,定义1

9、：设 R 是关系模式，U 是其属性集，X、Y 是 U 的子集。对 R 任取实例 r，对 r任取两个元组 t1和t2， 若 t1X=t2X，则t1Y=t2Y，则称 Y函数地依赖于X，或X函数地确定Y；记XY。 若XY，YX，即X和Y互相函数依赖，则记作XY。,学号身份证号,注意： 函数依赖实际是对现实世界某些强制性约束的抽象描述。 若XY,而且Y是X的子集，称为平凡函数依赖； 若XY,而且Y不是X的子集，称为非平凡的函数依赖。 关系模式上全体函数依赖由两部分组成：基本部分直接由语义得到，其它部分由公理系统导出。,例：,考虑关系模式；学生(学号,姓名,课程,分数)设有函数依赖：学号姓名 该函数依赖

10、意味着应用领域有这么一个约束：关系模式的任意实例(例如下边列出的两个实例)，实例中的任意两行，只要这两行在学号等值，那么这两行在姓名也必须等值。,定义2：若XY，而X 的任何真子集 Z，ZY不成立，则称X完全函数确定Y，或Y完全函数依赖于X； 若XY,但Y不完全函数依赖于X,则称X部分函数确定Y，或称Y部分函数依赖于X。 例：考虑关系模式：学生(学号,姓名,课程,分数)。设有函数依赖： 学号姓名，学号,课程分数 学号,课程姓名,显然，若X仅包含一个属性，则XY意味着Y完全函数依赖于X。,定义3：设R是关系模式，U是其属性集，X、Y、Z是U的子集，YX不成立，Z-X、Z-Y、Y-X非空。若XY，

11、YZ，则称X传递地函数确定Z，或称Z传递地函数依赖X。 例1：考虑关系模式；学生(学号,系,主任)。设有函数依赖：学号系主任。 由于系学号不成立，主任-学号、主任-系、系-学号均非空，故主任传递地函数依赖于学号。,考虑关系模式；学生(身份证号,学号,系) 设有函数依赖：身份证号学号系； 虽可推出身份证号系，但不能说系传递地函数依赖于身份证号。,考虑关系模式；学生(学号,姓名,性别) 令X=学号，Y= (姓名,性别)，Z=姓名。 设有函数依赖XY， 虽然YX不成立，且可推出YZ，但因Z-Y为空， 故不能说Z传递地函数依赖于X。,定义4：设R是关系模式，U是其属性集，KU。若K完全函数确定U，则称

12、K是R的候选键。 包含在任意候选键内的属性称为键属性，不是键属性的属性称为非键属性。在最简单的情况下，候选键只包含一个属性，在最复杂的情况下，候选键包含关系模式的所有属性,称为全键。 定义5 若关系R的属性子集X是另一关系S的候选键，则称X是R关于S的外部键。,主键和外部键描述了关系之间的联系,例,下边三个关系实例表中，有下划线的属性子集是主键。 表2的学号是关于表1的外部键，课号是关于表3的外部键。,三、数据依赖的公理系统,定义6：设关系模式 R 有属性集 U 和函数依赖集 F。若对 R 任一个使 F 成立的关系实例 r，函数依赖 XY 都成立，则称 F逻辑蕴含XY。 F蕴含XY意味着关系实

13、例只要满足F就必然满足XY。,学号系，系系主任 逻辑蕴涵学号系主任， 因为任意两元组，只要在学号等值，就必在系等值， 从而在系主任等值。,Armstrong公理系统：设关系模式 R 具有属性集合 U 和函数依赖集合 F。Armstrong公理系统包含如下三条推理规则： 自反律：若 Y X U，则F蕴含 XY. (XY是平凡依赖,与F无关) 增广率：若F蕴含XY,ZU,则F蕴含XZYZ. 传递率：若F蕴含XY,YZ,则F蕴含XZ.,定理1：Armstrong推理规则是正确的。(简称为A规则) 我们下面从函数依赖和蕴含的定义来证明A公理的三条推理规则,定理2：三条推理规则： 合并规则:若XY，XZ

14、，则XYZ； 伪传递规则:若XY，YWZ，则XWZ； 分解规则:若XY，Z Y，则XZ。 证1：由XY和增广率得XXY，由XZ和增广率得XYYZ，最后由传递率得XYZ . 证2：由XY和增广率得XWYW，由YWZ和传递率得XWZ . 证3：由ZY及自反率得YZ，再由XY和传递率得XZ .,引理1：XAB成立的充分必要条件是XA，XB. 引理1的推广形式是：XA1A2 Ak成立的充分必要条件是XAj (1jk) 定义7：设关系模式 R 有属性集 U 和函数依赖集 F，由 F 蕴含的所有函数依赖称为 F的闭包F+。,定义8：设关系模式 R 有属性集 U 和函数依赖集 F，XU。定义X+=A|XA能

15、由F通过Armstrong准则导出为属性子集X 关于函数依赖集 F 的闭包。 引理2：设关系模式R有属性集U和函数依赖集F，则XY能由F按A规则导出的充要条件是YX+ .,例：关系模式R(A,B,C)，函数依赖集FAB, BC 若X=A,则X+=A,B,C 若X=B,则X+=B,C 若X=C,则X+=C,计算闭包X+的算法：,算法1：给出属性子集 X 及函数依赖集 F，计算X+。 X0:=X; /*属性子集X0从X开始沿依赖集F扩张*/ B:=A|VWF,VX0,AW; /*扫描F中决定因素V含于X0的函数依赖VW，取W的所有属性*/ X1:=X0 B; if X1X0 then X0:=X1

16、;goto 2 else X+:=X1 endif,例：闭包的计算举例,已知关系模式R的属性集合U=A,B,C,D,E,函数依赖集合F=ABC, ACB, BD, CE, ECB，求(AB)+. 定理3：上面的算法能够正确的计算出 X 关于 F 的闭包X+.,定理4：Armstrong公理系统是有效且完备的。 定义9：设G、F是两个函数依赖集，若G+=F+，则称G、F等价。 引理3：函数依赖集G、F等价的充要条件是：FG+ ，GF+。,A公理的有效性是指:由F出发,按A公理推导的函数依赖一定在F+中;,A公理的完备性是指：F+中所有函数依赖必可由F出发按A公理推出.,定义10：满足以下条件的函

17、数依赖集F称为极小函数依赖集: F 任一依赖的右边是简单属性； XAF , F-XA与F不等价； XAF，ZX(真子集)，(F-XA) ZA 与 F 不等价。,例：,关系模式S : U= S#, SD, MN, CN, G , F= S#SD, SDMN, (S#, CN)G , F= S#SD, S#MN, SDMN, (S#,CN)G, (S#, SD)SD. F是最小覆盖 F不是最小覆盖 定理5：每个函数依赖集F都等价于一个极小函数依赖集。,例：求A-B, B-A, B-C, A-C, C-A的极小函数依赖集 结果1：A-B, B-C, C-A 结果2：A-B, B-A, A-C, C-

18、A,四、关系模式的规范形式,基于函数依赖概念的关系模式的范式(简称范式)主要有四种，即第一范式、第二范式、第三范式和BCNF范式. 关系模式满足这些约束可在一定程度上避免本节开头提到的四个异常问题：冗余问题、插入问题、更新问题和删除问题。,第一范式定义：若关系模式每个属性的值都是不可分的简单数据项，则称该关系模式为满足第一范式，简写为1NF. 第二范式定义：满足1NF的关系模式，若所有非主属性完全地依赖于键，则称之为满足第二范式，简写为2NF.,反例: 学生(学号,系名,系主任,课名,成绩) S(S#, SD, MN , C# , G) F=(S#,C#) -G, S#-SD,SD-MN 该例

19、存在的问题:插入问题,删除问题,冗余和更新问题,解决方法： 分解 S ( S#, SD, MN , C# , G)成为两个关系模式 使得分解后的子关系满足第二范式 分解结果： SC( S# , C# , G ) , SSS( S# ,SD ,MN ) Fsc=(S# , C# ) - G Fsss=S# -SD ,SD - MN 2NF部分解决了各种问题,第三范式定义：满足2NF的关系模式，若不存在非键属性传递地依赖于任何候选键，则称之为满足第三范式，简写为3NF.,反例：SC( S#，C#，G )，SSS( S#，SD，MN ) Fsc=(S#，C# ) - G Fsss=S# -SD，SD

20、 - MN 解决方法： 把SSS分解为满足第三范式的多个子关系模式 分解结果:SSD( S# , SD ) , SSM( SD , MN),BCNF范式定义：满足1NF的关系模式，若每个函数依赖XY(Y不是X的子集)的决定因素X都含有候选键，则称之为满足BCNF范式.,例,关系模式 Course(cno, cname, pcno) 是否满足2NF？ 是否满足3NF？ 是否满足BCNF？ 关系模式 Student(sno, sname, sdept, sage) 其中学生的姓名也满足唯一性,关系模式 选课(学生，教师，课程) 每个教师只教一门课程 每门课程有多个教师授课 每个学生选定某课程，就对

21、应一个固定的教师,例,候选码 (学生，课程) (学生，教师),函数依赖关系有： (学生, 教师)课程 (学生, 课程)教师 教师课程,存在什么问题？冗余？插入或删除异常？ 是否满足3NF？ 是否满足BCNF？ 解决方法： 把选课关系模式分解为满足BCNF的多个子关系模式 选课1(学生，教师) 授课2(教师，课程),满足2NF： 每一个非主属性都完全依赖于键 满足3NF： 不仅每一个非主属性完全依赖于键 并且每一个非主属性不传递依赖于键 满足BCNF： 非主属性对键的完全的和不传递的依赖 主属性对键的完全的和不传递的依赖,BCNF-3NF-2NF-1NF 如果一个关系数据库的所有关系模式都属于B

22、CNF，那么在函数依赖范围内，它已达到了最高的规范化程度，已消除了插入和删除异常。,第四范式和多值依赖 例：设学校中某一门课程由多个教师讲授，每门课程的参考书是相同的。考虑如下关系模式： 授课(课程，教师，参考书) 存在哪些问题？,多值依赖：设R是一个具有属性集合U的关系模式，X, Y和Z是U的子集， 并且 Z=U-X-Y，多值依赖XY成立当且仅当对R的任意关系r，r在(X, Z)上的每个值对应一组Y的值，这组值仅决定与X，而与Z值无关。 例子中的问题是由于它具有多值依赖的数据依赖而引起的。,4NF：设R是一个关系模式，D是R上的多值依赖集合。如果对于R的每个多值依赖XY(其中，Y-X非空，X

23、Y为包含R的全部属性)，X都含有R的候选键，则R是第四范式关系模式，简记为4NF。,授课(课程，教师，参考书)是否满足4NF？ 课程教师是多值依赖 关系的候选键是全键 故而，不满足4NF 问题在于： 关系模式有多值依赖，却不满足4NF 问题的解决： 授课(课程，教师)，参考书(课程，参考书),本章概要,形成初始关系数据库模式 关系数据库设计理论 关系模式作规范化方法 关系模式的优化 定义关系完整性和安全性约束 逻辑数据库的性能估计,6.3关系模式规范化方法,关系模式可划分为 静态关系模式 动态关系模式,关系模式的规范化关系模式的分解。,具有无损连接性 要保持函数依赖,例1，设 R 是一个关系模

24、式。 属性集合U=学号, 系, 系主任， 函数依赖集合F=学号系，系系主任。 分解为R1(学号), R2(系), R3(系主任); 分解为R1(学号，系), R2(学号，系主任); 分解为R1(学号，系), R2(系，系主任);,一、分解的无损连接性,关系模式 R(U, F)的一个分解是指 = R1, R2, , Rn 其中Ri的属性集是Ui，而且U=Ui Fi 是 F 在 Ui 上的投影 Fi= XY | XYF+, X,YUi ,关系实例的分解的投影连接：设=R1Rn是R的一个分解，r是R的一个实例，称 m(r)=R1(r)Rn(r) 是r在中各子模式的投影连接。 若对任意实例 r 有 r

25、 = m(r)， 则称分解 具无损连接性。,判别一个分解的无损连接性,输入：关系模式R(A1,A2,An)，R的分解 = R1, R2, , Rk. 输出： 分解是否具有无损连接性。,for i=1 to k do for j=1 to n do if Ri 包含属性Aj then Si, j=aj ; else Si, j=bij; Endfor; Endfor;,依次考虑函数依赖集F的每个函数依赖XY，在X对应的列上考虑相同元素所在的行,在Y对应列上考虑上述行的元素子列，并改为相同符号。 如果矩阵S中存在一行全为a类符号，则分解具有无损连接。否则，不具有无损连接。,算法的例题,设关系R(A

26、,B,C,D,E)有函数依赖集F=AC, BC, CD, DEC, CEA， 试判断模式分解=R1(AD), R2(AB), R3(BE), R4(CDE), R5(AE) 是否具有无损连接性。,(1) =R1,R2是关系模式R的一个分解； (2) U1、U2和U分别是R1、R2和R的属性集合； (3) F是R的函数依赖集， 则具无损连接性的充要条件是 U1U2U1-U2F+ 或 U1U2U2-U1F+。,定理2,二、函数依赖保持性,定义5：设关系模式R具有属性集U和函数依赖集 F，=(R1,Rk) 是 R 的一个分解，Ui 是 Ri 的属性集，Fi 是 F 在 Ui 的投影。若F+=(Fi)

27、+，则称分解 具函数依赖保持性。,函数依赖保持性的判断算法,(1)for 每个XYF do if Y 不属于X关于G的闭包 then 输出 F+G+ endfor; (2)输出F+=G+停止.,输入：函数依赖集合F, F1, F2, ,Fk，记G=(Fi) 输出：是否F+=G+,关系模式分解的例子,分解1：1=P(学号)，Q(系属)，R(主任). F1=F2=F3=, G+=(F1F2F3)+=， 因F+ G+，故1不具有函数依赖保持性。 分解2：2=P(学号，系属)，R(学号，主任). F1=学号系属，F2=学号主任 , 因G+缺少系属主任,故F+ G+, 从而2不具有函数依赖保持性。 分解

28、3：3=P(学号，系属)，R(系属，主任). F1=学号系属，F2=系属主任， 容易看到G=(F1F2)=F,故F+=G+ ， 故3具有函数依赖保持性。,三、关系模式的分解算法,这里仅讨论有关3NF、BCNF的分解算法。研究关系模式的分解，必须考虑分解是否满足无损连接性和函数依赖保持性。,输入：关系模式R(U, F) 输出：具有函数依赖保持性的分解，中的所有子关系模式都满足3NF 方法： 对函数依赖集合F，找到与F等价的极小函数依赖集合，仍记为F; 对未在F中出现的属性，这些属性单独构成一个关系，并从U中去除它们； 如果有XAF且XA=U，则算法终止； 否则， 对F按照相同的左部分组，记为Fi

29、 每组相关的全部属性为一个属性集Ui， 若某一属性集Ui被其它属性集Uj包含，去掉Ui 则每对(Ui, Fi)构成一个分解后的关系模式,分解算法1(合成法，3NF，保持函数依赖),例,关系模式 R(学号, 课程号, 姓名, 课程名, 成绩, 系, 系主任) 函数依赖关系集合 F=学号姓名，学号系，系系主任, 课程号课程名，(学号, 课程号)成绩 ,输入：关系模式R(U, F) 输出：既有无损连接性又保持函数依赖保持的分解T，T中的所有子关系模式都满足3NF 方法： 调用分解算法1，得到关系模式R(U, F)的分解=R1,R2,R3,Rn； 设K是R的一个候选键，构成关系模式RK(K, FK)； 令T= RK； 若有某Ui，使得KUi，则从T中去掉RK； T即所求,分解算法2(3NF，无损连接性，保持函数依赖),输入：关系模式R(U, F) 输出：具有无损连接性的分解T，T中的所有子关系模式都满足BC