第03章关系数据理论精选PPT.ppt

《第03章关系数据理论精选PPT.ppt》由会员分享，可在线阅读，更多相关《第03章关系数据理论精选PPT.ppt（110页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第03章关系数据理论第1页，此课件共110页哦2 23.1 基本概念函数依赖术语和符号为什么要讨论函数依赖？模式分解模式分解第2页，此课件共110页哦3 3函数依赖Y=f(X)函数Y=sin(X)Y=X+1Y=X2+2X+1省=f(城市)姓名=f(学号)?第3页，此课件共110页哦4 4函数依赖的直观定义：如果有一个关系模式R(A1,A2,An)，X和Y为A1,A2,An的子集，那么对于关系R中的任意一个X值，都只有一个Y值与之对应，则称X函数决定Y，或Y函数依赖于X，并用XY表示。第4页，此课件共110页哦5 5例：对仓库关系 仓库(仓库号,城市,面积)有函数依赖：仓库号城市（城市函数依赖于

2、仓库号）仓库号面积（面积函数依赖于仓库号）第5页，此课件共110页哦6 6函数依赖的严格形式化定义定义定义3.1：设有关系模式R(A1,A2,An)，X和Y均为A1,A2,An的子集，r是R的任一具体关系，t1、t2是r中的任意两个元组；如果由t1X=t2X可以推导出t1Y=t2Y，则称X函数决定Y，或Y函数依赖于X，记为XY。第6页，此课件共110页哦定义3.1中特别要注意：只要只要 t1X=t2X t1Y=t2Y就可以推导出就可以推导出:XY 也就是说：只有当也就是说：只有当 t1X=t2X 为真，而为真，而t1Y=t2Y为假时，函数依赖不成立；而当为假时，函数依赖不成立；而当t1X=t2

3、X为假时，不管为假时，不管t1Y=t2Y为真或为假都有为真或为假都有XY成立。成立。当当t1X=t2X 为为真真，t1Y=t2Y为为真真；当当t1X=t2X 为为真真，t1Y=t2Y为为假假；当当t1X=t2X 为为假假，t1Y=t2Y为为真真；当当t1X=t2X 为为假假，t1Y=t2Y为为假假；第7页，此课件共110页哦8 8注意：注意：1 1、函数依赖不是指关系模式、函数依赖不是指关系模式R R的某个或某些关系实例满足的某个或某些关系实例满足的约束条件，而是指的约束条件，而是指R R的所有关系实例均要满足的约束条件。2 2、函数依赖和别的数据之间的依赖关系一样，是语义范畴、函数依赖和别的

4、数据之间的依赖关系一样，是语义范畴的概念，我们只能根据数据的语义来确定函数依赖。的概念，我们只能根据数据的语义来确定函数依赖。例如：例如：“姓名年龄”这个函数依赖只有在没有同名人的条件下成立，如果有相同名字的人，则“年龄”就不再函数依赖于就不再函数依赖于“姓名姓名”了。了。第8页，此课件共110页哦9 9定义3.1 也可以这样来理解：即对于R(U)的任意一个可能的关系实例r,r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称XY。第9页，此课件共110页哦1010术语和符号(1)如果XY，但Y不包含于X，则称XY是非平凡的函数依赖。如不特别说明，我们总是讨论非平凡函数依赖。如

5、：(学号,课程号)成绩如：(学号,所在系)所在系非平凡依赖平凡依赖第10页，此课件共110页哦1111术语和符号(2)如果Y不函数依赖于X，则记作X Y。如学号不函数依赖于性别，则记作性别 学号。第11页，此课件共110页哦1212术语和符号(3)如果XY，则X称作决定因素。如学号所在系，则学号称作决定因素第12页，此课件共110页哦1313 用U表示关系模式R的属性全集，即U=A1,A2,An，用F表示关系模式R上的函数依赖集，则关系模式R可表示为R(U,F)。术语和符号(4)如U=仓库号,城市,面积 F=仓库号城市,仓库号面积则R(U,F)表示仓库关系第13页，此课件共110页哦1414术

6、语和符号(5)如果K是关系模式R(U,F)的任一候选关键字，X是任一属性或属性集，如果XK，则X称为主属性；否则称为非主属性。如(仓库号,器件号)是库存关系的关键字，那么仓库号和器件号均是主属性，而数量为非主属性。第14页，此课件共110页哦1515术语和符号(6)如果XY，并且YX，则可记作XY。第15页，此课件共110页哦1616术语和符号(7)如果XY，并且对于X的一个任意真子集X/都有X/Y，则称Y完全函数依赖于X，并记作 ；如果X/Y成立，则称Y部分函数依赖于X，并记作 。如：(学号,课程号)成绩是完全函数依赖而：(学号,所在系)系主任是部分函数依赖第16页，此课件共110页哦171

7、7术语和符号(8)如果XY（非平凡函数依赖，并且Y X）、YZ，则称Z传递函数依赖于X。如学号专业，专业所在系，则所在系传递函数依赖于学号。第17页，此课件共110页哦1818第18页，此课件共110页哦1919设有库存关系：数据冗余问题数据冗余问题数据更新问题数据更新问题数据插入问题数据插入问题数据删除问题数据删除问题第19页，此课件共110页哦2020为什么会出现以上种种操作异常现象呢？因为这个关系模式没有设计好，在它的某些属性之间存在着“不良”的函数依赖。如何改造这个关系模式？克服以上种种问题，就是我们这一章要解决的根本问题，也是我们要讨论函数依赖的根本原因。第20页，此课件共110页哦

8、2121模式分解模式分解 解决各种操作异常现象的方法就是进行模式分解，即把一个关系模式分解成两个或多个关系模式，在分解的过程中消除那些“不良”的函数依赖，从而获得好的关系模式。第21页，此课件共110页哦2222分解举例仓库（仓库号，地点）设备（设备号，设备名）库存（仓库号，设备号，库存数量）库存（仓库号，设备号，库存数量）刚才提到的刚才提到的库存库存关系模式，我们可以把其分解为：关系模式，我们可以把其分解为：第22页，此课件共110页哦2323注意：模式分解不能破坏原来的语义；模式分解必须遵守：l l无损连接分解；l l保持函数依赖分解。无损连接是指分无损连接是指分解后的关系经过自然解后的关

9、系经过自然连接可以恢复成原来连接可以恢复成原来的关系。的关系。保持函数依赖是指分保持函数依赖是指分保持函数依赖是指分保持函数依赖是指分解后的关系不能破坏原来解后的关系不能破坏原来解后的关系不能破坏原来解后的关系不能破坏原来的函数依赖（不能破坏原的函数依赖（不能破坏原的函数依赖（不能破坏原的函数依赖（不能破坏原来的语义）。来的语义）。来的语义）。来的语义）。第23页，此课件共110页哦2424函数依赖的推理规则Amstrong公理的内容及正确性Amstrong公理的推论及正确性逻辑蕴涵和闭包逻辑蕴涵和闭包公理的完备性公理的完备性闭包的计算闭包的计算函数依赖集的等价和最小化函数依赖集的等价和最小化

10、第24页，此课件共110页哦2525Amstrong公理：公理：设设有有关关系系模模式式R(U,F)，X、Y、Z均均为为U的的子集，推理规则如下：子集，推理规则如下：自反律自反律：如果：如果Y X，则，则XY；增广律增广律：如果：如果XY，则，则XZYZ；传递律传递律：如果：如果XY、YZ，则，则XZ。第25页，此课件共110页哦2626定理定理：Amstrong公理是公理是正确正确的的。第26页，此课件共110页哦2727证明自反律：设YX U 对关系模式R的任一关系 r 中的任意两个元组t和s，如果tX=sX，由于Y X，所以tY=sY，由定义3.1有XY成立，自反律得证。第27页，此课件

11、共110页哦2828证明增广律：设XY，且ZU，r、t、s的含义同上如果tXZ=sXZ，则一定有tX=sX和tZ=sZ又根据XY可有tY=sY由tY=sY和tZ=sZ可得tYZ=sYZ即由tXZ=sXZ推导出了tYZ=sYZ由定义3.1有XZYZ成立，增广律得证。第28页，此课件共110页哦2929证明传递律：设XY、YZ，r、t、s的含义同上 如果tX=sX，由于XY，根据定义3.1可得tY=sY 同理由于YZ，可得tZ=sZ 即由tX=sX推导出了tZ=sZ 根据定义3.1XZ成立，传递律得证。第29页，此课件共110页哦3030Amstrong公理的推论：推论推论推论推论-合并规则合并规

12、则合并规则合并规则：如果：如果：如果：如果XYXY、XZXZ，则，则XYZ；推论推论-分解规则分解规则分解规则分解规则：如果：如果：如果：如果XYZXYZ，则，则，则，则XYXY、XZ；推论推论-伪传递规则伪传递规则伪传递规则伪传递规则：如果：如果：如果：如果XYXY、YWZYWZ，则，则，则，则XWZ。第30页，此课件共110页哦3131 定理定理：Amstrong公理的三公理的三个推论是正确的。个推论是正确的。第31页，此课件共110页哦3232证明合并规则：设XY、XZ根据增广律分别有XXY、XYYZ又根据传递律有XYZ，合并规则得证。第32页，此课件共110页哦3333证明分解规则：设

13、XYZ 根据自反律有YZY和YZZ 又根据传递律分别有XY和XZ，分解规则得证。第33页，此课件共110页哦3434证明伪传递规则：设XY、YWZ根据增广律有XWYW又根据传递律有XWZ，伪传递规则得证。第34页，此课件共110页哦3535引理引理3.1 引引理理3.1：XA1A2An的的充充分分必必要要条条件件是是XAk成立成立(k=1,2,n)。根据合并规则和分解规则可以得出如下重要结论：第35页，此课件共110页哦3636逻辑蕴涵和闭包逻辑蕴涵和闭包 有时需要根据给定的一组函数依赖来有时需要根据给定的一组函数依赖来判断另外一些函数依赖是否成立，这就是判断另外一些函数依赖是否成立，这就是函

14、数依赖逻辑蕴涵所要研究的内容。函数依赖逻辑蕴涵所要研究的内容。比如有关系模式比如有关系模式R(U,F)，U=A,B,C，F=AB,B C，问，问A C是否也成立？是否也成立？第36页，此课件共110页哦3737逻辑蕴涵逻辑蕴涵 定义定义3.2：设有关系模式设有关系模式R(U,F)，X U、Y U，如果从，如果从F中的函数依赖能够推导出中的函数依赖能够推导出XY，则，则称称F逻辑蕴涵逻辑蕴涵XY，或称，或称XY是是F的逻辑蕴涵。的逻辑蕴涵。第37页，此课件共110页哦3838闭包闭包定义定义3.3 在关系模式在关系模式R(U,F)中，被中，被F 所逻辑蕴所逻辑蕴涵的函数依赖的全体称作涵的函数依赖

15、的全体称作F 的闭包，记为的闭包，记为F+。闭包闭包F F+的计算是一个的计算是一个NPNP完全问题，即理论上可计算而实际上不完全问题，即理论上可计算而实际上不可计算的问题。比如从可计算的问题。比如从F=XAF=XA1 1A A2 2A An n 出发，就至少能够推导出出发，就至少能够推导出2 2n n个不同的函数依赖，所以计算个不同的函数依赖，所以计算 F F+是非常麻烦的事情，即使是非常麻烦的事情，即使F F不太不太大，大，F F+也可能很大。也可能很大。第38页，此课件共110页哦3939闭包计算举例闭包计算举例 假设有关系模式R(U,F)，U=X,Y,Z，F=XY,YZ，则F+为：第3

16、9页，此课件共110页哦4040属性集闭包第40页，此课件共110页哦4141计算属性集闭包举例如果X=A，则：A,B,C如果X=B，则B,C如果X=C，则C设有关系模式R(U,F)，U=A,B,C，F=AB,BC第41页，此课件共110页哦4242公理的完备性公理的完备性建立一套公理系统必须明确两个问题：一一是是能能否否保保证证按按公公理理推推导导出出的的函函数数依依赖赖都都是是正正确确的的，即这些函数依赖是否都属于F+；也也就就是是说说对对于于关关系系模模式式R(U,F)R(U,F)，只要F中的函数依赖为真，则用公理根据F推推导导出出的的函函数数依依赖赖也也一定为真，这就是公理的正确性；一

17、定为真，这就是公理的正确性；另另外外一一个个问问题题是是：用公理能否推导出所有的函数依赖？也就是说F+中中所所有有的的函函数数依依赖赖是是否否都都能能用用公公理理推推导导出出来来？这这是是一一个个很很重重要要的的问问题题，因因为为如如果果F F+中有函数依赖不能用公理推导出来，那么就说明这些公理不够用、不完全，就必须补充新的公理，这就是公理的完备性问题。第42页，此课件共110页哦4343引理引理3.2第43页，此课件共110页哦4444引理3.2充分性证明：第44页，此课件共110页哦4545引理3.2必要性证明：第45页，此课件共110页哦4646通过对引理通过对引理3.2的充分性和必要性

18、的证明，得出：的充分性和必要性的证明，得出：定理定理3.1：Amstrong公理是完备的。公理是完备的。第46页，此课件共110页哦4747公理的完备性还可以理解为：所有不能用公理推导出的函数依赖都不为真，即如果XY不能根据F用公理导出，则XY F+。或者说存在一个具体的关系r，F+中的所有函数依赖都满足r，而不能用公理推导出的XY不满足r。也就是说，不能找到根据F用公理导出的函数依赖不属于F+。如果我们能够找到这样的r，则公理的完备性证明问题就解决了。第47页，此课件共110页哦4848由公理的完备性和引理3.2有结论：第48页，此课件共110页哦4949属性集闭包的计算第49页，此课件共1

19、10页哦5050算法3.1：第50页，此课件共110页哦5151例：设有R（U,F），U=A,B,C,D,E，F=ABC,B D,C E,EC B,AC B求A,B,C,D,E=如果求出的如果求出的 刚好是刚好是U（即属性的全集），则（即属性的全集），则（AB）为）为候选关键字候选关键字，因为（，因为（AB）能函数决定所有）能函数决定所有的属性。的属性。第51页，此课件共110页哦5252函数依赖集的等价和最小化第52页，此课件共110页哦5353覆盖和等价的定义定义3.5 设F和G是两个函数依赖集：如果F+G+，则称G是F的一个覆盖，或称G覆盖F；如果F+G+和G+F+同时成立，即F+=G+

20、，则称F和G等价。第53页，此课件共110页哦5454引理引理3.3F +=G +的充分必要条件是F G +并且G F +。必要性证明：充分性证明：第54页，此课件共110页哦5555研究函数依赖集等价的目的研究函数依赖集等价的目的研究函数依赖集等价的目的是为了对指定函数依赖集找出它的最小函数依赖等价集，即找出包含函数依赖尽可能少、甚至最少的函数依赖等价集，从而使模式分解简化，分解出最简单的关系模式。第55页，此课件共110页哦5656最小函数依赖集的定义定定义义3.6 如如果果函函数数依依赖赖集集F 满满足足如如下下条条件件，则则称称F 为为一一个个最最小小函函数数依依赖赖集集，也也称称为为

21、极极小小函函数数依依赖赖集集或或最最小覆盖：小覆盖：F 中任一函数依赖的右部都仅含有一个属性；中任一函数依赖的右部都仅含有一个属性；F中中不不存存在在这这样样的的函函数数依依赖赖XA，X有有真真子子集集Z，使得，使得F与与F-XA ZA等价；等价；F中中不不存存在在这这样样的的函函数数依依赖赖XA，使使得得F与与F-XA等价。等价。第56页，此课件共110页哦5757 例例：假设有属性集U=A,B,C,D,E，函数依赖集F=AB,BC,ADE和函数依赖集G=AB,AC,BC,ADE，问F和G是否是最小函数依赖集？答案：F是最小依赖集，G不是最小依赖集。第57页，此课件共110页哦5858引理3

22、.4 第58页，此课件共110页哦5959引理引理3.4必要性证明第59页，此课件共110页哦6060引理引理3.4充分充分性证明第60页，此课件共110页哦6161引理3.5 设XA是F 中任意函数依赖，G=F-XA，F 与G 等价的充分必要条件是 。必要性证明充分性证明第61页，此课件共110页哦6262逐逐逐逐一一一一检检检检查查查查F F 中中中中各各各各函函函函数数数数依依依依赖赖赖赖X XY Y，若若若若Y Y=A A1 1A Ak k，k k=2 2，则则则则用用用用 X XA Aj j|j j=1 1,k k 来来来来取取取取代代代代它它它它（分分分分解解解解规规规规则则则则）

23、；(将将将将函函函函数数数数依依依依赖赖赖赖的的的的右右右右部部部部单属性化单属性化单属性化单属性化)逐一取出逐一取出逐一取出逐一取出F F中各函数依赖中各函数依赖中各函数依赖中各函数依赖X XA A，若，若，若，若X X=B B1 1B B2 2B Bmm，mm=2 2，则逐一，则逐一，则逐一，则逐一考查考查考查考查B Bj j（j j=1 1,mm），如果），如果），如果），如果 ，则，则，则，则F F与与与与F F-X XA A (X X-B Bj j)A A 等价（引理等价（引理等价（引理等价（引理3.43.4），故以），故以），故以），故以X X-B Bj j取代取代取代取代X X；

24、（去掉函数依赖（去掉函数依赖（去掉函数依赖（去掉函数依赖左部的多余属性，称之为既约化）左部的多余属性，称之为既约化）左部的多余属性，称之为既约化）左部的多余属性，称之为既约化）逐一检查逐一检查逐一检查逐一检查F F中各函数依赖中各函数依赖中各函数依赖中各函数依赖X XA A，令，令，令，令G G=F F-X XA A，根据引理，根据引理，根据引理，根据引理3.53.5，如果，如果，如果，如果 ，则，则，则，则F F与与与与G G等价，故从等价，故从等价，故从等价，故从F F中去掉中去掉中去掉中去掉X XA A。（去掉多（去掉多（去掉多（去掉多余的函数依赖，称之为无冗余化）余的函数依赖，称之为无

25、冗余化）余的函数依赖，称之为无冗余化）余的函数依赖，称之为无冗余化）计算最小覆盖的算法算法3.2 给定函数依赖集给定函数依赖集F，求其最小覆盖的过程如下：，求其最小覆盖的过程如下：第62页，此课件共110页哦6363例例：已知已知F=AF=AB,BB,BA,BA,BC,AC,AC,CC,CAA，求，求F F的最小覆盖。的最小覆盖。逐一检查逐一检查F中的函数依赖是否多余，如果中的函数依赖是否多余，如果多余则可以去除之多余则可以去除之，最后的结果为：，最后的结果为：A B,B C,CA第63页，此课件共110页哦6464 注意：算法3.2的第2、3两步是不可以颠倒的。第64页，此课件共110页哦6

26、565设F=CA,A D,CD B,B A依照算法3.2先既约化后无冗余化既约化令G=F-CD BC B结果G与F等价G=CA,A D,C B,B A无冗余化结果所求最小覆盖为F=A D,C B,B A第65页，此课件共110页哦6666设F=CA,A D,CD B,B A先无冗余化后既约化先无冗余化后既约化无冗余化无冗余化结果没有多余的函数依赖结果没有多余的函数依赖既约化既约化结果结果G=CA,A D,C B,B A它不是最小覆盖，因为它不是最小覆盖，因为CA这时是多余的函数依赖这时是多余的函数依赖。第66页，此课件共110页哦6767规范化 规范化的目的就是要设计规范化的目的就是要设计“好

27、好”的关的关系，使关系尽量减少操作异常甚至拒绝操系，使关系尽量减少操作异常甚至拒绝操作异常现象。作异常现象。第67页，此课件共110页哦6868第一范式第一范式 每个关系模式都应满足最低要求：所有每个关系模式都应满足最低要求：所有分量都必须是不可分的最小数据项，并把其分量都必须是不可分的最小数据项，并把其称为第一范式（称为第一范式（1NF）关系。）关系。第68页，此课件共110页哦6969非规范化表格和规范化表格第69页，此课件共110页哦7070第二范式第二范式 定定义义3.7 如如果果R(U,F)1NF，并并且且R中中的的每每个个非非主主属属性性都都完完全全函函数数依依赖赖于于关关键键字，

28、则字，则R(U,F)2NF。第70页，此课件共110页哦7171库存A关系实例：数据冗余插入异常更新异常删除异常第71页，此课件共110页哦7272为了解决操作异常分解后的关系：库存B(仓库号,设备号,数量)仓库B(仓库号,地点)第72页，此课件共110页哦7373第三范式第三范式 定义定义3.8 如果如果R(U,F)2NF，并且所，并且所有非主属性都不传递依赖于关键字，则有非主属性都不传递依赖于关键字，则R(U,F)3NF。第73页，此课件共110页哦仓库A关系实例数据冗余插入异常更新异常删除异常假如插入（假如插入（“wh30”，“湖北湖北”，400，“邯郸邯郸”）会有哪些问题？会有哪些问题

29、？第74页，此课件共110页哦7575为了解决操作异常分解后的关系：为了解决操作异常分解后的关系：仓库仓库B(B(仓库号仓库号,仓库面积仓库面积,所在城市所在城市)城市城市(省省,城市城市)第75页，此课件共110页哦7676BC范式第76页，此课件共110页哦7777关系模式实例：管理管理(仓库号，设备号，职工号仓库号，设备号，职工号)它所包含的语义是：它所包含的语义是：一个仓库可以有多个职工；一个仓库可以有多个职工；一名职工仅在一个仓库工作；一名职工仅在一个仓库工作；在在每每个个仓仓库库一一种种设设备备仅仅由由一一名名职职工工保保管管（但但每名职工可以保管多种设备）。每名职工可以保管多种设

30、备）。根据以上语义有函数依赖：根据以上语义有函数依赖：职工号职工号仓库号仓库号(仓库号，设备号仓库号，设备号)职工号职工号第77页，此课件共110页哦7878进一步理解前述语义：（wh3,P5,E5）这样的）这样的记录能否插入？记录能否插入？第78页，此课件共110页哦7979为了解决操作异常现象如何进行分解？为了解决操作异常现象如何进行分解？任何分解都会破坏函数依赖：任何分解都会破坏函数依赖：（仓库号，设备号）（仓库号，设备号）职工号职工号结论：不将结论：不将3NF分解成分解成BCNF！第79页，此课件共110页哦8080如何解决非如何解决非BCNFBCNF带来的操作异常现象？带来的操作异常

31、现象？不可能靠模式分解来解决问题，只有靠不可能靠模式分解来解决问题，只有靠应用程序或设计数据库时建立一些必要的约应用程序或设计数据库时建立一些必要的约束来预防操作异常现象的发生。束来预防操作异常现象的发生。预留问题：使用第7章的触发器来拒绝此类异常发生。第80页，此课件共110页哦8181多值依赖与第四范式 在关系模式上不仅存在函数依赖，还存在着其他的在关系模式上不仅存在函数依赖，还存在着其他的在关系模式上不仅存在函数依赖，还存在着其他的在关系模式上不仅存在函数依赖，还存在着其他的“依赖依赖依赖依赖”影响着关系模式的质量，如多值依赖。影响着关系模式的质量，如多值依赖。影响着关系模式的质量，如多

32、值依赖。影响着关系模式的质量，如多值依赖。第81页，此课件共110页哦8282讨论：三个实体之间的联系 每每每每个个个个仓仓仓仓库库库库可可可可以以以以存存存存放放放放多多多多种种种种设设设设备备备备，每每每每名名名名职职职职工工工工管管管管理理理理一一一一个个个个仓仓仓仓库库库库中中中中的的的的所所所所有有有有设设设设备；备；备；备；每名职工可以管理多个仓库的设备；每名职工可以管理多个仓库的设备；每名职工可以管理多个仓库的设备；每名职工可以管理多个仓库的设备；每种设备可以存放在多个仓库。每种设备可以存放在多个仓库。每种设备可以存放在多个仓库。每种设备可以存放在多个仓库。示意数据第82页，此课

33、件共110页哦8383关键字是关键字是(仓库号仓库号,职工号职工号,设备号设备号)，即，即All-KeyBCNF是否还存在操作异常现象？为什么是否还存在操作异常现象？为什么？同同样样，如如果果P3不不再再存存放放在在WH1仓仓库库，这这时则要删除多个元组：时则要删除多个元组：WH1E1P3 WH1 E2P3 WH1E4P3排列成关系 例例如如，职职工工E4新新分分配配到到WH1仓仓库库工工作作，这时必须插入如下这时必须插入如下3个元组：个元组：WH1E4P1 WH1 E4P2 WH1E4P3第83页，此课件共110页哦8484多值依赖的定义 定义3.10 设有关系模式R(U)，X、Y、Z是U的

34、子集，Z=U-X-Y，如果对于X的一个给定值，存在一组Y值与其对应，而Y的这组值又不以任何方式与Z的值相关，则说Y多值依赖于X，记为XY。若Z=（即Z为空），则将多值依赖XY称为平凡的多值依赖。第84页，此课件共110页哦8585在该表所示的关系上：给定一个仓库号值，有一组职工号与其对应，而这组给定一个仓库号值，有一组职工号与其对应，而这组职工号值与设备号值没有任何依赖关系，所以职工号值与设备号值没有任何依赖关系，所以仓库号仓库号职工号职工号；同样同样仓库号仓库号设备号设备号；多值依赖具有对称的性质，即如果多值依赖具有对称的性质，即如果XY，并且，并且Z=U-X-Y，则，则XZ也成立。也成立。

35、第85页，此课件共110页哦8686 函数依赖可以看作是多值依赖的特例。第86页，此课件共110页哦8787第四范式 定义3 3.11.11 设关系模式R R(U,DU,D)1NF，若对每个非平凡 的 多 值 依 赖 XY，X X都都含含 有有 侯侯 选选 关关 键键 字字，则则R R(U,DU,D)4NFNF。从定义可以看出，从定义可以看出，从定义可以看出，从定义可以看出，4NF4NF限定了在关系模式的属性间不允许有非限定了在关系模式的属性间不允许有非限定了在关系模式的属性间不允许有非限定了在关系模式的属性间不允许有非平凡、且非函数依赖的多值依赖。平凡、且非函数依赖的多值依赖。平凡、且非函数

36、依赖的多值依赖。平凡、且非函数依赖的多值依赖。这是因为，若这是因为，若这是因为，若这是因为，若X XY Y是非平凡的多值依赖，且是非平凡的多值依赖，且是非平凡的多值依赖，且是非平凡的多值依赖，且X X含有侯选关键含有侯选关键含有侯选关键含有侯选关键字，则有字，则有字，则有字，则有X XY Y，所以，所以，所以，所以4NF4NF所允许的非平凡的多值依赖实际上就是函所允许的非平凡的多值依赖实际上就是函所允许的非平凡的多值依赖实际上就是函所允许的非平凡的多值依赖实际上就是函数依赖。数依赖。数依赖。数依赖。4NF4NF自然是自然是自然是自然是BCNFBCNF 第87页，此课件共110页哦8888 非非

37、4NF关系到关系到4NF关系的转换仍然是通过分解，上表所示的关系显然关系的转换仍然是通过分解，上表所示的关系显然不是不是4NF（有非平凡的多值依赖，但多值依赖的左部有非平凡的多值依赖，但多值依赖的左部不包含候选关键不包含候选关键字字），可以分解为：），可以分解为：职工职工(仓库号仓库号,职工号职工号)存放存放(仓库号仓库号,设备号设备号)分解结果都是分解结果都是4NF关系。关系。第88页，此课件共110页哦8989规范化小结第89页，此课件共110页哦9090模式分解模式分解的准则3NF无损连接和保持函数依赖算法使分解后的关系模式数最少第90页，此课件共110页哦9191模式分解的准则n模式分

38、解具有无损连接性；n模式分解能够保持函数依赖。第91页，此课件共110页哦9292无损连接的形式定义：第92页，此课件共110页哦9393保持函数依赖的形式定义：定义3.13 若 ，则R(U,F)的分解=R1(U1,F1),Rk(Uk,Fk)保持函数依赖。第93页，此课件共110页哦9494 设有关系模式设有关系模式R（U，F），），U=emp，wh，city，F=empwh，whcity，其中，其中emp是职工号，是职工号，wh是是仓库号，仓库号，city是仓库所在城市；从是仓库所在城市；从F中可以看出，一名中可以看出，一名职工只能在一个仓库工作，一个仓库只能位于一个城市职工只能在一个仓库工

39、作，一个仓库只能位于一个城市。看看如如下下的的三三个个分分解解是是否否满满足足无无损损连连接接和和保保持持函函数数依依赖赖的特性：的特性：1 1=R=R1 1(emp,),R(emp,),R2 2(wh,),R(wh,),R3 3(city,)(city,)2 2=R=R1 1(emp,wh,empwh),(emp,wh,empwh),R R2 2 2 2(emp,city,empcity)(emp,city,empcity)3 3=R=R1 1(emp,wh,empwh),(emp,wh,empwh),R R2 2(wh,city,whcity)(wh,city,whcity)第94页，此课

40、件共110页哦9595 为了得到更高范式的关系进行的模式分解，是否为了得到更高范式的关系进行的模式分解，是否总能既保证无损连接、又保持函数依赖？总能既保证无损连接、又保持函数依赖？如如果果要要求求分分解解保保持持函函数数依依赖赖，那那么么模模式式分分解解总总可可以达到以达到3NF，但是不一定能达到，但是不一定能达到BCNF；如如果果要要求求分分解解具具有有无无损损连连接接的的特特性性，那那么么一一定定可可以达到以达到BCNF；如如果果要要求求分分解解既既保保持持函函数数依依赖赖、又又具具有有无无损损连连接接的的特特性性，那那么么分分解解可可以以达达到到3NF，但但是是不不一一定定能能达到达到B

41、CNF。第95页，此课件共110页哦9696例：设有关系模式设有关系模式R（U，F），），U=A，B，C，F=ABC，CB，该关系模式是，该关系模式是3NF的，因为存在的，因为存在一个主属性对非主属性的函数依赖一个主属性对非主属性的函数依赖CB，所以该模式，所以该模式不是不是BCNF。为了达到为了达到BCNF就必须进行分解，但是就必须进行分解，但是任何任何分解都会破坏函数依赖分解都会破坏函数依赖ABC。所以为了保持所以为了保持函数依赖，就必须放弃函数依赖，就必须放弃BCNF。第96页，此课件共110页哦9797 在在实实践践中中BCNF的的意意义义并并不不大大，因因为为我我们们对对模模式式分分

42、解解的的要要求求总总是是既既要要保保证证无无损损连连接接、又又要要保保持持函数依赖。那么，当一个关系是函数依赖。那么，当一个关系是3NF时：时：l l关键字是单属性时关键字是单属性时，该模式，该模式自然是自然是BCNF；l l关关键键字字是是复复合合属属性性，并并且且不不存存在在主主属属性性对对非非主主属属性的函数依赖性的函数依赖，则该模式，则该模式自然是自然是BCNF；l l关关键键字字是是复复合合属属性性，并并且且至至少少存存在在一一个个主主属属性性对对非非主主属属性性的的函函数数依依赖赖，则则为为了了保保持持函函数数依依赖赖，模模式分解无法达到式分解无法达到BCNF。第97页，此课件共1

43、10页哦9898 判判断断一一个个分分解解是是否否保保持持函函数数依依赖赖，可可以以根根据据函函数数依依赖赖的的最最小小覆覆盖盖和和等等价价来判断。来判断。第98页，此课件共110页哦9999 判判断断一一个个分分解解是是否否具具有有无无损损连连接接特特性性可可以以用用如如下下法法则则：关关系系模模式式R分分解解为为R1和和R2是无损连接分解的充分必要条件是：是无损连接分解的充分必要条件是：R R1 1 R R2 2 R R1 1-R-R2 2或或 R R1 1 R R2 2 R R2 2 R R1 1例如分解后的例如分解后的例如分解后的例如分解后的3 3 3 3=R=R=R=R1 1 1 1

44、(emp,wh,empwh),(emp,wh,empwh),(emp,wh,empwh),(emp,wh,empwh),R R R R2 2 2 2(wh,city,whcity)(wh,city,whcity)(wh,city,whcity)(wh,city,whcity)第99页，此课件共110页哦1001003NF无损连接和保持函数依赖算法第100页，此课件共110页哦101101对对对对R R（U U，F F）中中中中的的的的F F进进进进行行行行最最最最小小小小化化化化处处处处理理理理，即即即即计计计计算算算算F F的的的的最最最最小小小小覆覆覆覆盖盖盖盖，并并并并将将将将最小等价依

45、赖集仍然记为最小等价依赖集仍然记为最小等价依赖集仍然记为最小等价依赖集仍然记为F F；若有若有若有若有XAXA，并且，并且，并且，并且X XA=UA=U，则，则，则，则=R=R=R=R，算法终止，算法终止，算法终止，算法终止；找找找找出出出出不不不不在在在在F F F F中中中中出出出出现现现现的的的的属属属属性性性性（即即即即与与与与F F F F中中中中任任任任意意意意函函函函数数数数依依依依赖赖赖赖的的的的左左左左部部部部和和和和右右右右部部部部都都都都无无无无关关关关的的的的属属属属性性性性），把把把把这这这这样样样样的的的的属属属属性性性性构构构构成成成成一一一一个个个个关关关关系系

46、系系模模模模式式式式R R R R0 0 0 0（U U U U0 0 0 0，），并并并并把把把把U U U U0 0 0 0从从从从U U U U中去掉，剩余的属性仍然记为中去掉，剩余的属性仍然记为中去掉，剩余的属性仍然记为中去掉，剩余的属性仍然记为U U U U；对对对对F F F F按按按按具具具具有有有有相相相相同同同同左左左左部部部部的的的的原原原原则则则则进进进进行行行行分分分分组组组组（假假假假定定定定分分分分为为为为k k k k组组组组），每每每每一一一一组组组组函函函函数数数数依依依依赖赖赖赖F F F Fi i i i所所所所涉涉涉涉及及及及的的的的全全全全部部部部属属

47、属属性性性性形形形形成成成成属属属属性性性性集集集集U U U Ui i i i，若若若若U U U Ui i i i U U U Uj j j j（ijijijij），就就就就去去去去掉掉掉掉U U U Ui i i i ；经经经经过过过过以以以以上上上上步步步步骤骤骤骤得得得得到到到到的的的的分分分分解解解解=R=R=R=R0 0 0 0，R R R R1 1 1 1，R R R Rk k k k （R R R R0 0 0 0可可可可能能能能为为为为空空空空，1 1 1 1k k k k可可可可能能能能不不不不连连连连续续续续）构构构构成成成成R R R R的的的的一一一一个个个个保保保

48、保持持持持函函函函数数数数依依依依赖赖赖赖的的的的分分分分解解解解，并并并并且且且且每每每每个个个个R R R Ri i i i均为均为均为均为3NF3NF3NF3NF；设设设设X X X X是是是是R R R R（U U U U，F F F F）的关键字，并令）的关键字，并令）的关键字，并令）的关键字，并令=R=R=R=RX X X X（X X X X，F F F FX X X X）；若若若若对对对对某某某某个个个个U U U Ui i i i ，如如如如果果果果X X X X U U U Ui i i i ，则则则则将将将将R R R RX X X X 从从从从中中中中去去去去掉掉掉掉，或

49、或或或U U U Ui i i i X X X X，则则则则将将将将RiRiRiRi从从从从中去掉；中去掉；中去掉；中去掉；最后最后最后最后就是所求分解。就是所求分解。就是所求分解。就是所求分解。3NF保持函数依赖和无损连接的分解算法第101页，此课件共110页哦1021023NF无损连接和保持函数依赖算法举例第102页，此课件共110页哦103103设有函数依赖集合设有函数依赖集合：F=ABF=AB，ACAC，BABA，BCBC，AEDAED，BDGBDG，DEDE利用算法利用算法3.2求得的最小覆盖集是：求得的最小覆盖集是：F=AB，BA，BC，AED，BDG，DE按照算法按照算法3.3得

50、到的模式分解是得到的模式分解是：=R1(A(A，B B，C，BAC，AB)，R2(A，E，D，AED，DE)，R3(B，D，G，BDG)第103页，此课件共110页哦104104使分解后的关系模式数最少第104页，此课件共110页哦105105算法3.3已经保证了：n3NF分解；n保持函数依赖分解；n无损连接分解；一般为了操作方便，我们还希望：分解的关系模式数最少第105页，此课件共110页哦106106还是刚才那个依赖集：还是刚才那个依赖集：还是刚才那个依赖集：还是刚才那个依赖集：F=ABF=AB，ACAC，BABA，BCBC，AEDAED，BDGBDG，DEDE利用算法利用算法3.2求得的