数据库3.Design

1、数据库系统与应用v 满足用户的完整性和安全性要求。v 动态关系至少具有第三规范形式第三规范形式。v 静态关系至少具有第一规范形式第一规范形式。v 能够在逻辑级上高效率地支持各种数据库事务的运行。v 存储空间利用率高。2022-2-42关系数据库设计：目标2022-2-43关系数据库设计：任务事物类事物性质现实世界信息世界概念数据库设计概念数据库设计实体型实体属性逻辑世界逻辑数据库设计逻辑数据库设计关系记录字段E-R模型模型物理世界文件物理数据库设计物理数据库设计关系模型关系模型1. 形成初始关系数据库模式形成初始关系数据库模式2. 关系模式规范化关系模式规范化3. 关系模式优化4. 定义关系上

2、的完整性和安全性约束5. 子模式定义6. 性能估计2022-2-44关系数据库设计步骤v 问题初始关系模式可以是逻辑设计的最终结果吗?某些关系模式可能存在冗余问题、插入问题、更新问题和删除问题。 2022-2-45形成初始关系数据库模式v 例：学生有下列信息：学号(S#)、系(SD)、系主任(MN)、课程名(CN)、成绩(G)v 有一个描述学生的关系模式：U = S#, SD, MN, CN, Gv 现实世界的已知事实： F = S#SD, SDMN, (S#, CN)G2022-2-46形成初始关系数据库模式2022-2-47插入异常S#SNMNCNGS1计算机刘伟数据库90S1计算机刘伟离

3、散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统852022-2-48删除异常S#SNMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库932022-2-49数据冗余和更新问题S#SNMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统

4、80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库931. 数据冗余：同一系中有n个学生，“系名”与”系主任”就重复n-1次；同一个学生选修了m门课程，学号就重复了m-1次。2. 更新异常：若调整了某系系主任，数据表中所有行的“系主任”值都要更新，否则会出现同一系系主任姓名不同的情况。2022-2-410形成初始关系数据库模式3. 插入异常：假设要开设一门新的课程，暂时还没有人选修。这样，由于还没有“学号”关键字，课程名称和设课系也无法记录入数据库。4. 删除异常：假设一批学生已经完成课程的选修，这些选修记

5、录就应该从数据库表中删除。但是，与此同时，系名与系主任信息也被删除了。很显然，这也会导致插入异常。2022-2-411形成初始关系数据库模式v 需要用关系模式的规范化方法消除初始逻辑数据库模式中存在的问题。v 某些关系模式可能存在由属性间的函数依赖引起的冗余问题、插入问题、更新问题和删除问题。2022-2-412形成初始关系数据库模式v 对初始关系数据库模式中的每个关系模式进行深入地分析，与用户协商，确定每个初始关系的函数依赖集，使用关系数据库设计理论，对关系模式进行规范化处理。v 函数依赖函数依赖：Functional Dependencyv 确定函数依赖集2022-2-413设计理论v 函

6、数依赖定义1：o设R是一个关系模式，U是R的属性集合，X和Y是U的非空子集。对于R的任意实例r，r中任意两个元组t1和t2，如果t1X=t2X，则t1Y=t2Y，我们称X函数地确定Y，或Y函数依赖于X，记作XY。只能根据数据的语义来确定函数依赖只能根据数据的语义来确定函数依赖。描述学生的关系模式：oU = S#, SD, MN, CN, G根据数据的语义确定的函数依赖：oF = S#SD, SDMN, (S#, CN)G2022-2-414设计理论v 如果XY而且Y不是X的子集，则称XY是非平凡函非平凡函数依赖数依赖。若不特别声明，我们总是讨论非平凡函数依赖。如果XY，我们称X为这个函数依赖的

7、决定属性集。 v 描述学生的关系模式：US#, SD, MN, CN, G(S#, SD)SDSDMN2022-2-415函数依赖v 定义2设R是一个具有属性集合U的关系模式，如果XY，并且对于X的任何一个真子集Z，ZY都不成立，则称Y完全函数依赖于X。若XY，但Y不完全函数依赖于X，则称Y部分函数依赖于X。v 描述学生的关系模式：US#,SD,MN,CN,G(S#, SD)MN(S#, CN)G2022-2-416函数依赖v 定义3：设R是一个具有属性集合U的关系模式，XU, YU, ZU，且YX不成立，同时Z-X、Z-Y和Y-X不空。如果XY，YZ，则称Z传递地函数依赖于X。v 描述学生的

8、关系模式：U = S#, SD, MN, CN, G根据S# SD, SD MN, 导出如下传递依赖：S# MN2022-2-417函数依赖v 定义4：（候选键）设R是一个具有属性集合U的关系模式，KU。如果K满足下列两个条件，则称K是R的一个候选键候选键： 1.KU。2.不存在K的真子集Z使得ZU。候选键可以唯一地标识关系的元组。2022-2-418函数依赖v 一个关系模式中可能具有多个候选键，指定其中一个作为识别关系元组的主键。v 包含在任何一个候选键中的属性称为键属性。v 不包含在任何候选键中的属性称为非键属性。v 在最简单的情况下，候选键只包含一个属性。v 在最复杂的情况下，候选键包含

9、关系模式的所有属性，称为全键。2022-2-419函数依赖v 定义5：设X是关系模式R的属性子集合。如果X是另一个关系模式的候选键，则称X是R的外部键。2022-2-420函数依赖v 定义6：设R是一个具有属性集合U的关系模式，F是R上的函数依赖集合。如果对于R的任意一个使F成立的关系实例r，函数依赖XY都成立，则称F逻辑地蕴含逻辑地蕴含XY.已知的函数依赖： F = S#SD, SDMN, (S#, CN)G2022-2-421逻辑蕴含S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S3信息王平操作系统85S4自动化李明数据库93v 给定一个函数依

10、赖集合，希望知道由给定的函数依赖集合所蕴涵的所有函数依赖的集合。v 推导依据：Armstrong公理系统2022-2-422函数依赖的公理系统v Armstrong公理系统 设R是一个具有属性集合U的关系模式，F是R的一个函数依赖集合。Armstrong公理系统包含如下三条推理规则： 2022-2-423函数依赖的公理系统 自反律：若自反律：若Y X U，则，则F蕴含蕴含XY 增广律：若增广律：若F蕴含蕴含XY，Z U，则，则F蕴含蕴含XZYZ 传递律：若传递律：若F蕴含蕴含XY和和YZ，则，则F蕴含蕴含XZ v 三条推论 合并规则：如果XY，XZ，则XYZ。伪传递规则：如果XY，YWZ，则X

11、WZ。分解规则：如果XY，ZY，则XZ。2022-2-424函数依赖的公理系统 自反律：若自反律：若Y X U，则，则F蕴含蕴含XY 增广律：若增广律：若F蕴含蕴含XY，Z U，则，则F蕴含蕴含XZYZ 传递律：若传递律：若F蕴含蕴含XY和和YZ，则，则F蕴含蕴含XZ v 定义7：设R是一个具有属性集合U的关系模式，F是给定的函数依赖集合。由F逻辑蕴含的所有函数依赖称为F的闭包的闭包，记为F+。 v 描述学生的关系模式：US#,SD,MN,CN,Gv 根据数据的语义确定的函数依赖： F = S#SD, SDMN, (S#,CN)GF+ = S#SD, SDMN, (S#, CN)G, S#MN

12、, (S#, SD)SD, 2022-2-425函数依赖的公理系统v Armstrong公理系统是有效有效而且完备完备的吗？Armstrong公理的有效性有效性是指由F出发根据Armstrong公理推导出来的每个函数依赖一定在F+中；Armstrong公理的完备性完备性是指F+中的每一个函数依赖一定可以由F出发根据Armstrong公理推导出来。2022-2-426函数依赖的公理系统v 为了证明Armstrong公理的完备性完备性，首先需要解决如何判定一个函数依赖是否可以由F根据Armstron公理推导出来。2022-2-427函数依赖的公理系统v 引理1：XA1A2.Ak成立的充分必要条件充

13、分必要条件是对于1ik，XAi成立。证明：2022-2-428函数依赖的公理系统合并规则：如果合并规则：如果XY，XZ，则，则XYZ。伪传递规则：如果伪传递规则：如果XY，YWZ，则，则XWZ。分解规则：如果分解规则：如果XY，Z Y，则，则XZ。v 定义8（属性闭包）：设F为属性集U上的一组函数依赖，XU。X+ = A|XA能由F根据Armstrong公理导出称为属性集属性集X关于函数依赖集关于函数依赖集F的闭包的闭包。例:关系模式R(A1, A2, A3)的函数依赖集F为A1A2，A2A32022-2-429函数依赖的公理系统 (1) 若若X=A1, X+ = (2) 若若X=A2, X+

14、 = (3) 若若X=A3, X+ =A1, A2, A3A2, A3A3v 引理2 设F为属性集U上的函数依赖，X、YU，XY能由F根据Armstrong公理导出的充分必要条件是Y X+。 v 证：v 三条推论 合并规则：如果XY，XZ，则XYZ。伪传递规则：如果XY，YWZ，则XWZ。分解规则：如果XY，ZY，则XZ。2022-2-430函数依赖的公理系统v 算法1 计算X+输入: X，F输出: X+1. X(1) := 空集合; X(0) := X;2. B := A | VWF, VX(0), AW;3. X(1) := BX(0);4. IF X(1) X(0) THEN X(0)

15、:= X(1); GOTO ； ELSE X+ := X(1) ENDIF.2022-2-431函数依赖的公理系统v 例：计算X+ = A,B,C,D,E， = ABC, ACB, BD, CE, ECB，求(AB)+。2022-2-432函数依赖的公理系统 1. X(1) := 空集合; X(0) := X;2. B := A | VWF，VX(0)，AW;3. X(1) := BX(0);4. IF X(1) X(0) THEN X(0) := X(1); GOTO ； ELSE X+ := X(1) ENDIF.v 定理3 算法1正确地计算出了X关于F的闭包X+.证：o算法的终止性o算法

16、的正确性2022-2-433函数依赖的公理系统 v 定理4 Armstrong公理系统是有效有效而且完备完备的。 证：oArmstrong公理的有效性是指由F出发根据Armstrong公理推导出来的每个函数依赖一定在F+中.o现只需证明完备性(Armstrong公理的完备性指的是F+中的每一个函数依赖一定可以由F出发根据Armstrong公理推导出来).2022-2-434函数依赖的公理系统v 定义9：设G和F是两个函数依赖集。如果G+ = F+则称F与G等价。 v 引理3 设G和F是两个函数依赖集。F与G等价的充分必要条件是FG+且GF+.v 证明：2022-2-435函数依赖的公理系统 v

17、 引理3给出了一个判断两个函数依赖集等价的算法。 v 例F = S#SD, SDMN, (S#,CN)GG = S#SD, SDMN, (S#,CN)G, S#MNF和G等价吗？2022-2-436函数依赖的公理系统 引理引理3 设设G和和F是两个函数依赖集。是两个函数依赖集。F与与G等价的充分必等价的充分必要条件是要条件是F G+且且G F+.v 定义10：函数依赖集F称为极小函数依赖集如果F满足下列条件:1.F中任一函数依赖的右部仅含有一个属性；2.F中不存在这样的函数依赖XA，使得F与F - XA等价；3.F中不存在这样的函数依赖XA：X包括真子集Z使得 (F - XA)ZA与F等价。2

18、022-2-437函数依赖的公理系统2022-2-438函数依赖的公理系统S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93v F1 = S#SD, SDMN, (S#, SD, CN)GF1是最小依赖集？v F2 = S#SD, SDMN, S#SD, (S#, SD)GF2是最小依赖集？2022-2-439函数依赖的公理系统1.F中任一函数依赖的右部仅含有一个属性；2.F中不存在这样的函数

19、依赖XA，使得F与F - XA等价；3.F中不存在这样的函数依赖XA：X包括真子集Z使得 (F - XA)ZA与F等价。v 定理5 每一个函数依赖集F都等价于一个极小函数依赖集。构造性证明。v 极极小函数依赖集是否唯一？小函数依赖集是否唯一？2022-2-440函数依赖的公理系统v 极小函数依赖集不唯一例：oF = AB, BA, BC, AC, CA的极小函数依赖集为F1 = AB, BC, CAoF = AB, BC, BA, AC, CA的极小函数依赖集为F2 = AB, BA, AC, CA2022-2-441函数依赖的公理系统函数依赖集函数依赖集F称为极小函数依赖集如果称为极小函数依

20、赖集如果F满足下列条件满足下列条件:(1) F中任一函数依赖的右部仅含有一个属性；中任一函数依赖的右部仅含有一个属性；(2) F中不存在这样的函数依赖中不存在这样的函数依赖XA，使得使得F与与F - XA等价；等价；(3) F中不存在这样的函数依赖中不存在这样的函数依赖XA：X包括真子集包括真子集Z使得使得 (F - XA)ZA与与F等价。等价。v 求极小函数依赖集练习：例：o求F = ABC, BC, ABC的极小函数依赖集o答案：AB, BCo求F = ABD, AC, ADC, BD的极小函数依赖集o答案：AB, AC, BD2022-2-442函数依赖的公理系统 函数依赖集函数依赖集F

21、称为极小函数依赖集如果称为极小函数依赖集如果F满足下列条件满足下列条件:(1) F中任一函数依赖的右部仅含有一个属性；中任一函数依赖的右部仅含有一个属性；(2) F中不存在这样的函数依赖中不存在这样的函数依赖XA，使得使得F与与F - XA等价；等价；(3) F中不存在这样的函数依赖中不存在这样的函数依赖XA：X包括真子集包括真子集Z使得使得 (F - XA)ZA与与F等价。等价。v 以函数依赖为基础讨论关系模式的规范形式(范式)。v 关系模式的范式包括第一范式（1NF）第二范式（2NF）第三范式（3NF）Boyce Codd范式（BCNF）第四范式 ( 4NF )第五范式 ( 5NF )20

22、22-2-443关系模式的规范形式关系模式的规范形式 v 满足这些范式条件的关系模式可以在不同程度上避免本节开始提到的冗余问题、插入问题、更新问题和删除问题。2022-2-444关系模式的规范形式 v 关系模式范式的基本概念定义11：第一范式(1NF)o设R是一个关系模式。如果R的每个属性的值域都是不可分的简单数据项的集合，则称这个关系模式为第一范式关系模式，记作1NF。2022-2-445关系模式的规范形式 2022-2-446关系模式的规范形式 S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王

23、平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93v 关系模式范式的基本概念定义12：第二范式(2NF)o若关系模式若关系模式R是是1NF，而且每一个非主属性都完全函数依赖于R的键，则R称为第二范式关系模式，记作2NF。 2022-2-447关系模式的规范形式 设设R是一个具有属性集合是一个具有属性集合U的关系模式，如果的关系模式，如果XY，并且对于并且对于X的任的任何一个真子集何一个真子集Z，ZY都不成立，则称都不成立，则称Y完全函数依赖于完全函数依赖于X。若若XY，但但Y不完全函数依赖于不完全函数依赖于X，则称则称Y部分函数依赖于部

24、分函数依赖于X。 2022-2-448关系模式的规范形式 R(S#,SD,MN,C#,G)不是不是2NF描述学生的关系模式：描述学生的关系模式：U US#,SD,MN,CN,GS#,SD,MN,CN,G根据数据的语义确定的函数依根据数据的语义确定的函数依赖：赖： F=S#F=S#SD, SDMN, SD, SDMN, (S#,CN)G(S#,CN)GS#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据

25、库93v 非2NF关系模式的插入问题2022-2-4491NF存在S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93S5自动化v 非2NF关系模式的删除问题2022-2-4501NF存在S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3

26、信息王平操作系统85S4自动化李明数据库93v 非2NF关系模式的更新问题2022-2-4511NF存在S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93把一个给定关系模式转化为某种范式的过程称为关系模式的规范化过程，简称为规范化。2022-2-4522NF的规范形式 定义定义12：第二范式：第二范式(2NF) 若关系模式是若关系模式是1NF，而且每一个非主属性都完全函数依赖于的键，则而且每一

27、个非主属性都完全函数依赖于的键，则称为第二范式关系模式，记作称为第二范式关系模式，记作2NF。 2022-2-4532NF的规范形式S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93S#CNGS1数据库90S1离散数学85S2数据结构57S2信息系统80S4S#SDS1计算机S2信息S3信息自动化MN刘伟王平王平李明SC(S#,C#,G)是是2NFSSS(S#,CN,MN)是是2NFv 2NF

28、关系模式解决了删除问题了吗？2022-2-4542NFS#CNGS1数据库90S1离散数学85S2数据结构57S2信息系统80S2VB70S3数据结构70S3数据库80S3离散数学70S3操作系统85S4数据库NULLS4S#SDS1计算机S2信息S3信息自动化MN刘伟王平王平李明v 2NF关系模式解决了插入问题了吗？2022-2-4552NFS#CNGS1数据库90S1离散数学85S2数据结构57S2信息系统80S2VB70S3数据结构70S3数据库80S3离散数学70S3操作系统85S4数据库93S4S#SDS1计算机S2信息S3信息自动化MN刘伟王平王平李明S5自动化李明v 2NF关系模

29、式解决了更新问题了吗？2022-2-4562NFS#CNGS1数据库90S1离散数学85S2数据结构57S2信息系统80S2VB70S3数据结构70S3数据库80S3离散数学70S3操作系统85S4数据库NULLS4S#SDS1计算机S2信息S3信息自动化MN刘伟王平王平李明计算机刘伟定义13：第三范式(3NF)o如果关系模式R是2NF, 而且它的任何一个非键属性都不传递地依赖于任何候选键，则R称为第三范式关系模式，记作3NF。2022-2-4573NF 传递地函数依赖定义传递地函数依赖定义： 设是一个具有属性集合的关系模式，设是一个具有属性集合的关系模式，X ,Y ,Z ，YX不成立，不成立

30、，Z-X、Z-Y和和Y-X不空。如果不空。如果XY，YZ，则称则称Z传递地函数依赖于传递地函数依赖于X。 2022-2-4583NFS#CNGS1数据库90S1离散数学85S2数据结构57S2信息系统80S2VB70S3数据结构70S3数据库80S3离散数学70S3操作系统85S4数据库93S4S#SDS1计算机S2信息S3信息自动化MN刘伟王平王平李明v 对非3NF关系模式进行规范化处理2022-2-4593NF2022-2-4603NFS4S#SDS1计算机S2信息S3信息自动化MN刘伟王平王平李明SSS(S#,SD,MN)不是不是3NFS4S#SDS1计算机S2信息S3信息自动化SD计算

31、机信息自动化MN刘伟王平李明SSD(S#,SD)是是3NFSSL(SD,SL)是是3NFv 3NF关系模式解决了更新问题了吗？2022-2-4613NFSD计算机信息自动化MN刘伟王平李明S4S#SDS1计算机S2信息S3信息自动化计算机v 定义14：BCNF范式(Boyce Codd Normal Form) 设关系模式设关系模式R是是1NF。如果对于R的每个函数依赖XY，则X必为候选键，则R是BCNF范式。每个BCNF关系模式都具有如下三个性质：1.所有非键属性都完全函数依赖于每个候选键。2.所有键属性都完全函数依赖于每个不包含它的候选键。3.没有任何属性完全函数依赖于非键的任何一组属性。

32、2022-2-462Boyce Codd范式完全依赖定义完全依赖定义设设R是一个具有属性集合是一个具有属性集合U的关系模式，如果的关系模式，如果XY，并且对于并且对于X的的任何一个真子集任何一个真子集Z，ZY都不成立，则称都不成立，则称Y完全函数依赖于完全函数依赖于X。若若XY，但但Y不完全函数依赖于不完全函数依赖于X，则称则称Y部分函数依赖于部分函数依赖于X。 2022-2-463范式的关系 BCNF 3NFv 若关系模式R是BCNF，则R一定是3NF。v 证明：2022-2-464关系模式范式的基本概念2022-2-465关系模式范式的基本概念 定义定义12：第二范式：第二范式(2NF)

33、若关系模式是若关系模式是1NF，而且每一个非主属性都完全函数依赖于而且每一个非主属性都完全函数依赖于的键，则称为第二范式关系模式，记作的键，则称为第二范式关系模式，记作2NF。 定义定义13：第三范式：第三范式(3NF) 如果关系模式是如果关系模式是2NF, 而且它的任何一个非主属性都不传递地而且它的任何一个非主属性都不传递地依赖于任何候选键，则称为第三范式关系模式，记作依赖于任何候选键，则称为第三范式关系模式，记作3NF。 定义定义14：BCNF范式范式(Boyce Codd Normal Form) 设关系模式设关系模式R是是1NF。如果对于如果对于R的每个函数依赖的每个函数依赖XY，则则

34、X必必为候选键，则为候选键，则R是是BCNF范式。范式。v 例：关系模式SJP(S, J, P)；S表示学生，J表示课程，P表示名次。每个学生每门课程都有一个确定的名次，每门课程中每一名次只有一个学生。由这些语义得到下面的函数依赖：oS, JP和J, PS。候选键有哪些？oS, J与J, P都是候选键。2022-2-466关系数据库设计理论SPJ是3NF吗？是！因为没有任何非主属性传递或部分依赖于任何候选键。SPJ是BCNF吗？是！因为每个函数依赖的决定属性集都是候选键。v 例：关系模式STJ(S, T, J)；S表示学生，T表示教师，J表示课程。每一教师只教一门课，每门课由若干教师教。某一学

35、生选定某门课，就确定了一个固定的教师。由这些语义得到下面的函数依赖：oS,JT, S, TJ, TJ.候选键有哪些：o(S,J)和(S,T)都是候选键。2022-2-4673NF与BCNFSTJ是3NF吗？是！因为没有任何非主属性传递或部分依赖于任何候选键。STJ是BCNF吗？不是！因为T是决定属性，而T不是候选键。v 如果一个关系数据库的所有关系模式都属于BCNF，那么在函数依赖范畴内，它已达到了最高的规范化程度。v 属于BCNF的关系模式是否就很完美了呢？2022-2-468关系数据库设计理论v 设某学校有多个专业，每个专业有多个教员，该专业的每个教员讲授该专业的所有课程。用关系模式TEA

36、CH(S,T,C)来表示专业S、教员T、课程C之间的关系。 2022-2-469关系数据库设计理论2022-2-470关系数据库设计理论S ST TC C计算机计算机王军王军数据结构数据结构计算机计算机王军王军系统结构系统结构计算机计算机李明李明数据结构数据结构计算机计算机李明李明系统结构系统结构软件软件张宏张宏数据结构数据结构软件软件张宏张宏JAVAJAVA软件软件李明李明数据结构数据结构软件软件李明李明JAVAJAVA软件软件赵亮赵亮数据结构数据结构软件软件赵亮赵亮JAVAJAVAv 设某学校有多个专业，每个专业有多个教员，该专业的每个教员讲授该专业的所有课程。用关系模式TEACH(S,T

37、,C)来表示专业S、教员T、课程C之间的关系。 2022-2-471关系数据库设计理论v 对关系模式TEACH的分析：v 候选键？v (S, T, C)v 是BCNF吗？v 是！v 存在的问题存在的问题：数据增删不方便， 冗余明显！S ST TC C计算机计算机王军王军数据结构数据结构计算机计算机王军王军系统结构系统结构计算机计算机李明李明数据结构数据结构计算机计算机李明李明系统结构系统结构软件软件张宏张宏数据结构数据结构软件软件张宏张宏JAVAJAVA软件软件李明李明数据结构数据结构软件软件李明李明JAVAJAVA软件软件赵亮赵亮数据结构数据结构软件软件赵亮赵亮JAVAJAVA2022-2-

38、472关系数据库设计理论W1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S1C1W2S1C4W2S3C1W2S3C4v 在关系模式WSC(W,S,C)中，W表示仓库，S表示保管员，C表示商品。假设每个仓库有多个保管员和多种商品。每个保管员保管所在库的所有商品，每种商品被所有保管员保管。2022-2-473关系数据库设计理论v 对关系模式WSC的分析：v 候选键？v (W, S, C)v 是BCNF吗？v 是！v 存在的问题：数据增删不方便，冗余明显！W1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S1C1W2S1C4W2S3C1W2S3C

39、4v 定义15(多值依赖)：设R是一个具有属性集合的关系模式，X、Y和Z是U的子集，并且Z = U X - Y，多值依赖XY成立当且仅当对R的任一关系r，r在(X, Z)上的每个值对应一组Y的值，这组值仅仅决定于X值而与Z值无关。2022-2-474多值依赖与4NF2022-2-475多值依赖与4NFv 在TEACH关系实例中，每个(S,C)上的值对应一组T值，而且这种对应与C无关。v 例如，尽管与(S,C)对应的两个元组(计算机，数据结构)和(计算机，系统结构)在C属性上的值不同(一个是“数据结构”，一个是“系统结构”)，它们都对应T的同一组值王军，李明。因此，T多值依赖于S，即ST。S S

40、T TC C计算机计算机王军王军数据结构数据结构计算机计算机王军王军系统结构系统结构计算机计算机李明李明数据结构数据结构计算机计算机李明李明系统结构系统结构软件软件张宏张宏数据结构数据结构软件软件张宏张宏JAVAJAVA软件软件李明李明数据结构数据结构软件软件李明李明JAVAJAVA软件软件赵亮赵亮数据结构数据结构软件软件赵亮赵亮JAVAJAVA2022-2-476多值依赖与第四范式v 在WSC关系实例中，每个(W,C)上的值对应一组S值，而且这种对应与S无关v 例如，尽管与(W,C)对应的两个元组(W1，C1)和(W1，C2)在C属性上的值不同(一个是“C1”，一个是“C2”)，它们都对应S

41、的同一组值S1，S2。因此，S多值依赖于W，即WS。 v 由C与S的完全对称性，有WC成立。 W WS SC CW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S1C1W2S1C4W2S3C1W2S3C4v 定义16：设R是一个关系模式，D是R上的多值依赖集。如果对于R的每个多值依赖XY(Y-X=非空集, XY未包含R的全部属性)，X都含有R的候选键，则R是第四范式关系模式，简记4NF。2022-2-477多值依赖与第四范式v 与函数依赖类似，可以定义多值依赖集合D的闭包D+。我们也有一组完备有效的多值依赖推理规则，可以用来推导出D+中的所有多值依赖。 2022-2

42、-478多值依赖与第四范式2022-2-479多值依赖与第四范式v在WSC关系中，候选键是(W,S,C)。v该关系模式上，有多值依赖WS，W不是候选键，因此，WSC不是第四范式。W WS SC CW1W1S1S1C1C1W1W1S1S1C2C2W1W1S1S1C3C3W1W1S2S2C1C1W1W1S2S2C2C2W1W1S2S2C3C3W2W2S1S1C1C1W2W2S1S1C4C4W2W2S3S3C1C1W2W2S3S3C4C4v 问题问题：WSC的关系可能具有相当大的数据冗余。v 例如，若某一仓库Wi有个保管员，存放m件物品，则对应关系中属性W的值为Wi的元组数是mn。每个保管员重复存储

43、m次，每种物品重复存储n次。2022-2-480多值依赖与第四范式W WS SW1S1W1S2W2S1W2S32022-2-481多值依赖与第四范式W WC CW1C1W1C2W1C3W2C1W3C4W WS SC CW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S1C1W2S1C4W2S3C1W2S3C42022-2-482多值依赖与第四范式v 当D包含函数依赖时，如果关系模式R是4NF，则R必为BCNF，反之不然反之不然。v 例：关系模式WSC具有两个多值依赖WS和WC。WSC的唯一候选键是全键W,S,C。定义定义14：BCNF范式范式(Boyce Codd

44、Normal Form) 设关系模式设关系模式R是是1NF。如果对于如果对于R的每个函数依赖的每个函数依赖XY，则则X必必为候选键，则为候选键，则R是是BCNF范式。范式。 定义定义16：4NF 设设R是一个关系模式，是一个关系模式，D是是R上的多值依赖集。如果对于上的多值依赖集。如果对于R的每的每个多值依赖个多值依赖XY(Y-X=非空集非空集, XY未包含未包含R的全部属性的全部属性)，X都都含有含有R的候选键，则的候选键，则R是第四范式关系模式，简记是第四范式关系模式，简记4NF。 2022-2-483多值依赖与第四范式v 当D包含函数依赖时，如果关系模式R是4NF，则R必为BCNF，反之

45、不然反之不然。v 例：关系模式WSC具有两个多值依赖WS和WC。WSC的唯一候选键是全键W,S,C。v WSC是4NF吗？2022-2-484多值依赖与第四范式v 当D包含函数依赖时，如果关系模式R是4NF，则R必为BCNF，反之不然反之不然。v 例：关系模式WSC具有两个多值依赖WS和WC。WSC的唯一候选键是全键W,S,C。v WSC是4NF吗？v 由于W不是候选键，WSC不是4NF。2022-2-485多值依赖与第四范式v 当D包含函数依赖时，如果关系模式R是4NF，则R必为BCNF，反之不然反之不然。v 例：关系模式WSC具有两个多值依赖WS和WC。WSC的唯一候选键是全键W,S,C。

46、v WSC是4NF吗？v 由于W不是候选键，WSC不是4NF。v WSC是BCNF吗？2022-2-486多值依赖与第四范式v 当D包含函数依赖时，如果关系模式R是4NF，则R必为BCNF，反之不然反之不然。v 例：关系模式WSC具有两个多值依赖WS和WC。WSC的唯一候选键是全键W,S,C。v WSC是4NF吗？v 由于W不是候选键，WSC不是4NF。v WSC是BCNF吗？v WSC是BCNF。v 形成初始关系数据库模式形成初始关系数据库模式v 关系数据库设计理论关系数据库设计理论v 关系模式规范化方法v 关系模式的优化v 完整性和安全性约束的定义v 逻辑数据库的性能估计2022-2-48

47、7关系数据库设计v 关系模式的分类：静态关系：一旦数据已加载, 用户只能在这个关系上运行查询操作, 不再进行插入、删除和更新操作。动态关系：经常被更新、插入和删除。v 静态关系只需具有第一规范形式。v 动态关系必须至少至少具有第三规范形式。2022-2-488关系模式规范化方法v 关系模式规范化的主要方法：关系模式分解。把一个关系模式分解为几个子模式，使得这些子模式具有指定的规范化形式。关系模式分解中的重要问题是分解的无损连接性和函数依赖保持性。2022-2-489关系模式规范化方法v 例：关系模式R的属性集合U=车号, 车主, 车型, 函数依赖集合F = 车号车主, 车主车型。R的关系实例:

48、 该实例存在的问题: 2022-2-490关系模式规范化方法车号车号车主车主车型车型黑A 00321张红A6L黑A 78712张红A6L黑A YZ279李微Bora黑A 77D01王力Benzv 例：关系模式R的属性集合U=车号, 车主, 车型, 函数依赖集合F = 车号车主, 车主车型。分解1：1=R1(车号) ，R2(车主)，R3(车型)2022-2-491关系模式规范化方法车号车号车主车主车型车型黑A 00321张红A6L黑A 78712张红A6L黑A YZ279李微Bora黑A 77D01王力Benz车号车号黑A 00321黑A 78712黑A YZ279黑A 77D01车主车主张红李

49、微王力车型车型A6LBoraBenzv 例：关系模式R的属性集合U=车号, 车主, 车型, 函数依赖集合F = 车号车主, 车主车型。分解2：2 = R1(车号, 车主) ，R2(车号, 车型)2022-2-492关系模式规范化方法车号车号车主车主车型车型黑A 00321张红A6L黑A 78712张红A6L黑A YZ279李微Bora黑A 77D01王力Benz车号车号车主车主黑A 00321张红黑A 78712张红黑A YZ279李微黑A 77D01王力车号车号车型车型黑A 00321A6L黑A 78712A6L黑A YZ279Bora黑A 77D01Benz具有无损连接性！具有无损连接性！

50、v 例：关系模式R的属性集合U=车号, 车主, 车型, 函数依赖集合F = 车号车主, 车主车型。分解2：2 = R1(车号, 车主) ，R2(车号, 车型)2022-2-493关系模式规范化方法车号车号车主车主车型车型黑A 00321张红A6L黑A 78712张红A6L黑A YZ279李微Bora黑A 77D01王力Benz车号车号车主车主黑A 00321张红黑A 78712张红黑A YZ279李微黑A 77D01王力车号车号车型车型黑A 00321A6L黑A 78712A6L黑A YZ279Bora黑A 77D01Benz不具有函数依赖保持性！不具有函数依赖保持性！v 例：关系模式R的属性

51、集合U=车号, 车主, 车型, 函数依赖集合F = 车号车主, 车主车型。分解3：3 = R1(车号, 车主) ，R2(车主, 车型)2022-2-494关系模式规范化方法车号车号车主车主车型车型黑A 00321张红A6L黑A 78712张红A6L黑A YZ279李微Bora黑A 77D01王力Benz车号车号车主车主黑A 00321张红黑A 78712张红黑A YZ279李微黑A 77D01王力车主车主车型车型张红A6L李微Bora王力Benz具有无损连接性！具有无损连接性！ 具有函数依赖保持性！具有函数依赖保持性！v 定义1 设R是具有属性集合U的关系模式。R的一个分解定义为=R1, R2

52、, ., Rn,其中, Ri的属性集合是Ui，且v 例：关系模式R的属性集合U=车号, 车主, 车型, 函数依赖集合F = 车号车主, 车主车型。分解： = R1(车号, 车主) , R2(车主, 车型)2022-2-495关系模式规范化方法niiUU1v 定义2 设R是一个具有属性集合U和函数依赖集合F的关系模式，=R1, ., Rn是R的一个分解。F在Ri的属性集合Ui上的投影是Fi =XYXYF, X, YUi。v 例: 关系模式R的属性集合U=车号, 车主, 车型, 函数依赖集合F = 车号车主, 车主车型。分解： = R1(车号, 车主) , R2(车主, 车型)函数依赖的投影：F1

53、 = 车号车主，F2 = 车主车型2022-2-496关系模式规范化方法v 定义3 设 = R1, ., Rn是关系模式R的一个分解，r是R的一个关系。定义m(r)R1(r) R2(r) . Rn(r)，即m(r)是r在中各关系模式上投影的连接。2022-2-497关系模式规范化方法v 例: 关系模式R的属性集合U=车号, 车主, 车型, 函数依赖集合F = 车号车主, 车主车型。分解： = R1(车号, 车主) , R2(车主, 车型)2022-2-498关系模式规范化方法车号车号车主车主车型车型黑A 00321张红A6L黑A 78712张红A6L黑A YZ279李微Bora黑A 77D01

54、王力Benz车号车号车主车主黑A 00321张红黑A 78712张红黑A YZ279李微黑A 77D01王力车主车主车型车型张红A6L李微Bora王力Benz R1(r) R2(r)m (r)= R1(r) R2(r)v 引理1 设R是一个关系模式，=R1, ., Rn是R的一个分解，r是R的一个关系实例，则：1.r m(r)2.若s = m(r)，则Ri(r) = Ri(s)3.m(m(r) = m(r)证明：2022-2-499关系模式规范化方法 定义定义3.3 设设 =R1, ., Rn是关系模式是关系模式R的一个分解，是的一个分解，是R的一个的一个关系。定义关系。定义m (r) R1(

55、r) R2(r) . Rn(r)，即即m (r)是是r在在 中各关系模式上投影的中各关系模式上投影的连接连接。 v 定义4 设 = R1, ., Rn是R的一个分解。若对R的任何一个关系r均有r = m(r)成立，则称分解具有无损连接性无损连接性。简称为无损连接分解。2022-2-4100关系模式规范化方法v 例: 关系模式R的属性集合U=车号, 车主, 车型, 函数依赖集合F = 车号车主, 车主车型。分解： = R1(车号, 车主) , R2(车主, 车型)2022-2-4101关系模式规范化方法车号车号车主车主车型车型黑A 00321张红A6L黑A 78712张红A6L黑A YZ279李

56、微Bora黑A 77D01王力Benz车号车号车主车主黑A 00321张红黑A 78712张红黑A YZ279李微黑A 77D01王力车主车主车型车型张红A6L李微Bora王力Benz R1(r) R2(r)m (r)= R1(r) R2(r)v 算法1: 判别一个分解的无损连接性。输入输入: 关系模式R(A1, ., An), R的函数依赖集F, R的分解 = R1, ., Rk。输出输出: 分解是否具有无损连接性。算法算法:2022-2-4102关系模式规范化方法(1) 建立矩阵S, 列j对应属性Aj, 行i对应Ri(2) FOR i =1 TO k DO FOR j =1 TO n DO

57、 Si,j=bij; ENDFOR ENDFOR(3) FOR i =1 TO k DO FOR j =1 TO n DO IF Ri包含属性Aj, THEN Si,j=aj; ENDFOR ENDFOR(4) 见下页2022-2-4103关系模式规范化方法2022-2-4104关系模式规范化方法DO UNTIL S 不变化 FOR (每个XY)F DO FOR (S中所有在X对应列上具有相同符号的行) DO 考察这些行中，Y所对应列的符号，按照下列进行规则修改 (a) FOR (每个具有”a”类符号的Y对应列) DO 把该列所有符号改成相同的”a”类符号; ENDFOR (b) FOR (每

58、个具有”b”类符号的Y对应列) DO 在该列中选择一个下标最小”b”类符号; 把该列的其它位置变为选中的”b”类符号; ENDFOR ENDFOR ENDFORENDUNTIL如果S中存在一行全为”a”类符号，则具有无损连接分解；否则，不具有无损连接分解;v 定理定理1 关系R的分解具有无损连接性的充分必要条件是算法1终止时, 矩阵S中有一行为(a1, a2, ., an).2022-2-4105关系模式规范化方法v 当关系模式R被分解为两个子模式时, 下述定理给出了一个判别无损连接性的简单方法。v 定理定理2 设=R1, R2是关系模式R的一个分解, U1、U2和U分别是R1、R2和R的属性

59、集合, F是R的函数依赖集合。具有无损连接性的充分必要条件是U1U2U1-U2F+或U1U2U2-U1F+。2022-2-4106关系模式规范化方法例子：例子： 关系模式关系模式R的属性集合的属性集合U=A,B,C,D,E,F 函数依赖集函数依赖集F=AB, CF, EA, CED 分解分解 =R1(A, B, E), R2(C, D, E, F)v 定义5 设R是具有属性集合U和函数依赖集合F的关系模式, =R1, ., Rk是R的一个分解，Ui是Ri的属性集合, Fi是F在Ui上的投影。如果 , 则称具有函数依赖保持性。v 例: 关系模式R的属性集合U=车号, 车主, 车型, 函数依赖集合

60、F = 车号车主, 车主车型。分解： = R1(车号, 车主) , R2(车主, 车型)2022-2-4107关系模式规范化方法)(1kiiFF 函数依赖的投影：函数依赖的投影： F1 = F2 =车号车号车主车主车主车主车型车型v 算法算法2 函数依赖保持性的判别算法输入:函数依赖集F, F1, F2, , Fk, 记 输出: 是否F+ = G+。方法:(1) FOR 每个XYF DO IF Y不属于X关于G的闭包 THEN 输出F+ G+, 停止。 ENDFOR；(2) 输出“F+ = G+”, 停止。2022-2-4108关系模式规范化方法)(1kiiFG算法3 o3NF分解算法1：只能