第03章关系数据理论优秀课件.ppt

《第03章关系数据理论优秀课件.ppt》由会员分享，可在线阅读，更多相关《第03章关系数据理论优秀课件.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=t2X为假时，不

3、管为假时，不管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)如果X

5、Y，但Y不包含于X，则称XY是非平凡的函数依赖。如不特别说明，我们总是讨论非平凡函数依赖。如：(学号,课程号)成绩如：(学号,所在系)所在系非平凡依赖平凡依赖第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=

6、仓库号城市,仓库号面积则R(U,F)表示仓库关系第13页，本讲稿共110页1414术语和符号(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，并记作 。如：(学号,课程号)成绩是完全函

7、数依赖而：(学号,所在系)系主任是部分函数依赖第16页，本讲稿共110页1717术语和符号(8)如果XY（非平凡函数依赖，并且Y X）、YZ，则称Z传递函数依赖于X。如学号专业，专业所在系，则所在系传递函数依赖于学号。第17页，本讲稿共110页1818第18页，本讲稿共110页1919设有库存关系：数据冗余问题数据冗余问题数据更新问题数据更新问题数据插入问题数据插入问题数据删除问题数据删除问题第19页，本讲稿共110页2020为什么会出现以上种种操作异常现象呢？因为这个关系模式没有设计好，在它的某因为这个关系模式没有设计好，在它的某些属性之间存在着些属性之间存在着“不良不良”的函数依赖。如何的

8、函数依赖。如何改造这个关系模式？克服以上种种问题，就是改造这个关系模式？克服以上种种问题，就是我们这一章要解决的根本问题，也是我们要讨我们这一章要解决的根本问题，也是我们要讨论函数依赖的根本原因。论函数依赖的根本原因。第20页，本讲稿共110页2121模式分解模式分解 解决各种操作异常现象的方法就是进行模式分解，即把一个关系模式分解成两个或多个关系模式，在分解的过程中消除那些“不良”的函数依赖，从而获得好的关系模式。第21页，本讲稿共110页2222分解举例仓库（仓库号，地点）仓库（仓库号，地点）设备（设备号，设备名）设备（设备号，设备名）库存（仓库号，设备号，库存数量）库存（仓库号，设备号，

9、库存数量）刚才提到的刚才提到的库存库存库存库存关系模式，我们可以把其分解为：关系模式，我们可以把其分解为：第22页，本讲稿共110页2323注意：模式分解不能破坏原来的语义；模式分解不能破坏原来的语义；模式分解必须遵守：l l无损连接分解；l l保持函数依赖分解。无损连接是指分无损连接是指分无损连接是指分无损连接是指分解后的关系经过自然解后的关系经过自然解后的关系经过自然解后的关系经过自然连接可以恢复成原来连接可以恢复成原来连接可以恢复成原来连接可以恢复成原来的关系。的关系。的关系。的关系。保持函数依赖是指分解保持函数依赖是指分解保持函数依赖是指分解保持函数依赖是指分解后的关系不能破坏原来的函

10、后的关系不能破坏原来的函后的关系不能破坏原来的函后的关系不能破坏原来的函数依赖（不能破坏原来的语数依赖（不能破坏原来的语数依赖（不能破坏原来的语数依赖（不能破坏原来的语义）。义）。义）。义）。第23页，本讲稿共110页2424函数依赖的推理规则Amstrong公理的内容及正确性Amstrong公理的推论及正确性逻辑蕴涵和闭包逻辑蕴涵和闭包公理的完备性公理的完备性闭包的计算闭包的计算函数依赖集的等价和最小化函数依赖集的等价和最小化第24页，本讲稿共110页2525Amstrong公理：公理：设设有有关关系系模模式式R(U,F)，X、Y、Z均均为为U的的子集，推理规则如下：子集，推理规则如下：自反

11、律自反律自反律自反律：如果：如果：如果：如果Y 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页，本讲稿共110页2828证明增广律：设XY，且ZU，r、t、s的含义同上如果tXZ=sXZ，则一定有tX=sX和tZ=sZ又根据XY

12、可有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公理的推论：推论推论推论推论-合并规则合并规则合并规则合并规则：如果：如果：如果：如果XYXY、XZXZ，则，则，则，则XYZXYZ；推论推论推论推论-分解规则分解规则分解规则

13、分解规则：如果：如果：如果：如果XYZXYZ，则，则，则，则XYXY、XZXZ；推论推论推论推论-伪传递规则伪传递规则伪传递规则伪传递规则：如果：如果：如果：如果XYXY、YWZYWZ，则，则，则，则XWZXWZ。第30页，本讲稿共110页3131 定理定理：Amstrong公理的三公理的三个推论是正确的。个推论是正确的。第31页，本讲稿共110页3232证明合并规则：设XY、XZ根据增广律分别有XXY、XYYZ又根据传递律有XYZ，合并规则得证。第32页，本讲稿共110页3333证明分解规则：设XYZ 根据自反律有YZY和YZZ 又根据传递律分别有XY和XZ，分解规则得证。第33页，本讲稿共

14、110页3434证明伪传递规则：设XY、YWZ根据增广律有XWYW又根据传递律有XWZ，伪传递规则得证。第34页，本讲稿共110页3535引理引理3.1 引引理理3.1：XA1A2An的的充充分分必必要要条条件件是是XAk k成立成立(k=1,2,n)。根据合并规则和分解规则可以得出如下重要结论：第35页，本讲稿共110页3636逻辑蕴涵和闭包逻辑蕴涵和闭包 有时需要根据给定的一组函数依赖来有时需要根据给定的一组函数依赖来判断另外一些函数依赖是否成立，这就是判断另外一些函数依赖是否成立，这就是函数依赖逻辑蕴涵所要研究的内容。函数依赖逻辑蕴涵所要研究的内容。比如有关系模式比如有关系模式R(U,F

15、)，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 所逻所逻辑蕴涵的函数依赖的全体称作辑蕴涵的函数依赖的全体称作F 的闭包，的闭包，记为记为F+。闭包闭包F F+的计算是一个的计算是一个NPNP完全问题，即

16、理论上可计算而实际上不可完全问题，即理论上可计算而实际上不可计算的问题。比如从计算的问题。比如从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+为：第39页，本讲稿共110页4040属性集闭包第40页，本讲稿共110页4141计算属性集闭包举例如果X=A，则

17、：A,B,C如果X=B，则B,C如果X=C，则C设有关系模式R(U,F)，U=A,B,C，F=AB,BC第41页，本讲稿共110页4242公理的完备性公理的完备性建立一套公理系统必须明确两个问题：一一是是能能否否保保证证按按公公理理推推导导出出的的函函数数依依赖赖都都是是正正确确的的，即即这这些些函函数数依依赖赖是是否否都都属属于于F F+；也也就就是是说说对对于于关关系系模模式式R(U,F)R(U,F)，只只要要F F中中的的函函数数依依赖赖为为真真，则则用用公公理理根根据据F F推推导导出出的的函函数数依依赖赖也也一一定为真，这就是公理的正确性；定为真，这就是公理的正确性；另另外外一一个个

18、问问题题是是：用用公公理理能能否否推推导导出出所所有有的的函函数数依依赖赖？也也就就是是说说F F+中中所所有有的的函函数数依依赖赖是是否否都都能能用用公公理理推推导导出出来来？这这是是一一个个很很重重要要的的问问题题，因因为为如如果果F F+中中有有函函数数依依赖赖不不能能用用公公理理推推导导出出来来，那那么么就就说说明明这这些些公公理理不不够够用用、不不完完全全，就就必必须须补充新的公理，这就是公理的完备性问题。补充新的公理，这就是公理的完备性问题。第42页，本讲稿共110页4343引理引理3.2第43页，本讲稿共110页4444引理3.2充分性证明：第44页，本讲稿共110页4545引理

19、3.2必要性证明：第45页，本讲稿共110页4646通过对引理通过对引理3.23.2的充分性和必要性的证明，得出：的充分性和必要性的证明，得出：定理定理3.1：Amstrong公理是完备的。公理是完备的。第46页，本讲稿共110页4747公理的完备性还可以理解为：所有不能用公理推导出的函数依赖都不为真，即如果XY不能根据F用公理导出，则XY F+。或者说存在一个具体的关系r，F+中的所有函数依赖都满足r，而不能用公理推导出的XY不满足r。也就是说，不能找到根据F用公理导出的函数依赖不属于F+。如果我们能够找到这样的r，则公理的完备性证明问题就解决了。第47页，本讲稿共110页4848由公理的完

20、备性和引理3.2有结论：第48页，本讲稿共110页4949属性集闭包的计算第49页，本讲稿共110页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

21、F+G+，则称G是F的一个覆盖，或称G覆盖F F；如果F+G G+和G G+F+同时成立，即F+=G+，则称，则称F和GG等价。第53页，本讲稿共110页5454引理引理3.3F +=G +的充分必要条件是F G +并且G F +。必要性证明：充分性证明：第54页，本讲稿共110页5555研究函数依赖集等价的目的研究函数依赖集等价的目的研究函数依赖集等价的目的是为了对指定函数依赖集找出它的最小函数依赖等价集，即找出包含函数依赖尽可能少、甚至最少的函数依赖等价集，从而使模式分解简化，分解出最简单的关系模式。第55页，本讲稿共110页5656最小函数依赖集的定义定定义义3.6 如如果果函函数数依依

22、赖赖集集F 满满足足如如下下条条件件，则则称称F 为为一一个个最最小小函函数数依依赖赖集集，也也称称为为极极小小函函数数依依赖赖集或最小覆盖：集或最小覆盖：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是

23、否是最小函数依赖集？答案：F是最小依赖集，G不是最小依赖集。第57页，本讲稿共110页5858引理3.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

24、 Aj j|j j=1 1,k k 来来来来取取取取代代代代它它它它（分分分分解解解解规规规规则则则则）；(将将将将函函函函数数数数依依依依赖赖赖赖的的的的右右右右部部部部单单单单属属属属性化性化性化性化)逐一取出逐一取出逐一取出逐一取出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 等价（引理等价（引理等价

25、（引理等价（引理3.43.4），故以），故以），故以），故以X X-B Bj j取代取代取代取代X X；（去掉函数依赖左（去掉函数依赖左（去掉函数依赖左（去掉函数依赖左部的多余属性，称之为既约化）部的多余属性，称之为既约化）部的多余属性，称之为既约化）部的多余属性，称之为既约化）逐一检查逐一检查逐一检查逐一检查F F中各函数依赖中各函数依赖中各函数依赖中各函数依赖X XA A，令，令，令，令G G=F F-X XA A，根据引理，根据引理，根据引理，根据引理3.53.5，如，如，如，如果果果果 ，则，则，则，则F F与与与与G G等价，故从等价，故从等价，故从等价，故从F F中去掉中去掉中去掉

26、中去掉X XA A。（去掉多余的函数（去掉多余的函数（去掉多余的函数（去掉多余的函数依赖，称之为无冗余化）依赖，称之为无冗余化）依赖，称之为无冗余化）依赖，称之为无冗余化）计算最小覆盖的算法算法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页，本

27、讲稿共110页6464 注意：算法3.2的第2、3两步是不可以颠倒的。第64页，本讲稿共110页6565设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它不是最小覆盖，因为它不是最小覆盖，因

28、为它不是最小覆盖，因为它不是最小覆盖，因为C CA A这时是多余的函数依赖这时是多余的函数依赖这时是多余的函数依赖这时是多余的函数依赖。第66页，本讲稿共110页6767规范化 规范化的目的就是要设计规范化的目的就是要设计“好好”的关的关系，使关系尽量减少操作异常甚至拒绝操系，使关系尽量减少操作异常甚至拒绝操作异常现象。作异常现象。第67页，本讲稿共110页6868第一范式第一范式 每个关系模式都应满足最低要求：所有每个关系模式都应满足最低要求：所有分量都必须是不可分的最小数据项，并把分量都必须是不可分的最小数据项，并把其称为第一范式（其称为第一范式（1NF）关系。）关系。第68页，本讲稿共1

29、10页6969非规范化表格和规范化表格第69页，本讲稿共110页7070第二范式第二范式 定定义义3.7 如如果果R(U,F)1NF，并并且且R中中的的每每个个非非主主属属性性都都完完全全函函数数依依赖赖于于关关键键字，则字，则R(U,F)2NF。第70页，本讲稿共110页7171库存A关系实例：数据冗余插入异常更新异常删除异常第71页，本讲稿共110页7272为了解决操作异常分解后的关系：库存B(仓库号,设备号,数量)仓库B(仓库号,地点)第72页，本讲稿共110页7373第三范式第三范式 定义定义3.8 如果如果R(U,F)2NF，并且所，并且所有非主属性都不传递依赖于关键字，则有非主属性

30、都不传递依赖于关键字，则R(U,F)3NF。第73页，本讲稿共110页仓库A关系实例数据冗余插入异常更新异常删除异常假如插入（假如插入（“wh30”，“湖北湖北”，400，“邯郸邯郸”）会有哪些问题？会有哪些问题？第74页，本讲稿共110页7575为了解决操作异常分解后的关系：为了解决操作异常分解后的关系：仓库仓库B(B(仓库号仓库号,仓库面积仓库面积,所在城市所在城市)城市城市(省省,城市城市)第75页，本讲稿共110页7676BC范式第76页，本讲稿共110页7777关系模式实例：管理管理(仓库号，设备号，职工号仓库号，设备号，职工号)它所包含的语义是：它所包含的语义是：一个仓库可以有多个

31、职工；一个仓库可以有多个职工；一个仓库可以有多个职工；一个仓库可以有多个职工；一名职工仅在一个仓库工作；一名职工仅在一个仓库工作；一名职工仅在一个仓库工作；一名职工仅在一个仓库工作；在在在在每每每每个个个个仓仓仓仓库库库库一一一一种种种种设设设设备备备备仅仅仅仅由由由由一一一一名名名名职职职职工工工工保保保保管管管管（但但但但每名职工可以保管多种设备）。每名职工可以保管多种设备）。每名职工可以保管多种设备）。每名职工可以保管多种设备）。根据以上语义有函数依赖：根据以上语义有函数依赖：职工号职工号职工号职工号仓库号仓库号仓库号仓库号(仓库号，设备号仓库号，设备号仓库号，设备号仓库号，设备号)职工

32、号职工号职工号职工号第77页，本讲稿共110页7878进一步理解前述语义：（wh3,P5,E5）这样）这样的记录能否插入？的记录能否插入？第78页，本讲稿共110页7979为了解决操作异常现象如何进行分解？为了解决操作异常现象如何进行分解？任何分解都会破坏函数依赖：任何分解都会破坏函数依赖：（仓库号，设备号）（仓库号，设备号）职工号职工号结论：不将结论：不将3NF分解成分解成BCNF！第79页，本讲稿共110页8080如何解决非如何解决非BCNFBCNF带来的操作异常现象？带来的操作异常现象？不可能靠模式分解来解决问题，只有靠不可能靠模式分解来解决问题，只有靠应用程序或设计数据库时建立一些必要

33、的应用程序或设计数据库时建立一些必要的约束来预防操作异常现象的发生。约束来预防操作异常现象的发生。预留问题：使用第7章的触发器来拒绝此类异常发生。第80页，本讲稿共110页8181多值依赖与第四范式 在关系模式上不仅存在函数依赖，还存在着其在关系模式上不仅存在函数依赖，还存在着其在关系模式上不仅存在函数依赖，还存在着其在关系模式上不仅存在函数依赖，还存在着其他的他的他的他的“依赖依赖依赖依赖”影响着关系模式的质量，如多值依赖。影响着关系模式的质量，如多值依赖。影响着关系模式的质量，如多值依赖。影响着关系模式的质量，如多值依赖。第81页，本讲稿共110页8282讨论：三个实体之间的联系 每个仓库

34、可以存放多种设备，每名职工管理一个仓库中的所有设备；每个仓库可以存放多种设备，每名职工管理一个仓库中的所有设备；每个仓库可以存放多种设备，每名职工管理一个仓库中的所有设备；每个仓库可以存放多种设备，每名职工管理一个仓库中的所有设备；每名职工可以管理多个仓库的设备；每名职工可以管理多个仓库的设备；每名职工可以管理多个仓库的设备；每名职工可以管理多个仓库的设备；每种设备可以存放在多个仓库。每种设备可以存放在多个仓库。每种设备可以存放在多个仓库。每种设备可以存放在多个仓库。示意数据第82页，本讲稿共110页8383关键字是关键字是(仓库号仓库号,职工号职工号,设备号设备号)，即即All-KeyBCN

35、F是否还存在操作异常现象？为什么是否还存在操作异常现象？为什么？同同样样，如如果果P3不不再再存存放放在在WH1仓仓库库，这这时则要删除多个元组：时则要删除多个元组：WH1E1P3 WH1E2P3 WH1E4P3排列成关系 例例如如，职职工工E4新新分分配配到到WH1仓仓库库工工作作，这时必须插入如下这时必须插入如下3个元组：个元组：WH1E4P1 WH1E4P2 WH1E4P3第83页，本讲稿共110页8484多值依赖的定义 定义3.10 设有关系模式R(U)，X、Y、Z是U的子集，Z=U-X-Y，如果对于X的一个给定值，存在一组Y值与其对应，而Y的这组值又不以任何方式与Z的值相关，则说Y多

36、值依赖于X，记为XY。若Z=（即Z为空），则将多值依赖XY称为平凡的多值依赖。第84页，本讲稿共110页8585在该表所示的关系上：给定一个仓库号值，有一组职工号与其对应，而这组给定一个仓库号值，有一组职工号与其对应，而这组职工号值与设备号值没有任何依赖关系，所以职工号值与设备号值没有任何依赖关系，所以仓库号仓库号职工号职工号；同样同样仓库号仓库号设备号设备号；多值依赖具有对称的性质，即如果多值依赖具有对称的性质，即如果XY，并且，并且Z=U-X-Y，则，则XZ也成立。也成立。第85页，本讲稿共110页8686 函数依赖可以看作是多值依赖的特例。第86页，本讲稿共110页8787第四范式 定定

37、义义3 3.11.11 设设关关系系模模式式R R(U,DU,D)1NF1NF，若若对对每每个个非非平平凡凡 的的 多多 值值 依依 赖赖X XY Y，X X都都含含 有有 侯侯 选选 关关 键键 字字，则则R R(U,DU,D)4 4NFNF。从定义可以看出，从定义可以看出，从定义可以看出，从定义可以看出，4NF4NF限定了在关系模式的属性间不允许有非平凡、限定了在关系模式的属性间不允许有非平凡、限定了在关系模式的属性间不允许有非平凡、限定了在关系模式的属性间不允许有非平凡、且非函数依赖的多值依赖。且非函数依赖的多值依赖。且非函数依赖的多值依赖。且非函数依赖的多值依赖。这是因为，若这是因为，

38、若这是因为，若这是因为，若X XY Y是非平凡的多值依赖，且是非平凡的多值依赖，且是非平凡的多值依赖，且是非平凡的多值依赖，且X X含有侯选关键字，则含有侯选关键字，则含有侯选关键字，则含有侯选关键字，则有有有有X XY Y，所以，所以，所以，所以4NF4NF所允许的非平凡的多值依赖实际上就是函数依赖。所允许的非平凡的多值依赖实际上就是函数依赖。所允许的非平凡的多值依赖实际上就是函数依赖。所允许的非平凡的多值依赖实际上就是函数依赖。4NF4NF自然是自然是自然是自然是BCNFBCNF 第87页，本讲稿共110页8888 非非4NF关系到关系到4NF关系的转换仍然是通过分解，上表所示的关系显然不

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

40、92无损连接的形式定义：第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中可以看出，一名中可以看出，一名职工只能在一个仓库工作，一个仓库只能位于一个城市职工只能在一个仓库工作，一个仓库只能位于一个城市。看看看看如如如如下下下下的的的的三三三三个个个个分分

41、分分解解解解是是是是否否否否满满满满足足足足无无无无损损损损连连连连接接接接和和和和保保保保持持持持函函函函数数数数依依依依赖的特性：赖的特性：赖的特性：赖的特性：1 1 1 1=R=R=R=R1 1 1 1(emp,),R(emp,),R(emp,),R(emp,),R2 2 2 2(wh,),R(wh,),R(wh,),R(wh,),R3 3 3 3(city,)(city,)(city,)(city,)2 2 2 2=R=R=R=R1 1 1 1(emp,wh,empwh),(emp,wh,empwh),(emp,wh,empwh),(emp,wh,empwh),R R R R2 2 2

42、 2(emp,city,empcity)(emp,city,empcity)(emp,city,empcity)(emp,city,empcity)3 3 3 3=R=R=R=R1 1 1 1(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)第94页，本讲稿共110页9595 为了得到更高范式的关系进行的模式分解，是否总能为了得到更高范式的关系进行的模式分解，是否总能为了

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

44、，但但是是不不一一定定能能达到达到BCNF。第95页，本讲稿共110页9696例：设有关系模式设有关系模式R（U，F），），U=A，B，C，F=ABCF=ABC，CB，该关系模式是，该关系模式是3NF的，因为存在的，因为存在一个主属性对非主属性的函数依赖一个主属性对非主属性的函数依赖CB，所以该模，所以该模，所以该模，所以该模式不是式不是式不是式不是BCNF。为了达到为了达到BCNF就必须进行分解，但是就必须进行分解，但是任何任何分解都会破坏函数依赖分解都会破坏函数依赖ABC。所以为了保持所以为了保持函数依赖，就必须放弃函数依赖，就必须放弃BCNF。第96页，本讲稿共110页9797 在在实实

45、践践中中BCNF的的意意义义并并不不大大，因因为为我我们们对对模模式式分分解解的的要要求求总总是是既既要要保保证证无无损损连连接接、又又要要保保持持函数依赖。那么，当一个关系是函数依赖。那么，当一个关系是3NF时：时：l l关键字是单属性时关键字是单属性时，该模式，该模式自然是自然是BCNFBCNF；l l关关键键字字是是复复合合属属性性，并并且且不不存存在在主主属属性性对对非非主主属属性的函数依赖性的函数依赖，则该模式，则该模式自然是自然是自然是自然是BCNF；l l关关键键字字是是复复合合属属性性，并并且且至至至至少少少少存存存存在在在在一一一一个个个个主主主主属属属属性性性性对对对对非非

46、非非主主主主属属属属性性性性的的的的函函函函数数数数依依依依赖赖赖赖，则则则则为为为为了了了了保保保保持持持持函函函函数数数数依依依依赖赖赖赖，模模模模式式式式分分分分解解解解无法达到无法达到无法达到无法达到BCNF。第97页，本讲稿共110页9898 判判断断一一个个分分解解是是否否保保持持函函数数依依赖赖，可可以以根根据据函函数数依依赖赖的的最最小小覆覆盖盖和和等等价价来来判判断。断。第98页，本讲稿共110页9999 判判断断一一个个分分解解是是否否具具有有无无损损连连接接特特性性可可以以用用如如下下法法则则：关关系系模模式式R分分解解为为R1和和R2是无损连接分解的充分必要条件是：是无

47、损连接分解的充分必要条件是：R R R R1 1 R R2 2 R R1 1-R-R2 2或或 R R R R1 1 R R2 2 R R R R2 2 R R1 1 1 1例如分解后的例如分解后的例如分解后的例如分解后的3 3 3 3=R=R=R=R1 1 1 1(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无损连接和保持

48、函数依赖算法第100页，本讲稿共110页101101对对对对R R（U U，F F）中中中中的的的的F F进进进进行行行行最最最最小小小小化化化化处处处处理理理理，即即即即计计计计算算算算F F的的的的最最最最小小小小覆覆覆覆盖盖盖盖，并并并并将将将将最最最最小等价依赖集仍然记为小等价依赖集仍然记为小等价依赖集仍然记为小等价依赖集仍然记为F F；若有若有若有若有XAXA，并且，并且，并且，并且X XA=UA=U，则，则，则，则=R=R=R=R，算法终止，算法终止，算法终止，算法终止；找找找找出出出出不不不不在在在在F F F F中中中中出出出出现现现现的的的的属属属属性性性性（即即即即与与与与

49、F F F F中中中中任任任任意意意意函函函函数数数数依依依依赖赖赖赖的的的的左左左左部部部部和和和和右右右右部部部部都都都都无无无无关关关关的的的的属属属属性性性性），把把把把这这这这样样样样的的的的属属属属性性性性构构构构成成成成一一一一个个个个关关关关系系系系模模模模式式式式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按按按按具具具具有有有有相相相相同同同同左左左

50、左部部部部的的的的原原原原则则则则进进进进行行行行分分分分组组组组（假假假假定定定定分分分分为为为为k k k k组组组组），每每每每一一一一组组组组函函函函数数数数依依依依赖赖赖赖F F F Fi i i i所所所所涉涉涉涉及及及及的的的的全全全全部部部部属属属属性性性性形形形形成成成成属属属属性性性性集集集集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