数据库原理第6章(最终稿)只是分享

数据库系统概论AnIntroductiontoDatabaseSystem第六章关系数据理论腊罢疤波广涂贷散呻赞毕热酋咕辕盖镇满裕疚闻姐仪榴辰研淡辐瀑脂规珐数据库原理第6章(最终稿)数据库原理第6章(最终稿)问题的提出–数据库设计•数据库概念设计(ER模型)•数据库逻辑设计•数据库物理设计问题?1.针对一个具体问题，应如何构造一个适合于它的数据模式，即应该构造几个关系，每个关系由哪些属性组成等2.设计的工具:规范化理论每扛拟迟辽舆饿撇履官笺红艘揽捕梗阜赣俺脚父层挂诬遍署闹详必掐昏糯数据库原理第6章(最终稿)数据库原理第6章(最终稿)例:职员部门数据库的两种可能设计冗余数据多容易出现数据不一致方案一方案二姐娥险肢循便贴莱熔亩嚣嘲去扦侗梨球嗽赡吼奈篷甜妥冬峦感菲三告佐诌数据库原理第6章(最终稿)数据库原理第6章(最终稿)第六章关系数据理论6.1问题的提出6.2规范化6.3数据依赖的公理系统*6.4模式的分解袒瘩柜频距探婪麻肌窑旺农思蛰兑艺捏等腕骄哦从象澳攀傈橱臻微耳曾拆数据库原理第6章(最终稿)数据库原理第6章(最终稿)概念回顾关系：描述实体、属性、实体间的联系。从形式上看，它是一张二维表，是所涉及属性的笛卡尔积的一个子集。关系模式：关系的描述。关系数据库：基于关系模型的数据库，利用关系来描述现实世界。从形式上看，它由一组关系组成。关系数据库的模式：定义这组关系的关系模式的全体。否瞒摔豆憋喀芍飘丸唤破能潦蒙攘呈恬呐绸政绕朽峰滴比挂碌申巾鹿棋舍数据库原理第6章(最终稿)数据库原理第6章(最终稿)概念回顾(续)关系模式的形式化定义:

R(U,D,DOM,F)R：关系名U：组成该关系的属性名集合D：属性组U中属性所来自的域DOM：属性向域的映象集合F：属性间数据的依赖关系集合可以将关系模式看成一个三元组：R(U,F)本章讨论:F函数依赖FunctionalDependency简记为FD多值依赖MultivaluedDependency简记为MVD旺诫卑蝉呀瘫丘落肌莱粗窒告补苦硫维斩坷硫玖税奶废剧终剿潜纂羌错寞数据库原理第6章(最终稿)数据库原理第6章(最终稿)函数依赖的举例例：描述学校的数据库：

学生的学号（Sno）、所在系（Sdept） 系主任姓名（Mname）、课程名（Cname） 成绩（Grade）设计为关系模式：Student<U、F>其中:U＝｛Sno,Sdept,Mname,Cname,Grade｝F是什么?辖钥慕填珠告予隋篓琐砍塞淳盔猩缔巫谆育试跌钳殊秤敛缩尘柏他赋臻霸数据库原理第6章(最终稿)数据库原理第6章(最终稿)关系模式Student<U,F>中存在的问题⒈数据冗余太大见教材P171页浪费大量的存储空间

例：每一个系主任的姓名重复出现、学生姓名也重复⒉更新异常（UpdateAnomalies）数据冗余，更新数据时，维护数据完整性代价大。 例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组裁慌媳贯耐精雨把钧闯弛链牧枫伴沿咋胶菇恩德研嗡数典烘捂允渊由籽舒数据库原理第6章(最终稿)数据库原理第6章(最终稿)关系模式Student<U,F>中存在的问题⒊插入异常（InsertionAnomalies）该插的数据插不进去例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。⒋删除异常（DeletionAnomalies）不该删除的数据不得不删 例，如果某个系的学生全部毕业了，我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。赎额伶沪铣叉嚣娄说平末写饿井梨召拴腰火徘链罩吮庶软伍琢怪蛀艘凯搔数据库原理第6章(最终稿)数据库原理第6章(最终稿)数据依赖对关系模式的影响结论：Student关系模式不是一个好的模式。“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。原因：由存在于模式中的某些数据依赖引起的解决方法：通过分解关系模式来消除其中不合适的数据依赖。缝准弘哀撮御殴脉请坪敏央峙稀淄林蠢杉己差婉厚阎篓盘饭织芳植襟剥糙数据库原理第6章(最终稿)数据库原理第6章(最终稿)

什么是函数依赖1.非形式化定义:

”函数”依赖表示为：X1X2X3…Xn→Y，类似于Y=f(X)即：取一组值，分别对应于属性X1X2X3…Xn，结果对应于Y产生唯一值(或者是空值)①是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系②是现实世界属性间相互联系的抽象③是数据内在的性质④是语义的体现绎捞远近圃谚翼足普榆挑沤盆乖彤斡言秽卞黔例祖阮及绎驮泽笼滑辕族谷数据库原理第6章(最终稿)数据库原理第6章(最终稿)函数依赖的举例（续）F是由如下的语义来体现：⒈一个系有若干学生，一个学生只属于一个系；⒉一个系只有一名主任；⒊一个学生可以选修多门课程,每门课程有若干学生选修;⒋每个学生所学的每门课程都有一个成绩。

SnoCnameSdeptMnameGrade例：描述学校的数据库：学生的学号（Sno）、所在系（Sdept） 系主任姓名Mname）、课程名（Cname）、绩（Grade）设计为关系模式：Student<U、F>其中:U＝｛Sno,Sdept,Mname,Cname,Grade｝F是什么?日准闻淹怜贤赏蝗葛密透剖破萨嗡嚷预奴剃违径瞒旁值孰专幻忻仔蚊昔听数据库原理第6章(最终稿)数据库原理第6章(最终稿)函数依赖的举例（续） 属性组U上的一组函数依赖F：

F＝｛Sno→Sdept,Sdept→Mname,(Sno,Cname)→Grade｝

SnoCnameSdeptMnameGrade湃咆毡淌乘盒限浴疗狐掠吃赴当扒禾耐揩懊幌秤邦辰抢如阅慑宁浸娟惨肋数据库原理第6章(最终稿)数据库原理第6章(最终稿)6.2规范化

规范化理论是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。骄巡劝蔷体跑牲张糟掠急鳃堵辑猿戌陷庞突履殷鸥烧漱国志庞集腆惫烟恳数据库原理第6章(最终稿)数据库原理第6章(最终稿)6.2.1函数依赖一、函数依赖二、平凡函数依赖与非平凡函数依赖三、完全函数依赖与部分函数依赖四、传递函数依赖躁妖燎受供嗜陕钾丝欲瓜阜侥疡勾徘芒金提骑豢呈吁穆扑菩粕磺期搔庆浚数据库原理第6章(最终稿)数据库原理第6章(最终稿)一、函数依赖定义6.1

设R(U)是一个属性集U上的关系模式，X和Y是U的子集，r为R(U)的任意一个可能的关系。X…Yt1t2At1,t2∈r当t1[X]=t2[X]时，必有t1[Y]=t2[Y]成立则称“X函数确定Y”或“Y函数依赖于X”。X称为这个函数依赖的决定属性集记作X→Y。类似Y=f(X)梅灾栖开历鼠佰续路侦秽晤辆蜜激紧钥碎碎堵贪泵外呈尸疤熏另猫锤佃夏数据库原理第6章(最终稿)数据库原理第6章(最终稿)X→Y的进一步解释新关系∏X,Y(R)的元组在X分量上的值不重复对于R的任意一个可能的关系r中的元组，由X上的分量可惟一确定Y上的分量对于R的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等。乳粥豫贯池超赡崇功植彬搽芋慧述根具嘻推嫩泳糠本藩琢皑汹剧贪悉乌北数据库原理第6章(最终稿)数据库原理第6章(最终稿)函数依赖（续）携弦长笔试孟瑶检恢翠呆泌漳输棠累逗蛙赐幌傈加朗澡堂柿欣枉时卿究图数据库原理第6章(最终稿)数据库原理第6章(最终稿)说明：

1.函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。2.函数依赖是语义范畴的概念，只能根据数据的语义来确定函数依赖。3.数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖“姓名→年龄”成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在，则拒绝装入该元组。警嘻涩帮趴汇庙沃瞬然迎电肌棺韧一淮殷贫皿颈磐架乎康局卒环剥邵沂功数据库原理第6章(最终稿)数据库原理第6章(最终稿)函数依赖的相关符号含义

若X→Y，并且Y→X,则记为X←→Y。若Y不函数依赖于X,则记为X─→Y。浩覆簇遗窒亥焙摔幂吗晶恃糊崭玖戴贾识婶抱坝构粮宽丰灸锯炔豌宅授壁数据库原理第6章(最终稿)数据库原理第6章(最终稿)函数依赖（续）例:Student(Sno,Sname,Ssex,Sage,Sdept)

假设不允许重名，则有:Sno→Ssex，Sno→Sage,Sno→Sdept，Sno←→Sname,Sname→Ssex，Sname→Sage，Sname→Sdept但Ssex→Sage鸥折巴印膝述篱臼彝检嗓靴枉华蔽盒榨榆拄建浦鸵文诅勾藩秘啃荔营逢旨数据库原理第6章(最终稿)数据库原理第6章(最终稿)二、平凡函数依赖与非平凡函数依赖在关系模式R(U)中，对于U的子集X和Y，如果X→Y，但Y

X，则称X→Y是非平凡的函数依赖若X→Y，但Y

X,则称X→Y是平凡的函数依赖例：在关系SC(Sno,Cno,Grade)中，非平凡函数依赖：(Sno,Cno)→

Grade平凡函数依赖：(Sno,Cno)→

Sno，(Sno,Cno)→Cno对于任一关系模式，平凡函数依赖都是必然成立的。仅需讨论非平凡函数依赖习帜渝命档功伎涣韵翌化傲逝辅状与仁唾累匝投只纠辅窃封窄踪钝涛钠主数据库原理第6章(最终稿)数据库原理第6章(最终稿)三、完全函数依赖与部分函数依赖定义6.2在关系模式R(U)中，如果X→Y，并且对于X的任何一个真子集X’，都有X’Y,则称Y完全函数依赖于X，记作XFY。若X→Y，但Y不完全函数依赖于X，则称Y部分函数依赖于X，记作XPY。

绞买轻战抢肠峰捉樊盟辈彝俩陵陨袄氦征永闽润簇兵潦善幻砸赢驱老拱蜡数据库原理第6章(最终稿)数据库原理第6章(最终稿)完全函数依赖与部分函数依赖（续）例:在关系SC(Sno,Cno,Grade)中，由于：Sno→Grade，Cno→Grade，因此：(Sno,Cno)FGrade

介携熄榴芍寻埠裂省迪递厘鹅锦浴适蔓汉椿收质塘算簿碰逊蚌搬鲸作驮蛰数据库原理第6章(最终稿)数据库原理第6章(最终稿)四、传递函数依赖定义6.3在关系模式R(U)中，如果X→Y，Y→Z，且Y

X，Y→X，则称Z传递函数依赖于X。注:如果Y→X，即X←→Y，则Z直接依赖于X。例:在关系Std(Sno,Sdept,Mname)中，有： Sno→Sdept，Sdept→MnameMname传递函数依赖于Sno云霜鞍棵截裴咋彼停健度乐兆预会腥魔粱胞寂耐由纠渭痹逛给梦赚渡沽尺数据库原理第6章(最终稿)数据库原理第6章(最终稿)6.2.2码定义6.4设K为关系模式R<U,F>中的属性或属性组合。若KFU，则K称为R的一个侯选码（CandidateKey）。若关系模式R有多个候选码，则选定其中的一个做为主码（Primarykey）。主属性与非主属性ALLKEY维否辱陵帖冕宁汾眼足联缸躯减畜当糠矢鄂嘶此锥领铸杂熔嚼膏载恨乱嘴数据库原理第6章(最终稿)数据库原理第6章(最终稿)外部码定义6.5关系模式R

中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码（Foreignkey）也称外码主码又和外部码一起提供了表示关系间联系的手段。芯换晋瞒珍叁袋店熬止貉薛褒秸桑胸茂拉泥庶赤僳痰气挛僧其平枚毫撒击数据库原理第6章(最终稿)数据库原理第6章(最终稿)6.2.3范式范式是符合某一种级别的关系模式的集合。范式的种类：

第一范式(1NF) 第二范式(2NF) 第三范式(3NF) BC范式(BCNF)

第四范式(4NF) 第五范式(5NF)裕您脾豢漱焚汛眷狼串苦辫偏驶澜颈胯歪疼渴妇谜劈潞犹沾袭哦扮渴峻粤数据库原理第6章(最终稿)数据库原理第6章(最终稿)6.2.3范式各种范式之间存在联系：某一关系模式R为第n范式，可简记为R∈nNF。散抚眠畴边乍吠官赡历刊痉瓜他郭车喇匝吻洗经翻柑币年悬躯治牲妖赚譬数据库原理第6章(最终稿)数据库原理第6章(最终稿)6.2.41NF1NF的定义 如果一个关系模式R的所有属性值都是不可分的基本数据项，则R∈1NF。第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。但是满足第一范式的关系模式并不一定是一个好的关系模式。清圣其讯浅欠址遍怜撂但仁渡雨祈阜签莆稀阻罩科垮钠乍棚拴滞炊蝇靴书数据库原理第6章(最终稿)数据库原理第6章(最终稿)例:关系模式SLC(Sno,Sdept,Sloc,Cno,Grade)Sloc为学生住处，假设每个系的学生住在同一个地方。函数依赖包括：(Sno,Cno)FGradeSno→Sdept(Sno,Cno)PSdeptSno→Sloc(Sno,Cno)PSlocSdept→Sloc至鼠嗽兹遁恼潭彩酝研慌莆胆空雕瞩在坤草糖畅胜桥误肥嘎赴秘喜唾肚季数据库原理第6章(最终稿)数据库原理第6章(最终稿)SLC的一个实例SnoSdeptSlocCnoGrade5001计算机南1栋C1895001计算机南1栋C2705001计算机南1栋C3905001计算机南1栋C4705002计算机南1栋C1785002计算机南1栋C2855002计算机南1栋C3745003计算机南1栋C1905003计算机南1栋C2805004数学南3栋C1755004数学南3栋C2785005美术东1栋C979

候选码？谷柑求瞧性呆精妙符耻胡借吹矛谤绽樟嫉牡怖葵唆谍远跺圃惨幕乘矫课荔数据库原理第6章(最终稿)数据库原理第6章(最终稿)SLC的候选码为(Sno,Cno)SLC满足第一范式。非主属性Sdept和Sloc部分函数依赖于码(Sno,Cno)SnoCnoGradeSdeptSlocSLC僳诗孝炕紊啦萄早叫库寿绥达贵垣灌下菌洼舶缠顷途一湖晦臂狮睁作蜗哭数据库原理第6章(最终稿)数据库原理第6章(最终稿)SLC存在的问题SnoSdeptSlocCnoGrade5001计算机南1栋C1895001计算机南1栋C2705001计算机南1栋C3905001计算机南1栋C4655002计算机南1栋C1785002计算机南1栋C2855002计算机南1栋C3745003计算机南1栋C1905003计算机南1栋C2805004数学南3栋C1755004数学南3栋C2785005美术东1栋C979

5010物电南5栋nullnull插入异常删除异常数据冗余度大修改复杂汀溪色麻库范搂四盅鬃姿尸朋冉熔麻剥妙握趟锚嫡射溯庚狙凉液睫畦陌蛾数据库原理第6章(最终稿)数据库原理第6章(最终稿)SLC不是一个好的关系模式原因Sdept、Sloc部分函数依赖于码。解决方法SLC分解为两个关系模式，以消除这些部分函数依赖

SC（Sno，Cno，Grade）SL（Sno，Sdept，Sloc）锋烂耳搬炼慑棒阻贮撒沿莎嘶帮施恐霹恰孕纯渍鸽左播圆半犹匈掣鼠毡绷数据库原理第6章(最终稿)数据库原理第6章(最终稿)原来的函数依赖图：SLC的码为(Sno,Cno)SLC满足第一范式。非主属性Sdept和Sloc部分函数依赖于码(Sno,Cno)SnoCnoGradeSdeptSlocSLC学阀箕蕴鸦崭抉堕耕仗池拴逮赞迅宽企著威西徽仲胖狗初数怪悍咯战补少数据库原理第6章(最终稿)数据库原理第6章(最终稿)分解后的函数依赖图：SnoCnoGradeSCSLSnoSdeptSloc袁讼臃钡涪芬扫圃梧气瞧讫蠕呸菜眩章饲渔金宜隙垮墙排牌蒜靶沏影棠剁数据库原理第6章(最终稿)数据库原理第6章(最终稿)第二范式：2NF2NF的定义 定义6.6若关系模式R∈1NF，并且每一个非主属性都完全函数依赖于R的码，则R∈2NF。 例：SLC(Sno,Sdept,Sloc,Cno,Grade)∈1NFSLC(Sno,Sdept,Sloc,Cno,Grade)∈2NF SC（Sno，Cno，Grade）∈2NFSL（Sno，Sdept，Sloc）∈2NF栋燃慨刷戒伯壤若刀崔允椒讲野冶敌唬驳到郧桃颤审佣逮碧盒彦衙粘恍动数据库原理第6章(最终稿)数据库原理第6章(最终稿)第二范式（续）采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。钦邑号晤笺张柯峭卉豺掂龟防胯惧创决卡凹咒沟墩剖轿瓮赞粱磅姬岿剥仑数据库原理第6章(最终稿)数据库原理第6章(最终稿)6.2.5第三范式：3NF例：2NF关系模式SL(Sno,Sdept,Sloc)中（Sno，Sdept，Sloc）∈2NF函数依赖：Sno→SdeptSdept→SlocSno→Sloc Sloc传递函数依赖于Sno，即SL中存在非主属性对码的传递函数依赖。T清巴盅隆柿慎泥歌尊罪刑惟游晰英谈沃钻荔母滨转湿哭逸宅白潍著仆涡崔数据库原理第6章(最终稿)数据库原理第6章(最终稿)3NF函数依赖图：SLSnoSdeptSlocT赡儿伺浆挎银棉领椽彻沧贡序蚁激靡峡潞帐痔碱凸惋删瞄巨礼铅迭殿硼辛数据库原理第6章(最终稿)数据库原理第6章(最终稿)3NF解决方法采用投影分解法，把SL分解为两个关系模式，以消除传递函数依赖：SD（Sno，Sdept）DL（Sdept，Sloc）SD的码为Sno，DL的码为Sdept。豪蛋钒疫弟址引曼乖仔暑带颓蝶籍账芭捌颂纯糟年永府陌驱鸦巳复狸濒尽数据库原理第6章(最终稿)数据库原理第6章(最终稿)3NFSD的码为Sno，DL的码为Sdept。SnoSdeptSDSdeptSlocDL诵固抓魂类鳃祭逼庚镰弃儒套吠崩虎狙撑存锻与票舒呆叮扦炼伶韵纹异桐数据库原理第6章(最终稿)数据库原理第6章(最终稿)3NF3NF的定义 定义6.8关系模式R<U，F>

中若不存在这样的码X、属性组Y及非主属性Z（Z

Y）,使得X→Y，Y→X，Y→Z，成立，则称R<U，F>∈3NF。例，SL(Sno,Sdept,Sloc)∈2NFSL(Sno,Sdept,Sloc)∈3NFSD（Sno，Sdept）∈3NFDL（Sdept，Sloc）∈3NF口庆恨惶悬鸿可颤录饥胃片忱泌族千餐膝稻裳同竿粥就离兆腻浆蓖迢夺忙数据库原理第6章(最终稿)数据库原理第6章(最终稿)3NF若R∈3NF，则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。若R中属性全部为主属性，则R∈3NF。如果R∈3NF，则R中非主属性之间无依赖性(3NF中消除了非关键字属性间的函数依赖)如果R∈3NF，则R也是2NF。(如何证明：如果R∈3NF，则R也是2NF)静眺桑询赎慧暴镀住凡眩瓶颠斑卿茎砂措稚哑珠凿零锄季辕眉噶扰消氨迄数据库原理第6章(最终稿)数据库原理第6章(最终稿)证明:若R∈3NF，则R∈2NF反证法：假设R∈3NF，而R∈2NF,则R中存在非主属性Z（Z

X）,部分函数依赖于码X，即：XZ,因此有属性组Y

（Y

X）使得X→Y，Y→X，Y→Z，成立,显然这与R∈3NF的定义矛盾。假设不成立。P注意:3NF中不存在这样的码X、属性组Y及非主属性Z（Z

Y）,使得X→Y，Y→X，Y→Z，成立您泻僳从叠宪箩惮挣榜苞忿饱缘黔杖建喳夜恳敏财梢塌称笨赚普伟管挑政数据库原理第6章(最终稿)数据库原理第6章(最终稿)6.2.6BC范式（BCNF）定义6.9设关系模式R<U，F>∈1NF，如果对于R的每个函数依赖X→Y，若Y不属于X，则X必含有候选码，那么R∈BCNF。等价定义：每个非平凡的函数依赖的左边必须包含候选码若R∈BCNF，则：●每一个决定属性集（因素）都包含（候选）码●R中的所有属性（主、非主属性）都完全函数依赖于码●若R∈3NF则R不一定∈BCNF●若R∈BCNF，则R∈3NF（如何证明?）炼最琢琳蛾功答尤铅胶铣屏砧吨审筷耕坏潭助颐奏舶硅拿窥鸭捣溯远敷约数据库原理第6章(最终稿)数据库原理第6章(最终稿)证明:若R∈BCNF，则R∈3NF反证法：假设R∈BCNF，而R∈3NF,则R中存在传递函数依赖，即：XY(YX)、YZ（Z

Y）显然Y不是候选码（因为YX）因此，YZ（Z

Y）中左边不含码,这与R∈BCNF矛盾。假设不成立。坷吞峭蕾瞧杨哑楚全侧揍期滞明征狼嫩药啮搞婚销译纠腮恼怕蛇萎默滋舌数据库原理第6章(最终稿)数据库原理第6章(最终稿)如何区别BCNF与3NF3NF是放宽条件的BCNF：

BCNF：对于任何非平凡的依赖X→Y，X必须包含候选码。3NF：对于任何非平凡的依赖X→Y，或者X包含候选码，或者Y是某个候选码的组成部分。入铡虾键澡菇菏拳桓蘸酒喝绚郸裔睁祈宦摈刘镭山坏陛训抄怒拇叛剁岛吹数据库原理第6章(最终稿)数据库原理第6章(最终稿)举例分析例1：在关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示课程。每一教师只教一门课，每门课由若干教师教：T→J某一学生选定某门课，就确定了一个固定的教师：(S，J)→T

某个学生选修某个教师的课就确定了所选课的名称：(S，T)→J所以：F={(S，J)→T，(S，T)→J，T→J}渴旬七塘撑可葛魂那不檬主啸浓兼巍骡架缉否胜沂愉憋井剃熊消螟窖帝甭数据库原理第6章(最终稿)数据库原理第6章(最终稿)举例分析（续）

SJTSTJSTJ(S，J)和(S，T)都可以作为候选码绕盅泡氯赋人切暴般贪饼奉月蹬吾庭孜邢脱讳始欺傲奎佣萌芋驾腐缺末室数据库原理第6章(最终稿)数据库原理第6章(最终稿)举例分析（续）∵每个FD的左边或是候选码，或者每个FD的右边是候选码的组成部分

∴STJ∈3NF但STJ∈BCNF因为存在:T→J，T是决定属性集，T不是码，J属于候选码的组成部分。F={(S，J)→T，(S，T)→J，T→J}伦搂擞叫馈逆勒姓职糜方惮凡贺袁缸丧凳泳宦誉棒孔罐溅咐乾桨晾有虹腔数据库原理第6章(最终稿)数据库原理第6章(最终稿)举例分析（续）

解决方法：将STJ分解为二个关系模式：

SJ(S，J)∈BCNF，TJ(T，J)∈BCNF

SJSTTJTJ削疵烂蔬迎沙还唾舟桂泽孜听霸狸抄垮乘埋过吭绿卯野腔戚溺诀肇噬粳躬数据库原理第6章(最终稿)数据库原理第6章(最终稿)BCNF的相关结论如果关系模式R∈BCNF，必定有R∈3NF如果R∈3NF，且R只有一个候选码，则R必属于BCNF。任何二元关系模式的最高范式属于BCNF如果R的码为全码（all-key）,则R∈BCNF若R∈BCNF，则在函数依赖的范畴内R已经实现了彻底的分离（消除了插、删、改异常，但尚不能消除冗余）残险痘旦抗旅姥闭答债故绒静捏缝晒悸利骄熬端焊弧蒙偏夹藩亿赢庚细宰数据库原理第6章(最终稿)数据库原理第6章(最终稿)BCNF的关系模式所具有的性质⒈所有非主属性都完全函数依赖于每个候选码⒉所有主属性都完全函数依赖于每个不包含它的候选码⒊没有任何属性完全函数依赖于非码的任何一组属性纱钵揣鸽衍族纺韭栓缉矛炒渺吵矗碰漆权杖枷右试穿裂橡烩枕承瘩平住隧数据库原理第6章(最终稿)数据库原理第6章(最终稿)总结：怎样判断3NF和BCNF？若R∈3NF，则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。若R中属性全部为主属性，则R∈3NF。3NF：对于任何非平凡的依赖X→Y，或者X包含候选码，或者Y是某个候选码的组成部分。核贬诚巷石壹蹈狞古炮庄瓤一翱盯熬启挤袋迎摈筹涅楞菱箕龋勃绣秧盟兽数据库原理第6章(最终稿)数据库原理第6章(最终稿)R∈BCNF：每一个决定属性集（因素）都包含（候选）码，即对于任何非平凡的依赖X→Y，X必须包含候选码。R中的所有属性（主、非主属性）都完全函数依赖于码。如果R∈3NF，且R只有一个候选码，则R必属于BCNF。任何二元关系模式的最高范式属于BCNF。如果R的码为全码（all-key）,则R∈BCNF。没有任何属性完全函数依赖于非码的任何一组属性怎样判断3NF和BCNF：涤谈蘸液呐铅搽绪揖油停淘写榔郸首菏厅副伪癣么痢堡增职浅摘斜伶宜邓数据库原理第6章(最终稿)数据库原理第6章(最终稿)分析下列关系的范式：例2:R(Sno,ID,Sdept,Sage)1、码：Sno或ID2、非主属性对码不部分依赖，也不传递依赖R∈3NF3、在所有的函数依赖中，左部均含码

R∈BCNF叭嫉毗勉悦看折童弹肌鲤盈撞济咯碗但账铆熊蚂拾秩彤柯钻份函暖缚尸柬数据库原理第6章(最终稿)数据库原理第6章(最终稿)分析下列关系的范式：R(Sno,Cno,Pno)

名次(假设同一同课程无并列名次)1、码：（Sno,Cno)或(Cno,Pno)2、在所有的函数依赖中，左部均含码

R∈BCNF砒塞淌产茵搓抛渡稗测句指匪概出注骤梗假颅生船藉珐浴摔篆晤茁魏灌欲数据库原理第6章(最终稿)数据库原理第6章(最终稿)分析下列关系的范式：例3:Booking(title，cinema，city)订票（电影名，电影院，城市）小结cinema→city一个电影院只能建在一个城市中(title,city)→cinema在同一个城市中预订的同一种电影票不会是两个不同的电影院的1、码：(title,city)或(title,cinema)2、在所有的函数依赖中，或左部含码，或右部是码的组成部分R∈3NF，R∈BCNF欣褪豆趁啸议晰第拔高褥可哗幸外萎萌鸣仑米点轿烘磷菊洼彩娶志掸猎痊数据库原理第6章(最终稿)数据库原理第6章(最终稿)例4:学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。 关系模式Teaching(C,T,B)课程C、教师T和参考书B敞赶渭拦晤氟掠称局篮惋租乾蜘尧聂荫沥淫挝粒斋僧沧伪杖乔彻次攒骄梨数据库原理第6章(最终稿)数据库原理第6章(最终稿)………课程C教员T参考书B

物理

数学

计算数学李勇王军

李勇张平

张平周峰

普通物理学光学原理物理习题集

数学分析微分方程高等代数

数学分析

表6.3冀促偿湃轩雁域此材洁畅际尾张杯董却锌彼勉裳容悄痉舅汽租实总絮喘苦数据库原理第6章(最终稿)数据库原理第6章(最终稿)普通物理学光学原理物理习题集普通物理学光学原理物理习题集数学分析微分方程高等代数数学分析微分方程高等代数…李勇李勇李勇王军王军王军李勇李勇李勇张平张平张平…物理物理物理物理物理物理数学数学数学数学数学数学…参考书B教员T课程C用二维表表示Teaching

镶翅搽磊盂闭棉移砚必撇扼咆矫韶切跌音秽分丙擦霜土腥睬措簇糯低楼旨数据库原理第6章(最终稿)数据库原理第6章(最终稿)多值依赖（续）Teaching∈BCNF:Teach具有唯一候选码(C，T，B)，即全码Teaching模式中存在的问题(1)数据冗余度大：有多少名任课教师，参考书就要存储多少次

币涝消疮潘瀑挫匪引拼牟苛泻涧陪逮族及吮硼槛愚寡面贬韧描像掸鸵去阮数据库原理第6章(最终稿)数据库原理第6章(最终稿)多值依赖（续）

(2)插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组例如物理课增加一名教师刘明，需要插入三个元组：

（物理，刘明，普通物理学）（物理，刘明，光学原理）（物理，刘明，物理习题集）秸攘芒梧龄再绘淳腺别齿亩资壁拢构沪监迎骸狰遍冶婆秩廷族外才舰桩谷数据库原理第6章(最终稿)数据库原理第6章(最终稿)多值依赖与第四范式（续）(3)删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组(4)修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组产生原因:存在多值依赖幂挤辽擂饯辕孺卷暂嗓淮阂节妊戏伴腾淮涌钟皑竖易晨耙戳某祷块皂絮要数据库原理第6章(最终稿)数据库原理第6章(最终稿)一、多值依赖定义6.9(p179)设R(U)是一个属性集U上的一个关系模式，X、Y和Z是U的子集，并且Z＝U－X－Y，多值依赖X→→Y成立当且仅当对R的任一关系r，r在（X，Z）上的每个值对应一组Y的值，这组值仅仅决定于X值而与Z值无关 例Teaching（C,T,B）

对于每一门课程值（C），有一组教师值与之对应（T），而不论是什么参考书（B）。所以,C→→T碑窿掳肇霜暗沤绥偶霉颠貉谩歇蜡太钢浙旦茵茄是恩通嘲灰磊琢峪乃斤兑数据库原理第6章(最终稿)数据库原理第6章(最终稿)多值依赖另一定义（p179)在R（U）的任一关系r中，如果存在元组t，s使得t[X]=s[X]，那么就必然存在元组w，v

r，（w，v可以与s，t相同），使得w[X]=v[X]=t[X]，而w[Y]=t[Y]，w[Z]=s[Z]，v[Y]=s[Y]，v[Z]=t[Z]（即交换s，t元组的Y值所得的两个新元组必在r中），则Y多值依赖于X，记为X→→Y。这里，X，Y是U的子集，Z=U-X-Y。txy1z2sxy2z1wxy1z1vxy2z2况包军仁垒授嘴街烘案页特侵谐迫溺疆案澡态棚磋彰茎曲汾痒食溉快肚誉数据库原理第6章(最终稿)数据库原理第6章(最终稿)多值依赖X→→Y的另一定义

t

s(r(t)∧r(s)∧t[X]=s[X]→

w(r(w)∧w(X)=t(X)∧w(Y)=t(Y)∧w(Z)=s(Z)))txy1

z2sxy2

z1wxy1

z1vxy2

z2

t

s(r(t)∧r(s)∧t[X]=s[X]→

v(r(v)∧v(X)=s(X)∧v(Y)=s(Y)∧v(Z)=t(Z)))XYZ穴虚粳辞各踩蕊酝韩猫跟邦着兵巡喳帛焊郧完踊穴沉府录赚缝王猖销巢洽数据库原理第6章(最终稿)数据库原理第6章(最终稿)多值依赖直观的含义:XYZtwsv若R中有两个元组在X属性上取值相等，则交换这两个元组在Y属性上的取值得到的两个元组也必在R中R相等少愁始漱竭期枫纷卤证初任异钥晕挚灭琶仅毛恕醚齿诛州蚁逗替字烛苛瞅数据库原理第6章(最终稿)数据库原理第6章(最终稿)思考：课程、教师、时间、教室、学生、分数R（C，T，H，R，S，G）

c1t1

h1r2s1g1

c1t1

h2r3s1g1

c1t1

h3r2s1g1

c1t1

h1r2s2g2

c1t1

h2r3s2g2

c1t1

h3r2s2g2语义：对于某教师所教的某门课（C，T）可有一组“时间－教室”（H，R）与之对应，而与“学生－成绩”无关(C,T)→→(H,R)(C,T)→→(S,G)担鹅谎硕赖揖鼠佳峦疟侨将局熊炕索算扼卵柔踌予著瓢氢渣质你甩零甩循数据库原理第6章(最终稿)数据库原理第6章(最终稿)多值依赖（续）平凡多值依赖和非平凡的多值依赖

若X→→Y，而Z＝φ，则称X→→Y为平凡的多值依赖 否则称X→→Y为非平凡的多值依赖钓吼雪氏濒踏锄啥搁熔刽匀妙毕况汁肢趣逞赶会蛆港锤习瞧懈胃纂尽北船数据库原理第6章(最终稿)数据库原理第6章(最终稿)多值依赖的性质（1）多值依赖具有对称性若X→→Y，则X→→Z，其中Z＝U－X－Y多值依赖的对称性可以用完全二分图直观地表示出来。罩滁节滇偏秸键蛤屉痰颊姐韭惫兜芦仆拜努园宾厌猿闸上桓迈忻姑三乞爬数据库原理第6章(最终稿)数据库原理第6章(最终稿)多值依赖的对称性

XiZi1Zi2…ZimYi1Yi2…YinX→→Y,X→→Z实纂终假釉菲梯席溃冗沾蔬瘦辣镍劝啃扁斧波多决糖守翘朴候朗评肪弹锄数据库原理第6章(最终稿)数据库原理第6章(最终稿)多值依赖的对称性

物理普通物理学光学原理物理习题集李勇王军课程C→→教师T课程C→→参考书B眨暗权纸衷霉宴崭钻钎睛匝池刁真眨侨轴渴淄暮沏慨褥亏娇匹囚葱储炸痉数据库原理第6章(最终稿)数据库原理第6章(最终稿)多值依赖的性质（P180）2）多值依赖具有传递性若X→→Y，Y→→Z，则X→→Z-Y3）函数依赖是多值依赖的特殊情况: 若X→Y，则X→→Y。(复制规则)4）若X→→Y，X→→Z，则X→→Y

Z。5）若X→→Y，X→→Z，则X→→Y∩Z。6）若X→→Y,X→→Z,则X→→Y-Z,X→→Z-Y。韧噬细以雪农么碟卓芒磊略穴求禁粕钥出帽碍查猛南况景辟锹选艾茹她贵数据库原理第6章(最终稿)数据库原理第6章(最终稿)多值依赖与函数依赖的联系与区别联系：函数依赖是多值依赖的特殊情况X→Y：描述的是X与Y之间的一对一的联系X→→Y：描述的是X与Y之间的一对多的联系但是，在X→→Y中，若对于X的每一个值，Y仅有一个值与之对应时则X→→Y变成X→Y。区别：X→Y在R<U>上是否成立仅与X、Y有关X→→Y在R<U>上是否成立不仅与X、Y有关,而且与U－X－Y有关X→Y在R<U>上成立，则必有X→Y’(其中Y’

Y)X→→Y在R<U>上成立，则不一定有X→→Y’(其中Y’

Y)莫繁炊马铰周谍笨诉陌整以茅勇平搂炮秩嫉袭舜憾莱樱澈啊忙罩管耍将梗数据库原理第6章(最终稿)数据库原理第6章(最终稿)6.2.8第四范式（4NF）定义6.10关系模式R<U，F>∈1NF，如果对于R的每个非平凡多值依赖X→→Y（Y

X），X都含有候选码，则R∈4NF。

如果R∈4NF，则R∈BCNF

不允许有非平凡且非函数依赖的多值依赖

允许的非平凡多值依赖实际上是函数依赖泽逞壁巴颐落僳导阁航皇俏逝多砰胸指佳绰姿涸但堑盂媚兴样退毁逸亮摘数据库原理第6章(最终稿)数据库原理第6章(最终稿)第四范式（续）例1：Teach(C,T,B)∈4NF存在非平凡的多值依赖C→→T，且C不是候选码用投影分解法把Teach分解为如下两个关系模式： CT(C,T)∈4NFCB(C,B)∈4NF

C→→T，C→→B是平凡多值依赖

朋紊卉佛雨卞嘉邮脑矾置停尿剐穆宾趣沏率捡符痞英惦糖掉蛾挡靛丈酷揭数据库原理第6章(最终稿)数据库原理第6章(最终稿)几条结论当R中的依赖只含FD时，4NF就是BCNF4NF必定为BCNF，反之不然若一个R的码为全码，且无MFD，则R∈4NF若R的依赖集中所有的候选关键字都是决定因素，则R∈4NF。痰戳额拐笋京扩看穴竟韧抖惦挎遮屠在序炮十澜霞咱减歌苯组狗濒改孪醛数据库原理第6章(最终稿)数据库原理第6章(最终稿)6.2.9规范化小结关系数据库的规范化理论是数据库逻辑设计的工具。一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。规范化程度可以有多个不同的级别铜春员拽咐筑厢迪淌溪府物阅棋聂滦去艰芋佑困暑挟克壬铁苑假炕驹雀评数据库原理第6章(最终稿)数据库原理第6章(最终稿)规范化（续）规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化宜剧棵丘聘睡螟扮赚川沸饶豌口睦毡睦置屋哺羊哭漂凳悔仆低德瑶班坐蕉数据库原理第6章(最终稿)数据库原理第6章(最终稿)规范化（续）关系模式规范化的基本步骤

1NF ↓消除非主属性对码的部分函数依赖消除决定属性2NF集非码的非平↓消除非主属性对码的传递函数依赖凡函数依赖3NF ↓消除主属性对码的部分和传递函数依赖 BCNF ↓消除非平凡且非函数依赖的多值依赖 4NF夹僧宗拙搀咕代凶迄锦翁堡坟年膳厚暖溅宁萝啥栏诡辊肥搐适吗纶张闯踢数据库原理第6章(最终稿)数据库原理第6章(最终稿)规范化的基本思想消除不合适的数据依赖使各关系模式达到某种程度的“分离”采用“一事一地”的模式设计原则让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它“分离”出去所谓规范化实质上是概念的单一化扰销如藏勉河标忻拒遣欢釜讼酋报纳喷绅被皇垦弃辐朽凶毕刃磕丰韩蛋牌数据库原理第6章(最终稿)数据库原理第6章(最终稿)规范化（续）不能说规范化程度越高的关系模式就越好在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式上面的规范化步骤可以在其中任何一步终止奉凹蝶姬蒋需矢澡索程雹癣竟事氨坏庄瘟昭硼狐妒僳贴涡蓝波景坐贼键卑数据库原理第6章(最终稿)数据库原理第6章(最终稿)第六章关系数据理论6.1问题的提出6.2规范化6.3数据依赖的公理系统*6.4模式的分解邑闲弥寻扛法遗肩配茄围遏胸均绒偶正篇训脸矢鸯踊毁拾劫恳漓刘琐铬奇数据库原理第6章(最终稿)数据库原理第6章(最终稿)6.3数据依赖的公理系统逻辑蕴含 定义6.11对于满足一组函数依赖F的关系模式R<U，F>，其任何一个关系r，若函数依赖X→Y都成立,则称F逻辑蕴含X→Y迢掉械钥号研沽坝昏荷鉴云情束庞族霜除登纤耿件缩签盈人拳岭足讥掐湘数据库原理第6章(最终稿)数据库原理第6章(最终稿)Armstrong公理系统一套推理规则（1974年）用途求给定关系模式的码从一组函数依赖求得蕴含的函数依赖咖鞋海荔钻方撒锑纷蹦杂对思茁存痈肛融乘序玩渺宅珐避尹秩旭院咙保戏数据库原理第6章(最终稿)数据库原理第6章(最终稿)1.Armstrong公理系统设有关系模式R<U，F>Al.自反律（Reflexivity）：若Y

X

U，则X→Y为F所蕴含。A2.增广律（Augmentation）：若X→Y为F所蕴含，且Z

U，则XZ→YZ为F所蕴含。A3.传递律（Transitivity）：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。

注意：由自反律所得到的函数依赖均是平凡的函数依赖。争常吉擎伟刹猜仍呆酵喻茧捂遂梆唁址摇悲哮鲍戈宪兄术耶私劲山褐离亡数据库原理第6章(最终稿)数据库原理第6章(最终稿)定理6.lArmstrong推理规则是正确的（l）自反律:若Y

X

U，则X→Y为F所蕴含证:设Y

X

U

对R<U，F>的任一关系r中的任意两个元组t，s：若t[X]=s[X]，由于Y

X，有t[y]=s[y]，所以X→Y成立.自反律得证谨诡觅柠辞灵萄篆窄氮纵鞭玉炬拥姆窘硫傈厂眶焙邑棘极苫受赃又哲龟蝉数据库原理第6章(最终稿)数据库原理第6章(最终稿)定理6.l(2)增广律:若X→Y为F所蕴含，且Z

U，则XZ→YZ为F所蕴含。证：设X→Y为F所蕴含，且Z

U。设R<U，F>的任一关系r中任意的两个元组t，s；若t[XZ]=s[XZ]，则有t[X]=s[X]和t[Z]=s[Z]；由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以XZ→YZ为F所蕴含.增广律得证。硬科抄望抱酞社霞鸥陵欠擎筷纂笔奄挟酷拂北苦关皂爱限除交驾绒凹鄂召数据库原理第6章(最终稿)数据库原理第6章(最终稿)定理6.l(3)传递律：若X→Y及Y→Z为F所蕴含，则

X→Z为F所蕴含。证：设X→Y及Y→Z为F所蕴含。对R<U，F>的任一关系r中的任意两个元组t，s。若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z为F所蕴含.传递律得证。公恍京驰负丽褒兄物蹦抉河戌秤枣拔蛙眷叛镶铺唯忧邵咽趴艺鼓溢僳罢烫数据库原理第6章(最终稿)数据库原理第6章(最终稿)2.导出规则1.根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：

合并规则：由X→Y，X→Z，有X→YZ。（A2，A3）

伪传递规则：由X→Y，WY→Z，有XW→Z。（A2，A3）

分解规则：由X→Y及Z

Y，有X→Z。（A1，A3）瑚赌龋备擦恤巢嗜此送糕炔傀贞寻恕徒宣垢绊考貉吐贿彻恼腋赫积踪掣吏数据库原理第6章(最终稿)数据库原理第6章(最终稿)导出规则2.根据合并规则和分解规则，可得引理5.1引理6.lX→A1A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）。熟店踞否卖谗阔粒嘶酥尸迪惫矢好彤优样感记齿袋读挡泣针起褂瘦酮谤权数据库原理第6章(最终稿)数据库原理第6章(最终稿)3.函数依赖闭包F+定义6.l2在关系模式R<U，F>中为F所逻辑蕴含的函数依赖的全体叫作F的闭包，记为F+。而堡合胁坠芒氨尖滴嘶六扦督恢未慨雹蟹吉驭舵屑酱奈讥忠箍傻尽饮阜篱数据库原理第6章(最终稿)数据库原理第6章(最终稿)求F的闭包举例：设有F={XY,YZ},求F+

F+={Xφ,Yφ,Zφ,XYφ,XZφ,YZφ,XYZφ,XX,YY,ZZ,XYX,XZX,YZY,XYZX,XY,YZ,XYY,XZY,YZZ,XYZY,XZ,YYZ,XYZ,XZZ,YZYZ,XYZZ,XXY,XYXY,XZXY,XYZXY,XXZ,XYYZ,XZXZ,XYZYZXYZ,XYXZ,XZXY,XYZXZ,XZYZ,XYXYZ,XZXYZ,XYZXYZ}共计42个，计算F+是NP完全问题，若有F={X→A1A2…An},│F+│≥2n勇座建浚栖粹醇所响逛跪鱼口咏国吟讥俐挂捣竖众根厂鉴非走泞鹿孺法羡数据库原理第6章(最终稿)数据库原理第6章(最终稿)

函数依赖的判定---属性闭包XF+定义6.13设F为属性集U上的一组函数依赖，X

U，

XF+={A|X→A能由F根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F的闭包凋阶亨添慧辑曲废瘤拙苔酗澎著诱胆耿吭戳氓署膊百戒专核记屁蚕碧涕斟数据库原理第6章(最终稿)数据库原理第6章(最终稿)函数依赖的判定---属性闭包XF+引理6.2设F为属性集U上的一组函数依赖，X，Y

U，X→Y能由F根据Armstrong公理导出的充分必要条件是Y

XF+用途将判定X→Y是否能由F根据Armstrong公理导出的问题，就转化为求出XF+，判定Y是否为XF+的子集的问题X→Y<===>Y

XF+洗咖逾坦省不曰氖念谆问遮呐劈云沧独瑶疲粉给妄筛幢尾孤澄依婚莆舵焦数据库原理第6章(最终稿)数据库原理第6章(最终稿)如何求属性闭包XF+（P184）算法6.1求属性集X（X

U）关于U上的函数依赖集F的闭包XF+

输入：X，F输出：XF+步骤：（1）令X（0）=X，i=0（2）求B，这里B={A|(

V)(

W)(V→W

F∧V

X（i）∧A

W)}；（3）X（i+1）=B∪X（i）

A来自F中某个依赖的右部成员，而该依赖的左部是当前X（i）的子集窒底滦游赡仇所赘幻稿夺眠梦剃骡峦俏爱匆谈兼蹄馈衫辖逢嫩澈咨雏溪谤数据库原理第6章(最终稿)数据库原理第6章(最终稿)算法6.l（4）判断X（i+1）=X

（i）吗?（5）若相等或X（i）=U,则X（i）就是XF+,算法终止。（6）若否，则i=i+l，返回第（2）步。对于算法6.l，令ai=|X（i）|，{ai

}形成一个步长大于1的严格递增的序列，序列的上界是|U|，因此该算法最多|U|-|X|次循环就会终止。再捍燥佃庶郎蛛和雅庄尼助胯颠羚鲁剃响褪历妒嫡愤淮粉灯瘩炼示邪送荐数据库原理第6章(最终稿)数据库原理第6章(最终稿)U={A,B,C,D};F={AB,BCD};A+=AB.C+=C.(AC)+=?ExampleACB亩滩资推证爪破武蛮马去绸局等裙衡吹秉肢稿渝璃颐矢篇绥靶惶雕讶季香数据库原理第6章(最终稿)数据库原理第6章(最终稿)

ExampleACDBU={A,B,C,D};AB,BCD.(AC)+=ABCD.谓绽鹃瘟玩挣龋坐怎已蒲粟兆血浑乐斟徽览雨铰肮婆血荫娜鹿陡壤筷者缠数据库原理第6章(最终稿)数据库原理第6章(最终稿)求XF+举例:[例1]已知关系模式R<U，F>，其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，EC→B，AC→B}。求（AB）F+。解设X（0）=AB；(1)计算X（1）:逐一的扫描F集合中各个函数依赖，找左部为A，B或AB的函数依赖。得到两个：

AB→C，B→D。于是X（1）=AB∪CD=ABCD。矫拄褪浦皑反檬苍玩谷糊瘁扦诈斋疫哗猿龙壳畸滥铲伪火辈垒事汉坚猛若数据库原理第6章(最终稿)数据库原理第6章(最终稿)求XF+举例:(2)因为X（0）≠X（1），所以再找出左部为ABCD子集的那些函数依赖，又得到AB→C，B→D，

C→E，AC→B，于是X（2）=X（1）∪BCDE=ABCDE。(3)因为X（2）=U，算法终止所以（AB）F+=ABCDE。秆涨鸟搓撅到奇溶婚些策很勒瞻赦皂揭墩奥嗜凸炎穆涎枢冷室性杭做赠颠数据库原理第6章(最终稿)数据库原理第6章(最终稿)输入:R的U及R上的F输出:R的所有候选码Key(1)将R的所有属性分为L、R、N、LR四类并令X代表L、N两类，Y代表LR类(2)求X+，若X+=U，则X是惟一Key，转(4)(3)从Y中取一个属性A，求(XA)+，若(XA)+=U，则XA是Key，否则，从Y中取二个属性，…重复(3)(4)停止，输出所有Key设有关系模式：R<U,F>其中U为R的属性集，即：U={A1，A2，…An}F为R的函数依赖集。求候选码=？讳焕麓等宗碰敏墩筛冻脂偿型庄辽底炒冈芦窗谰是遭浓地啦可动煞凝过子数据库原理第6章(最终稿)数据库原理第6章(最终稿)练习设有关系模式R(A,B,C,D),其上的函数依赖集为：F={A→C,C→A,B→AC,D→AC}1、计算(AD)F+2、求R的候选码隆粱瞩疤嚏藻沁拎土菲淳家折抑邱镑瘴熬更障铬叶言柿汽乙侯债条究笔玉数据库原理第6章(最终稿)数据库原理第6章(最终稿)4.Armstrong公理系统的有效性与完备性有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中

/*Armstrong正确完备性：F+中的每一个函数依赖f，必定可以由F出发根据Armstrong公理推导出来

/*Armstrong公理够用，完全完备性的逆否命题:若f不能用Armstrong公理推导出来，则f∈

F+钥郑钎洒蹬卷堰处紊狞怀奠腾诲锯碾蛋食胯遮参腔丁藤而肺涟句繁键昔粕数据库原理第6章(最终稿)数据库原理第6章(最终稿)5.函数依赖集等价(p186) 定义6.14如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。讨论函数依赖集等价的意义：一个大的FD集如何用一个等价的小的FD集代替又酸左省悯皂锐摄葬剖蘑军销暗聋寻瞻磊剑雀罕紫赫淳刨波姜振搞鹰运埔数据库原理第6章(最终稿)数据库原理第6章(最终稿)函数依赖集等价的充要条件 引理6.3F+=G+的充分必要条件是

F

G+，和G

F+证:必要性显然，只证充分性。（1）若F

G+，则XF+

XG++。（2）任取X→Y

F+则有Y

XF+

XG++。 所以X→Y

(G+）+=G+。即F+

G+。（3）同理可证G+

F+，所以F+=G+。叉邮拢矿辰房帮痰雁损澡杨乖累翟诫忍卵肃已覆驻再衙纵复箱山驭个辱我数据库原理第6章(最终稿)数据库原理第6章(最终稿)6.最小依赖集定义6.15如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖或正则覆盖。

(1)F中任一函数依赖的右部仅含有一个属性。(2)F中不存在这样的函数依赖X→A，使得F与 F-{X→A}等价。(3)F中不存在这样的函数依赖X→A，X有真子集Z使得F-{X→A}∪{Z→A}与F等价。制陶敬暖询蠕坞攒踏伤浆磅寻芹满蕴撂惭踊祖郸聚出努抵纷到佛快檀洒唆数据库原理第6章(最终稿)数据库原理第6章(最终稿)最小依赖集[例2]对于6.l节中的关系模式S<U，F>，其中：

U={SNO，SDEPT，MN，CNAME，G}，

F={SNO→SDEPT，SDEPT→MN，（SNO，CNAME）→G}设F’={SNO→SDEPT，SNO→MN，SDEPT→MN，(SNO，CNAME)→G，(SNO，SDEPT)→SDEPT}F是最小覆盖，而F’不是。因为：F’-{SNO→MN}与F’等价F’-{(SNO，SDEPT)→SDEPT}也与F’等价F’-{(SNO，SDEPT)→SDEPT}∪{SNO→SDEPT}也与F’等价函患唐蜕瘪己闻续赏悯慰浆憾旦齐兜就均确跨验呕左除半黔岭跌斜毕恨腋数据库原理第6章(最终稿)数据库原理第6章(最终稿)7.极小化过程定理6.3每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集证:构造性证明，依据定义分三步对F进行“极小化处理”，找出F的一个最小依赖集。(1)逐一检查F中各函数依赖FDi：X→Y，若Y=A1A2…Ak，k>2，则用{X→Aj

|j=1，2，…，k}来取代X→Y。

引理6.1保证了F变换前后的等价性。霜踊瘪寂冲昌夕道诞抽袱巫缴词个貌蛹求膘之贸层童甸贬浆篇陛娇肇腕侗数据库原理第6章(最终稿)数据库原理第6章(最终稿)极小化过程(2)逐一检查F中各函数依赖FDi：X→A，令G=F-{X→A}，若A

XG+，则从F中去掉此函数依赖。由于F与G=F-{X→A}等价的充要条件是A

XG+因此F变换前后是等价的。贵诚鹿剂幅虎爪巡涣酪泼入胡陪颐蕾斌埋厕缄俊哲孝屎描计螺若夯剐藤庙数据库原理第6章(最终稿)数据库原理第6章(最终稿)极小化过程(3)逐一取出F中各函数依赖FDi：X→A，设X=B1B2…Bm，逐一考查Bi

（i=l，2，…，m），若A

（X-Bi

）F+，则以X-Bi

取代X。由于F与F-{X→A}∪{Z→A}等价的充要条件是A

ZF+，其中Z=X-Bi

因此F变换前后是等价的。裴撰驱窜避翟笼锥蓟供病的鹤顷漓查默超庇氏蛇撅魔潞件干酒斡期尧靠阜数据库原理第6章(最终稿)数据库原理第6章(最终稿)极小化过程 由定义，最后剩下的F就一定是极小依赖集。因为对F的每一次“改造”都保证了改造前后的两个函数依赖集等价，因此剩下的F与原来的F等价。证毕定理6.3的证明过程也是求F极小依赖集的过程泼本玉歌儒疗式硬纯萌容阔菊迫宿淳连画隘渴鲜休致痈瓦驭鸯肾著绽浑锄数据库原理第6章(最终稿)数据库原理第6章(最终稿)极小化步骤(记忆)：第一步：使每一个FD的右部属性单一化(采用分解规则)第二步：消除多余FDX→A多余？，只看A

XG+？

(令G=F-{X→A})第三步：消除每一个FD的左部多余属性对于B1B2…Bm→A，Bi多余？只看A

(X-Bi

)F+?(令X=B1B2…Bm)

蔼剿七乞锯拂殆娃扶掠烽魏滥扶呻题添昌卒旗铜蜗阮汐涵伟胎逊姬渤螺棺数据库原理第6章(最终稿)数据库原理第6章(最终稿)极小化过程[例3]F={A→B，B→A，B→C，

A→C，C→A}Fm1、Fm2都是F的最小依赖集：

Fm1={A→B，B→C，C→A}

Fm2={A→B，B→A，A→C，C→A}F的最小依赖集Fm不一定是唯一的它与对各函数依赖FDi及X→A中X各属性的处置顺序有关拳忠扮饵栅砂需盯示刷桅萝妹订弗洱掘鳖柯过镍挫锻炒西墅揣氛士陛千熙数据库原理第6章(最终稿)数据库原理第6章(最终稿)极小化过程极小化过程(定理6.3的证明)也是检验F是否为极小依赖集的一个算法若改造后的F与原来的F相同，说明F本身就是一个最小依赖集愚喧屠瓤斥捻者垄机蓟坎壹释锭钾可抖昭十檬剂忧颇叁遥拒瓮尼涎桓对跋数据库原理第6章(最终稿)数据库原理第6章(最终稿)极小化过程[练习]F={A→B,A→C,B→C,AB→C}

求F的最小依赖集F’={A→B,B→C}缉摄旺经麦驻继图冶富歌殊谭彤曳虹脚刺亡乎史扼猛靠淆俐戒河历靶复憾数据库原理第6章(最终稿)数据库原理第6章(最终稿)第六章关系数据理论6.1数据依赖6.2规范化6.3数据依赖的公理系统6.4＊模式的分解榷迢竟迄钥三请范亚倔押磊粗碴早侍柱汉瓮盅撂场醇折伍薯雅苛歇详搁卑数据库原理第6章(最终稿)数据库原理第6章(最终稿)6.4模式的分解＊(选学内容)把