第6章关系形式的标准化实际ppt课件.ppt

《第6章关系形式的标准化实际ppt课件.ppt》由会员分享，可在线阅读，更多相关《第6章关系形式的标准化实际ppt课件.ppt（61页珍藏版）》请在三一办公上搜索。

1、第6章 关系模式的规范化理论,檀腐箍霖墒三抬责诗邢篷葫宙珠烘阑绷船追拭龚榜站洞氏象汐瘪蘸感具锦第6章 关系模式的规范化理论第6章 关系模式的规范化理论,本章主要内容,关系数据库的规范化设计是指面对一个现实问题，如何选择一个比较好的关系模式集合。规范化设计理论对关系数据库结构的设计起着重要的作用。,袄帜株胰潦核亚宗晴磋赵镊脊蜂悲子瞳掩娟呼赡晾易耙徽在谱滞绚测钱净第6章 关系模式的规范化理论第6章 关系模式的规范化理论,本章主要内容,(1)关系模式的冗余及相关的异常问题。(插入、删除、更新异常)(2)函数依赖(FD)的定义、(非)平凡函数依赖、完全(部分)函数依赖、（非）传递函数依赖。(3)关系模

2、式的范式的概念：1NF，2NF，3NF，BCNF。（理解概念并能够判断一个关系模式的范式级别）,玲替悄混牡凑窗蹭罐廖鼓鞍德尉淘幌爱颖液瞩含蠢虑距桌馒腆宝嗽堑赛锄第6章 关系模式的规范化理论第6章 关系模式的规范化理论,关系模式的规范化理论,6.1 关系模式设计中的问题 6.2 函数依赖 6.3 函数依赖的公理系统 6.4 关系模式的分解及其问题 6.5 关系模式的规范化 6.6 多值函数依赖与4NF本章小结,哲披呼腰逃斧哼替砖搅疵檄筹每隋唤卑李移扩耐赴束稀疡剐社阎讶胰恳键第6章 关系模式的规范化理论第6章 关系模式的规范化理论,6.1 关系模式设计中的问题,假设需要设计一个学生学习情况数据库S

3、tuDB。 下面我们以模式S_C_G（S#，SN，SD，SA，C，CN，G，PC）为例来说明该模式存在的问题。下表是其一个实例。,（1）冗余度大：同样的数据被多次重复存储。（2）操作异常由于数据的冗余，在对数据操作时会引起多种异常：插入异常:应该能插入的数据，但无法插入删除异常：不该被删除的数据，却被删掉修改异常：修改数据，很困难，容易造成遗漏或出错。,瑚唱呼迂烁眼帝掳参妙藐驶拣浊琵听犯早厌晰州信远赖帚决蔽猛轨锨运测第6章 关系模式的规范化理论第6章 关系模式的规范化理论,关系模式的分解,我们采用分解的方法，将上述S_C_G分解成以下三个模式： S（S，SN，SD，SA） C（C，CN，PC）

4、 S_C（S，C，G）(让每个模式表达单一的概念信息),这三个模式，冗余度小， 也消除了各类异常,硼刘啼济陀荫只京黎庙入这问磨恿币片薛弦姆俊沸邵柠菱桩指崇早岛腹屡第6章 关系模式的规范化理论第6章 关系模式的规范化理论,6.2 函数依赖,1）函数依赖(Functional Dependency，简称FD),在上述的关系模式S和SC，存在以下函数依赖：S #SDSSNSSA（S,C）G,定义6.1（函数依赖）：设有关系模式R(U)，其中U=A1，A2，An是关系的属性全集，X、Y是U的属性子集，设t和u是关系R上的任意两个元组，如果t和u在X的投影tX=uX推出tY=uY，即：tXuX = tY

5、uY则称X函数决定Y，或Y函数依赖于X。记为XY。,每火辆剪狗磊壬伯沼瘸爵瓶暴担婪杯烹凹睫墨咯愉淹低她竭苫百嘻辛都谩第6章 关系模式的规范化理论第6章 关系模式的规范化理论,2）几种类型的函数依赖,例如X, XX , XZX等都是平凡函数依赖。,定义6.2（非平凡函数依赖、平凡函数依赖）：一个函数依赖XY如果满足YX，则称此函数依赖为非平凡函数依赖，否则称为平凡函数依赖。,定义6.3（完全函数依赖、部分函数依赖）：设X、Y是关系R的不同属性集，若XY （Y函数依赖于X），且不存在XX ，使XY，则称Y完全函数依赖于X，记为 ；否则称Y部分函数依赖于X，记为 。,例如，在上例关系S中, 是完全函

6、数依赖; 、 是部分函数依赖。,富愁篱谢靶泄纂谜粥饺月酶吻琶驯摘若脑烤馋伐森描萨酶肯炸绸项并股琉第6章 关系模式的规范化理论第6章 关系模式的规范化理论,几种类型的函数依赖,在属性Y与X之间，除了完全函数依赖和部分函数依赖关系等直接函数依赖，还存在间接函数依赖关系。 如果在关系S中增加系的电话号码DT，从而有S #SD,SDDT，于是S#DT。在这个函数依赖中，DT并不直接依赖于S#，是通过中间属性SD间接依赖于S#。这就是传递函数依赖。,沏湿进遁壬跪搪巍县迂纤兑休沃亥淑褥崎逞仍虫友训凳菠皋棚搏怒会纷恐第6章 关系模式的规范化理论第6章 关系模式的规范化理论,3）关系的关健字和超关键字,一个包

7、含了关键字的属性集合也能够函数决定（但不是完全函数决定，而是部分决定）属性全集，我们把这种包含了关键字的属性集合称为超关键字(Super Key)。,例如，在上例的S（S，SN，SD，SA）、C（C,CN,PC）、S_C（S，C，G）三个关系模式中，存在以下关键字：,所以，S#、C#和（S#，C#）分别是关系模式S、C和S_C的关键字 。,所以，(S#，SN)和(S#，SD)都不是关键字，而是超关键字。,定义6.5（关键字）:在关系模式R(U)中，若K U，且满足 ，则称K为R的关键字。,蜗忽晓曰卓膜擒素木牡选搁吞果各拘窘瘟址圣跌食剑碰菱否脖丸晃肪晰拨第6章 关系模式的规范化理论第6章 关系模

8、式的规范化理论,6.3 函数依赖的公理系统,6.3.1 函数依赖的逻辑蕴涵 6.3.2 Armstrong公理系统 6.3.3 函数依赖集的等价与覆盖,筑撕恿晒释臭健菱站难脱帘掐餐猜槐亿沽焦豹谗肛绸兰蔽咎猎继叛挑话附第6章 关系模式的规范化理论第6章 关系模式的规范化理论,6.3.1 函数依赖的逻辑蕴涵,例如在上述的传递函数依赖中，由XY，YZ，推导出XZ，这可以表示为： XY，YZ XZ 其中: 表示逻辑蕴涵。 一般地讲，函数依赖的逻辑蕴涵定义如下：,定义6.6（逻辑蕴涵）：设F是由关系模式R(U)满足的一个函数依赖集，XY是R的一个函数依赖，且不包含在F，如果满足F中所有函数依赖的任一具体

9、关系r，也满足XY，则称函数依赖集F逻辑地蕴涵函数依赖XY，或称XY可从F推出。可表示为：FXY,扶板惟踞磺骂捡炽情林组涂婚蓄女絮条勘厌您瘁罚诚滇痢佳蛙寂垛痢挥诞第6章 关系模式的规范化理论第6章 关系模式的规范化理论,函数依赖集F的闭包F+,定义6.7：函数依赖集F所逻辑蕴涵的函数依赖的全体称为为F的闭包（Closure），记为F+，即F+XYFXY,例如，有关系R（X，Y，Z），它的函数依赖集FXY，YZ，则其闭包F+为：,钦辞脉音和录摄轨痊恳呀锭恰碍剐守扭劣挎秆等汉罚翁螺堪第技郡烟枣社第6章 关系模式的规范化理论第6章 关系模式的规范化理论,6.3.2 Armstrong公理系统,1）独

10、立推理规则即下面给出的Armstrong公理的三条推理规则是彼此独立的。,（3） A3：传递律(Transitivity)如果XY且YZ，则XZ成立。,（2） A2：增广律(Augmentation) 如果XY，且Z W，则XWYZ成立。 根据A2可以推出XWY、XZYZ或XWYW、XXY、XYX等。,（1） A1：自反律(Reflexivity) 如果Y X，则XY成立，这是一个平凡函数依赖。 根据A1可以推出X、UX等平凡函数依赖（因为 X U）。,向唾汇荔泽壳濒釉河授敌馒坍道早绕窝驴化疯赶焊铬剐痘改菠燃李迎譬职第6章 关系模式的规范化理论第6章 关系模式的规范化理论,2）其他推理规则,推

11、论1：合并规则(The Union Rule) XY，XZ XYZ,推论3：伪传递规则(The Pseudo Transitivity Rule) XY，WYZ XWZ,证：（1）XY XXY（A2增广律） XZ XYYZ （A2增广律） 由上可得XYZ （A3传递律）,（3）XYWXWY （A2增广律） WYZ （给定条件） 由上可得XWZ（A3传递律）,（2）Z Y YZ （A1自反律） XY （给定条件） 由上可得XZ（A3传递律）,推论2：分解规则(The Decomposition Rule) 如果XY，Z Y，则XZ成立,箕梢乐邯谨寇钩填盂奋哦芥颖蕴害番农椎轰匙矮碑升贝处郭岳丧述煞

12、熟鸭第6章 关系模式的规范化理论第6章 关系模式的规范化理论,一个重要定理,例6.2：设有关系模式R(A,B,C,D,E)及其上的函数依赖集F=ABCD,AB,DE，求证F必蕴涵AE。,定理6.1：若Ai(i=1，2，,n)是关系模式R的属性， 则X(A1，A2，,An)成立的充分必要条件是XAi均成立。,证明： AB （给定条件） AAB （A2增广律） ABCD （给定条件） ACD （A3传递律） AC，AD （分解规则） DE （给定条件） AE （A3传递律） 证毕。,凸疮肝票刨热覆出碘酱蟹覆馒坡绸沾绘滥郁棕忙谰痰盐袖贷论孪宾思源赤第6章 关系模式的规范化理论第6章 关系模式的规范化

13、理论,属性集闭包,定义6.8（属性集闭包）:设有关系模式R(U),U= A1，A2，,An,X是U的子集,F是U上的一个函数依赖集，则属性集X关于函数依赖集F的闭包 定义为： AiAiU，且XAi可用阿氏公理从F推出,例：设关系模式R(A,B,C)的函数依赖集为F=AB,BC，分别求A、B、C的闭包。,解：若XA， AB,BC（给定条件） AC （A2传递律） AA （A1自反律） =A，B，C （据定义）,若X=B BB （A1自反律） BC （给定条件） =B，C （据定义）,若X=C， CC （自反律） =C （据定义）,嗜低毋备啼涕仰赂敞琶嘻瓦瑚近封碳宙山衬酞损规遭虱了葛叔糟释佛睛并第

14、6章 关系模式的规范化理论第6章 关系模式的规范化理论,定理6.2:设F是关系模式R(U)上的函数依赖集,U是属性全集，X,Y U,则函数依赖XY是用阿氏公理从F推出的，充分必要条件是Y ；反之，能用阿氏公理从F推出的所有XY的Y都在 中。,这个定理告诉我们，只要Y ，则必有XY。于是，一个函数依赖XY能否用阿氏公理从F推出的问题，就变成判断Y是否为 子集的问题。下面介绍一下计算 的算法。,叭歇喊朵臼述獭沃撼腻民煞续哨厄蛙戏涛诱液幌枚并总誊潜爬寞险焕耪畔第6章 关系模式的规范化理论第6章 关系模式的规范化理论,属性集的闭包计算,方法：根据下列步骤计算一系列属性集合X(0)，X(1)， (1)

15、令X(0)=X，i0； (2) 求属性集/*在F中寻找满足条件V X(i)的所有函数依赖VW,并记属性W的并集为B*/ (3) X(i+1)X(i) B (4)判断X(i+1)= X(i)吗？ (4)若X(i+1) X(i)，则用i+1取代i,返回(2)； (5)若X(i+1) = X(i)，则 =X(i)，结束。,算法6.1：求属性集X(X U)关于U上的函数依赖集F的闭包 。输入：属性全集U,U上的函数依赖集F,以及属性集X U。输出：X关于F的闭包 。,踏次缓抒礁痢科缝整杂徽此讨死挥湾正蘑有旧煮鸦友闻就孔漱府者五强漓第6章 关系模式的规范化理论第6章 关系模式的规范化理论,算法6.1的求

16、解过程,例：设FAHC，CA，EHC，CHD，DEG，CGDH，CEAG，ACDH，令XDH ，求 。,最后，(DH)+=ACDEGH。,解： X(0)=X=DH 在F中找所有满足条件V X(0)=DH的函数依赖VW，结果只有DEG，则B=EG，于是X(1)X(0)B=DEGH 。 判断是否X(i+1)= X(i)，显然X(1)X(0)。 在F中找所有满足条件V X(1)=DEGH的函数依赖VW，结果为EHC，于是B=C，则X(2)X(1)B=CDEGH 。 判断是否X(i+1)= X(i)，显然X(2)X(1)。 在F中找所有满足条件V X(2)=CDEGH的函数依赖VW，结果为CA，CHD

17、，CGDH，CEAG，则B=ADGH，于是X(3)X(2)B=CDEGHB=ACDEGH 。判断是否X(i+1)= X(i)，这时虽然X(3)X(2)。但X(3)已经包含了全部属性，所以不必再继续计算下去。,匿财颖运峭侨填瞥暇朱弹产文车娃臆陇伟旅某气妆离莲持展沮事湿尚斥贴第6章 关系模式的规范化理论第6章 关系模式的规范化理论,属性集闭包计算结束判断方法,在判断计算何时结束时，可用下面四种方法： （1）X(i+1)= X(i)。 （2）X(i+1)已包含了全部属性。 （3）在F中再也找不到函数依赖的右部属性是X(i)中未出现过的属性。 （4）在F中再也找不到满足条件V X(i)的函数依赖VW。

18、,腮粥鼻蜕虚勾扼琵正蛋特伙咳穆汀打弗俏谚侧研伦臼烽寝篇圃涪虱卉阅遂第6章 关系模式的规范化理论第6章 关系模式的规范化理论,6.3.3 函数依赖集的等价和覆盖,定义6.9（函数依赖集的等价、覆盖）：设F和G是关系R（U）上的两个依赖集，若F+=G+，则称F与G等价，记为F=G。也可以称F覆盖G，或G覆盖F；也可说F与G相互覆盖。,检查两个函数依赖集F和G是否等价的方法是：第一步：检查F中的每个函数依赖是否属于G+，若全部满足，则F G+。如若有XYF,则计算 ,如果Y , 则XYG+;第二步：同第一步，检查是否G F+;第三步：如果F G+，且G F+，则F与G等价。由此可见,F和G等价的充分

19、必要条件是：F G+，且G F+。,誓赚讥侗运降碘满规熄立歼姓锈蒙纤羞轧隶乱媚番浮欲世堪荣据晨肩杆涛第6章 关系模式的规范化理论第6章 关系模式的规范化理论,引理6.1：设G是一个函数依赖集，且其中所有依赖的右部都只有一个属性，则G覆盖任一左部与G（左部）相同的函数依赖集。,一个函数依赖集F可能有若干个与其等价的函数依赖集，我们可以从中选择一个较好以便应用的函数依赖集。标准至少是：所有函数依赖均独立，即该函数依赖集中不存在这样的函数依赖，它可由这个集合中的别的函数依赖推导出来。表示最简单，即每个函数依赖的右部为单个属性，左部最简单。,证明：构造GXAXYF且AY由AY，XYF根据分解规则导出，

20、从而等到G F+。反之，如果YA1A2An，而且XA1，XA2，XAn在G中可根据合并律等到F G +。由此可见，F与G等价，即F被G覆盖。,属客瓮贸桓铅巡马笋碑壁汛蓟袁弯讥蒜量惹烦殉恿凹恤蚁裁勒力辈断颇抡第6章 关系模式的规范化理论第6章 关系模式的规范化理论,最小函数依赖集,定义6.10（最小函数依赖集）:函数依赖集F如果满足下列条件，则称F为最小函数覆盖，记为Fmin：(1) F中每一个函数依赖的右部都是单个属性。(2) 对F中任一函数依赖XA，FXA都不与F等价。(3) 对于F中的任一函数依赖XA, FXAZA都不与F等价，其中Z为X的任一子集。,求函数依赖集F的最小覆盖的方法是：(1

21、) 检查F中的每个函数依赖XA,若A= A1,A2,Ak,则根据分解规则，用XAi(i=1，2，k)取代XA。(2) 检查F中的每个函数依赖XA,令G=FXA， 若有 A ，则从F中去掉此函数依赖。(3) 检查F中各函数依赖XA，设X= B1,B2,Bm,检查Bi ， 当A 时，即以XBi替换X。,赵慨铜负署捡拖发拢悍声痊古蝗光商涂劳脏舵混俗贺皆桩币吹浴怨恿谊包第6章 关系模式的规范化理论第6章 关系模式的规范化理论,最小覆盖的求解事例,例6.5：求下列函数依赖集的最小覆盖：FAHC，CA，CHD，CEG，EHC， CGDH， CEAG，ACDH 。,解：(1)用分解规则将F中的所有依赖的右部

22、变成单个属性，可以得到以下11个函数依赖：AHC，CA，CHD，ACDH （给定） CE，CG（由CEG分解得到） EHC （给定） CGH，CGD（由CGDH分解得到） CEA，CEG（由CEAG分解得到） (2) 根据阿氏公理去掉F中的冗余依赖由于从CA可推出CEA，从CA、CGD、ACDH推出CGH，因此CEA和CGH是冗余，可从F删除 。(3) 用所含属性较少的依赖代替所含属性较多的依赖。 由于CA, ACDH中A是冗余属性，因此，可用CDH代替ACDH，故删除ACDH。 最后得到F的最小覆盖为： FAHC，CA，CHD，CDH，CE，CG，EHC，CGD，CEG,葛雌充畴已震攻肄叉扩

23、尸窖榔妻享友襄厩馒禄卜寿户悟蓝猾绝绩馁邹妒唉第6章 关系模式的规范化理论第6章 关系模式的规范化理论,6.4 关系模式的分解 及其问题,6.4.1 什么叫模式分解 6.4.2 分解的无损连接性 6.4.3 保持函数依赖性,扇惭怂翻画比骆沽舍拐拈娥兰则砧第关烛锥氟悲训郁辱枯蔡匪篷旱磁啪芬第6章 关系模式的规范化理论第6章 关系模式的规范化理论,6.4.1 什么叫模式分解,例6.6：设在模式R(U,F)中 USNO，SNAME，DNAME，DADDR FSNOSNAME，SNODNAME，DNAMEDADDR如果对R作如下分解（方法1）： =R1（SNO,SNAME,SNOSNAME）， R2（

24、DNAME，DADDR, DNAMEDADDR）,定义6.11（模式分解）：关系模式R(U，F)的一个分解是若干个关系模式的一个集合：=R1(U1,F1),R2(U2,F2),Rn(Un,Fn)式中：(1) 。 (2) 对每个i，j（1i,jn）有 。 (3) Fi(i=1，2，,n)是F在Ui上的投影，即,叭夫下狡媒拿怔钟石眉踢离搏汝奠厘志肝嚏祝晦瞩毡越褐膛氧辛芭羞驼横第6章 关系模式的规范化理论第6章 关系模式的规范化理论,（1）连接不失真问题,娱儡屯痒短抓搜洋肪闹尝驭民镁站诲炕氨霞齐碗该蚤饰霹氯便求依刁孜嘴第6章 关系模式的规范化理论第6章 关系模式的规范化理论,方法2：假设按下列方法对

25、R进行分解=R1 (SNO,SNAME,DNAME,SNOSNAME,SNODNAME ), R2（DNAME,DADDR），DNAMEDADDR）,豆势泥初五屑嫌朵服锡洋酸爽际夺卸忻奋垂烛易示咏晨啡塔汀凹驱唐巨艇第6章 关系模式的规范化理论第6章 关系模式的规范化理论,（2）依赖保持问题,上例方法1： FSNOSNAME，SNODNAME，DNAMEDADDR F1F2SNOSNAME，DNAMEDADDR F+SNOSNAME,SNODNAME,DNAMEDADDR,SNODADDR (F1F2)+SNOSNAME，DNAMEDADDR,一个关系模式经分解后，其函数依赖集F也随之被分解，则

26、分解后的依赖集Fi并集是否能保持原有的函数依赖关系？即 ?若出现 ，说明分解后有些函数依赖被丢失了。,上例方法2： FSNOSNAME，SNODNAME，DNAMEDADDR F1F2SNOSNAME,SNODNAME,DNAMEDADDR F+SNOSNAME,SNODNAME,DNAMEDADDR,SNODADDR (F1F2)+ SNOSNAME,SNODNAME,DNAMEDADDR,SNODADDR,再萌窖腮宾岛该信饼烘阻渺觉铂普贸沿炕朽洲乡诛渔炒肪灸俊搏瘁菜孪客第6章 关系模式的规范化理论第6章 关系模式的规范化理论,6.4.2 分解的无损连接性,1）无损连接分解的定义,定义6.1

27、2（无损连接分解，即连接不失真分解）：设关系模式R（U，F）上的一个分解为=R1(U1,F1)，R2(U2,F2)，Rk(Uk,Fk)，F是R（U，F）上的一个函数依赖集。如果对R中满足F的任一关系r都有则称这个分解相对于F的是连接不失真分解或称无损连接分解。,对于关系模式R关于F的无损连接条件是： 任何满足F的关系r有r = m(r)。,砾鳞紫锹百崭逸咱旭斩番享幕冬妊方疚六妓罐汀倦差和问少漂患帝粹舅拖第6章 关系模式的规范化理论第6章 关系模式的规范化理论,r 和m(r)之间的联系,定理6.4：设R是一关系模式，=R1(U1,F1)，R2(U2,F2)，Rk(Uk,Fk)是关系模式R的一个分

28、解，r是R的任一关系，（1ik）,那么有： ； 如果s= m(r)，则 ，或 mm(r)= m(r),儡用庚悸然貌巍歪搬颈迂痛腑厢揭换后渴蒸龟春坠施怒胰肃持褥余订奋癌第6章 关系模式的规范化理论第6章 关系模式的规范化理论,定理6.4证明, 由定理6-5可知 ，可得到 ，即 （因为s= m(r)）（也就是两边同时在Ui上投影，得 ）。 为了证明 。假设 ，则s中必存在满足tRi=ti的元组t。由于ts,对每个j,在rj中必存在元组uj满足tRj=uj (1jk),即 。 于是对那个特定的i，亦有tRi=ui，即tRiri。但tRi=ti，所以tiri，从而得到 （即 ）。 由 和 可得 （即

29、）。, 由定理6-5可知 (i=1,2,k)，于是有 。此式左式m(s)= mm(r)（由得），右式 m(r)， 因此得：mm(r) =m(r)该定理说明，关系模式只有在第一次分解的连接恢复后有可能丢失信息，此后的多次分解恢复均能使分解不失真,证明： 设任意一个元组tr,ti=tUi(i=1,2,k);则tiRi。根据自然连接定义，可知t在 中，即tm(r)，所以 。该定理说明，一个关系模式经分解再连接恢复所得的新关系m(r)的元组一般比原关系的元组要多，而且m(r)一定包括原关系的元组。只有当r= m(r)时，分解才是连接不失真分解。,壮泽冉维磷操忍偏沁绪掩封贺殴摊窍呼凰哆胖收剐摹肥郸靡些鼓

30、暗娶蜗阑第6章 关系模式的规范化理论第6章 关系模式的规范化理论,2）无损连接的检验,方法1：采用检验表格构造法算法6.2：连接不失真检验,方法1：(1)构造一个n列k行表，每一行对应于一个模式Ri（1ik），每一列对应于一个属性Aj（1jn），如下表所示。,(2) 初始表（填表）：若AjRi，则第i行第j列上填入aj，否则填入bij。(3) 修改表：反复检查F中的每一个函数依赖XY，按下方法修改表格中的元素：取F中的函数依赖XY，检查Y中的属性所对应的列，找出X相等的那些行，将这些X的符号相同的行中的Y的属性所对应的符号改成一致。即如果其中有aj，则将bij改为aj；若无aj，则将它们全改为

31、bij。一般取i是为其中的最小行号值。(4) 如发现某一行变成a1，a2，,ak，则此分解具有连接不失真性。,子戒藩狰捣杭酷饭开颠师拾甚龙惭邪耳您释海粗孔漾翱甭绒炬腮硬澈数亿第6章 关系模式的规范化理论第6章 关系模式的规范化理论,事例说明,例：设有R(U,F)，其中：U =(A,B,C,D,E),F=(AC,BC,CD,DEC,CEA)，R的一个分解为：R1(AD)，R2 (AB)，R3(BE) ，R4(CDE) ，R5(AE)是否无损分解？,根据算法6.2中(1)和(2)构造初始表，如表(a)所示。根据AC，对表(a)进行处理，将b13、b23、b53改成同一符号b13，即b13b23b5

32、3。再根据BC，将b33、b13（R2中）改成同一符号b13。修改后如表(b)所示。 考虑CD，根据上述修改原则，将D所在的第4列的b24、b34、b54均修改成a4，其结果如表（c）所示。(因为AC,BC)再考虑DEC，根据修改原则，将C所在的第3列第3、4、5行的b13、a3、b13均修改成a3，其结果如表（d）所示。(因为BC, AC, CD)再考虑CEA，根据修改原则，将A所在的第1列第3、4、5行的b31（由BC推出）、b41（由AC推出）、a1均修改成a1，其结果如表（e）所示。,俩瞪贩洒血农施解垣遭盈先街餐魁经岁垫兄峨吴泄芬混夷坑脖袒讳促番膨第6章 关系模式的规范化理论第6章 关

33、系模式的规范化理论,简单的检验方法,方法2：定理6.5：设= R1,R2是关系模式R的一个分解，F是R的一个函数依赖集，则对于F, 具有连接不失真性的充分必要条件是R1R2R1R2 F+，或R1R2R2R1F+。,例6.8：设有关系模式R(S,SN,C,G，SSN,(S,C)G)的一个分解为：=R1(S,SN,SSN)，R2(S,C,G,(S,C)G)因为R1R2=S#，R1R2=SN，故R1R2R1R2，且S#SN属于F，所以该分解具有连接不失真性。,定理6-8和例6-9告诉我们一个事实：如果两个关系模式间的公共属性集至少包含其中一个关系模式的关键字，则此分解必定具有连接不失真性。,颓矿肇永

34、汁殖接轨还娶阮惨柴俩略熔耳年灯液氓气敢甄镁鉴难忽襟些奠胰第6章 关系模式的规范化理论第6章 关系模式的规范化理论,6.4.3 函数依赖保持性,定义6.13：设有关系模式R,F是R上的函数依赖集，Z是R上的一个属性集合，则称Z所涉及到的F+中的所有函数依赖为F在Z上的投影，记为z(F)。,该定义实质上是，当XYF+时，若XYZ，则有z(F)，可以定义为：,定义6-17：设关系模式R的一个分解为=R1,F1，R2,F2，Rk,Fk,F是R上的依赖集，如果对于所有的i=1,2, ,k，z(F)中的全部函数依赖的并集逻辑地蕴涵F中的全部依赖，则称分解具有依赖保持性。,趴迸八术缆胖寒挥遭钳灌崔粟粮氰滇动

35、旷谜庭汕暖邹食腔肥镐恶该似叭架第6章 关系模式的规范化理论第6章 关系模式的规范化理论,判断两个函数依赖集是否等价的方法也可以用来判断一个分解是否保持依赖。下面以一个例子来说明一下。：设R(A,B,C,D)，FAB,CD，=R1(A,B，AB)，R2（C,D，CD）。因为FAB,CD，F1F2AB,CD所以 F+ = (F1F2)+,该例还说明，一个具有依赖保持性的分解不一定具有连接不失真性。反之，一个连接不失真分解也不一定具有依赖保持性。,例：设R(A,B,C)，FAB，CB，=R1(A,B，AB)，R2（A,C，AC）。R1R2=A, R1R2=B，R2R1=CR1R2R1R2= ABF但

36、FAB,CB，F1F2AB,AC,即F+ (F1F2)+可见具有连接不失真性，但不具有依赖保持性。,葛咯推甭钟娘迭恕址式轻滤籽谁依钡臭援徽帘诡绵噶谭蒜灵汀庇均创迢蜜第6章 关系模式的规范化理论第6章 关系模式的规范化理论,范式的概念是由E. F. Codd在1970年首先提出来的。 满足特定要求的模式称之为范式。所谓模式规范化，就是把关系模式规范到某一级范式,目的是：(1)消除异常现象。(2)方便用户使用，简化操作。 (3)加强数据独立性。关系规范化的条件可以分成几级，每一级称为一个范式，记为xNF，其中x表示级别,NF是范式(Normal Form)，即关系模式满足的条件。范式的级别越高，条

37、件越严格，因此有：,6.5 关系模式的规范化6.5.1 范式,募凸庇唐舷茶胳馆阉涟雍漏雅瘟练铝今饿人矾抓指只街掏抗驴投演擂温照第6章 关系模式的规范化理论第6章 关系模式的规范化理论,1）第一范式（1NF）,定义6.14（1NF）：如果一个关系模式R的每个属性的域都只包含单纯值，而不是一些值的集合或元组，则称R是第一范式，记为R1NF,把一个非规范化关系模式变为1NF有两种方法，一是把不含单纯值的属性分解为多个属性，并使它们仅含单纯值。,例如，设模式：P (PNO，PNAME，QOH,PJ(PJNO,PJNAME，PJMNO，PQC）将模式P变为： P(PNO,PNAME,QOH,PJNO,P

38、JNAME,PJMNO,PQC）第二种方法是把关系模式分解，并使每个关系都符合1NF。则： Pl (PNO,PNAME,QOH) PJl (PNO,PJNO,PJNAME,PJMNO,PQC) 思考：PJNAME,PJMNO对(PNO,PJNO)函数依赖的类型？,便谅衫迸汉凤嫉嫡泊数页隐殆雏庇扣辞父腰彰窿俺吊遮尿钦厅甜咽光骇惧第6章 关系模式的规范化理论第6章 关系模式的规范化理论,2）第二范式（2NF）,定义6.15（2NF）：如果关系模式R1NF，且它的任一非主属性都完全函数依赖于任一候选关键字，则称R满足第二范式，记为R2NF。把一个1NF的关系模式变为2NF的方法是，通过模式分解，使任

39、一非主属性都完全函数依赖于它的任一候选关键字。,例如对上例，若把PJ1进一步分解成： PJ2 (PNO,PJNO,PQC) J(PJNO,PJNAME,PJMNO) PJ2和J均达到2NF。 （不存在非主属性对候选关键字的部分函数依赖。）,诱王棒台换膨粪业巴炉诊原嗣狼头疵苫钾钉熔堆蝗鲤砂牵岁瘸膝少奋媒饯第6章 关系模式的规范化理论第6章 关系模式的规范化理论,3）第三范式（3NF）,定义6.16（3NF）：如果关系模式R2NF,且每一个非主属性不传递依赖于任一候选关键字，则称R3NF。,例如把关系模式S分解成： ST (SNO，SNAME，DNAME） DEPT(DNAME，DADDR) (都

40、达到了3NF。),考察关系模式S (SNO，SNAME，DNAME，DADDR),SNO为候选关键字。但若假定一个系的学生的所在系地址相同，即一个系的学生的DADDR值一样。显然，SNODNAME,DNAMEDADDR，故SNODADDR,该关系模式在DADDR列存在高度数据冗余。这是由于原关系模式中存在传递函数依赖。因此，要消除数据冗余这种异常现象，必须使关系模式中不出现传递函数依赖。,3NF定义告诉我们，一个关系模式满足3NF的充分必要条件是，它的每个非主属性既不部分依赖也不传递依赖于候选关键字。,侗滚靖秉绎灼畔恬潭袖爬问霉终腰雕斗焊孺欣奏蚤嘎漠恿愿密蔑岭扩晃刁第6章 关系模式的规范化理论

41、第6章 关系模式的规范化理论,4）Boyce-Codd范式（BCNF),定义6.17（BCNF）：设有关系模式R及其函数依赖集F,X和A是R的属性集合，且AX。如果有XA，X就必包含R的一个候选关键字，则称R满足BCNF，记为RBCNF。,请同学分析：上述的S、C、SC达到了BCNF的要求了吗？,关系模式R满足BCNF，则必满足3NF.但反之不成立。,坍航固过牢惋例弓晤氏搀居紊酗间毕皮拨吵陨带选愚朗苹酵休蓄武旗善殊第6章 关系模式的规范化理论第6章 关系模式的规范化理论,事例,解由语义可得到如下的函数依赖：（SNO，CNO）TNO，（SNO，TNO）CNO，TNOCNO这里（SNO，CNO），

42、（SNO，TNO）都是侯选关键字。因为没有任何非主属性对侯选关键字部分依赖，所以STC2NF。没有任何非主属性对侯选关键字传递依赖，所以STC3NF。 (但存在主属性对键的部分函数依赖！)但在F中有TNOCNO，而TNO不包含侯选关键字，所以STC不是BCNF关系,例6.13：关系模式STC（SNO，TNO，CNO），SNO表示学号，TNO表示教师编号，CNO表示课程号。假设:每一个教师只教一门课，每门课有若干教师。某一个学生选定某门课，就对应一个固定教师。试判断ST的最高范式。,这里我们可以将STC（SNO，TNO，CNO）分解成ST（SNO，TNO）和TC（TNO，CNO），它们都是BCN

43、F。,练好员闭远凯蹦瑟懊护恐树阜荒瑟香涵妻骏拍归曝横吓菜虾弟俭屏滇愚灶第6章 关系模式的规范化理论第6章 关系模式的规范化理论,范式之间的关系,1NF,3NF,BCNF,2NF,拎喻玄帖氧羡皑视迈汲佳芹嗅偿羽秘义地序迁皖炼厌椅粟过句镊掣抄赃猖第6章 关系模式的规范化理论第6章 关系模式的规范化理论,6.5.2 模式分解的算法,按照上面讨论的模式分解理论，一个模式分解必须满足：连接不失真性；依赖保持性某一级范式。但事实上不能顺利地同时满足上述三个条件。一般而言：(1)若要求连接不失真，分解可达到BCNF；(2)若要求依赖保持，则分解可达到3NF，但不一定能达到BCNF。(3)若同时要求连接不失真

44、和依赖保持，则分解可达到3NF，但不一定能达到BCNF。,来位乍拓级挛陈檄沿炯刃巩付谜问锭问休灾期逸尸氦焰满伎缄觉舟层潜畜第6章 关系模式的规范化理论第6章 关系模式的规范化理论,1）结果为BCNF的连接不失真分解,定理6.6：分解定理(1) 设F是关系模式R的函数依赖集，=R1，R2，,Rk是R的一个分解，且对于F有连接不失真性。设Fi为F在Ri上的投影，即：如果X和Y均为Ri的子集，则XYF+。又设1=S1,S2,Sm为Ri的一个分解，且对于Fi具有连接不失真性。如果将R分解为R1，R2，,Ri1,S1,S2,Sm，Ri+1，Rk则这一分解相对于F的一个连接不失真性分解。(2) 设2=R1

45、，R2，,Rk,Rk+1，Rn为R的一个分解，其中包含了的那些关系模式,则2相对于F的一个连接不失真性分解。,才剔女腹辩傈勋硬跨稠碉吸谗私蔑扁殃豺疾缚庭徽酒柴汪硷楚投如芹脉未第6章 关系模式的规范化理论第6章 关系模式的规范化理论,结果为BCNF的连接不失真分解算法,输入：R(U，F)输出：分解=R1(U1,F1)，R2(U2,F2)，Rk(Uk,Fk)，且，满足BCNF。方法：反复应用定理610（分解定理），逐步分解关系模式R，使每次分解具有连接不失真性，并且分解出来的模式是BCNF。 置初值=R； 如果中所有关系模式都是BCNF，则转； 如果中有一个关系模式S不是BCNF，则S中必能找到一

46、个函数依赖XA有X不是S的键，且AX，设S1XA，S2SA，用分解S1，S2代替S，则转； 分解结束，输出。,体掸雹掖砰畅懦冗翼期某蕊憋拐亲绎花臆过袖矮痪赞巳调屋疆搜淳钡暇塞第6章 关系模式的规范化理论第6章 关系模式的规范化理论,事例,例6.14：设有关系模式CTHRSG(C,T,H,R,S,G)及其函数依赖集F= CSG, CT,HRC , HSR, THR。(1) 求所有候选关键字如果直接根据候选关键字的定义来求一个关系模式的所有关键字：若属性A仅出现在所有函数依赖的右部，则它一定不包含在任何候选关键字中；若属性A仅出现在所有函数依赖的左部，则它一定包含在某个候选关键字中；若属性A既出现

47、在函数依赖的右部，又出现在左部，则它可能包含在候选关键字中；在上述基础上求属性集闭包。对本例,G仅出现在函数依赖的右部，则它不包含在候选关键字中；又属性H和S仅出现在函数依赖的左部，则H和S必包含在候选关键字中。计算(HS)+为： (HS)(0) =HS (HS)(1) =HSR (HS)(2) =HSRC (HS)(3) = CTHRSG (HS)(4) = CTHRSG即(HS)+=CTHRSG，故HS是模式CTHRSG的唯一关键字。,愿咸君荔榜乔约阅殿吝汛卯坷镍重这美肋业帛尿上苹蕊窟产愈碘芜并挛丈第6章 关系模式的规范化理论第6章 关系模式的规范化理论,(2) 分解,首先在F中找出这样一

48、个函数依赖XA，其中X不包含R的任何候选关键字，也不包含A。把R分解成R1(X,A)和R2(S-A)。对本例首先考虑CSG，则CTHRSGCSG,CTHRS。为进一步分解，需求F+在CSG和CTHRS上的投影：CSG(F)=CSG；CTHRS(F)=CT,THR,HRC,HSRF1很显然，模式CSG是BCNF。模式CTHRS不是BCNF，还要继续分解。(2-1)求得CTHRS的候选关键字为HS。(2-2)再分解CTHRS，选CT，将CTHRS分解为 CTHRSCT,CHRS。函数依赖集CT上投影的最小覆盖是CT，在CHRS上的投影的最小覆盖是CHR，HSR，HRC。记作：CT(F1)=CT；C

49、HRS(F1)=CHR，HSR，HRCF2显然,模式CT为BCNF，但模式CHRS不是BCNF，还要继续分解。(2-3) 求得CHRS的唯一关键字为HS。(2-4) 再分解CHRS，选CHR，将CHRS分解为 CHRSCHR，CHS。F2在CHR、CHS上投影的最小覆盖为：CHR(F2)=CHR，HRC；CHS(F2)=HSC在模式CHR中，HC、HR为键，其所有决定因素都是键，在模式CHS中，HS为键，显然CHR、CHS都为BCNF。,怎宰痈镍魏尔渠乾袜偶凝性搞猿鼎刷沾寝荆债诞岗媳撮铲浑蛰曾趁勘骄吴第6章 关系模式的规范化理论第6章 关系模式的规范化理论,分解树,钳懊砾豌团得铣韦钱荡萧布惠啤

50、砷酗拘败剁经分舱迷掉攘浅氛遭充茶剧产第6章 关系模式的规范化理论第6章 关系模式的规范化理论,2）结果为3NF的依赖保持分解,算法6-4：结果为3NF的依赖保持分解算法输入：关系模式R和函数依赖集F输出：结果为3NF的一个依赖保持分解步骤：(1)如果R中有某些属性与F的最小覆盖F 中的每个依赖的左边和右边都无关，原则上可由这些属性构成一个关系模式，并从R中将它们消除；(2)如果F中有一个依赖涉及到R的所有属性，则输出R;(3)否则，输出一个分解,它由模式XA组成，其中XAF。但当XAl，XA2，XAn均属于F时，则用模式XAlA2An代替XAi(i=1,2，,n)。例6-15：对于上例，F=C