数据库应用第3章Desig.ppt
《数据库应用第3章Desig.ppt》由会员分享,可在线阅读,更多相关《数据库应用第3章Desig.ppt(155页珍藏版)》请在三一办公上搜索。
1、关系数据库设计,满足用户的完整性和安全性要求;动态关系至少具有第三规范形式,静态关系至少具有第一规范形式;能够在逻辑级上高效率地支持各种数据库事务的运行;存储空间利用率高。,2023/10/14,2,关系数据库设计:目标,2023/10/14,3,关系数据库设计:任务,现实世界,信息世界,概念数据库设计,逻辑世界,逻辑数据库设计,物理世界,文件,物理数据库设计,形成初始关系数据库模式;关系模式规范化;关系模式优化;定义关系上的完整性和安全性约束;子模式定义;性能估计。,2023/10/14,4,关系数据库设计步骤,问题初始关系模式可以是逻辑设计的最终结果吗?某些关系模式可能存在冗余问题、插入问
2、题、更新问题和删除问题。,2023/10/14,5,形成初始关系数据库模式,例:学生有下列信息:学号(S#)、系(SD)、系主任(MN),课程名(CN),成绩(G)有一个描述学生的关系模式:U=S#,SD,MN,CN,G现实世界的已知事实:F=S#SD,SDMN,(S#,CN)G,2023/10/14,6,形成初始关系数据库模式,2023/10/14,7,插入异常,2023/10/14,8,插入异常,2023/10/14,9,删除异常,2023/10/14,10,数据冗余和更新问题,数据冗余:同一系中有n个学生,“系名”与”系主任”就重复n-1次;同一个学生选修了m门课程,学号就重复了m-1次
3、。更新异常:若调整了某系系主任,数据表中所有行的“系主任”值都要更新,否则会出现同一系系主任姓名不同的情况。,2023/10/14,11,形成初始关系数据库模式,插入异常:假设要开设一门新的课程,暂时还没有人选修。这样,由于还没有“学号”关键字,课程名称和设课系也无法记录入数据库。删除异常:假设一批学生已经完成课程的选修,这些选修记录就应该从数据库表中删除。但是,与此同时,系名与系主任信息也被删除了。很显然,这也会导致插入异常。,2023/10/14,12,形成初始关系数据库模式,需要用关系模式的规范化方法消除初始逻辑数据库模式中存在的问题。某些关系模式可能存在由属性间的函数依赖引起的冗余问题
4、、插入问题、更新问题和删除问题。,2023/10/14,13,形成初始关系数据库模式,确定函数依赖集 函数依赖:Functional Dependency对初始关系数据库模式中的每个关系模式进行深入地分析,与用户协商,确定每个初始关系的函数依赖集,使用关系数据库设计理论,对关系模式进行规范化处理。,2023/10/14,14,形成初始关系数据库模式,函数依赖定义1:设R是一个关系模式,U是R的属性集合,X和Y是U的子集。对于R的任意实例r,r中任意两个元组t1和t2,如果t1X=t2X,则t1Y=t2Y,我们称X函数地确定Y,或Y函数依赖于X,记作XY。只能根据数据的语义来确定函数依赖。描述学
5、生的关系模式:U=S#,SD,MN,CN,G根据数据的语义确定的函数依赖:F=S#SD,SDMN,(S#,CN)G,2023/10/14,15,设计理论,函数依赖定义1:设R是一个关系模式,U是R的属性集合,X和Y是U的子集。对于R的任意实例r,r中任意两个元组t1和t2,如果t1X=t2X,则t1Y=t2Y,我们称X函数地确定Y,或Y函数依赖于X,记作XY。只能根据数据的语义来确定函数依赖。描述学生的关系模式:U=S#,SD,MN,CN,G根据数据的语义确定的函数依赖:F=S#SD,SDMN,(S#,CN)G,2023/10/14,16,设计理论,如果XY而且Y不是X的子集,则称XY是非平凡
6、函数依赖。若不特别声明,我们总是讨论非平凡函数依赖。如果XY,我们称X为这个函数依赖的决定属性集。描述学生的关系模式:US#,SD,MN,CN,G(S#,SD)SDSDMN,2023/10/14,17,函数依赖,定义2设R是一个具有属性集合U的关系模式,如果XY,并且对于X的任何一个真子集Z,ZY都不成立,则称Y完全函数依赖于X。若XY,但Y不完全函数依赖于X,则称Y部分函数依赖于X。描述学生的关系模式:US#,SD,MN,CN,G(S#,SD)MN(S#,CN)G,2023/10/14,18,函数依赖,定义3:设R是一个具有属性集合U的关系模式,XU,YU,ZU,且YX不成立,同时Z-X、Z
7、-Y和Y-X不空。如果XY,YZ,则称Z传递地函数依赖于X。描述学生的关系模式:U=S#,SD,MN,CN,G根据S#SD,SD MN,导出如下传递依赖:S#MN,2023/10/14,19,函数依赖,定义4:设R是一个具有属性集合U的关系模式,KU。如果K满足下列两个条件,则称K是R的一个候选键:(1)KU。(2)不存在K的真子集Z使得ZU。候选键可以唯一地标识关系的元组。,2023/10/14,20,函数依赖,一个关系模式中可能具有多个候选键,指定其中一个作为识别关系元组的主键。包含在任何一个候选键中的属性称为键属性。不包含在任何候选键中的属性称为非键属性。在最简单的情况下,候选键只包含一
8、个属性。在最复杂的情况下,候选键包含关系模式的所有属性,称为全键。,2023/10/14,21,函数依赖,定义5:设X是关系模式R的属性子集合。如果X是另一个关系模式的候选键,则称X是R的外部键。,2023/10/14,22,函数依赖,设R是一个具有属性集合U的关系模式,F是R上的函数依赖集合。如果对于R的任意一个使F成立的关系实例r,函数依赖XY都成立,则称F逻辑地蕴含XY.已知的函数依赖:F=S#SD,SDMN,(S#,CN)G,2023/10/14,23,逻辑蕴含,S#MN成立吗?,F蕴含S#MN,给定一个函数依赖集合,希望知道由给定的函数依赖集合所蕴涵的所有函数依赖的集合。推导依据:A
9、rmstrong公理系统,2023/10/14,24,函数依赖的公理系统,Armstrong公理系统 设R是一个具有属性集合U的关系模式,F是R的一个函数依赖集合。Armstrong公理系统包含如下三条推理规则:,2023/10/14,25,函数依赖的公理系统,自反律:若YXU,则F蕴含XY 增广律:若F蕴含XY,ZU,则F蕴含XZYZ 传递律:若F蕴含XY和YZ,则F蕴含XZ,三条推论 合并规则:如果XY,XZ,则XYZ。伪传递规则:如果XY,YWZ,则XWZ。分解规则:如果XY,ZY,则XZ。,2023/10/14,26,函数依赖的公理系统,自反律:若YXU,则F蕴含XY 增广律:若F蕴含
10、XY,ZU,则F蕴含XZYZ 传递律:若F蕴含XY和YZ,则F蕴含XZ,引理1:XA1A2.Ak成立的充分必要条件是对于1ik,XAi成立。证明:,2023/10/14,27,函数依赖的公理系统,合并规则:如果XY,XZ,则XYZ。伪传递规则:如果XY,YWZ,则XWZ。分解规则:如果XY,ZY,则XZ。,定义7:设R是一个具有属性集合U的关系模式,F是给定的函数依赖集合。由F逻辑蕴含的所有函数依赖称为F的闭包,记为F+。描述学生的关系模式:US#,SD,MN,CN,G根据数据的语义确定的函数依赖:F=S#SD,SDMN,(S#,CN)GF+=S#SD,SDMN,(S#,CN)G,S#MN,(
11、S#,SD)SD,2023/10/14,28,函数依赖的公理系统,Armstrong公理系统是有效而且完备的吗?Armstrong公理的有效性是指由F出发根据Armstrong公理推导出来的每个函数依赖一定在F+中;Armstrong公理的完备性是指F+中的每一个函数依赖一定可以由F出发根据Armstrong公理推导出来。,2023/10/14,29,函数依赖的公理系统,为了证明Armstrong公理的完备性,首先需要解决如何判定一个函数依赖是否可以由F根据Armstron公理推导出来。,2023/10/14,30,函数依赖的公理系统,定义8(属性闭包):设F为属性集U上的一组函数依赖,XU。
12、X+=A|XA能由F根据Armstrong公理导出称为属性集X关于函数依赖集F的闭包。例:关系模式R(A1,A2,A3)的函数依赖集F为A1A2,A2A3,2023/10/14,31,函数依赖的公理系统,(1)若X=A1,X+=,(2)若X=A2,X+=,(3)若X=A3,X+=,A1,A2,A3,A2,A3,A3,引理2 设F为属性集U上的函数依赖,X、YU,XY能由F根据Armstrong公理导出的充分必要条件是Y X+。证:三条推论 合并规则:如果XY,XZ,则XYZ。伪传递规则:如果XY,YWZ,则XWZ。分解规则:如果XY,ZY,则XZ。,2023/10/14,32,函数依赖的公理系
13、统,算法1 计算X+输入:X,F输出:X+算法:.,2023/10/14,33,函数依赖的公理系统,在整个计算机领域,算法无处不在!操作系统的进程管理,内存管理,编译系统的语法分析、词法分析、代码优化.数据库管理系统的数据操作算法、查询优化算法Google、Baidu等搜索引擎使用数据挖掘算法PageRank,2023/10/14,34,附加内容:算法介绍,算法是解决某问题的一个方法或一个过程。,时间复杂性空间复杂性排序冒泡、插入、快速等分治算法动态规划算法贪心算法近似算法,2023/10/14,35,附加内容:算法介绍,算法1 计算X+输入:X,F输出:X+1.X(1):=空集合;X(0):
14、=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.,2023/10/14,36,函数依赖的公理系统,例:计算X+=A,B,C,D,E,=ABC,ACB,BD,CE,ECB,求(AB)+。,2023/10/14,37,函数依赖的公理系统,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.,定理3 算法1正确
15、地计算出了X关于F的闭包X+。证:算法的终止性算法的正确性,2023/10/14,38,函数依赖的公理系统,定理4 Armstrong公理系统是有效而且完备的。证:Armstrong公理的有效性是指由F出发根据Armstrong公理推导出来的每个函数依赖一定在F+中现只需证明完备性(Armstrong公理的完备性指的是F+中的每一个函数依赖一定可以由F出发根据Armstrong公理推导出来)。,2023/10/14,39,函数依赖的公理系统,证明完备性的逆否命题:如果函数依赖XY不能由F根据Armstrong公理导出,它必然不为F蕴含。,由F出发经Armstrong公理导出的函数依赖集合为F+
16、,定义9:设G和F是两个函数依赖集。如果G+=F+则称F与G等价。引理3 设G和F是两个函数依赖集。F与G等价的充分必要条件是FG+且GF+。证明:,2023/10/14,40,函数依赖的公理系统,引理3给出了一个判断两个函数依赖集等价的算法。例F=S#SD,SDMN,(S#,CN)GG=S#SD,SDMN,(S#,CN)G,S#MNF和G等价吗?,2023/10/14,41,函数依赖的公理系统,引理3 设G和F是两个函数依赖集。F与G等价的充分必要条件是FG+且GF+。,定义10:函数依赖集F称为极小函数依赖集如果F满足下列条件:F中任一函数依赖的右部仅含有一个属性;F中不存在这样的函数依赖
17、XA,使得F与F-XA等价;F中不存在这样的函数依赖XA:X包括真子集Z使得(F-XA)ZA与F等价。,2023/10/14,42,函数依赖的公理系统,2023/10/14,43,函数依赖的公理系统,F1=S#SD,SDMN,(S#,SD,CN)GF1是最小依赖集?F2=S#SD,SDMN,S#SD,(S#,SD)GF2是最小依赖集?,2023/10/14,44,函数依赖的公理系统,F中任一函数依赖的右部仅含有一个属性;F中不存在这样的函数依赖XA,使得F与F-XA等价;F中不存在这样的函数依赖XA:X包括真子集Z使得(F-XA)ZA与F等价。,定理5 每一个函数依赖集F都等价于一个极小函数依
18、赖集。构造性证明。极小函数依赖集是否唯一?,2023/10/14,45,函数依赖的公理系统,极小函数依赖集不唯一例:F=AB,BA,BC,AC,CA的极小函数依赖集为F1=AB,BC,CAF=AB,BC,BA,AC,CA的极小函数依赖集为F2=AB,BA,AC,CA,2023/10/14,46,函数依赖的公理系统,函数依赖集F称为极小函数依赖集如果F满足下列条件:(1)F中任一函数依赖的右部仅含有一个属性;(2)F中不存在这样的函数依赖XA,使得F与F-XA等价;(3)F中不存在这样的函数依赖XA:X包括真子集Z使得(F-XA)ZA与F等价。,求极小函数依赖集练习:例:求F=ABC,BC,AB
19、C的极小函数依赖集答案:AB,BC求F=ABD,AC,ADC,BD的极小函数依赖集答案:AB,AC,BD,2023/10/14,47,函数依赖的公理系统,函数依赖集F称为极小函数依赖集如果F满足下列条件:(1)F中任一函数依赖的右部仅含有一个属性;(2)F中不存在这样的函数依赖XA,使得F与F-XA等价;(3)F中不存在这样的函数依赖XA:X包括真子集Z使得(F-XA)ZA与F等价。,以函数依赖为基础讨论关系模式的规范形式(范式)。关系模式的范式包括第一范式(1NF)第二范式(2NF)第三范式(3NF)Boyce Codd范式(BCNF)第四范式(4NF)第五范式(5NF),2023/10/1
20、4,48,关系模式的规范形式,满足这些范式条件的关系模式可以在不同程度上避免本节开始提到的冗余问题、插入问题、更新问题和删除问题。,2023/10/14,49,关系模式的规范形式,关系模式范式的基本概念定义11:第一范式(1NF)设R是一个关系模式。如果R的每个属性的值域都是不可分的简单数据项的集合,则称这个关系模式为第一范式关系模式,记作1NF。,2023/10/14,50,关系模式的规范形式,2023/10/14,51,关系模式的规范形式,关系模式范式的基本概念定义12:第二范式(2NF)若关系模式R是1NF,而且每一个非主属性都完全函数依赖于R的键,则R称为第二范式关系模式,记作2NF。
21、,2023/10/14,52,关系模式的规范形式,完全依赖定义设R是一个具有属性集合U的关系模式,如果XY,并且对于X的任何一个真子集Z,ZY都不成立,则称Y完全函数依赖于X。若XY,但Y不完全函数依赖于X,则称Y部分函数依赖于X。,2023/10/14,53,关系模式的规范形式,描述学生的关系模式:US#,SD,MN,CN,G根据数据的语义确定的函数依赖:F=S#SD,SDMN,(S#,CN)G,非2NF关系模式的插入问题,2023/10/14,54,1NF存在,非2NF关系模式的插入问题,2023/10/14,55,1NF存在,非2NF关系模式的删除问题,2023/10/14,56,1NF
22、存在,非2NF关系模式的删除问题,2023/10/14,57,1NF存在,非2NF关系模式的更新问题,2023/10/14,58,1NF存在,非2NF关系模式的更新问题,2023/10/14,59,1NF存在,把一个给定关系模式转化为某种范式的过程称为关系模式的规范化过程,简称为规范化。,2023/10/14,60,2NF的规范形式,定义12:第二范式(2NF)若关系模式是1NF,而且每一个非主属性都完全函数依赖于的键,则称为第二范式关系模式,记作2NF。,2023/10/14,61,2NF的规范形式,SC(S#,C#,G)是2NF,SSS(S#,CN,MN)是2NF,2NF关系模式解决了插入
23、问题了吗?,2023/10/14,62,2NF,解决了!,2NF关系模式解决了删除问题了吗?,2023/10/14,63,2NF,解决了!,2NF关系模式解决了更新问题了吗?,2023/10/14,64,2NF,没完全解决!,计算机,刘伟,定义13:第三范式(3NF)如果关系模式R是2NF,而且它的任何一个非键属性都不传递地依赖于任何候选键,则R称为第三范式关系模式,记作3NF。,2023/10/14,65,3NF,传递地函数依赖定义:设是一个具有属性集合的关系模式,X,Y,Z,YX不成立,Z-X、Z-Y和Y-X不空。如果XY,YZ,则称Z传递地函数依赖于X。,2023/10/14,66,3N
24、F,对非3NF关系模式进行规范化处理。,2023/10/14,67,3NF,SSS(S#,SD,MN)不是3NF,SSD(S#,SD)是3NF,SSL(SD,SL)是3NF,3NF关系模式解决了更新问题了吗?,2023/10/14,68,3NF,解决了!,计算机,定义14:BCNF范式(Boyce Codd Normal Form)设关系模式R是1NF。如果对于R的每个函数依赖XY,则X必为候选键,则R是BCNF范式。每个BCNF关系模式都具有如下三个性质:所有非键属性都完全函数依赖于每个候选键。所有键属性都完全函数依赖于每个不包含它的候选键。没有任何属性完全函数依赖于非键的任何一组属性。,2
25、023/10/14,69,Boyce Codd范式,完全依赖定义设R是一个具有属性集合U的关系模式,如果XY,并且对于X的任何一个真子集Z,ZY都不成立,则称Y完全函数依赖于X。若XY,但Y不完全函数依赖于X,则称Y部分函数依赖于X。,2023/10/14,70,范式的关系,BCNF 3NF若关系模式R是BCNF,则R一定是3NF。证明:,2023/10/14,71,关系模式范式的基本概念,?,2023/10/14,72,关系模式范式的基本概念,例:关系模式SJP(S,J,P);S表示学生,J表示课程,P表示名次。每个学生每门课程都有一个确定的名次,每门课程中每一名次只有一个学生。由这些语义得
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据库 应用 Desig
链接地址:https://www.31ppt.com/p-6296459.html