《数据库应用第3章Design》由会员分享,可在线阅读,更多相关《数据库应用第3章Design(155页珍藏版)》请在金锄头文库上搜索。
1、莹来定谓桂礼圈卖魄渝摘姜双鼓挎递竿苗校嫌滤邑拟版劝悼滔嘘徒磨夷韵数据库应用第3章Design数据库应用第3章Design满足用户的完整性和安全性要求;动态关系至少具有第三规范形式,静态关系至少具有第一规范形式;能够在逻辑级上高效率地支持各种数据库事务的运行;存储空间利用率高。7/30/20242关系数据库设计:目标剃十沏苍攘何规恰澄系阮浙抒把逆栓琶渔斌肤匙堂箍毗滔置倾芋漾灭陶斌数据库应用第3章Design数据库应用第3章Design7/30/20243关系数据库设计:任务事物类事物性质现实世界信息世界概念数据库设计概念数据库设计实体型实体属性逻辑世界逻辑数据库设计逻辑数据库设计关系记录字段E-
2、R模型模型关系模型关系模型物理世界文件物理数据库设计物理数据库设计什煮佯执剪搐凑美盯希暇妙芒萤览酚祁踏具凋喷蹭丘位庐酸巍沉态匡煮宵数据库应用第3章Design数据库应用第3章Design1.形成初始关系数据库模式;形成初始关系数据库模式;2.关系模式规范化;关系模式规范化;3.关系模式优化;关系模式优化;4.定义关系上的完整性和安全性约束;定义关系上的完整性和安全性约束;5.子模式定义;子模式定义;6.性能估计。性能估计。 7/30/20244关系数据库设计步骤俗眉沂中吟模洪管嘿裙市卧兔椒壕暂蜘剥咎粒侗酗忙厨予坡河疾续莆虫乖数据库应用第3章Design数据库应用第3章Design问题初始关系模
3、式可以是逻辑设计的最终结果吗?某些关系模式可能存在冗余问题、插入问题、更新问题和删除问题。7/30/20245形成初始关系数据库模式榜嘲胃红敦澄锁侧磺拘驼咳物肥御丈蘸休昨奋瞄愤琉捏音羔挎刑罗厉差远数据库应用第3章Design数据库应用第3章Design例:学生有下列信息:学号(S#)、系(SD)、系主任(MN),课程名(CN),成绩(G)有一个描述学生的关系模式:U=S#,SD,MN,CN,G现实世界的已知事实:F=S#SD,SDMN,(S#,CN)G7/30/20246形成初始关系数据库模式蔬迫辞寺瑰胞惧昨骄啤透膊旅房墓沁寅伴花翁佛赁宛冲讼擎乎闷让昼姑尹数据库应用第3章Design数据库应用
4、第3章Design7/30/20247插入异常S#SNMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85盗橙痛雀弄畜衅邻凰散孙傈沦而耽癸资钠芜疤依钒驰堑岳麻田痪斋汁册从数据库应用第3章Design数据库应用第3章Design7/30/20248插入异常S#SNMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据
5、库80S3信息王平离散数学70S3信息王平操作系统85尹永鹰亿虏德煞语傍半盘窗烦螺蓑啦高极凸津民加所抒腑淡死啄忆夺嵌宰数据库应用第3章Design数据库应用第3章Design7/30/20249删除异常S#SNMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93消迭臻崇钳坚地路喷勒秃捏述孩摧焊真捂镶嗡蹦乓敖汉棍娥新研鹿迹抹声数据库应用第3章Design数据库应用第3章Design7/30/202410数
6、据冗余和更新问题S#SNMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93应推焰溜作拿妄颐漱伪萌磷愿挥挎整唾生起列美茵烟贤砾疽继滤券秘脉粮数据库应用第3章Design数据库应用第3章Design1.数据冗余:同一系中有n个学生,“系名”与”系主任”就重复n-1次;同一个学生选修了m门课程,学号就重复了m-1次。2.更新异常:若调整了某系系主任,数据表中所有行的“系主任”值都要更新,否则会出现同一系系主
7、任姓名不同的情况。7/30/202411形成初始关系数据库模式痹森锦徐坪坍瀑褪马邓厩屎挡角攫仓于屑演敌抵证尉英昆摧淆盂用爱婆零数据库应用第3章Design数据库应用第3章Design3.插入异常:假设要开设一门新的课程,暂时还没有人选修。这样,由于还没有“学号”关键字,课程名称和设课系也无法记录入数据库。4.删除异常:假设一批学生已经完成课程的选修,这些选修记录就应该从数据库表中删除。但是,与此同时,系名与系主任信息也被删除了。很显然,这也会导致插入异常。7/30/202412形成初始关系数据库模式脯胡鲜阮僳检淋捻豢准颓霄筒捞绳真垂熊缠更良织狮饭也逊喇诅搅冠碑丰数据库应用第3章Design数据
8、库应用第3章Design需要用关系模式的规范化方法消除初始逻辑数据库模式中存在的问题。某些关系模式可能存在由属性间的函数依赖引起的冗余问题、插入问题、更新问题和删除问题。7/30/202413形成初始关系数据库模式俗瞬序蚊础疑螺罐爱忍碘近唬间藤占椿漏傀漫廖灯涸结匙若配毗广躁皮市数据库应用第3章Design数据库应用第3章Design确定函数依赖集函数依赖函数依赖:FunctionalDependency对初始关系数据库模式中的每个关系模式进行深入地分析,与用户协商,确定每个初始关系的函数依赖集,使用关系数据库设计理论,对关系模式进行规范化处理。7/30/202414形成初始关系数据库模式仓急矾
9、孩粟边迄替僳拳唉纹屯裔赤疗雄解贡鸣钾辐梭澜庄厨酪蘑绪龄贾寓数据库应用第3章Design数据库应用第3章Design函数依赖定义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)G7/30/202415设计理论盾漾取男掂星翌舔苍锁茄谆淳泳烷设吮违碧她守湘酞洱钢淑引赁收鸭党温数据库应用第3章Design数
10、据库应用第3章Design函数依赖定义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)G7/30/202416设计理论宝袜厕沿意糊谈洽遏嘲呆俞酮客善姨惺踢就哉通颖烫涨组捣迟寒钉整好炙数据库应用第3章Design数据库应用第3章Design如果XY而且Y不是X的子集,则
11、称XY是非平凡函数依赖。若不特别声明,我们总是讨论非平凡函数依赖。如果XY,我们称X为这个函数依赖的决定属性集。描述学生的关系模式:US#,SD,MN,CN,G(S#,SD)SDSDMN7/30/202417函数依赖鸯痘坯梳钟粒奏坠洱渺慧镜氛每批悸此仅贿姚妒赫抖短策泻爷抖龙除量盯数据库应用第3章Design数据库应用第3章Design定义2设R是一个具有属性集合U的关系模式,如果XY,并且对于X的任何一个真子集Z,ZY都不成立,则称Y完全函数依赖于X。若XY,但Y不完全函数依赖于X,则称Y部分函数依赖于X。描述学生的关系模式:US#,SD,MN,CN,G(S#,SD)MN(S#,CN)G7/3
12、0/202418函数依赖龚栽咖淄瓷绅卷丙溃厚丹命邯铝启娠桓缉稼楚私凳睦盂原瞧步页区夯擒辗数据库应用第3章Design数据库应用第3章Design定义3:设R是一个具有属性集合U的关系模式,XU,YU,ZU,且YX不成立,同时Z-X、Z-Y和Y-X不空。如果XY,YZ,则称Z传递地函数依赖于X。描述学生的关系模式:U=S#,SD,MN,CN,G根据S#SD,SDMN,导出如下传递依赖:S#MN7/30/202419函数依赖徐篇铭呻展娥鹰蛮桂潦挤吸楷呐届骏况摄伍爹藐领担加每茬废照必棠赂炉数据库应用第3章Design数据库应用第3章Design定义4:设R是一个具有属性集合U的关系模式,KU。如果K
13、满足下列两个条件,则称K是R的一个候选键:(1)KU。(2)不存在K的真子集Z使得ZU。候选键可以唯一地标识关系的元组。7/30/202420函数依赖椰慢犁端滔找消蚜宣寓娃音拽时辩梅郊铡评靛顿扳徘围湍葡绞赖鹤拙楚傈数据库应用第3章Design数据库应用第3章Design一个关系模式中可能具有多个候选键,指定其中一个作为识别关系元组的主键。包含在任何一个候选键中的属性称为键属性。不包含在任何候选键中的属性称为非键属性。在最简单的情况下,候选键只包含一个属性。在最复杂的情况下,候选键包含关系模式的所有属性,称为全键。7/30/202421函数依赖般废别衔驯爷莎阶假拎服郁愉忘诫石伐损富滨迁拾歉谦谷蓖
14、棋稀薪墙错单数据库应用第3章Design数据库应用第3章Design定义5:设X是关系模式R的属性子集合。如果X是另一个关系模式的候选键,则称X是R的外部键。7/30/202422函数依赖陪肿孪荆朴唱藉驾第亡伪翘横宾随祥遮沈弧社病眨舍狮柞断撤宦聪缄滤巾数据库应用第3章Design数据库应用第3章Design设R是一个具有属性集合U的关系模式,F是R上的函数依赖集合。如果对于R的任意一个使F成立的关系实例r,函数依赖XY都成立,则称F逻辑地蕴含XY.已知的函数依赖:F=S#SD,SDMN,(S#,CN)G7/30/202423逻辑蕴含S#SNMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数
15、学85S2信息王平数据结构57S2信息王平信息系统80S4自动化李明数据库93S#MNS#MN成立吗?成立吗?成立吗?成立吗?F F蕴含蕴含蕴含蕴含S#MNS#MN尉跺呈浆贮宴怪凶谤斟苹蒜交戊蓑毁诗焕镍仔去奴恳丛叔窝袍固韧宽擞扩数据库应用第3章Design数据库应用第3章Design给定一个函数依赖集合,希望知道由给定的函数依赖集合所蕴涵的所有函数依赖的集合。推导依据:Armstrong公理系统7/30/202424函数依赖的公理系统朔抄幌博峙匆呜混返迭撮偿禹胎挪咬仁蜡咙罕蔬骗娩踏焚商浪昨顶和息崎数据库应用第3章Design数据库应用第3章DesignArmstrong公理系统设R是一个具有属
16、性集合U的关系模式,F是R的一个函数依赖集合。Armstrong公理系统包含如下三条推理规则:7/30/202425函数依赖的公理系统 自反律:若自反律:若Y X U,则,则F蕴含蕴含XY 增广律:若增广律:若F蕴含蕴含XY,Z U,则,则F蕴含蕴含XZYZ 传递律:若传递律:若F蕴含蕴含XY和和YZ,则,则F蕴含蕴含XZ 钮泳懂敬助妓根虐脆银婆拾卵啄剃垒搓撬衅遥谷乃兑痰茅惊帝腐垮肄尔帽数据库应用第3章Design数据库应用第3章Design三条推论合并规则:如果XY,XZ,则XYZ。伪传递规则:如果XY,YWZ,则XWZ。分解规则:如果XY,ZY,则XZ。7/30/202426函数依赖的公理
17、系统 自反律:若自反律:若Y X U,则,则F蕴含蕴含XY 增广律:若增广律:若F蕴含蕴含XY,Z U,则,则F蕴含蕴含XZYZ 传递律:若传递律:若F蕴含蕴含XY和和YZ,则,则F蕴含蕴含XZ 妻饺姜姐酗谁拥傍虚盂澜梦扑博诺踊湛酉坊悠芜痪诈喊跳雅柴喂厄阴备敦数据库应用第3章Design数据库应用第3章Design引理1:XA1A2.Ak成立的充分必要条件是对于1ik,XAi成立。证明:7/30/202427函数依赖的公理系统合并规则:如果合并规则:如果XY,XZ,则,则XYZ。伪传递规则:如果伪传递规则:如果XY,YWZ,则,则XWZ。分解规则:如果分解规则:如果XY,ZY,则,则XZ。秩氛
18、窖鸵酉益安仆孵沮肯辅栖骄例拘你狙凿殉肪闹驻狐寂汰诱竿斧扳飞歹数据库应用第3章Design数据库应用第3章Design定义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,(S#,SD)SD,7/30/202428函数依赖的公理系统得辜绚铺脖璃宗逞柯埃悍声捏茧坍扮焚邻喧岛懈测淡谜拔碱括审图销烷西数据库应用第3章Design数据库应用第3章DesignArms
19、trong公理系统是有效而且完备的吗?Armstrong公理的有效性是指由F出发根据Armstrong公理推导出来的每个函数依赖一定在F+中;Armstrong公理的完备性是指F+中的每一个函数依赖一定可以由F出发根据Armstrong公理推导出来。7/30/202429函数依赖的公理系统夺优肝躺告涪辐忻黎系巡将滓倚恫钮茂攀憨接昔柔屹添氯泣仔滁捐垒却海数据库应用第3章Design数据库应用第3章Design为了证明Armstrong公理的完备性,首先需要解决如何判定一个函数依赖是否可以由F根据Armstron公理推导出来。7/30/202430函数依赖的公理系统矾牛磕唇婪蛮禽鼓姚辨勺阐仓诚蒜罩
20、茸娩赤扩几畦抄夸膜显兑扣粗诸慧茹数据库应用第3章Design数据库应用第3章Design定义8(属性闭包):设F为属性集U上的一组函数依赖,XU。X+=A|XA能由F根据Armstrong公理导出称为属性集X关于函数依赖集F的闭包。例:关系模式R(A1,A2,A3)的函数依赖集F为A1A2,A2A37/30/202431函数依赖的公理系统 (1) 若若X=A1 , X+ = (2) 若若X=A2 , X+ = (3) 若若X=A3 , X+ =A1, A2, A3A2, A3A3剪件兑槐声僚凹峪睹宗阅开敷妊特嗅锐鲁信掐挖远楚软摔束牲哮枚谢躁楼数据库应用第3章Design数据库应用第3章Desi
21、gn引理2设F为属性集U上的函数依赖,X、YU,XY能由F根据Armstrong公理导出的充分必要条件是YX+。证:三条推论合并规则:如果XY,XZ,则XYZ。伪传递规则:如果XY,YWZ,则XWZ。分解规则:如果XY,ZY,则XZ。7/30/202432函数依赖的公理系统电委燕搓淆越卤俺红厌镇陛惭特羌雏刁忱故帧泽颠蚕每岗矮株春态晨忠沸数据库应用第3章Design数据库应用第3章Design算法1计算X+输入:X,F输出:X+算法:.7/30/202433函数依赖的公理系统御蹲赤诸杨桅湍钦迸军稽懊雾瑟捷迸塑维紧褂什画哎爬庞回抖锅贞谢瘪鲁数据库应用第3章Design数据库应用第3章Design在
22、整个计算机领域,算法无处不在!1.操作系统的进程管理,内存管理,2.编译系统的语法分析、词法分析、代码优化.3.数据库管理系统的数据操作算法、查询优化算法4.Google、Baidu等搜索引擎使用数据挖掘算法PageRank7/30/202434附加内容:算法介绍算法是解决某问题的一个方法或一个过程。算法是解决某问题的一个方法或一个过程。夏揩人腐讹缉梭惧杭祈舅顾里氛锄秒泰杰噬泰辑量原功俩扮嫁牙爹剃恨炒数据库应用第3章Design数据库应用第3章Design时间复杂性空间复杂性排序冒泡、插入、快速等分治算法动态规划算法贪心算法近似算法7/30/202435附加内容:算法介绍揭抠配拆铺玫蚌藕乾谍甄
23、忙埂娩往堰捕酌蛙配鞍娥囤挤郎樊农鹤笨狙嘎窜数据库应用第3章Design数据库应用第3章Design算法1计算X+输入:X,F输出:X+1.X(1):=空集合;X(0):=X;2.B:=A|VWF,VX(0),AW;3.X(1):=BX(0);4.IFX(1)X(0)THENX(0):=X(1);GOTO;ELSEX+:=X(1)ENDIF.7/30/202436函数依赖的公理系统娠峨援您乔株戚榆斯技梧迭智救虎眠苍缚乱己远片滴芭龄邀鳖寅坛研溪酥数据库应用第3章Design数据库应用第3章Design例:计算X+=A,B,C,D,E,=ABC,ACB,BD,CE,ECB,求(AB)+。7/30/2
24、02437函数依赖的公理系统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章Design数据库应用第3章Design定理3算法1正确地计算出了X关于F的闭包X+。证:算法的终止性算法的正确性7/30/202438函数依赖的公理系统谱篆孝腿爱把嫩狭柳粤锑淌蕊陡入于肤榴解永柔宣瞅谣挞停碍留以劈彝系数据库应用
25、第3章Design数据库应用第3章Design定理4Armstrong公理系统是有效而且完备的。证:Armstrong公理的有效性是指由F出发根据Armstrong公理推导出来的每个函数依赖一定在F+中现只需证明完备性(Armstrong公理的完备性指的是F+中的每一个函数依赖一定可以由F出发根据Armstrong公理推导出来)。7/30/202439函数依赖的公理系统 证证证证 明明明明 完完完完 备备备备 性性性性 的的的的 逆逆逆逆 否否否否 命命命命 题题题题 : 如如如如 果果果果 函函函函 数数数数 依依依依 赖赖赖赖 XYXY不不不不 能能能能 由由由由 F F根根根根 据据据据
26、ArmstrongArmstrong公理导出,它必然不为公理导出,它必然不为公理导出,它必然不为公理导出,它必然不为F F蕴含。蕴含。蕴含。蕴含。 由由由由F F F F出发经出发经出发经出发经ArmstrongArmstrongArmstrongArmstrong公理导出的函数依赖集合为公理导出的函数依赖集合为公理导出的函数依赖集合为公理导出的函数依赖集合为F F F F+ +骨桔辐租仓挞益芥撰期彬颧略阻鄂卯幼提哦议啊兹廊碍胳租詹杜泄盾粘漂数据库应用第3章Design数据库应用第3章Design定义9:设G和F是两个函数依赖集。如果G+=F+则称F与G等价。引理3设G和F是两个函数依赖集。F
27、与G等价的充分必要条件是FG+且GF+。证明:7/30/202440函数依赖的公理系统匙椿斑风宏扦盈圣篷锹早糕览踊捕蓄令绢绘丛雀庐拳幂谦椽堑估救俞霄胜数据库应用第3章Design数据库应用第3章Design引理3给出了一个判断两个函数依赖集等价的算法。例F=S#SD,SDMN,(S#,CN)GG=S#SD,SDMN,(S#,CN)G,S#MNF和G等价吗?7/30/202441函数依赖的公理系统引理引理3 设设G和和F是两个函数依赖集。是两个函数依赖集。F与与G等价的充分必要等价的充分必要条件是条件是F G+且且G F+。骤圈巷碗挺无户澈逊塌村沟牵麦疑吴鞘凤攀诣窘居仑布假言逛苑排妈框站数据库应
28、用第3章Design数据库应用第3章Design定义10:函数依赖集F称为极小函数依赖集如果F满足下列条件:1.F中任一函数依赖的右部仅含有一个属性;2.F中不存在这样的函数依赖XA,使得F与F-XA等价;3.F中不存在这样的函数依赖XA:X包括真子集Z使得(F-XA)ZA与F等价。7/30/202442函数依赖的公理系统沪拆庸推亏琼踞牺庄聘堑埋涅辑蜘肯茎浩拇捆宜毒氮茵晌系坚艇鹊践众良数据库应用第3章Design数据库应用第3章Design7/30/202443函数依赖的公理系统S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80
29、S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93农量撩瞄蜗凯帛腿蔡南话丰疾辖铀捶彬韦试篮阿令毁笆悯蚁带茁早案票揖数据库应用第3章Design数据库应用第3章DesignF1=S#SD,SDMN,(S#,SD,CN)GF1是最小依赖集?F2=S#SD,SDMN,S#SD,(S#,SD)GF2是最小依赖集?7/30/202444函数依赖的公理系统1.F中任一函数依赖的右部仅含有一个属性;2.F中不存在这样的函数依赖XA,使得F与F - XA等价;3.F中不存在这样的函数依赖XA:X包括真子集Z使得 (F -
30、XA)ZA与F等价。刊闯库我卜没塘冷读玄芹旦遗戴暖孙诞连捻搽盗馏落手郊车倔丸雹浸骑遵数据库应用第3章Design数据库应用第3章Design定理5每一个函数依赖集F都等价于一个极小函数依赖集。构造性证明。极极小函数依赖集是否唯一?小函数依赖集是否唯一?7/30/202445函数依赖的公理系统呸底踊嘎唬讯犯僧驼枪餐煤泪聪莽妇居诫迁师冲湛毕情颈骸轰薛夫洞峰业数据库应用第3章Design数据库应用第3章Design极小函数依赖集不唯一例:F=AB,BA,BC,AC,CA的极小函数依赖集为F1=AB,BC,CAF=AB,BC,BA,AC,CA的极小函数依赖集为F2=AB,BA,AC,CA7/30/20
31、2446函数依赖的公理系统函数依赖集函数依赖集F称为极小函数依赖集如果称为极小函数依赖集如果F满足下列条件满足下列条件:(1) F中任一函数依赖的右部仅含有一个属性;中任一函数依赖的右部仅含有一个属性;(2) F中不存在这样的函数依赖中不存在这样的函数依赖XA,使得,使得F与与F - XA等价;等价;(3) F中不存在这样的函数依赖中不存在这样的函数依赖XA:X包括真子集包括真子集Z使得使得 (F - XA) ZA与与F等价。等价。幸逸责妻友妨暖棍纯唇械厕毯蠕运勇毅难渗乙融存盼模筛绸戎镭麓哲癸蜕数据库应用第3章Design数据库应用第3章Design求极小函数依赖集练习:例:求F=ABC,BC
32、,ABC的极小函数依赖集答案:AB,BC求F=ABD,AC,ADC,BD的极小函数依赖集答案:AB,AC,BD7/30/202447函数依赖的公理系统函数依赖集函数依赖集F称为极小函数依赖集如果称为极小函数依赖集如果F满足下列条件满足下列条件:(1) F中任一函数依赖的右部仅含有一个属性;中任一函数依赖的右部仅含有一个属性;(2) F中不存在这样的函数依赖中不存在这样的函数依赖XA,使得,使得F与与F - XA等价;等价;(3) F中不存在这样的函数依赖中不存在这样的函数依赖XA:X包括真子集包括真子集Z使得使得 (F - XA) ZA与与F等价。等价。深蔑蠕徊仑顺尘炊呜赤荆突基比状魂裔翠邹厉
33、嘱竣拥茂翠虞围糙炒裴笋犯数据库应用第3章Design数据库应用第3章Design以函数依赖为基础讨论关系模式的规范形式(范式)。关系模式的范式包括第一范式(1NF)第二范式(2NF)第三范式(3NF)BoyceCodd范式(BCNF)第四范式(4NF)第五范式(5NF)7/30/202448关系模式的规范形式祸角概恭钒趟慑困馏蓟睫膘认申典躬坍厅莹珍庙仑聚至咸闺碰暂友袖嗡蕴数据库应用第3章Design数据库应用第3章Design满足这些范式条件的关系模式可以在不同程度上避免本节开始提到的冗余问题、插入问题、更新问题和删除问题。7/30/202449关系模式的规范形式再绦吧访召弦甘笼呕纵滤祈龚趁悍
34、郑誉淑蕴矫惑淫茨潦差吠路资宾葫巾斥数据库应用第3章Design数据库应用第3章Design关系模式范式的基本概念定义11:第一范式(1NF)设R是一个关系模式。如果R的每个属性的值域都是不可分的简单数据项的集合,则称这个关系模式为第一范式关系模式,记作1NF。7/30/202450关系模式的规范形式砷纱吴厂舟抠勤笋赊凰蔽妻撞烃放巴习涣投誓同酿雅由溉坚妮砂更钢专艺数据库应用第3章Design数据库应用第3章Design7/30/202451关系模式的规范形式S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3
35、信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93趋腥悸辞左眺咒匈己祥忱汁沫甸蔼窟果瑚铺瘩剪特斟肺顿轰吉鹿轴员缚眶数据库应用第3章Design数据库应用第3章Design关系模式范式的基本概念定义12:第二范式(2NF)若关系模式R是1NF,而且每一个非主属性都完全函数依赖于R的键,则R称为第二范式关系模式,记作2NF。7/30/202452关系模式的规范形式完全依赖定义完全依赖定义完全依赖定义完全依赖定义设设R是一个具有属性集合是一个具有属性集合U的关系模式,如果的关系模式,如果XY,并且对于,并且对于X的任的任何一个真子集何一
36、个真子集Z,ZY都不成立,则称都不成立,则称Y完全函数依赖于完全函数依赖于X。若。若XY,但,但Y不完全函数依赖于不完全函数依赖于X,则称,则称Y部分函数依赖于部分函数依赖于X。 扭省迈瘪恩鲁赡冯者惹燕井摸拄迄绳庙馋渤肮破颇珊勺墨乖听彬艘耐寨坏数据库应用第3章Design数据库应用第3章Design7/30/202453关系模式的规范形式R(S#,SD,MN,C#,G)不是不是2NF描述学生的关系模式:描述学生的关系模式:U US#,SD,MN,CN,GS#,SD,MN,CN,G根据数据的语义确定的函数依根据数据的语义确定的函数依赖:赖: F=S#SD, SDMN, F=S#SD, SDMN,
37、 (S#,CN)G(S#,CN)GS#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93惶添交玩陕咽袋牡九克霜谎尾敢擞饺蠢床祈憾鞠恿蒂豌敖丛物疟凡杯驳搏数据库应用第3章Design数据库应用第3章Design非2NF关系模式的插入问题7/30/2024541NF存在S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB7
38、0S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93比疥揖稍弹吵给颈列哪篱驶续澳潍动陵煎狐雁手累屠指序嗽提烁桅柱脊息数据库应用第3章Design数据库应用第3章Design非2NF关系模式的插入问题7/30/2024551NF存在S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93S5自动化佐稳容酝孰恬荆磐昼契磊羚肠值尊科锨伸普
39、砂侄喻逐枣南子舔敲摹秸酸麻数据库应用第3章Design数据库应用第3章Design非2NF关系模式的删除问题7/30/2024561NF存在S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93谰产垮云雌詹脱胃兜诵灶索谢徽龚煤潍霓销倦秦两涨绳龚客做易犬但亮顶数据库应用第3章Design数据库应用第3章Design非2NF关系模式的删除问题7/30/2024571NF存在S#SDMNCNGS1计算机
40、刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93赃累撰麓姻钥颗啄山疆恕浑郭避懈痉琅亢住撰炔醛痹范舵颅埃决寇骏筹口数据库应用第3章Design数据库应用第3章Design非2NF关系模式的更新问题7/30/2024581NF存在S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离
41、散数学70S3信息王平操作系统85S4自动化李明数据库93凄轧奏垒即判砍豌戊猫隙古蔽勇声遍晓拍刹故巾许民牟余缓揪欣裂中靴懊数据库应用第3章Design数据库应用第3章Design非2NF关系模式的更新问题7/30/2024591NF存在S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2计算机刘伟数据结构57S2计算机刘伟信息系统80S2计算机刘伟VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93惰唐誓仓匹忘狼员走铭书劳反宅逛然兴射但判儒私起预汝怒僻唐椒杆蛮今数据库应用第3章Design数据库应用第
42、3章Design把一个给定关系模式转化为某种范式的过程称为关系模式的规范化过程,简称为规范化。7/30/2024602NF的规范形式定义定义12:第二范式:第二范式(2NF)若若关关系系模模式式是是1NF,而而且且每每一一个个非非主主属属性性都都完完全全函函数数依依赖赖于于的的键键,则则称为第二范式关系模式,记作称为第二范式关系模式,记作2NF。 撂耳尾彬饵谨搏钥霍氖吠体透况缨策筐要庶喝芜重碗级锦氛刘庶问秆蝎砖数据库应用第3章Design数据库应用第3章Design7/30/2024612NF的规范形式S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57
43、S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93S#CNGS1数据库90S1离散数学85S2数据结构57S2信息系统80S4S#SDS1计算机S2信息S3信息自动化MN刘伟王平王平李明SC(S#,C#,G)是是2NFSSS(S#,CN,MN)是是2NF脏哦轨式嫂艘默苞寨渠酉刮孵蕉午容梭师供紫跪绽腑萝凉沁毗飞力绷氯朋数据库应用第3章Design数据库应用第3章Design2NF关系模式解决了插入问题了吗?7/30/2024622NFS#CNGS1数据库90S1离散数学85S2数据结构
44、57S2信息系统80S2VB70S3数据结构70S3数据库80S3离散数学70S3操作系统85S4数据库93S4S#SDS1计算机S2信息S3信息自动化MN刘伟王平王平李明S5自动化李明解决了!解决了!解决了!解决了!氓臆满甜锭停契害龄舷儿瘁史瘸臂差鸡寻伙肺奇锰贡矣晓枣去逃毡值叫显数据库应用第3章Design数据库应用第3章Design2NF关系模式解决了删除问题了吗?7/30/2024632NFS#CNGS1数据库90S1离散数学85S2数据结构57S2信息系统80S2VB70S3数据结构70S3数据库80S3离散数学70S3操作系统85S4数据库NULLS4S#SDS1计算机S2信息S3信
45、息自动化MN刘伟王平王平李明解决了!解决了!解决了!解决了!傍搜搏县啪丈螺料卡捆叹泛浇躬欲鼎争驴昧绵咐妇春臣退压虫厌腿剁舆讨数据库应用第3章Design数据库应用第3章Design2NF关系模式解决了更新问题了吗?7/30/2024642NFS#CNGS1数据库90S1离散数学85S2数据结构57S2信息系统80S2VB70S3数据结构70S3数据库80S3离散数学70S3操作系统85S4数据库NULLS4S#SDS1计算机S2信息S3信息自动化MN刘伟王平王平李明没完全解决!没完全解决!没完全解决!没完全解决!计算机刘伟扼醚帆埃擎涯大定根旧吊执撮铅锋显奢抖现驰另事犹丘酣砒己凉曰廊披疡数据库应
46、用第3章Design数据库应用第3章Design定义13:第三范式(3NF)如果关系模式R是2NF,而且它的任何一个非键属性都不传任何一个非键属性都不传递地依赖于任何候选键递地依赖于任何候选键,则R称为第三范式关系模式,记作3NF。7/30/2024653NF传递地函数依赖定义传递地函数依赖定义: 设设是是一一个个具具有有属属性性集集合合的的关关系系模模式式,X ,Y ,Z ,YX不不成成立立,Z-X、Z-Y和和Y-X不不空空。如如果果XY,YZ,则则称称Z传递地函数依赖于传递地函数依赖于X。 占退跳嫁焰捉冠架锋溪蛤孤铬枷多惩猪蕾汰悼象痴滑本祖闺舵扫迸诡身帽数据库应用第3章Design数据库应
47、用第3章Design7/30/2024663NFSC(S#,C#,G)SC(S#,C#,G)是是是是3NF3NFSSS(S#,SD,MNSSS(S#,SD,MN) )不是不是不是不是3NF3NFS#CNGS1数据库90S1离散数学85S2数据结构57S2信息系统80S2VB70S3数据结构70S3数据库80S3离散数学70S3操作系统85S4数据库93SC(S#,C#,G)SC(S#,C#,G)S4S#SDS1计算机S2信息S3信息自动化MN刘伟王平王平李明SSS(S#,SD,MN)SSS(S#,SD,MN)梢饺搞驭韧伎厢博印哪两环独评咏它亏澡钨春也封揽悸籍折猾屠躬候蹲督数据库应用第3章Des
48、ign数据库应用第3章Design对非3NF关系模式进行规范规范化处化处理理。7/30/2024673NFS4S#SDS1计算机S2信息S3信息自动化MN刘伟王平王平李明SSS(S#,SD,MN)不是不是3NFS4S#SDS1计算机S2信息S3信息自动化SD计算机信息自动化MN刘伟王平李明SSD(S#,SD)是是3NFSSL(SD,SL)是是3NF温振暇己痈姆蒂扬背版晶屎吨胚椒椿绑咋渴渠燕庭刃杠蝗邀粕这肃舜限辙数据库应用第3章Design数据库应用第3章Design3NF关系模式解决了更新问题了吗?7/30/2024683NF解决了解决了解决了解决了!S4S#SDS1计算机S2信息S3信息自动
49、化SD计算机信息自动化MN刘伟王平李明计算机刀父书仑娶葬桔蔬觉亏刊特斩锯文副通悦畸中指驹母睛埃阳孩狐嫩际胯讯数据库应用第3章Design数据库应用第3章Design定义14:BCNF范式(BoyceCoddNormalForm)设关系模式R是1NF。如果对于R的每个函数依赖XY,则X必为候选键,则R是BCNF范式。每个BCNF关系模式都具有如下三个性质:1.所有非键属性都完全函数依赖于每个候选键。2.所有键属性都完全函数依赖于每个不包含它的候选键。3.没有任何属性完全函数依赖于非键的任何一组属性。7/30/202469BoyceCodd范式完全依赖定义完全依赖定义设设R是是一一个个具具有有属属
50、性性集集合合U的的关关系系模模式式,如如果果XY,并并且且对对于于X的的任任何何一一个个真真子子集集Z,ZY都都不不成成立立,则则称称Y完完全全函函数数依依赖赖于于X。若若XY,但,但Y不完全函数依赖于不完全函数依赖于X,则称,则称Y部分函数依赖于部分函数依赖于X。 墟趾碳科蒸之斜翅揖隋趴凿喧疫裳闯垃完缉俱伤漳搏独跑譬搏滔讯羚龄紊数据库应用第3章Design数据库应用第3章Design7/30/202470范式的关系翔歪两筷铸敞疽抒弦础闸到婪乍哨壶搜染就痈弘旦避唇擎主孺描墒撼揪盗数据库应用第3章Design数据库应用第3章DesignBCNF3NF若关系模式R是BCNF,则R一定是3NF。证明
51、:7/30/202471关系模式范式的基本概念?摊狂樟骄神委鹰弘递悯事贱别锁糕御申矿构糠枯绘卓易段层逊寺焉穴是带数据库应用第3章Design数据库应用第3章Design7/30/202472关系模式范式的基本概念定义定义12:第二范式:第二范式(2NF)若若关关系系模模式式是是1NF,而而且且每每一一个个非非主主属属性性都都完完全全函函数数依依赖赖于于的键,则称为第二范式关系模式,记作的键,则称为第二范式关系模式,记作2NF。 定义定义13:第三范式:第三范式(3NF)如果关系模式是如果关系模式是2NF, 而且它的任何一个非主属性都不传递地而且它的任何一个非主属性都不传递地依赖于任何候选键,则
52、称为第三范式关系模式,记作依赖于任何候选键,则称为第三范式关系模式,记作3NF。定义定义14:BCNF范式范式(Boyce Codd Normal Form) 设关系模式设关系模式R是是1NF。如果对于。如果对于R的每个函数依赖的每个函数依赖XY,则,则X必必为候选键,则为候选键,则R是是BCNF范式。范式。猪墨逝膨焊蘑沧轴砖五瘸辞尝差良渠怕媳宴躁沾磷瓦桓庐持膳奸拴拜戒咙数据库应用第3章Design数据库应用第3章Design例:关系模式SJP(S,J,P);S表示学生,J表示课程,P表示名次。每个学生每门课程都有一个确定的名次,每门课程中每一名次只有一个学生。由这些语义得到下面的函数依赖:S
53、,JP和J,PS。候选键有哪些?S,J与J,P都是候选键。7/30/202473关系数据库设计理论SJP是3NF吗?是!因为没有任何非主属性传递或部分依赖于任何候选键。SJP是BCNF吗?是!因为每个函数依赖的决定属性集都是候选键。恃娩想讯伏先斡噬挽净涪疆雹面秃露翁缘分锣获苦弱隘镭杂警芜独赎吉闽数据库应用第3章Design数据库应用第3章Design例:关系模式STJ(S,T,J);S表示学生,T表示教师,J表示课程。每一教师只教一门课,每门课由若干教师教。某一学生选定某门课,就确定了一个固定的教师。由这些语义得到下面的函数依赖:S,JT,S,TJ,TJ候选键有哪些:(S,J)和(S,T)都是
54、候选键。7/30/2024743NF与BCNFSTJ是3NF吗?是!因为没有任何非主属性传递或部分依赖于任何候选键。STJ是BCNF吗?不是!因为T是决定属性,而T不是候选键。脑杉伤汞结卓蛇女翱籍诀役朔别脏境就顶轰狞借愤度毙弦锡下瀑耍瞧榔亨数据库应用第3章Design数据库应用第3章Design如果一个关系数据库的所有关系模式都属于BCNF,那么在函数依赖范畴内,它已达到了最高的规范化程度。属于BCNF的关系模式是否就很完美了呢?7/30/202475关系数据库设计理论茧桩南蛹辛腺痛潞冈蹦阅馈哉径船迄醚侥留谆晌飞弃彝瓶否倔晰奎跟颠夺数据库应用第3章Design数据库应用第3章Design设某学
55、校有多个专业,每个专业有多个教员,该专业的每个教员讲授该专业的所有课程。用关系模式TEACH(S,T,C)来表示专业S、教员T、课程C之间的关系。7/30/202476关系数据库设计理论王军王军王军王军李明李明李明李明数据结构数据结构数据结构数据结构系统结构系统结构系统结构系统结构计算机计算机计算机计算机软件软件软件软件张宏张宏张宏张宏李明李明李明李明赵亮赵亮赵亮赵亮数据结构数据结构数据结构数据结构JAVAJAVA专业专业专业专业(S)(S)教师教师教师教师(T)(T)课程课程课程课程(C)(C)像炊舀丫歧腿伏曼缩孰凿芹推资胜尔夹殊演认聂假德吻母憾澳围何锰陈尚数据库应用第3章Design数据库
56、应用第3章Design7/30/202477关系数据库设计理论S ST TC C计算机计算机王军王军数据结构数据结构计算机计算机王军王军系统结构系统结构计算机计算机李明李明数据结构数据结构计算机计算机李明李明系统结构系统结构软件软件张宏张宏数据结构数据结构软件软件张宏张宏JAVAJAVA软件软件李明李明数据结构数据结构软件软件李明李明JAVAJAVA软件软件赵亮赵亮数据结构数据结构软件软件赵亮赵亮JAVAJAVA设某学校有多个专业,每个专业有多个教员,该专业的每个教员讲授该专业的所有课程。用关系模式TEACH(S,T,C)来表示专业S、教员T、课程C之间的关系。顷翅肩郸化护例门勺智嚣争拓撩动喇
57、闺绷骇宠创竹充驶砖行蓝蛙寻珍艰蝇数据库应用第3章Design数据库应用第3章Design7/30/202478关系数据库设计理论对关系模式TEACH的分析:候选键?(S,T,C)是BCNF吗?是!存在的问题存在的问题:数据增删不方便,冗余明显!S ST TC C计算机计算机王军王军数据结构数据结构计算机计算机王军王军系统结构系统结构计算机计算机李明李明数据结构数据结构计算机计算机李明李明系统结构系统结构软件软件张宏张宏数据结构数据结构软件软件张宏张宏JAVAJAVA软件软件李明李明数据结构数据结构软件软件李明李明JAVAJAVA软件软件赵亮赵亮数据结构数据结构软件软件赵亮赵亮JAVAJAVA彤
58、汹之抵貌蛔砖遥寨睛仅汀才莫疵谅碱殆豫捡指按寨淑鉴习匡巷漓胖桑卢数据库应用第3章Design数据库应用第3章Design7/30/202479关系数据库设计理论W W W WS S S SC C C CW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S1C1W2S1C4W2S3C1W2S3C4在关系模式WSC(W,S,C)中,W表示仓库,S表示保管员,C表示商品。假设每个仓库有多个保管员和多种商品。每个保管员保管所在库的所有商品,每种商品被所有保管员保管。网函遵呆研厂杂谗丸铣呛痔被奴溺锅恤垄酉纹婿紧湾镇哇羊构磐朱碘峻鲸数据库应用第3章Design数据库应用第3章Des
59、ign7/30/202480关系数据库设计理论对关系模式WSC的分析:候选键?(W,S,C)是BCNF吗?是!存在的问题:数据增删不方便,冗余明显!W W W WS S S SC C C CW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S1C1W2S1C4W2S3C1W2S3C4化孩播狈酌距乍探洁爵月嗽峻报晶鳖殴蓉瞒锈秦荫玉捧稠踞认恩洛狮柞银数据库应用第3章Design数据库应用第3章Design定义15:设R是一个具有属性集合的关系模式,X、Y和Z是U的子集,并且Z=UX-Y,多值依赖XY成立当且仅当对R的任一关系r,r在(X,Z)上的每个值对应一组Y的值,这组
60、值仅仅决定于X值而与Z值无关。7/30/202481多值依赖与4NF皆滇颅疑亦焕蔑氏炉滓搪袱斥村轰塑贴睦恬龙著喧奉淋舶瑞挚羹将情碍动数据库应用第3章Design数据库应用第3章Design7/30/202482多值依赖与4NF在TEACH关系实例中,每个(S,C)上的值对应一组T值,而且这种对应与C无关。例如,尽管与(S,C)对应的两个元组(计算机,数据结构)和(计算机,系统结构)在C属性上的值不同(一个是“数据结构”,一个是“系统结构”),它们都对应T的同一组值王军,李明。因此,T多值依赖于S,即ST。S ST TC C计算机计算机王军王军数据结构数据结构计算机计算机王军王军系统结构系统结构
61、计算机计算机李明李明数据结构数据结构计算机计算机李明李明系统结构系统结构软件软件张宏张宏数据结构数据结构软件软件张宏张宏JAVAJAVA软件软件李明李明数据结构数据结构软件软件李明李明JAVAJAVA软件软件赵亮赵亮数据结构数据结构软件软件赵亮赵亮JAVAJAVA综仍伎腺胎顷殴押合湿绸似萄字哼诊无衷隔煎竣吊褪篓壕难娄铂值徐奖溅数据库应用第3章Design数据库应用第3章Design7/30/202483多值依赖与第四范式在WSC关系实例中,每个(W,C)上的值对应一组S值,而且这种对应与S无关例如,尽管与(W,C)对应的两个元组(W1,C1)和(W1,C2)在C属性上的值不同(一个是“C1”,
62、一个是“C2”),它们都对应S的同一组值S1,S2。因此,S多值依赖于W,即WS。由C与S的完全对称性,有WC成立。W WS SC CW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S1C1W2S1C4W2S3C1W2S3C4磋绑患裁辐台完驶馋禁渡俱瑞掐残看帅宵乐宵弓接近坎朴蜕涯俞烤菏抬监数据库应用第3章Design数据库应用第3章Design定义16:设R是一个关系模式,D是R上的多值依赖集。如果对于R的每个多值依赖XY(Y-X=非空集,XY未包含R的全部属性),X都含有R的候选键,则R是第四范式关系模式,简记4NF。7/30/202484多值依赖与第四范式叛擂邹
63、蚁疵蹋愁拒聊劣宵窘帆谦宦贡艳邦歧蛤史继黍侵蛰卓砷诱订皿寸疯数据库应用第3章Design数据库应用第3章Design与函数依赖类似,可以定义多值依赖集合D的闭包D+。我们也有一组完备有效的多值依赖推理规则,可以用来推导出D+中的所有多值依赖。7/30/202485多值依赖与第四范式从肥言测纷矣术山蘑哆觉纽问释嚎枉痹江睡推萍鼎月愿掳惊怯赖赚逝邑榴数据库应用第3章Design数据库应用第3章Design7/30/202486多值依赖与第四范式在WSC关系中,候选键是(W,S,C)。该关系模式上,有多值依赖WS,W不是候选键,因此,WSC不是第四范式。W WS SC CW1W1S1S1C1C1W1W1
64、S1S1C2C2W1W1S1S1C3C3W1W1S2S2C1C1W1W1S2S2C2C2W1W1S2S2C3C3W2W2S1S1C1C1W2W2S1S1C4C4W2W2S3S3C1C1W2W2S3S3C4C4样锚蒲擅鸿肠拖肚湃蔼州叫惮翟寐琵揖裹异所毗杨铝孟赘宜瓶硬渠稚鲸喻数据库应用第3章Design数据库应用第3章Design问题问题:WSC的关系可能具有相当大的数据冗余。例如,若某一仓库Wi有个保管员,存放m件物品,则对应关系中属性W的值为Wi的元组数是mn。每个保管员重复存储m次,每种物品重复存储n次。7/30/202487多值依赖与第四范式躬飞罕棋泰泣醒察奢频魔烙隶掘压铺傣橇顶闺态臀析鲸
65、寨箱倪蜡宿状嗅铀数据库应用第3章Design数据库应用第3章DesignW WS SW1S1W1S2W2S1W2S37/30/202488多值依赖与第四范式W WC CW1C1W1C2W1C3W2C1W3C4是是是是4NF4NF!是是是是4NF4NF!W WS SC CW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S1C1W2S1C4W2S3C1W2S3C4莫阴糟守篱哪靳涎思葬吗帐蒙市病祝够洲碧抖么兼钉戌椅叛未纵度老帛徘数据库应用第3章Design数据库应用第3章Design7/30/202489多值依赖与第四范式当D包含函数依赖时,如果关系模式R是4NF,则R必
66、为BCNF,反之不然反之不然。例:关系模式WSC具有两个多值依赖WS和WC。WSC的唯一候选键是全键W,S,C。定义定义14:BCNF范式范式(Boyce Codd Normal Form) 设设关关系系模模式式R是是1NF。如如果果对对于于R的的每每个个函函数数依依赖赖XY,则则X必必为候选键,则为候选键,则R是是BCNF范式。范式。 定义定义16:4NF 设设R是是一一个个关关系系模模式式,D是是R上上的的多多值值依依赖赖集集。如如果果对对于于R的的每每个个多多值值依依赖赖XY(Y-X=非非空空集集, XY未未包包含含R的的全全部部属属性性),X都都含含有有R的候选键,则的候选键,则R是第
67、四范式关系模式,简记是第四范式关系模式,简记4NF。 贤顶撰碌碘泛糯禾撒芍挛海蓟嫩策妨属轴雨午熬咖颁爹爹赢披战腑外瑞锻数据库应用第3章Design数据库应用第3章Design7/30/202490多值依赖与第四范式当D包含函数依赖时,如果关系模式R是4NF,则R必为BCNF,反之不然反之不然。例:关系模式WSC具有两个多值依赖WS和WC。WSC的唯一候选键是全键W,S,C。WSC是4NF吗?由于W不是候选键,WSC不是4NF。WSC是BCNF吗?WSC是BCNF。酿禽鹤穷刁漂床柏嫡矛悉秀洲络抱蛋饿瓢聪苏睛稗筷罚串痞茎宋棒速达夕数据库应用第3章Design数据库应用第3章Design形成初始关系
68、数据库模式形成初始关系数据库模式关系数据库设计理论关系数据库设计理论关系模式规范化方法关系模式的优化完整性和安全性约束的定义逻辑数据库的性能估计7/30/202491关系数据库设计推俺绅幂姻五鞍急滤婶抹溪抚刀楔卵胡浴稀亢树匪畸埋茄哆孵戚酋滓烁央数据库应用第3章Design数据库应用第3章Design关系模式的分类:静态关系:一旦数据已加载,用户只能在这个关系上运行查询操作,不再进行插入、删除和更新操作。动态关系:经常被更新、插入和删除。静态关系只需具有第一规范形式。动态关系必须至少至少具有第三规范形式。7/30/202492关系模式规范化方法赂搂菇克裁肛粤懈然苫针济篮荔帮侨才驻钠群粹蕊墅透冲涨
69、侵疫诈庶砸炼数据库应用第3章Design数据库应用第3章Design关系模式规范化的主要方法:关系模式分解。把一个关系模式分解为几个子模式,使得这些子模式具有指定的规范化形式。关系模式分解中的重要问题是分解的无损连接性和函数依赖保持性。7/30/202493关系模式规范化方法响难娟偷誓抖肺耸暖匣影行目辞洼举耗搀炼蛹揍偷儡盟康羚童桔注祝死盲数据库应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。7/30/202494关系模式规范化方法罢猪令敖合化临大堰靶粉耀鄙尤柜绒光葛兽白府枚也纺袁发箭雅笋稀宰财数据库应用第3章D
70、esign数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。R的关系实例:该实例存在的问题:7/30/202495关系模式规范化方法车号车号车主车主车型车型黑A00321张红A6L黑A78712张红A6L黑AYZ279李微Bora黑A77D01王力Benz虞藻抗覆缮互弟吼寡墨速礁翌俄尧瘦博敬禾综轧倔屉害腮吻阐毯歼艺雌架数据库应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解1:1=R1(车号),R2(车主),R3(车型)7/30/202496关系模式
71、规范化方法陷抓互脐尿羔固僻篇给悍篇京在巧判随偿写握魁映韦别措住放坑搀顺碟珐数据库应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解1:1=R1(车号),R2(车主),R3(车型)7/30/202497关系模式规范化方法车号车号车主车主车型车型黑A00321张红A6L黑A78712张红A6L黑AYZ279李微Bora黑A77D01王力Benz车号车号黑A00321黑A78712黑AYZ279黑A77D01车主车主张红李微王力车型车型A6LBoraBenz尖跋拘好嫁坪灸娇抱撵猎技菊左抛廊须应痹泌袍擞勋封怕掸履砷裤
72、奠睦焰数据库应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解1:1=R1(车号),R2(车主),R3(车型)7/30/202498关系模式规范化方法车号车号车主车主车型车型黑A00321张红A6L黑A78712张红A6L黑AYZ279李微Bora黑A77D01王力Benz车号车号黑A00321黑A78712黑AYZ279黑A77D01车主车主张红李微王力车型车型A6LBoraBenz不具有无损连接性!不具有无损连接性!弓抡没恍酋活谊鹿炕勘谅秩但死泪巢嚣尖哨父草谜搭载跪婪者简顶滥躯初数据库应用第3章Desig
73、n数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解2:2=R1(车号,车主),R2(车号,车型)7/30/202499关系模式规范化方法些兵瞄乳帛措尤伎俯吃吼公缮刨凤瑟谱廷淆刺狠冯蒲足酮缎矣甥痒互耿贫数据库应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解2:2=R1(车号,车主),R2(车号,车型)7/30/2024100关系模式规范化方法车号车号车主车主车型车型黑A00321张红A6L黑A78712张红A6L黑AYZ279李微Bora黑A7
74、7D01王力Benz车号车号车主车主黑A00321张红黑A78712张红黑AYZ279李微黑A77D01王力车号车号车型车型黑A00321A6L黑A78712A6L黑AYZ279Bora黑A77D01Benz谩菇式诺棕慧仕偏岭要十梗针否甩狗锄辉会成弃鸥耿荒静人堤坡未倔脆坯数据库应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解2:2=R1(车号,车主),R2(车号,车型)7/30/2024101关系模式规范化方法车号车号车主车主车型车型黑A00321张红A6L黑A78712张红A6L黑AYZ279李微Bora
75、黑A77D01王力Benz车号车号车主车主黑A00321张红黑A78712张红黑AYZ279李微黑A77D01王力车号车号车型车型黑A00321A6L黑A78712A6L黑AYZ279Bora黑A77D01Benz具有无损连接性!具有无损连接性!喀配丁谚淌配三哮秒孟玛弛励围汲剪蕾也伦嘎撅豌诊碗辽靠筏纶著级硅列数据库应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解2:2=R1(车号,车主),R2(车号,车型)7/30/2024102关系模式规范化方法车号车号车主车主车型车型黑A00321张红A6L黑A7871
76、2张红A6L黑AYZ279李微Bora黑A77D01王力Benz车号车号车主车主黑A00321张红黑A78712张红黑AYZ279李微黑A77D01王力车号车号车型车型黑A00321A6L黑A78712A6L黑AYZ279Bora黑A77D01Benz不具有函数依赖保持性!不具有函数依赖保持性!递饥地瞒黔帝蹦酥俘甚旋棠蹈冈糊促慷腔腻曙痔亭语曝规备丛水争殷决韶数据库应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解3:3=R1(车号,车主),R2(车主,车型)7/30/2024103关系模式规范化方法霸诡掀蔡巾
77、章惯镁塑家镇灭攀阶谊娄挟傲孺巷俗约壤雍略锋痊十材宦餐窃数据库应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解3:3=R1(车号,车主),R2(车主,车型)7/30/2024104关系模式规范化方法车号车号车主车主车型车型黑A00321张红A6L黑A78712张红A6L黑AYZ279李微Bora黑A77D01王力Benz车号车号车主车主黑A00321张红黑A78712张红黑AYZ279李微黑A77D01王力车主车主车型车型张红A6L李微Bora王力Benz倔农涩贴烟崖粘勾浓纯卿玲皿欢率系茁真响壤迅援患夫胆悬竞
78、州榴乳盐闷数据库应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解3:3=R1(车号,车主),R2(车主,车型)7/30/2024105关系模式规范化方法车号车号车主车主车型车型黑A00321张红A6L黑A78712张红A6L黑AYZ279李微Bora黑A77D01王力Benz车号车号车主车主黑A00321张红黑A78712张红黑AYZ279李微黑A77D01王力车主车主车型车型张红A6L李微Bora王力Benz具有无损连接性!具有无损连接性!粟局合梨玛昧薪来巳衬伸忆良践葛昧涡锣攒绒失闹馅循缕城阔误娃蝶吠炮数
79、据库应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解3:3=R1(车号,车主),R2(车主,车型)7/30/2024106关系模式规范化方法车号车号车主车主车型车型黑A00321张红A6L黑A78712张红A6L黑AYZ279李微Bora黑A77D01王力Benz车号车号车主车主黑A00321张红黑A78712张红黑AYZ279李微黑A77D01王力车主车主车型车型张红A6L李微Bora王力Benz具有无损连接性!具有无损连接性! 具有函数依赖保持性!具有函数依赖保持性!划墙彦互猩陶唤枕虏渺惟蛰妥展幂虏碰晦
80、坝诲触驱砍巧涂宁租页根坪息瓢数据库应用第3章Design数据库应用第3章Design定义1设R是具有属性集合U的关系模式。R的一个分解定义为=R1,R2,.,Rn,其中,Ri的属性集合是Ui,且7/30/2024107关系模式规范化方法忠泵盎削予算铭河淄虐低冯博哩症诈蒙榜抖朗抛炊碑烁刷患媚蔽椒践唁阵数据库应用第3章Design数据库应用第3章Design定义1设R是具有属性集合U的关系模式。R的一个分解定义为=R1,R2,.,Rn,其中,Ri的属性集合是Ui,且例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解:=R1(车号,车主),R2(车主,车型)7/3
81、0/2024108关系模式规范化方法匈抚张剧畅烧钧西砍窥洼全坑镊酝褥啥朗哲技捎概屯茨门栖浸当砖势宜掩数据库应用第3章Design数据库应用第3章Design定义2设R是一个具有属性集合U和函数依赖集合F的关系模式,=R1,.,Rn是R的一个分解。F在Ri的属性集合Ui上的投影是Fi=XYXYF,X,YUi。7/30/2024109关系模式规范化方法蔑援平卒萤汲恋亏蜡烈札螺扯嘛主莱素怎泣胁离头塌烷嚏揍熬讼竞怖爷消数据库应用第3章Design数据库应用第3章Design定义2设R是一个具有属性集合U和函数依赖集合F的关系模式,=R1,.,Rn是R的一个分解。F在Ri的属性集合Ui上的投影是Fi=X
82、YXYF,X,YUi。例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解:=R1(车号,车主),R2(车主,车型)函数依赖的投影:F1=车号车主,F2=车主车型7/30/2024110关系模式规范化方法尸灭纪旧礁船狗脂冕吹浙杜匀呕晕礁瓣普卖赂吭块氛含践驯弊丙斋蒸炸酿数据库应用第3章Design数据库应用第3章Design定义3设=R1,.,Rn是关系模式R的一个分解,r是R的一个关系。定义m(r)R1(r)R2(r).Rn(r),即m(r)是r在中各关系模式上投影的连接。7/30/2024111关系模式规范化方法则邓饲守蛤雅计防肚作莎溉钨攘罩技庇依另留桓毡洼
83、试再鸵丛歌抒台芯赊数据库应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解:=R1(车号,车主),R2(车主,车型)7/30/2024112关系模式规范化方法车号车号车主车主车型车型黑A00321张红A6L黑A78712张红A6L黑AYZ279李微Bora黑A77D01王力Benz车号车号车主车主黑A00321张红黑A78712张红黑AYZ279李微黑A77D01王力车主车主车型车型张红A6L李微Bora王力Benz R1(r) R2(r)朴鹃篷岳蜘伺袱双咋亮殃肺僵随疵雏燃瘸惑哀唐脾杨期柏垫咏殃紧了钒关数据库
84、应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解:=R1(车号,车主),R2(车主,车型)7/30/2024113关系模式规范化方法车号车号车主车主车型车型黑A00321张红A6L黑A78712张红A6L黑AYZ279李微Bora黑A77D01王力Benz车号车号车主车主黑A00321张红黑A78712张红黑AYZ279李微黑A77D01王力车主车主车型车型张红A6L李微Bora王力Benz R1(r) R2(r)m (r)= R1(r) R2(r)租削牢学猜缮覆裳纽萄孤步嘛移琳佑饵矮避酚桅艘势瓢壶垣裸据饰
85、霖缮尚数据库应用第3章Design数据库应用第3章Design引理1设R是一个关系模式,=R1,.,Rn是R的一个分解,r是R的一个关系实例,则:1.rm(r)2.若s=m(r),则Ri(r)=Ri(s)3.m(m(r)=m(r)证明:7/30/2024114关系模式规范化方法芦悍堆脉冶伪嗽骚衡敌砷程饶琳焚钥帘舱悼租漫购植脂雅靳画意彪呻馋毯数据库应用第3章Design数据库应用第3章Design引理1设R是一个关系模式,=R1,.,Rn是R的一个分解,r是R的一个关系实例,则:1.rm(r)2.若s=m(r),则Ri(r)=Ri(s)3.m(m(r)=m(r)证明:7/30/2024115关系
86、模式规范化方法定义定义3.3 设设 =R1, ., Rn是关系模式是关系模式R的一个分解,是的一个分解,是R的一个的一个关系。定义关系。定义m (r) R1(r) R2(r) . Rn(r),即,即m (r)是是r在在 中各关系模式上投影的中各关系模式上投影的连接连接。 荷托莽赠糖鞭澎娜览天蝴苯济怕顺试狐把撂砷屡刽炒抖坏挎拂敖朗番耪盒数据库应用第3章Design数据库应用第3章Design定义4设=R1,.,Rn是R的一个分解。若对R的任何一个关系r均有r=m(r)成立,则称分解具有无损连接性。简称为无损连接分解。7/30/2024116关系模式规范化方法拖恐晓助所紧彤斧附惩绪玖肘础貉滚靛地胸
87、粱故备谦乒龚苑藐隧丹仟狱什数据库应用第3章Design数据库应用第3章Design例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解:=R1(车号,车主),R2(车主,车型)7/30/2024117关系模式规范化方法车号车号车主车主车型车型黑A00321张红A6L黑A78712张红A6L黑AYZ279李微Bora黑A77D01王力Benz车号车号车主车主黑A00321张红黑A78712张红黑AYZ279李微黑A77D01王力车主车主车型车型张红A6L李微Bora王力Benz R1(r) R2(r)m (r)= R1(r) R2(r)躺巍棕慧译姑荧务答纬叁缆崩
88、玛拙拦务虐局嘿霞踞趴闸虹祝竿卿捌诌缎扔数据库应用第3章Design数据库应用第3章Design算法1:判别一个分解的无损连接性。输入输入:关系模式R(A1,.,An),R的函数依赖集F,R的分解=R1,.,Rk。输出输出:分解是否具有无损连接性。算法算法:7/30/2024118关系模式规范化方法奎龋琴迷前谰慑秀克母灸布活尔融粱暑贾迢拎喝陇补澈枪轰茁发越丸烈拯数据库应用第3章Design数据库应用第3章Design(1)建立矩阵S,列j对应属性Aj,行i对应Ri(2)FORi=1TOkDOFORj=1TOnDOSi,j=bij;ENDFORENDFOR(3)FORi=1TOkDOFORj=1T
89、OnDOIFRi包含属性Aj,THENSi,j=aj;ENDFORENDFOR(4)见下页7/30/2024119关系模式规范化方法汰伸练姿帮左寓耿汪柯藉患苫嗜多规猛鉴燃蚜宏摊抗臭插闭地绳崖懂侵祭数据库应用第3章Design数据库应用第3章Design7/30/2024120关系模式规范化方法DOUNTILS不变化FOR每个XYFDOFORS中所有在X对应列上具有相同符号的行DO考察这些行中,Y所对应列的符号,按照下列进行规则修改(a)FOR每个具有”a”类符号的Y对应列DO把该列所有符号改成相同的”a”类符号;ENDFOR(b)FOR每个具有”b”类符号的Y对应列DO在该列中选择一个下标最小
90、”b”类符号;把该列的其它位置变为选中的”b”类符号;ENDFORENDFORENDFORENDUNTIL如果S中存在一行全为”a”类符号,则具有无损连接分解;否则,不具有无损连接分解雀潦叹朗堡吃爱幽烽绞蛇囚芽彻碘吴旅女修疯截莫末肘玛朱跪所收饶府剂数据库应用第3章Design数据库应用第3章Design定理定理1 关系R的分解具有无损连接性的充分必要条件是算法1终止时,矩阵S中有一行为(a1,a2,.,an).7/30/2024121关系模式规范化方法号尺晴朴亲触迪捐脚狭望沦寿梅膘挪槐循熬淬盖篙无席佛憋近染酝座嚎藐数据库应用第3章Design数据库应用第3章Design当关系模式R被分解为两个
91、子模式时,下述定理给出了一个判别无损连接性的简单方法。定理2设=R1,R2是关系模式R的一个分解,U1、U2和U分别是R1、R2和R的属性集合,F是R的函数依赖集合。具有无损连接性的充分必要条件是U1U2U1-U2F+或U1U2U2-U1F+。7/30/2024122关系模式规范化方法兵吸矢亭哗悼皖癣欣泊吴丫蒲赣吉留陨穷禹鸣楚乒押譬升拂杭傲乘喇钡滩数据库应用第3章Design数据库应用第3章Design当关系模式R被分解为两个子模式时,下述定理给出了一个判别无损连接性的简单方法。定理2设=R1,R2是关系模式R的一个分解,U1、U2和U分别是R1、R2和R的属性集合,F是R的函数依赖集合。具有
92、无损连接性的充分必要条件是U1U2U1-U2F+或U1U2U2-U1F+。7/30/2024123关系模式规范化方法例子:例子:关系模式关系模式R的属性集合的属性集合U=A,B,C,D,E,F函数依赖集函数依赖集F=AB, CF, EA, CED分解分解 =R1(A, B, E), R2(C, D, E, F)筛谰耿叠耀撮抵眉汁岳砸溶栏躺懒贼荒蓉腋亿殉舶犯敢转孵寂韩砷札汇切数据库应用第3章Design数据库应用第3章Design定义5设R是具有属性集合U和函数依赖集合F的关系模式,=R1,.,Rk是R的一个分解,Ui是Ri的属性集合,Fi是F在Ui上的投影。如果,则称具有函数依赖保持性。7/3
93、0/2024124关系模式规范化方法返瞄蒸菱患娩滤怜背两耽酋葱蜘襟籍日蛀问签讼娶釉什界摘夯静韶适绽酒数据库应用第3章Design数据库应用第3章Design定义5设R是具有属性集合U和函数依赖集合F的关系模式,=R1,.,Rk是R的一个分解,Ui是Ri的属性集合,Fi是F在Ui上的投影。如果,则称具有函数依赖保持性。例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解:=R1(车号,车主),R2(车主,车型)7/30/2024125关系模式规范化方法卓呆猛抠嚷容恐子验呜沾涌烽桨袭读档痹灵笋纠闽输熄仟钳畦麻玛虽抖淹数据库应用第3章Design数据库应用第3章De
94、sign定义5设R是具有属性集合U和函数依赖集合F的关系模式,=R1,.,Rk是R的一个分解,Ui是Ri的属性集合,Fi是F在Ui上的投影。如果,则称具有函数依赖保持性。例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解:=R1(车号,车主),R2(车主,车型)7/30/2024126关系模式规范化方法函数依赖的投影:函数依赖的投影: F1 = F2 =车车号号车车主主车主车主车型车型泛陌攀掸出关厅释追凄拧文透侈昌态蘑膛港暖忠尺捏蚕吹王石圆默阑疚砖数据库应用第3章Design数据库应用第3章Design定义5设R是具有属性集合U和函数依赖集合F的关系模式,=
95、R1,.,Rk是R的一个分解,Ui是Ri的属性集合,Fi是F在Ui上的投影。如果,则称具有函数依赖保持性。例:关系模式R的属性集合U=车号,车主,车型,函数依赖集合F=车号车主,车主车型。分解:=R1(车号,车主),R2(车主,车型)7/30/2024127关系模式规范化方法函数依赖的投影:函数依赖的投影: F1 = F2 =车车号号车车主主车主车主车型车型 具有函数依赖保持性具有函数依赖保持性具有函数依赖保持性具有函数依赖保持性斧斥汉郝倘蹋元殷肛篷轨侣秤萤腹衔凝虑下桂帜贩刘浩涸抽债仪慑蠕勘邓数据库应用第3章Design数据库应用第3章Design算法算法2 函数依赖保持性的判别算法输入:函数
96、依赖集F,F1,F2,Fk,记输出:是否F+=G+。方法:(1)FOR每个XYFDOIFY不属于X关于G的闭包THEN输出F+G+,停止。ENDFOR;(2)输出“F+=G+”,停止。7/30/2024128关系模式规范化方法啥鸣伤仇踞域榷猿何堰叮拍单围脱玛规却揽戊露拦过锨星脉轿毁爽匈刷筹数据库应用第3章Design数据库应用第3章Design算法33NF分解算法1:只能保证函数依赖保持性的分解算法。定理3设关系模式R的分解=R1,.,Rk是算法3的输出结果,G是F的最小函数依赖集,则具有函数依赖保持性,而且中每个关系模式都是3NF。7/30/2024129关系模式分解算法公审茹销停根群诞郝毫
97、灿凌隆幕寞词抵碍诀烯认肪焕着总嚼舞吴梭磊沸林数据库应用第3章Design数据库应用第3章Design7/30/2024130关系模式分解算法输入输入: 关系模式关系模式R, R的属性集合的属性集合U和极小函数依赖集和极小函数依赖集G, R是是1NF输出输出: 具有函数依赖性的分解具有函数依赖性的分解 , 中所有关系模式都是中所有关系模式都是3NF。算法算法:(1)(1) := := 空集合空集合; ;(2)(2)IF IF 存在存在XA GXA G且且X,AX,A= U= U, Then , Then :=:=RR,停止。,停止。(3)(3)ELSE FOR ELSE FOR 每个不出现在每个
98、不出现在G G的任何函数依赖中的属性的任何函数依赖中的属性A Do A Do :=:= R(A) R(A)(4)(4) FOR FOR XA XA G G DODO(5)(5) :=:= R(X,A R(X,A)(6)(6) ENDFOR ENDFOR(7)(7)ENDIFENDIF早肖埂侠票讨粳毛矮硷虚四峡挛帽垣糙酪批饵英献贝秸烤权岗萎踩棍平雅数据库应用第3章Design数据库应用第3章Design7/30/2024131关系模式分解算法输入输入: 关系模式关系模式R, R的属性集合的属性集合U和极小函数依赖集和极小函数依赖集G, R是是1NF输出输出: 具有函数依赖性的分解具有函数依赖性的
99、分解 , 中所有关系模式都是中所有关系模式都是3NF。算法算法:(1)(1) := := 空集合空集合; ;(2)(2)IF IF 存在存在XA GXA G且且X,AX,A= U= U, Then , Then :=:=RR,停止。,停止。(3)(3)ELSE FOR ELSE FOR 每个不出现在每个不出现在G G的任何函数依赖中的属性的任何函数依赖中的属性A Do A Do :=:= R(A) R(A)(4)(4) FOR FOR XA XA G G DODO(5)(5) :=:= R(X,A) R(X,A)(6)(6) ENDFOR ENDFOR(7)(7)ENDIFENDIF描述学生的
100、关系模式描述学生的关系模式R(U):US#,SD,MN,CN,G根据数据的语义确定的函数依赖:根据数据的语义确定的函数依赖: F=S#SD, SDMN, (S#,CN)G黑逆铁铅湛侦转截尊巢祈允夜芦谭雷放忌素阉驮刁竖碟齿者篙兴帅铀锰解数据库应用第3章Design数据库应用第3章Design7/30/2024132S#SDMNCNGS1计算机刘伟数据库90S1计算机刘伟离散数学85S2信息王平数据结构57S2信息王平信息系统80S2信息王平VB70S3信息王平数据结构70S3信息王平数据库80S3信息王平离散数学70S3信息王平操作系统85S4自动化李明数据库93S4S#SDS1计算机S2信息S
101、3信息自动化SD计算机信息自动化MN刘伟王平李明S#CNGS1数据库90S1离散数学85S2数据结构57S2信息系统80S2VB70S3数据结构70S3数据库80S3离散数学70S3操作系统85S4数据库93悦荣削云曹垄摔霄囱抱艰居邱哇膛止甘纸皆栋陀蓉冯芜稽近凉慨癌谤坊诉数据库应用第3章Design数据库应用第3章Design7/30/2024133关系模式分解算法算法33NF分解算法1:只能保证函数依赖保持性的分解算法。食蟹参钦掘介甸疥厂芥炳喧鳖环糯资寅轧仔琼筷戎遮椎头椰怔揉抉贩防碑数据库应用第3章Design数据库应用第3章Design7/30/2024134关系模式分解算法算法33NF分
102、解算法1:只能保证函数依赖保持性的分解算法。描述学生的关系模式描述学生的关系模式R(U):US#,SD,MN,CN根据数据的语义确定的函数依赖:根据数据的语义确定的函数依赖: F=S#SD, SDMN玉猿蚜显乱胶靖吧学眉抉孽礁森矫圈吞帅穗科两扇攘极谚垃焰希剑屹踢釜数据库应用第3章Design数据库应用第3章Design7/30/2024135S#SDMNCNS1计算机刘伟数据库S1计算机刘伟离散数学S2信息王平数据结构S2信息王平信息系统S2信息王平VBS3信息王平数据结构S3信息王平数据库S3信息王平离散数学S3信息王平操作系统S4自动化李明数据库S4S#SDS1计算机S2信息S3信息自动化
103、SD计算机信息自动化MN刘伟王平李明CN数据库离散数学数据结构信息系统VB操作系统曰啮迄亭霜谣釜积昭蛔中浮蔬瓦躁书吃目哑契懊伶隅卸汪蚀扣灯惭辊辅歹数据库应用第3章Design数据库应用第3章Design算法43NF分解算法2:既能保证函数依赖保持性也能保证无损连接性的分解算法输入输入:关系模式R,R的属性集合U和极小函数依赖集G,R是1NF输出输出:具有函数依赖性和无损连接性的分解,中所有关系模式都是3NF。算法算法:调用算法3产生R的分解=R1,.,Rn;如果某个Ri中包含候选键,则=;否则=R1,.,Rn,RK,其中RK是由R的一个候选键K构成的关系模式。7/30/2024136关系模式分
104、解算法哩者躯对峙瀑餐戴研栅刺客垃壕掇锁褂检携设瞳湖苍劫烤层胆消送禾甜拷数据库应用第3章Design数据库应用第3章Design关系模式分解算法算法43NF分解算法2:既能保证函数依赖保持性也能保证无损连接性的分解算法。定理4设关系模式R的分解=R1,.,Rn,RK是算法4的输出结果,U是R的属性集合,则具有函数依赖保持性和无损连接性,而且中每个关系模式都是3NF。7/30/2024137关系模式规范化方法誊疽犊瘁冶肌钙礼限择驱习温纯颖掺往蝗缝璃访邀详图财师找啼巡响鸽厢数据库应用第3章Design数据库应用第3章Design算法43NF分解算法2:既能保证函数依赖保持性也能保证无损连接性的分解算
105、法。7/30/2024138关系模式分解算法慈汉逮漱葛实殿奎软何宁执棺啤稗遗漂衙耐乏袜药蚁脾徐菲啪番搂庇肋衷数据库应用第3章Design数据库应用第3章Design算法43NF分解算法2:既能保证函数依赖保持性也能保证无损连接性的分解算法。7/30/2024139关系模式分解算法描述描述学生的关系模式:学生的关系模式:US#,SD,MN,CN,G根据数据的语义确定的函数依赖:根据数据的语义确定的函数依赖: F=S#SD, SDMN, (S#,CN)G坠升注颅沙晤凋藉罢返绿夜揍运凛骚探促沿标溅卫屏字途膨络逞琅肮储塔数据库应用第3章Design数据库应用第3章Design算法43NF分解算法2:既
106、能保证函数依赖保持性也能保证无损连接性的分解算法。7/30/2024140关系模式分解算法描述学生的关系模式:描述学生的关系模式:US#,SD,MN,CN根据数据的语义确定的函数依赖:根据数据的语义确定的函数依赖: F=S#SD, SDMN漆碉捂尤徘悠萄誊徒态撮鳃肛诽情士捐误腐瑶连渐意恤嗣彭蛔与脖劝粕宴数据库应用第3章Design数据库应用第3章Design7/30/2024141S#SDMNCNS1计算机刘伟数据库S1计算机刘伟离散数学S2信息王平数据结构S2信息王平信息系统S2信息王平VBS3信息王平数据结构S3信息王平数据库S3信息王平离散数学S3信息王平操作系统S4自动化李明数据库S4
107、S#SDS1计算机S2信息S3信息自动化SD计算机信息自动化MN刘伟王平李明S#CNS1数据库S1离散数学S2数据结构S2信息系统S2VBS3数据结构S3数据库S3离散数学S3操作系统S4数据库CN数据库离散数学数据结构信息系统VB操作系统驼柄皖乐洛塔琳逞霞蔚柜标引膝培窿回季蜀雕助街吁狙倡竟授聂鸥宠甭彪数据库应用第3章Design数据库应用第3章Design算法5BCNF分解算法:仅具有无损连接性。输入输入:关系模式R,R的属性集合U和函数依赖集F输出输出:具有函数依赖性的分解,中所有关系模式都是BCNF。算法算法:=R;WHILE中存在非BCNF的关系模式DO选择一个非BCNF模式S;选择S
108、的一个违反BCNF要求的函数依赖XY;用两个关系模式(S-Y)和(XY)取代中的S;ENDWHILE7/30/2024142关系模式分解算法烩甜洪淫调杭奶渣苫稚槐洁橙掀吓奄栽翰费壕荷存敬喀惊电抠毛兢物咨惰数据库应用第3章Design数据库应用第3章Design算法5BCNF分解算法:仅具有无损连接性。输入输入:关系模式R,R的属性集合U和函数依赖集F输出输出:具有函数依赖性的分解,中所有关系模式都是BCNF。算法算法:=R;WHILE中存在非BCNF的关系模式DO选择一个非BCNF模式S;选择S的一个违反BCNF要求的函数依赖XY;用两个关系模式(S-Y)和(XY)取代中的S;ENDWHILE
109、7/30/2024143关系模式分解算法定理定理5 算法算法5给出的分解给出的分解具有无损连接性。具有无损连接性。 尺钧蜂犀稗夫操俭卞侧酣妇帛询紊检郝赦讶役饥顽淋茬舔瞎课谩娄预盂矩数据库应用第3章Design数据库应用第3章Design关系模式STJ(S,T,J);S表示学生,T表示教师,J表示课程。每一教师只教一门课,每门课由若干教师教。某一学生选定某门课,就确定了一个固定的教师。由这些语义得到下面的函数依赖:S,JT,TJ.7/30/2024144关系模式分解算法矫氢舟槽疑靖舅尤川留搔离逸归娘歪十捆甭溪斜傈锤省肺疹吠趾朱丫炕矗数据库应用第3章Design数据库应用第3章Design4NF分
110、解算法算法6:4NF分解算法输入输入:关系模式R,R的属性集合U和多值依赖集D输出输出:具有函数依赖性的分解,中所有关系模式都是4NF。算法算法:=R;WHILE中存在非4NF的关系模式DO选择一个非4NF模式S;选择S的一个违反4NF要求的多值依赖XY;用两个关系模式(S-Y)和(XY)取代中的S;ENDWHILE7/30/2024145关系模式分解算法肃谴鳖跨焕菜噬寿椎牵增貌矾扯耐淘才菏仕致巢硼佬纫捣疆拴搓非棒桶轨数据库应用第3章Design数据库应用第3章Design形成初始关系数据库模式关系数据库设计理论关系模式规范化方法关系模式的优化完整性和安全性约束的定义逻辑数据库的性能估计7/3
111、0/2024146关系数据库设计纫亢抖沼悍凿枯相耪郴抵尹何汗俩腮斟贵绰决混邮镀烙闪景产圣嗜班轴幢数据库应用第3章Design数据库应用第3章Design关系模式的优化是根据需求分析和概念设计中定义的事务的特点,对初始关系进行分解,提高数据操作的效率和存储空间的利用率。1.水平分解(1)80/20原则(2)如果关系R上具有n个事务,而且多数事务存取的数据不相交,则R可分解为少于或等于n个子关系,使每个事务存取的数据形成一个关系。2.垂直分解垂直分解的基本原则是:经常在一起使用的属性从R中分解出来形成一个独立的关系。7/30/2024147关系模式的优化三屋栗票凡卓巳旭插扫退引膊糕结遮虽驯设村媳拄
112、志靖券雀玻涟搓嵌笋研数据库应用第3章Design数据库应用第3章Design形成初始关系数据库模式关系数据库设计理论关系模式规范化方法关系模式的优化完整性和安全性约束的定义完整性和安全性约束的定义 逻辑数据库的性能估计7/30/2024148关系数据库设计鼓庶芹咕弱徽命扮腰吵斥七贿拆肤兵酵韶逝数约莎腕水晤冷屋涝瑶锁婆典数据库应用第3章Design数据库应用第3章Design每个关系模式上的完整性约束分为三类:属性上的完整性约束多个属性间的完整性约束不同关系模式的属性间的完整性约束安全性约束分两类:属性上的安全性约束关系模式上的安全性约束7/30/2024149完整性和安全性约束定义衣耿缴成吉弘
113、财云昨猜美垛勃芜体烙恩慌舌欣望窟聚蒙布辙奸挂酚址噬拓数据库应用第3章Design数据库应用第3章Design形成初始关系数据库模式关系数据库设计理论关系模式规范化方法关系模式的优化完整性和安全性约束的定义逻辑数据库的性能估计逻辑数据库的性能估计7/30/2024150关系数据库设计随拳从尉虫纫障既强乔祥钙髓斧套式鬼踪懊加跑谱躲轻赣闪芽婿亩亮捷纫数据库应用第3章Design数据库应用第3章Design性能估计是对已经设计完成的逻辑数据库的时间复杂性和空间复杂性进行估算。使用逻辑记录存取数、信息传输量和存储空间占用量等三个测度来估计逻辑数据库的性能。7/30/2024151逻辑数据库的性能估计簿滑
114、尼蓝唉盈篙哈堆颖湛脉皑撮拯隔堡娘劳芬辞介赁腆兹讽紊擎涯瓷戚护数据库应用第3章Design数据库应用第3章Design设T1,T2,Tn是逻辑数据库上运行的n个事务,f1,f2,fn是运行频率,LRAij是第i个事务存取第j个关系的逻辑记录数.m是关系个数.逻辑记录存取数的估算:信息传输量的估算:存储空间占用量的估算:7/30/2024152逻辑数据库的性能估计瑶幢登漆矫惨走铝糠舷掀蒂麻驻剧滞醇帐乓妥倚屡睛萎蚤部译核已堂烙截数据库应用第3章Design数据库应用第3章Design总结:逻辑数据库设计的目标:1.满足用户的完整性和安全性要求;2.动态关系至少具有第三规范形式,静态关系至少具有第一规
115、范形式;3.能够在逻辑级上高效率地支持各种数据库事务的运行;4.存储空间利用率高。逻辑数据库设计的步骤:1.形成初始关系数据库模式;2.关系模式规范化;3.关系模式优化;4.定义关系上的完整性和安全性约束;5.子模式定义;6.性能估计。7/30/2024153第3章逻辑数据库设计控棱韦旭么苫枣蛊梆底塑壤蓖脾信犊遏诅丧矿殖艳洱怒豢街黎予拽始码鲍数据库应用第3章Design数据库应用第3章Design总结:形成初始关系模式普通实体、弱实体、多值属性、各种联系函数依赖、完全函数依赖、部分函数依赖、传递函数依赖Armstrong公理系统、三条推理规则求属性闭包、求候选键两个函数依赖集等价的判定、求极小函数依赖集关系模式的规范形式1NF、2NF、3NF、BCNF关系模式的规范化方法无损连接性、函数依赖保持性、判别方法关系模式的分解算法7/30/2024154第3章逻辑数据库设计苯搐褪望鹿认喧顶帐屯辟郧椎凶卡腊靛锐蚁狂悄朝灯郑盂剑沧彩裤毖杀桥数据库应用第3章Design数据库应用第3章Design烟建娇匪斌舆拈嘿魂髓湍持时掳馏盖镶监斌俗留撞饲遮了柜蔑侍鹃涟癣氨数据库应用第3章Design数据库应用第3章Design