最新第6章 关系形式的标准化实际

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

玲替悄混牡凑窗蹭罐廖鼓鞍德尉淘幌爱颖液瞩含蠢虑距桌馒腆宝嗽堑赛锄第6章关系模式的规范化理论第6章关系模式的规范化理论关系模式的规范化理论6.1关系模式设计中的问题6.2函数依赖6.3函数依赖的公理系统6.4关系模式的分解及其问题6.5关系模式的规范化6.6多值函数依赖与4NF本章小结哲披呼腰逃斧哼替砖搅疵檄筹每隋唤卑李移扩耐赴束稀疡剐社阎讶胰恳键第6章关系模式的规范化理论第6章关系模式的规范化理论6.1关系模式设计中的问题假设需要设计一个学生学习情况数据库StuDB。下面我们以模式S_C_G（S#，SN，SD，SA，C＃，CN，G，PC＃）为例来说明该模式存在的问题。下表是其一个实例。S#SNSDSAC＃CNPC＃G0001张华计算机17C101离散数学C11050001张华计算机17C102数据结构C10150001张华计算机17C105数据库原理C10230002李明信息管理19C103操作系统C10230002李明信息管理19C105数据库原理C10230003刘强计算机18C107汇编语言C1104（1）冗余度大：同样的数据被多次重复存储。（2）操作异常由于数据的冗余，在对数据操作时会引起多种异常：插入异常:应该能插入的数据，但无法插入删除异常：不该被删除的数据，却被删掉修改异常：修改数据，很困难，容易造成遗漏或出错。瑚唱呼迂烁眼帝掳参妙藐驶拣浊琵听犯早厌晰州信远赖帚决蔽猛轨锨运测第6章关系模式的规范化理论第6章关系模式的规范化理论关系模式的分解我们采用分解的方法，将上述S_C_G分解成以下三个模式：S（S＃，SN，SD，SA）C（C＃，CN，PC＃）S_C（S＃，C＃，G）(让每个模式表达单一的概念信息)关系SS#SNSDSA0001张华计算机170002李明信息管理190003刘强计算机18关系CC＃CNPC＃C101离散数学C110C102数据结构C101C103操作系统C102C105数据库原理C102C107汇编语言C110关系S_CS#C＃G0001C10150001C10250001C10530002C10330002C10530003C1074这三个模式，冗余度小，也消除了各类异常硼刘啼济陀荫只京黎庙入这问磨恿币片薛弦姆俊沸邵柠菱桩指崇早岛腹屡第6章关系模式的规范化理论第6章关系模式的规范化理论6.2函数依赖1）函数依赖(FunctionalDependency，简称FD)在上述的关系模式S和SC，存在以下函数依赖：S#→SDS＃→SNS＃→SA（S＃,C＃）→G定义6.1（函数依赖）：设有关系模式R(U)，其中U={A1，A2，…，An｝是关系的属性全集，X、Y是U的属性子集，设t和u是关系R上的任意两个元组，如果t和u在X的投影t[X]=u[X]推出t[Y]=u[Y]，即：t[X]＝u[X]=>t[Y]＝u[Y]则称X函数决定Y，或Y函数依赖于X。记为X→Y。每火辆剪狗磊壬伯沼瘸爵瓶暴担婪杯烹凹睫墨咯愉淹低她竭苫百嘻辛都谩第6章关系模式的规范化理论第6章关系模式的规范化理论2）几种类型的函数依赖例如X→Φ,X→X,XZ→X等都是平凡函数依赖。定义6.2（非平凡函数依赖、平凡函数依赖）：一个函数依赖X→Y如果满足Y⊈X，则称此函数依赖为非平凡函数依赖，否则称为平凡函数依赖。定义6.3（完全函数依赖、部分函数依赖）：设X、Y是关系R的不同属性集，若X→Y（Y函数依赖于X），且不存在X’⊂X

，使X’→Y，则称Y完全函数依赖于X，记为；否则称Y部分函数依赖于X，记为。例如，在上例关系S中,是完全函数依赖;、是部分函数依赖。富愁篱谢靶泄纂谜粥饺月酶吻琶驯摘若脑烤馋伐森描萨酶肯炸绸项并股琉第6章关系模式的规范化理论第6章关系模式的规范化理论几种类型的函数依赖在属性Y与X之间，除了完全函数依赖和部分函数依赖关系等直接函数依赖，还存在间接函数依赖关系。如果在关系S中增加系的号码DT，从而有S#→SD,SD→DT，于是S#→DT。在这个函数依赖中，DT并不直接依赖于S#，是通过中间属性SD间接依赖于S#。这就是传递函数依赖。定义6.4（传递函数依赖）：设X、Y、Z是关系模式R(U)中的不同的属性集，如果X→Y，Y→X，Y→Z，则称Z传递依赖于X，否则，称为非传递函数依赖。沏湿进遁壬跪搪巍县迂纤兑休沃亥淑褥崎逞仍虫友训凳菠皋棚搏怒会纷恐第6章关系模式的规范化理论第6章关系模式的规范化理论3）关系的关健字和超关键字一个包含了关键字的属性集合也能够函数决定（但不是完全函数决定，而是部分决定）属性全集，我们把这种包含了关键字的属性集合称为超关键字(SuperKey)。例如，在上例的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章关系模式的规范化理论6.3函数依赖的公理系统6.3.1函数依赖的逻辑蕴涵6.3.2Armstrong公理系统

函数依赖集的等价与覆盖筑撕恿晒释臭健菱站难脱帘掐餐猜槐亿沽焦豹谗肛绸兰蔽咎猎继叛挑话附第6章关系模式的规范化理论第6章关系模式的规范化理论6.3.1函数依赖的逻辑蕴涵例如在上述的传递函数依赖中，由X→Y，Y→Z，推导出X→Z，这可以表示为：｛X→Y，Y→Z｝⊨X→Z其中:⊨表示逻辑蕴涵。一般地讲，函数依赖的逻辑蕴涵定义如下：定义6.6（逻辑蕴涵）：设F是由关系模式R(U)满足的一个函数依赖集，X→Y是R的一个函数依赖，且不包含在F，如果满足F中所有函数依赖的任一具体关系r，也满足X→Y，则称函数依赖集F逻辑地蕴涵函数依赖X→Y，或称X→Y可从F推出。可表示为：F⊨X→Y扶板惟踞磺骂捡炽情林组涂婚蓄女絮条勘厌您瘁罚诚滇痢佳蛙寂垛痢挥诞第6章关系模式的规范化理论第6章关系模式的规范化理论函数依赖集F的闭包F+定义6.7：函数依赖集F所逻辑蕴涵的函数依赖的全体称为为F的闭包（Closure），记为F+，即F+＝｛X→Y｜F⊨X→Y｝例如，有关系R（X，Y，Z），它的函数依赖集F＝｛X→Y，Y→Z｝，则其闭包F+为：钦辞脉音和录摄轨痊恳呀锭恰碍剐守扭劣挎秆等汉罚翁螺堪第技郡烟枣社第6章关系模式的规范化理论第6章关系模式的规范化理论6.3.2Armstrong公理系统1）独立推理规则即下面给出的Armstrong公理的三条推理规则是彼此独立的。（3）A3：传递律(Transitivity)如果X→Y且Y→Z，则X→Z成立。

（2）A2：增广律(Augmentation)如果X→Y，且ZW，则XW→YZ成立。根据A2可以推出XW→Y、XZ→YZ或XW→YW、X→XY、XY→X等。

（1）A1：自反律(Reflexivity)如果Y

X，则X→Y成立，这是一个平凡函数依赖。

根据A1可以推出X→Ф、U→X等平凡函数依赖（因为ФXU）。向唾汇荔泽壳濒釉河授敌馒坍道早绕窝驴化疯赶焊铬剐痘改菠燃李迎譬职第6章关系模式的规范化理论第6章关系模式的规范化理论2）其他推理规则推论1：合并规则(TheUnionRule)｛X→Y，X→Z｝⊨X→YZ推论3：伪传递规则(ThePseudoTransitivityRule)｛X→Y，WY→Z｝⊨XW→Z证：（1）X→Y⊨X→XY（A2增广律）X→Z⊨XY→YZ（A2增广律）由上可得X→YZ（A3传递律）（3）X→Y⊨WX→WY（A2增广律）WY→Z（给定条件）由上可得XW→Z（A3传递律）（2）Z

Y⊨Y→Z（A1自反律）X→Y（给定条件）由上可得X→Z（A3传递律）推论2：分解规则(TheDecompositionRule)如果X→Y，ZY，则X→Z成立箕梢乐邯谨寇钩填盂奋哦芥颖蕴害番农椎轰匙矮碑升贝处郭岳丧述煞熟鸭第6章关系模式的规范化理论第6章关系模式的规范化理论一个重要定理例6.2：设有关系模式R(A,B,C,D,E)及其上的函数依赖集F=｛AB→CD,A→B,D→E｝，求证F必蕴涵A→E。定理6.1：若Ai(i=1，2，…,n)是关系模式R的属性，则X→(A1，A2，…,An)成立的充分必要条件是X→Ai均成立。证明：∵A→B（给定条件）∴A→AB（A2增广律）∵AB→CD（给定条件）∴A→CD（A3传递律）∴A→C，A→D（分解规则）∵D→E（给定条件）∴A→E（A3传递律）证毕。凸疮肝票刨热覆出碘酱蟹覆馒坡绸沾绘滥郁棕忙谰痰盐袖贷论孪宾思源赤第6章关系模式的规范化理论第6章关系模式的规范化理论属性集闭包定义6.8（属性集闭包）:设有关系模式R(U),U={A1，A2，…,An},X是U的子集,F是U上的一个函数依赖集，则属性集X关于函数依赖集F的闭包定义为：＝｛Ai｜Ai∈U，且X→Ai可用阿氏公理从F推出｝例：设关系模式R(A,B,C)的函数依赖集为F=｛A→B,B→C｝，分别求A、B、C的闭包。解：若X＝A，

∵A→B,B→C（给定条件）

∴A→C（A2传递律）

∵A→A（A1自反律）

∴={A，B，C}（据定义）若X=B

∵B→B（A1自反律）B→C（给定条件）

∴={B，C}（据定义）若X=C，C→C（自反律）∴={C}（据定义）嗜低毋备啼涕仰赂敞琶嘻瓦瑚近封碳宙山衬酞损规遭虱了葛叔糟释佛睛并第6章关系模式的规范化理论第6章关系模式的规范化理论定理6.2:设F是关系模式R(U)上的函数依赖集,U是属性全集，X,Y

U,则函数依赖X→Y是用阿氏公理从F推出的，充分必要条件是Y

；反之，能用阿氏公理从F推出的所有X→Y的Y都在中。这个定理告诉我们，只要Y

，则必有X→Y。于是，一个函数依赖X→Y能否用阿氏公理从F推出的问题，就变成判断Y是否为子集的问题。下面介绍一下计算的算法。叭歇喊朵臼述獭沃撼腻民煞续哨厄蛙戏涛诱液幌枚并总誊潜爬寞险焕耪畔第6章关系模式的规范化理论第6章关系模式的规范化理论属性集的闭包计算方法：根据下列步骤计算一系列属性集合X(0)，X(1)，…(1)令X(0)=X，i＝0；(2)求属性集/*在F中寻找满足条件V⊆X(i)的所有函数依赖V→W,并记属性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(XU)关于U上的函数依赖集F的闭包。输入：属性全集U,U上的函数依赖集F,以及属性集XU。输出：X关于F的闭包。踏次缓抒礁痢科缝整杂徽此讨死挥湾正蘑有旧煮鸦友闻就孔漱府者五强漓第6章关系模式的规范化理论第6章关系模式的规范化理论算法6.1的求解过程例：设F＝｛AH→C，C→A，EH→C，CH→D，D→EG，CG→DH，CE→AG，ACD→H｝，令X＝DH，求。最后，＝(DH)+=｛ACDEGH｝。解：①X(0)=X=DH②在F中找所有满足条件V

X(0)=DH的函数依赖V→W，结果只有D→EG，则B=EG，于是X(1)＝X(0)∪B=DEGH。

③判断是否X(i+1)=X(i)，显然X(1)≠X(0)。④在F中找所有满足条件V

X(1)=DEGH的函数依赖V→W，结果为EH→C，于是B=C，则X(2)＝X(1)∪B=CDEGH。⑤判断是否X(i+1)=X(i)，显然X(2)≠X(1)。⑥在F中找所有满足条件V

X(2)=CDEGH的函数依赖V→W，结果为C→A，CH→D，CG→DH，CE→AG，则B=ADGH，于是X(3)＝X(2)∪B=CDEGH∪B=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中再也找不到满足条件VX(i)的函数依赖V→W。腮粥鼻蜕虚勾扼琵正蛋特伙咳穆汀打弗俏谚侧研伦臼烽寝篇圃涪虱卉阅遂第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+。如若有X→Y∈F,则计算,如果Y

,则X→Y∈G+;第二步：同第一步，检查是否G

F+;第三步：如果F

G+，且G

F+，则F与G等价。由此可见,F和G等价的充分必要条件是：F

G+，且G

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

证明：构造G＝｛X→A｜X→Y∈F且A∈Y｝由A∈Y，X→Y∈F根据分解规则导出，从而等到G

F+。反之，如果Y＝A1A2…An，而且X→A1，X→A2，…X→An在G中可根据合并律等到F

G+。由此可见，F与G等价，即F被G覆盖。属客瓮贸桓铅巡马笋碑壁汛蓟袁弯讥蒜量惹烦殉恿凹恤蚁裁勒力辈断颇抡第6章关系模式的规范化理论第6章关系模式的规范化理论最小函数依赖集定义6.10（最小函数依赖集）:函数依赖集F如果满足下列条件，则称F为最小函数覆盖，记为Fmin：(1)F中每一个函数依赖的右部都是单个属性。(2)对F中任一函数依赖X→A，F－｛X→A｝都不与F等价。(3)对于F中的任一函数依赖X→A,｛F－｛X→A｝｝∪｛Z→A｝都不与F等价，其中Z为X的任一子集。求函数依赖集F的最小覆盖的方法是：(1)检查F中的每个函数依赖X→A,若A=A1,A2,…,Ak,则根据分解规则，用X→Ai(i=1，2，…，k)取代X→A。(2)检查F中的每个函数依赖X→A,令G=F－｛X→A｝，若有A∈，则从F中去掉此函数依赖。(3)检查F中各函数依赖X→A，设X=B1,B2,…,Bm,检查Bi，当A∈时，即以X－Bi替换X。赵慨铜负署捡拖发拢悍声痊古蝗光商涂劳脏舵混俗贺皆桩币吹浴怨恿谊包第6章关系模式的规范化理论第6章关系模式的规范化理论最小覆盖的求解事例例6.5：求下列函数依赖集的最小覆盖：F＝｛AH→C，C→A，CH→D，C→EG，EH→C，CG→DH，CE→AG，ACD→H｝。解：(1)用分解规则将F中的所有依赖的右部变成单个属性，可以得到以下11个函数依赖：AH→C，C→A，CH→D，ACD→H（给定）C→E，C→G（由C→EG分解得到）EH→C（给定）CG→H，CG→D（由CG→DH分解得到）CE→A，CE→G（由CE→AG分解得到）(2)根据阿氏公理去掉F中的冗余依赖由于从C→A可推出CE→A，从C→A、CG→D、ACD→H推出CG→H，因此CE→A和CG→H是冗余，可从F删除。(3)用所含属性较少的依赖代替所含属性较多的依赖。由于C→A,ACD→H中A是冗余属性，因此，可用CD→H代替ACD→H，故删除ACD→H。最后得到F的最小覆盖为：F＝｛AH→C，C→A，CH→D，CD→H，C→E，C→G，EH→C，CG→D，CE→G｝葛雌充畴已震攻肄叉扩尸窖榔妻享友襄厩馒禄卜寿户悟蓝猾绝绩馁邹妒唉第6章关系模式的规范化理论第6章关系模式的规范化理论6.4关系模式的分解及其问题6.4.1什么叫模式分解6.4.2分解的无损连接性

保持函数依赖性扇惭怂翻画比骆沽舍拐拈娥兰则砧第关烛锥氟悲训郁辱枯蔡匪篷旱磁啪芬第6章关系模式的规范化理论第6章关系模式的规范化理论6.4.1什么叫模式分解例6.6：设在模式R(U,F)中U＝｛SNO，SNAME，DNAME，DADDR｝F＝｛SNO→SNAME，SNO→DNAME，DNAME→DADDR｝如果对R作如下分解（方法1）：ρ=｛R1（{SNO,SNAME},{SNO→SNAME}），R2（{DNAME，DADDR},{DNAME→DADDR}）｝定义6.11（模式分解）：关系模式R(U，F)的一个分解ρ是若干个关系模式的一个集合：ρ=｛R1(U1,F1),R2(U2,F2),…,Rn(Un,Fn)｝式中：(1)。

(2)对每个i，j（1≤i,j≤n）有。(3)Fi(i=1，2，…,n)是F在Ui上的投影，即

叭夫下狡媒拿怔钟石眉踢离搏汝奠厘志肝嚏祝晦瞩毡越褐膛氧辛芭羞驼横第6章关系模式的规范化理论第6章关系模式的规范化理论（1）连接不失真问题（a）原关系RSNOSNAMEDNAMEDADDR0001张华计算机D10002李明信息管理D20003刘强计算机D1（b）方法1：关系R1SNOSNAME0001张华0002李明0003刘强（c）方法1：关系R2DNAMEDADDR计算机D1信息管理D2（d）方法1：关系R1×R2SNOSNAMEDNAMEDADDR0001张华计算机D10001张华信息管理D20002李明计算机D10002李明信息管理D20003刘强计算机D10003刘强信息管理D2娱儡屯痒短抓搜洋肪闹尝驭民镁站诲炕氨霞齐碗该蚤饰霹氯便求依刁孜嘴第6章关系模式的规范化理论第6章关系模式的规范化理论方法2：假设按下列方法对R进行分解ρ={R1({SNO,SNAME,DNAME},{SNO→SNAME,SNO→DNAME}),R2（{DNAME,DADDR}），{DNAME→DADDR}）}（a）原关系RSNOSNAMEDNAMEDADDR0001张华计算机D10002李明信息管理D20003刘强计算机D1（e）方法2：关系R1（f）方法2：关系R2DNAMEDADDR计算机D1信息管理D2SNOSNAMEDNAME0001张华计算机0002李明信息管理0003刘强计算机（g）方法2：R1⋈R2

SNOSNAMEDNAMEDADDR0001张华计算机D10002李明信息管理D20003刘强计算机D1豆势泥初五屑嫌朵服锡洋酸爽际夺卸忻奋垂烛易示咏晨啡塔汀凹驱唐巨艇第6章关系模式的规范化理论第6章关系模式的规范化理论（2）依赖保持问题上例方法1：F＝｛SNO→SNAME，SNO→DNAME，DNAME→DADDR｝F1∪F2＝｛SNO→SNAME，DNAME→DADDR｝F+＝{SNO→SNAME,SNO→DNAME,DNAME→DADDR,SNO→DADDR}(F1∪F2)+＝｛SNO→SNAME，DNAME→DADDR｝一个关系模式经分解后，其函数依赖集F也随之被分解，则分解后的依赖集Fi并集是否能保持原有的函数依赖关系？即?若出现，说明分解后有些函数依赖被丢失了。

上例方法2：F＝｛SNO→SNAME，SNO→DNAME，DNAME→DADDR｝F1∪F2＝｛SNO→SNAME,SNO→DNAME,DNAME→DADDR｝F+＝{SNO→SNAME,SNO→DNAME,DNAME→DADDR,SNO→DADDR}(F1∪F2)+＝{SNO→SNAME,SNO→DNAME,DNAME→DADDR,SNO→DADDR}再萌窖腮宾岛该信饼烘阻渺觉铂普贸沿炕朽洲乡诛渔炒肪灸俊搏瘁菜孪客第6章关系模式的规范化理论第6章关系模式的规范化理论6.4.2分解的无损连接性1）无损连接分解的定义定义6.12（无损连接分解，即连接不失真分解）：设关系模式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的一个分解，r是R的任一关系，（1≤i≤k）,那么有：①；②如果s=mρ(r)，则，或③mρmρ(r)=mρ(r)儡用庚悸然貌巍歪搬颈迂痛腑厢揭换后渴蒸龟春坠施怒胰肃持褥余订奋癌第6章关系模式的规范化理论第6章关系模式的规范化理论②由定理6-5①可知，可得到，即（因为s=mρ(r)）（也就是两边同时在Ui上投影，得）。为了证明。假设，则s中必存在满足t[Ri]=ti的元组t。由于t∈s,对每个j,在rj中必存在元组uj满足t[Rj]=uj(1≤j≤k),即。于是对那个特定的i，亦有t[Ri]=ui，即t[Ri]∈ri。但t[Ri]=ti，所以ti∈ri，从而得到（即）。由和可得（即）。③由定理6-5①可知(i=1,2,…,k)，于是有。此式左式＝mρ(s)=mρmρ(r)（由②得），右式＝＝mρ(r)，因此得：mρmρ(r)=mρ(r)该定理③说明，关系模式只有在第一次分解的连接恢复后有可能丢失信息，此后的多次分解恢复均能使分解不失真证明：①设任意一个元组t∈r,ti=t[Ui](i=1,2,…,k);则ti∈Ri。根据自然连接定义，可知t在中，即t∈mρ(r)，所以。该定理①说明，一个关系模式经分解再连接恢复所得的新关系mρ(r)的元组一般比原关系的元组要多，而且mρ(r)一定包括原关系的元组。只有当r=mρ(r)时，分解才是连接不失真分解。壮泽冉维磷操忍偏沁绪掩封贺殴摊窍呼凰哆胖收剐摹肥郸靡些鼓暗娶蜗阑第6章关系模式的规范化理论第6章关系模式的规范化理论2）无损连接的检验方法1：采用检验表格构造法算法6.2：连接不失真检验方法 1：(1)构造一个n列k行表，每一行对应于一个模式Ri（1≤i≤k），每一列对应于一个属性Aj（1≤j≤n），如下表所示。A1A2…AnR1

R2

…

Rk

(2)初始表（填表）：若Aj∈Ri，则第i行第j列上填入aj，否则填入bij。(3)修改表：反复检查F中的每一个函数依赖X→Y，按下方法修改表格中的元素：取F中的函数依赖X→Y，检查Y中的属性所对应的列，找出X相等的那些行，将这些X的符号相同的行中的Y的属性所对应的符号改成一致。即如果其中有aj，则将bij改为aj；若无aj，则将它们全改为bij。一般取i是为其中的最小行号值。(4)如发现某一行变成a1，a2，…,ak，则此分解ρ具有连接不失真性。子戒藩狰捣杭酷饭开颠师拾甚龙惭邪耳您释海粗孔漾翱甭绒炬腮硬澈数亿第6章关系模式的规范化理论第6章关系模式的规范化理论事例说明例：设有R(U,F)，其中：U=(A,B,C,D,E),F=(A→C,B→C,C→D,DE→C,CE→A)，R的一个分解为：ρ＝{R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}是否无损分解？根据算法6.2中(1)和(2)构造初始表，如表(a)所示。根据A→C，对表(a)进行处理，将b13、b23、b53改成同一符号b13，即b13＝b23＝b53。再根据B→C，将b33、b13（R2中）改成同一符号b13。修改后如表(b)所示。考虑C→D，根据上述修改原则，将D所在的第4列的b24、b34、b54均修改成a4，其结果如表（c）所示。(因为A→C,B→C)再考虑DE→C，根据修改原则，将C所在的第3列第3、4、5行的b13、a3、b13均修改成a3，其结果如表（d）所示。(因为B→C,A→C,C→D)再考虑CE→A，根据修改原则，将A所在的第1列第3、4、5行的b31（由B→C推出）、b41（由A→C推出）、a1均修改成a1，其结果如表（e）所示。

表(a)初始表格ABCDER1:ADa1b12b13a4b15R2:ABa1a2b23b24b25R3:BEb31a2b33b34a5R4:CDEb41b42a3a4a5R5:AEa1b52b53b54a5表(b)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13b24b25R3:BEb31a2b13b34a5R4:CDEb41b42a3a4a5R5:AEa1b52b13b54a5表(c)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13a4b25R3:BEb31a2b13a4a5R4:CDEb41b42a3a4a5R5:AEa1b52b13a4a5表(d)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13a4b25R3:BEb31a2a3a4a5R4:CDEb41b42a3a4a5R5:AEa1b52a3a4a5表(e)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13a4b25R3:BEa1a2a3a4a5R4:CDEa1b42a3a4a5R5:AEa1b52a3a4a5俩瞪贩洒血农施解垣遭盈先街餐魁经岁垫兄峨吴泄芬混夷坑脖袒讳促番膨第6章关系模式的规范化理论第6章关系模式的规范化理论简单的检验方法方法2：定理6.5：设ρ=｛R1,R2｝是关系模式R的一个分解，F是R的一个函数依赖集，则对于F,ρ具有连接不失真性的充分必要条件是R1∩R2→R1－R2∈F+，或R1∩R2→R2－R1∈F+。例6.8：设有关系模式R({S＃,SN,C＃,G}，{S＃→SN,(S＃,C＃)→G})的一个分解为：ρ={R1({S＃,SN},{S＃→SN})，R2({S＃,C＃,G},{(S＃,C＃)→G})}因为R1∩R2=S#，R1－R2=SN，故R1∩R2→R1－R2，且S#→SN属于F，所以该分解具有连接不失真性。定理6-8和例6-9告诉我们一个事实：如果两个关系模式间的公共属性集至少包含其中一个关系模式的关键字，则此分解必定具有连接不失真性。颓矿肇永汁殖接轨还娶阮惨柴俩略熔耳年灯液氓气敢甄镁鉴难忽襟些奠胰第6章关系模式的规范化理论第6章关系模式的规范化理论6.4.3函数依赖保持性定义6.13：设有关系模式R,F是R上的函数依赖集，Z是R上的一个属性集合，则称Z所涉及到的F+中的所有函数依赖为F在Z上的投影，记为∏z(F)。该定义实质上是，当X→Y∈F+时，若XY⊆Z，则有∏z(F)，可以定义为：定义6-17：设关系模式R的一个分解为ρ=｛｛R1,F1｝，｛R2,F2｝，…，｛Rk,Fk｝｝,F是R上的依赖集，如果对于所有的i=1,2,…,k，∏z(F)中的全部函数依赖的并集逻辑地蕴涵F中的全部依赖，则称分解ρ具有依赖保持性。趴迸八术缆胖寒挥遭钳灌崔粟粮氰滇动旷谜庭汕暖邹食腔肥镐恶该似叭架第6章关系模式的规范化理论第6章关系模式的规范化理论判断两个函数依赖集是否等价的方法也可以用来判断一个分解是否保持依赖。下面以一个例子来说明一下。：设R(A,B,C,D)，F＝{A→B,C→D}，ρ=｛R1({A,B}，{A→B})，R2（{C,D}，{C→D}）｝。因为F＝{A→B,C→D}，F1∪F2＝{A→B,C→D}所以F+=(F1∪F2)+该例还说明，一个具有依赖保持性的分解不一定具有连接不失真性。反之，一个连接不失真分解也不一定具有依赖保持性。例：设R(A,B,C)，F＝｛A→B，C→B｝，ρ=｛R1({A,B}，{A→B})，R2（{A,C}，{A→C}）｝。R1∩R2=A,R1－R2=B，R2－R1=CR1∩R2→R1－R2=A→B∈F但F＝{A→B,C→B}，F1∪F2＝{A→B,A→C},即F+≠(F1∪F2)+可见具有连接不失真性，但不具有依赖保持性。葛咯推甭钟娘迭恕址式轻滤籽谁依钡臭援徽帘诡绵噶谭蒜灵汀庇均创迢蜜第6章关系模式的规范化理论第6章关系模式的规范化理论范式的概念是由E.F.Codd在1970年首先提出来的。满足特定要求的模式称之为范式。所谓模式规范化，就是把关系模式规范到某一级范式,目的是：(1)消除异常现象。(2)方便用户使用，简化操作。(3)加强数据独立性。关系规范化的条件可以分成几级，每一级称为一个范式，记为xNF，其中x表示级别,NF是范式(NormalForm)，即关系模式满足的条件。范式的级别越高，条件越严格，因此有：6.5关系模式的规范化

6.5.1范式募凸庇唐舷茶胳馆阉涟雍漏雅瘟练铝今饿人矾抓指只街掏抗驴投演擂温照第6章关系模式的规范化理论第6章关系模式的规范化理论1）第一范式（1NF）定义6.14（1NF）：如果一个关系模式R的每个属性的域都只包含单纯值，而不是一些值的集合或元组，则称R是第一范式，记为R∈1NF,把一个非规范化关系模式变为1NF有两种方法，一是把不含单纯值的属性分解为多个属性，并使它们仅含单纯值。例如，设模式：P(PNO，PNAME，QOH,PJ(PJNO,PJNAME，PJMNO，PQC））将模式P变为：P(PNO,PNAME,QOH,PJNO,PJNAME,PJMNO,PQC）第二种方法是把关系模式分解，并使每个关系都符合1NF。则：Pl(PNO,PNAME,QOH)PJl(PNO,PJNO,PJNAME,PJMNO,PQC)思考：PJNAME,PJMNO对(PNO,PJNO)函数依赖的类型？便谅衫迸汉凤嫉嫡泊数页隐殆雏庇扣辞父腰彰窿俺吊遮尿钦厅甜咽光骇惧第6章关系模式的规范化理论第6章关系模式的规范化理论2）第二范式（2NF）定义6.15（2NF）：如果关系模式R∈1NF，且它的任一非主属性都完全函数依赖于任一候选关键字，则称R满足第二范式，记为R∈2NF。把一个1NF的关系模式变为2NF的方法是，通过模式分解，使任一非主属性都完全函数依赖于它的任一候选关键字。例如对上例，若把PJ1进一步分解成：PJ2(PNO,PJNO,PQC)J(PJNO,PJNAME,PJMNO)PJ2和J均达到2NF。（不存在非主属性对候选关键字的部分函数依赖。）诱王棒台换膨粪业巴炉诊原嗣狼头疵苫钾钉熔堆蝗鲤砂牵岁瘸膝少奋媒饯第6章关系模式的规范化理论第6章关系模式的规范化理论3）第三范式（3NF）定义6.16（3NF）：如果关系模式R∈2NF,且每一个非主属性不传递依赖于任一候选关键字，则称R∈3NF。例如把关系模式S分解成：ST(SNO，SNAME，DNAME）DEPT(DNAME，DADDR)(都达到了3NF。)考察关系模式S(SNO，SNAME，DNAME，DADDR),SNO为候选关键字。但若假定一个系的学生的所在系地址相同，即一个系的学生的DADDR值一样。显然，SNO→DNAME,DNAME→DADDR，故SNO→DADDR,该关系模式在DADDR列存在高度数据冗余。这是由于原关系模式中存在传递函数依赖。因此，要消除数据冗余这种异常现象，必须使关系模式中不出现传递函数依赖。3NF定义告诉我们，一个关系模式满足3NF的充分必要条件是，它的每个非主属性既不部分依赖也不传递依赖于候选关键字。侗滚靖秉绎灼畔恬潭袖爬问霉终腰雕斗焊孺欣奏蚤嘎漠恿愿密蔑岭扩晃刁第6章关系模式的规范化理论第6章关系模式的规范化理论4）Boyce-Codd范式（BCNF)定义6.17（BCNF）：设有关系模式R及其函数依赖集F,X和A是R的属性集合，且A⊈X。如果有X→A，X就必包含R的一个候选关键字，则称R满足BCNF，记为R∈BCNF。请同学分析：上述的S、C、SC达到了BCNF的要求了吗？关系模式R满足BCNF，则必满足3NF.但反之不成立。坍航固过牢惋例弓晤氏搀居紊酗间毕皮拨吵陨带选愚朗苹酵休蓄武旗善殊第6章关系模式的规范化理论第6章关系模式的规范化理论事例解由语义可得到如下的函数依赖：（SNO，CNO）→TNO，（SNO，TNO）→CNO，TNO→CNO这里（SNO，CNO），（SNO，TNO）都是侯选关键字。因为没有任何非主属性对侯选关键字部分依赖，所以STC∈2NF。没有任何非主属性对侯选关键字传递依赖，所以STC∈3NF。(但存在主属性对键的部分函数依赖！！)但在F中有TNO→CNO，而TNO不包含侯选关键字，所以STC不是BCNF关系例6.13：关系模式STC（SNO，TNO，CNO），SNO表示学号，TNO表示教师编号，CNO表示课程号。假设:每一个教师只教一门课，每门课有若干教师。某一个学生选定某门课，就对应一个固定教师。试判断ST的最高范式。这里我们可以将STC（SNO，TNO，CNO）分解成ST（SNO，TNO）和TC（TNO，CNO），它们都是BCNF。练好员闭远凯蹦瑟懊护恐树阜荒瑟香涵妻骏拍归曝横吓菜虾弟俭屏滇愚灶第6章关系模式的规范化理论第6章关系模式的规范化理论范式之间的关系1NF3NFBCNF2NF消去非主属性对键的部分函数依赖消去非主属性对键的传递函数依赖消去主属性对键的部分函数依赖拎喻玄帖氧羡皑视迈汲佳芹嗅偿羽秘义地序迁皖炼厌椅粟过句镊掣抄赃猖第6章关系模式的规范化理论第6章关系模式的规范化理论6.5.2模式分解的算法按照上面讨论的模式分解理论，一个模式分解必须满足：①连接不失真性；②依赖保持性③某一级范式。但事实上不能顺利地同时满足上述三个条件。一般而言：(1)若要求连接不失真，分解可达到BCNF；(2)若要求依赖保持，则分解可达到3NF，但不一定能达到BCNF。(3)若同时要求连接不失真和依赖保持，则分解可达到3NF，但不一定能达到BCNF。来位乍拓级挛陈檄沿炯刃巩付谜问锭问休灾期逸尸氦焰满伎缄觉舟层潜畜第6章关系模式的规范化理论第6章关系模式的规范化理论1）结果为BCNF的连接不失真分解定理6.6：分解定理(1)设F是关系模式R的函数依赖集，ρ=｛R1，R2，…,Rk｝是R的一个分解，且对于F有连接不失真性。设Fi为F在Ri上的投影，即：如果X和Y均为Ri的子集，则X→Y∈F+。又设ρ1=｛S1,S2,…,Sm｝为Ri的一个分解，且对于Fi具有连接不失真性。如果将R分解为｛R1，R2，…,Ri－1,S1,S2,…,Sm，Ri+1，…，Rk｝则这一分解相对于F的一个连接不失真性分解。(2)设ρ2=｛R1，R2，…,Rk,Rk+1，…，Rn｝为R的一个分解，其中包含了ρ的那些关系模式,则ρ2相对于F的一个连接不失真性分解。才剔女腹辩傈勋硬跨稠碉吸谗私蔑扁殃豺疾缚庭徽酒柴汪硷楚投如芹脉未第6章关系模式的规范化理论第6章关系模式的规范化理论结果为BCNF的连接不失真分解算法输入：R(U，F)输出：分解ρ=｛R1(U1,F1)，R2(U2,F2)，…，Rk(Uk,Fk)｝，且，满足BCNF。方法：反复应用定理6－10（分解定理），逐步分解关系模式R，使每次分解具有连接不失真性，并且分解出来的模式是BCNF。①置初值ρ={R}；②如果ρ中所有关系模式都是BCNF，则转④；③如果ρ中有一个关系模式S不是BCNF，则S中必能找到一个函数依赖X→A有X不是S的键，且A∉X，设S1＝XA，S2＝S－A，用分解｛S1，S2｝代替S，则转②；④分解结束，输出ρ。体掸雹掖砰畅懦冗翼期某蕊憋拐亲绎花臆过袖矮痪赞巳调屋疆搜淳钡暇塞第6章关系模式的规范化理论第6章关系模式的规范化理论事例例6.14：设有关系模式CTHRSG(C,T,H,R,S,G)及其函数依赖集F=｛CS→G,C→T,HR→C,HS→R,TH→R｝。(1)求所有候选关键字如果直接根据候选关键字的定义来求一个关系模式的所有关键字：若属性A仅出现在所有函数依赖的右部，则它一定不包含在任何候选关键字中；若属性A仅出现在所有函数依赖的左部，则它一定包含在某个候选关键字中；若属性A既出现在函数依赖的右部，又出现在左部，则它可能包含在候选关键字中；在上述基础上求属性集闭包。对本例,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中找出这样一个函数依赖X→A，其中X不包含R的任何候选关键字，也不包含A。把R分解成R1(X,A)和R2(S-A)。对本例首先考虑CS→G，则CTHRSG＝｛CSG,CTHRS｝。为进一步分解，需求F+在CSG和CTHRS上的投影：∏CSG(F)=｛CS→G｝；∏CTHRS(F)=｛C→T,TH→R,HR→C,HS→R｝＝F1很显然，模式CSG是BCNF。模式CTHRS不是BCNF，还要继续分解。(2-1)求得CTHRS的候选关键字为HS。(2-2)再分解CTHRS，选C→T，将CTHRS分解为CTHRS＝{CT,CHRS}。函数依赖集CT上投影的最小覆盖是C→T，在CHRS上的投影的最小覆盖是CH→R，HS→R，HR→C。记作：∏CT(F1)=｛C→T｝；∏CHRS(F1)=｛CH→R，HS→R，HR→C｝＝F2显然,模式CT为BCNF，但模式CHRS不是BCNF，还要继续分解。(2-3)求得CHRS的唯一关键字为HS。(2-4)再分解CHRS，选CH→R，将CHRS分解为CHRS＝{CHR，CHS}。F2在CHR、CHS上投影的最小覆盖为：∏CHR(F2)=｛CH→R，HR→C｝；∏CHS(F2)=｛HS→C｝在模式CHR中，HC、HR为键，其所有决定因素都是键，在模式CHS中，HS为键，显然CHR、CHS都为BCNF。怎宰痈镍魏尔渠乾袜偶凝性搞猿鼎刷沾寝荆债诞岗媳撮铲浑蛰曾趁勘骄吴第6章关系模式的规范化理论第6章关系模式的规范化理论分解树CTHRSGkey=HSCS→GC→THR→CHS→RTH→RCTHRSkey=HSC→THR→CHS→RTH→RCSGkey=CS

CS→GCTkey=CC→TCHRkey=CH,HRCH→RHR→CCHRSkey=HS

CH→RHR→CHS→RCHSkey=HSHS→C钳懊砾豌团得铣韦钱荡萧布惠啤砷酗拘败剁经分舱迷掉攘浅氛遭充茶剧产第6章关系模式的规范化理论第6章关系模式的规范化理论

2）结果为3NF的依赖保持分解算法6-4：结果为3NF的依赖保持分解算法输入：关系模式R和函数依赖集F输出：结果为3NF的一个依赖保持分解步骤：(1)如果R中有某些属性与F的最小覆盖F′中的每个依赖的左边和右边都无关，原则上可由这些属性构成一个关系模式，并从R中将它们消除；(2)如果F′中有一个依赖涉及到R的所有属性，则输出R;(3)否则，输出一个分解ρ,它由模式XA组成，其中X→A∈F。但当X→Al，X→A2，…，X→An均属于F′时，则用模式XAlA2…An代替XAi(i=1,2，…,n)。例6-15：对于上例，F′={{C→T,CS→G,HT→R,HR→C,CH→R,HS→R｝,KEY＝HS}所以ρ={CT,CSG,HRT,CHR,HSR}蔷坠番宇晓暗研戌绵拷焚身强派素嗡莫植企涛妈啦柒易钥衡剧锡什笋撬党第6章关系模式的规范化理论第6章关系模式的规范化理论定理6-11：设δ是由结果为3NF的依赖保持分解算法得到的3NF分解，X为R的一个候选关键字，则τ＝δ∪｛X｝是R的一个分解，且τ中的所有关系模式均满足3NF,同时，既具有连接不失真性，又具有依赖保持性。3）结果为3NF且具有依赖保持和连接不失真的分解例：已知R(C,T,H,R,S,G),F′=｛C→T,HR→C,CS→G,HS→R,HT→R｝，KEY=HS，则τ={CT,CSG,HRT,CHR,HSR,HS｝但HSHSR，故τ=｛CT，CSG，HRT，CHR，HSR｝拐体炮粉嘱讶诽乎曼穆鸡崇烬拿格寓榷筑篆苯递褪月洗贞蕾针冶蔓涝搭阔第6章关系模式的规范化理论第6章关系模式的规范化理论6.6多值函数依赖与4NF6.6.1BCNF关系模式存在的问题(CTB是关键字)CTB高等数学张华民高等数学高等数学张华民高等数学教程高等数学王天华高等数学高等数学王天华高等数学教程高等数学林静高等数学高等数学林静高等数学教程普通物理吴刚物理学普通物理吴刚普通物理普通物理吴刚普通物理基础普通物理李晓芳物理学普通物理李晓芳普通物理普通物理李晓芳普通物理基础帮消墓跃沾灌嫁腰方寥两差鹃牛臀讣港哩骑踢药舒撇翼瓷倦俊抒吸擎腕鞘第6章关系模式的规范化理论第6章关系模式的规范化理论6.6.2多值函数依赖为了形式地定义多值依赖，根据上例，构造一个抽象关系R(U)（