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

第03章关系数据理论本讲稿第一页，共一百一十页2 23.1 基本概念函数依赖术语和符号为什么要讨论函数依赖？模式分解模式分解本讲稿第二页，共一百一十页3 3函数依赖Y=f(X)函数Y=sin(X)Y=X+1Y=X2+2X+1省=f(城市)姓名=f(学号)?本讲稿第三页，共一百一十页4 4函数依赖的直观定义：如果有一个关系模式R(A1,A2,An)，X和Y为A1,A2,An的子集，那么对于关系R中的任意一个X值，都只有一个Y值与之对应，则称X函数决定Y，或Y函数依赖于X，并用XY表示。本讲稿第四页，共一百一十页5 5例：对仓库关系 仓库(仓库号,城市,面积)有函数依赖：仓库号城市（城市函数依赖于仓库号）仓库号面积（面积函数依赖于仓库号）本讲稿第五页，共一百一十页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。本讲稿第六页，共一百一十页定义3.1中特别要注意：只要只要 t1X=t2X t1Y=t2Y就可以推导出就可以推导出:XY 也就是说：只有当也就是说：只有当 t1X=t2X 为真，而为真，而t1Y=t2Y为假时，函数依赖不成立；而当为假时，函数依赖不成立；而当t1X=t2X为假时，不管为假时，不管t1Y=t2Y为真或为假都有为真或为假都有XY成立。成立。当当t1X=t2X 为为真真，t1Y=t2Y为为真真；当当t1X=t2X 为为真真，t1Y=t2Y为为假假；当当t1X=t2X 为为假假，t1Y=t2Y为为真真；当当t1X=t2X 为为假假，t1Y=t2Y为为假假；本讲稿第七页，共一百一十页8 8注意：1 1、函数依赖不是指关系模式、函数依赖不是指关系模式R的某个或某些关系实例的某个或某些关系实例满足的约束条件，而是指满足的约束条件，而是指R的所有关系实例均要满足的所有关系实例均要满足的约束条件。的约束条件。2 2、函数依赖和别的数据之间的依赖关系一样，是语义、函数依赖和别的数据之间的依赖关系一样，是语义范畴的概念，我们只能根据数据的语义来确定函数依范畴的概念，我们只能根据数据的语义来确定函数依赖。赖。例如：例如：“姓名姓名年龄年龄”这个函数依赖只有在没有同名人的这个函数依赖只有在没有同名人的条件下成立，如果有相同名字的人，则条件下成立，如果有相同名字的人，则“年龄年龄”就不就不再函数依赖于再函数依赖于“姓名姓名”了。了。本讲稿第八页，共一百一十页9 9定义3.1 也可以这样来理解：即对于R(U)的任意一个可能的关系实例r,r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称XY。本讲稿第九页，共一百一十页1010术语和符号(1)如果XY，但Y不包含于X，则称XY是非平凡的函数依赖。如不特别说明，我们总是讨论非平凡函数依赖。如：(学号,课程号)成绩如：(学号,所在系)所在系非平凡依赖平凡依赖本讲稿第十页，共一百一十页1111术语和符号(2)如果Y不函数依赖于X，则记作X Y。如学号不函数依赖于性别，则记作性别 学号。本讲稿第十一页，共一百一十页1212术语和符号(3)如果XY，则X称作决定因素。如学号所在系，则学号称作决定因素本讲稿第十二页，共一百一十页1313 用U表示关系模式R的属性全集，即U=A1,A2,An，用F表示关系模式R上的函数依赖集，则关系模式R可表示为R(U,F)。术语和符号(4)如U=仓库号,城市,面积 F=仓库号城市,仓库号面积则R(U,F)表示仓库关系本讲稿第十三页，共一百一十页1414术语和符号(5)如果K是关系模式R(U,F)的任一候选关键字，X是任一属性或属性集，如果XK，则X称为主属性；否则称为非主属性。如(仓库号,器件号)是库存关系的关键字，那么仓库号和器件号均是主属性，而数量为非主属性。本讲稿第十四页，共一百一十页1515术语和符号(6)如果XY，并且YX，则可记作XY。本讲稿第十五页，共一百一十页1616术语和符号(7)如果XY，并且对于X的一个任意真子集X/都有X/Y，则称Y完全函数依赖于X，并记作 ；如果X/Y成立，则称Y部分函数依赖于X，并记作 。如：(学号,课程号)成绩是完全函数依赖而：(学号,所在系)系主任是部分函数依赖本讲稿第十六页，共一百一十页1717术语和符号(8)如果XY（非平凡函数依赖，并且Y X）、YZ，则称Z传递函数依赖于X。如学号专业，专业所在系，则所在系传递函数依赖于学号。本讲稿第十七页，共一百一十页1818本讲稿第十八页，共一百一十页1919设有库存关系：数据冗余问题数据冗余问题数据更新问题数据更新问题数据插入问题数据插入问题数据删除问题数据删除问题本讲稿第十九页，共一百一十页2020为什么会出现以上种种操作异常现象呢？因为这个关系模式没有设计好，在它的某些属性之间存在着“不良”的函数依赖。如何改造这个关系模式？克服以上种种问题，就是我们这一章要解决的根本问题，也是我们要讨论函数依赖的根本原因。本讲稿第二十页，共一百一十页2121模式分解模式分解 解决各种操作异常现象的方法就是进行模式分解，即把一个关系模式分解成两个或多个关系模式，在分解的过程中消除那些“不良”的函数依赖，从而获得好的关系模式。本讲稿第二十一页，共一百一十页2222分解举例仓库（仓库号，地点）仓库（仓库号，地点）设备（设备号，设备名）设备（设备号，设备名）库存（仓库号，设备号，库存数量）刚才提到的库存库存库存库存关系模式，我们可以把其分解为：关系模式，我们可以把其分解为：本讲稿第二十二页，共一百一十页2323注意：模式分解不能破坏原来的语义；模式分解必须遵守：l l无损连接分解；l l保持函数依赖分解。无损连接是指分无损连接是指分解后的关系经过自然解后的关系经过自然连接可以恢复成原来连接可以恢复成原来的关系。的关系。保持函数依赖是指分解保持函数依赖是指分解保持函数依赖是指分解保持函数依赖是指分解后的关系不能破坏原来的函后的关系不能破坏原来的函后的关系不能破坏原来的函后的关系不能破坏原来的函数依赖（不能破坏原来的语数依赖（不能破坏原来的语数依赖（不能破坏原来的语数依赖（不能破坏原来的语义）。义）。义）。义）。本讲稿第二十三页，共一百一十页2424函数依赖的推理规则Amstrong公理的内容及正确性Amstrong公理的推论及正确性逻辑蕴涵和闭包逻辑蕴涵和闭包公理的完备性公理的完备性闭包的计算闭包的计算函数依赖集的等价和最小化函数依赖集的等价和最小化本讲稿第二十四页，共一百一十页2525Amstrong公理：公理：设设有有关关系系模模式式R(U,F)，X、Y、Z均均为为U的的子集，推理规则如下：子集，推理规则如下：自反律自反律：如果：如果Y X，则，则XY；增广律增广律：如果：如果XY，则，则XZYZ；传递律传递律：如果：如果XY、YZ，则，则XZ。本讲稿第二十五页，共一百一十页2626定理定理：Amstrong公理是公理是正确正确的的。本讲稿第二十六页，共一百一十页2727证明自反律：设YX U 对关系模式R的任一关系 r 中的任意两个元组t和s，如果tX=sX，由于Y X，所以tY=sY，由定义3.1有XY成立，自反律得证。本讲稿第二十七页，共一百一十页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成立，增广律得证。本讲稿第二十八页，共一百一十页2929证明传递律：设XY、YZ，r、t、s的含义同上 如果tX=sX，由于XY，根据定义3.1可得tY=sY 同理由于YZ，可得tZ=sZ 即由tX=sX推导出了tZ=sZ 根据定义3.1XZ成立，传递律得证。本讲稿第二十九页，共一百一十页3030Amstrong公理的推论：推论推论推论推论-合并规则合并规则：如果：如果XY、XZXZ，则，则，则，则XYZXYZ；推论推论推论推论-分解规则分解规则分解规则分解规则：如果：如果：如果：如果XYZXYZ，则，则，则，则XY、XZXZ；推论推论推论推论-伪传递规则伪传递规则：如果：如果：如果：如果XY、YWZYWZ，则，则，则，则XWZ。本讲稿第三十页，共一百一十页3131 定理定理：Amstrong公理的三公理的三个推论是正确的。个推论是正确的。本讲稿第三十一页，共一百一十页3232证明合并规则：设XY、XZ根据增广律分别有XXY、XYYZ又根据传递律有XYZ，合并规则得证。本讲稿第三十二页，共一百一十页3333证明分解规则：设XYZ 根据自反律有YZY和YZZ 又根据传递律分别有XY和XZ，分解规则得证。本讲稿第三十三页，共一百一十页3434证明伪传递规则：设XY、YWZ根据增广律有XWYW又根据传递律有XWZ，伪传递规则得证。本讲稿第三十四页，共一百一十页3535引理引理3.1 引引理理3.1：XA1A2An的的充充分分必必要要条条件件是是XAk成立成立(k=1,2,n)。根据合并规则和分解规则可以得出如下重要结论：本讲稿第三十五页，共一百一十页3636逻辑蕴涵和闭包逻辑蕴涵和闭包 有时需要根据给定的一组函数依赖来判断有时需要根据给定的一组函数依赖来判断另外一些函数依赖是否成立，这就是函数依赖另外一些函数依赖是否成立，这就是函数依赖逻辑蕴涵所要研究的内容。逻辑蕴涵所要研究的内容。比如有关系模式比如有关系模式R(U,F)，U=A,B,C，F=AB,B C，问，问A C是否也成立？是否也成立？本讲稿第三十六页，共一百一十页3737逻辑蕴涵逻辑蕴涵 定义定义3.2：设有关系模式设有关系模式R(U,F)，X U、Y U，如果从，如果从F中的函数依赖能够推导出中的函数依赖能够推导出XY，则称，则称F逻辑蕴涵逻辑蕴涵XY，或称，或称XY是是F的逻辑蕴涵。的逻辑蕴涵。本讲稿第三十七页，共一百一十页3838闭包闭包定义定义3.3 在关系模式在关系模式R(U,F)中，被中，被F 所逻辑蕴所逻辑蕴涵的函数依赖的全体称作涵的函数依赖的全体称作F 的闭包，记为的闭包，记为F+。闭包闭包F F+的计算是一个的计算是一个NPNP完全问题，即理论上可计算而实际上完全问题，即理论上可计算而实际上不可计算的问题。比如从不可计算的问题。比如从F=XAF=XA1 1A A2 2A An n 出发，就至少能够推导出发，就至少能够推导出出2 2n n个不同的函数依赖，所以计算个不同的函数依赖，所以计算 F F+是非常麻烦的事情，即使是非常麻烦的事情，即使F F不不太大，太大，F F+也可能很大。也可能很大。本讲稿第三十八页，共一百一十页3939闭包计算举例闭包计算举例 假设有关系模式R(U,F)，U=X,Y,Z，F=XY,YZ，则F+为：本讲稿第三十九页，共一百一十页4040属性集闭包本讲稿第四十页，共一百一十页4141计算属性集闭包举例如果X=A，则：A,B,C如果X=B，则B,C如果X=C，则C设有关系模式R(U,F)，U=A,B,C，F=AB,BC本讲稿第四十一页，共一百一十页4242公理的完备性公理的完备性建立一套公理系统必须明确两个问题：一一是是能能否否保保证证按按公公理理推推导导出出的的函函数数依依赖赖都都是是正正确确的的，即这些函数依赖是否都属于F F+；也也就就是是说说对对于于关关系系模模式式R(U,F)R(U,F)，只只要要F F中中的的函函数数依依赖赖为为真真，则则用用公公理理根根据据F F推推导导出出的的函函数数依依赖赖也也一一定为真，这就是公理的正确性；定为真，这就是公理的正确性；另另外外一一个个问问题题是是：用用公公理理能能否否推推导导出出所所有有的的函函数数依依赖赖？也也就就是是说说F F+中所有的函数依赖是否都能用公理推导出来？这是一个很重要的问题，因为如果F F+中有函数依赖不能用公理推导出来，那么就说明这些公理不够用、不完全，就必须补充新的公理，这就是公理的完备性问题。本讲稿第四十二页，共一百一十页4343引理引理3.2本讲稿第四十三页，共一百一十页4444引理3.2充分性证明：本讲稿第四十四页，共一百一十页4545引理3.2必要性证明：本讲稿第四十五页，共一百一十页4646通过对引理3.23.2的充分性和必要性的证明，得出：的充分性和必要性的证明，得出：定理定理3.1：Amstrong公理是完备的。公理是完备的。本讲稿第四十六页，共一百一十页4747公理的完备性还可以理解为：所有不能用公理推导出的函数依赖都不为真，即如果XY不能根据F用公理导出，则XY F+。或者说存在一个具体的关系r，F+中的所有函数依赖都满足r，而不能用公理推导出的XY不满足r。也就是说，不能找到根据F用公理导出的函数依赖不属于F+。如果我们能够找到这样的r，则公理的完备性证明问题就解决了。本讲稿第四十七页，共一百一十页4848由公理的完备性和引理3.2有结论：本讲稿第四十八页，共一百一十页4949属性集闭包的计算本讲稿第四十九页，共一百一十页5050算法3.1：本讲稿第五十页，共一百一十页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）能函数决定所有）能函数决定所有的属性。的属性。本讲稿第五十一页，共一百一十页5252函数依赖集的等价和最小化本讲稿第五十二页，共一百一十页5353覆盖和等价的定义定义3.5 设F和G是两个函数依赖集：如果F+G+，则称G是F的一个覆盖，或称G覆盖F；如果F+G+和G+F+同时成立，即F+=G+，则称F和G等价。本讲稿第五十三页，共一百一十页5454引理引理3.3F +=G +的充分必要条件是F G +并且G F +。必要性证明：充分性证明：本讲稿第五十四页，共一百一十页5555研究函数依赖集等价的目的研究函数依赖集等价的目的研究函数依赖集等价的目的是为了对指定函数依赖集找出它的最小函数依赖等价集，即找出包含函数依赖尽可能少、甚至最少的函数依赖等价集，从而使模式分解简化，分解出最简单的关系模式。本讲稿第五十五页，共一百一十页5656最小函数依赖集的定义定定义义3.6 如如果果函函数数依依赖赖集集F 满满足足如如下下条条件件，则则称称F 为为一一个个最最小小函函数数依依赖赖集集，也也称称为为极极小小函函数数依依赖赖集集或或最最小覆盖：小覆盖：F 中任一函数依赖的右部都仅含有一个属性；中任一函数依赖的右部都仅含有一个属性；F中中不不存存在在这这样样的的函函数数依依赖赖XA，X有有真真子子集集Z，使得，使得F与与F-XA ZA等价；等价；F中中不不存存在在这这样样的的函函数数依依赖赖XA，使使得得F与与F-XA等价。等价。本讲稿第五十六页，共一百一十页5757 例例：假设有属性集U=A,B,C,D,E，函数依赖集F=AB,BC,ADE和函数依赖集G=AB,AC,BC,ADE，问F和G是否是最小函数依赖集？答案：F是最小依赖集，G不是最小依赖集。本讲稿第五十七页，共一百一十页5858引理3.4 本讲稿第五十八页，共一百一十页5959引理引理3.4必要性证明本讲稿第五十九页，共一百一十页6060引理引理3.4充分充分性证明本讲稿第六十页，共一百一十页6161引理3.5 设XA是F 中任意函数依赖，G=F-XA，F 与G 等价的充分必要条件是 。必要性证明充分性证明本讲稿第六十一页，共一百一十页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 来来来来取取取取代代代代它它它它（分分分分解解解解规规规规则则则则）；(将将将将函函函函数数数数依依依依赖赖赖赖的的的的右右右右部部部部单属性化单属性化单属性化单属性化)逐一取出逐一取出逐一取出逐一取出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；（去掉函数依赖左（去掉函数依赖左（去掉函数依赖左（去掉函数依赖左部的多余属性，称之为既约化）部的多余属性，称之为既约化）部的多余属性，称之为既约化）部的多余属性，称之为既约化）逐一检查逐一检查逐一检查逐一检查F F中各函数依赖中各函数依赖中各函数依赖中各函数依赖X XA A，令，令，令，令G G=F F-X XA A，根据引理，根据引理，根据引理，根据引理3.53.5，如果如果如果如果 ，则，则，则，则F F与与与与G G等价，故从等价，故从等价，故从等价，故从F F中去掉中去掉中去掉中去掉X XA A。（去掉多余的（去掉多余的（去掉多余的（去掉多余的函数依赖，称之为无冗余化）函数依赖，称之为无冗余化）函数依赖，称之为无冗余化）函数依赖，称之为无冗余化）计算最小覆盖的算法算法3.2 给定函数依赖集给定函数依赖集F，求其最小覆盖的过程如下：，求其最小覆盖的过程如下：本讲稿第六十二页，共一百一十页6363例例：已知已知F=AF=AB,BB,BA,BA,BC,AC,AC,CC,CAA，求，求F F的最小覆盖。的最小覆盖。逐一检查逐一检查F中的函数依赖是否多余，如中的函数依赖是否多余，如果多余则可以去除之果多余则可以去除之，最后的结果为：，最后的结果为：A B,B C,CA本讲稿第六十三页，共一百一十页6464 注意：算法3.2的第2、3两步是不可以颠倒的。本讲稿第六十四页，共一百一十页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本讲稿第六十五页，共一百一十页6666设F=CA,A D,CD B,B A先无冗余化后既约化先无冗余化后既约化无冗余化无冗余化结果没有多余的函数依赖结果没有多余的函数依赖既约化既约化结果结果G=CA,A D,C B,B A它不是最小覆盖，因为它不是最小覆盖，因为CA A这时是多余的函数依赖这时是多余的函数依赖这时是多余的函数依赖这时是多余的函数依赖。本讲稿第六十六页，共一百一十页6767规范化 规范化的目的就是要设计规范化的目的就是要设计“好好”的关的关系，使关系尽量减少操作异常甚至拒绝操系，使关系尽量减少操作异常甚至拒绝操作异常现象。作异常现象。本讲稿第六十七页，共一百一十页6868第一范式第一范式 每个关系模式都应满足最低要求：所有每个关系模式都应满足最低要求：所有分量都必须是不可分的最小数据项，并把其分量都必须是不可分的最小数据项，并把其称为第一范式（称为第一范式（1NF）关系。）关系。本讲稿第六十八页，共一百一十页6969非规范化表格和规范化表格本讲稿第六十九页，共一百一十页7070第二范式第二范式 定定义义3.7 如如果果R(U,F)1NF，并并且且R中中的的每每个个非非主主属属性性都都完完全全函函数数依依赖赖于于关关键键字，则字，则R(U,F)2NF。本讲稿第七十页，共一百一十页7171库存A关系实例：数据冗余插入异常更新异常删除异常本讲稿第七十一页，共一百一十页7272为了解决操作异常分解后的关系：库存B(仓库号,设备号,数量)仓库B(仓库号,地点)本讲稿第七十二页，共一百一十页7373第三范式第三范式 定义定义3.8 如果如果R(U,F)2NF，并且所，并且所有非主属性都不传递依赖于关键字，则有非主属性都不传递依赖于关键字，则R(U,F)3NF。本讲稿第七十三页，共一百一十页仓库A关系实例数据冗余插入异常更新异常删除异常假如插入（假如插入（“wh30”，“湖北湖北”，400，“邯郸邯郸”）会有哪些问题？会有哪些问题？本讲稿第七十四页，共一百一十页7575为了解决操作异常分解后的关系：为了解决操作异常分解后的关系：仓库仓库B(B(仓库号仓库号,仓库面积仓库面积,所在城市所在城市)城市城市(省省,城市城市)本讲稿第七十五页，共一百一十页7676BC范式本讲稿第七十六页，共一百一十页7777关系模式实例：管理管理(仓库号，设备号，职工号仓库号，设备号，职工号)它所包含的语义是：它所包含的语义是：一个仓库可以有多个职工；一个仓库可以有多个职工；一名职工仅在一个仓库工作；一名职工仅在一个仓库工作；在在每每个个仓仓库库一一种种设设备备仅仅由由一一名名职职工工保保管管（但但每名职工可以保管多种设备）。每名职工可以保管多种设备）。根据以上语义有函数依赖：根据以上语义有函数依赖：职工号职工号仓库号仓库号(仓库号，设备号仓库号，设备号)职工号职工号本讲稿第七十七页，共一百一十页7878进一步理解前述语义：（wh3,P5,E5）这样的）这样的记录能否插入？记录能否插入？本讲稿第七十八页，共一百一十页7979为了解决操作异常现象如何进行分解？为了解决操作异常现象如何进行分解？任何分解都会破坏函数依赖：任何分解都会破坏函数依赖：（仓库号，设备号）（仓库号，设备号）职工号职工号结论：不将结论：不将3NF分解成分解成BCNF！本讲稿第七十九页，共一百一十页8080如何解决非如何解决非BCNFBCNF带来的操作异常现象？带来的操作异常现象？不可能靠模式分解来解决问题，只有靠不可能靠模式分解来解决问题，只有靠应用程序或设计数据库时建立一些必要的约应用程序或设计数据库时建立一些必要的约束来预防操作异常现象的发生。束来预防操作异常现象的发生。预留问题：使用第7章的触发器来拒绝此类异常发生。本讲稿第八十页，共一百一十页8181多值依赖与第四范式 在关系模式上不仅存在函数依赖，还存在着其在关系模式上不仅存在函数依赖，还存在着其他的他的“依赖依赖”影响着关系模式的质量，如多值依赖。影响着关系模式的质量，如多值依赖。本讲稿第八十一页，共一百一十页8282讨论：三个实体之间的联系 每每每每个个个个仓仓仓仓库库库库可可可可以以以以存存存存放放放放多多多多种种种种设设设设备备备备，每每每每名名名名职职职职工工工工管管管管理理理理一一一一个个个个仓仓仓仓库库库库中中中中的的的的所有设备；所有设备；所有设备；所有设备；每名职工可以管理多个仓库的设备；每名职工可以管理多个仓库的设备；每名职工可以管理多个仓库的设备；每名职工可以管理多个仓库的设备；每种设备可以存放在多个仓库。每种设备可以存放在多个仓库。每种设备可以存放在多个仓库。每种设备可以存放在多个仓库。示意数据本讲稿第八十二页，共一百一十页8383关键字是关键字是(仓库号仓库号,职工号职工号,设备号设备号)，即即All-KeyBCNF是否还存在操作异常现象？为什么是否还存在操作异常现象？为什么？同同样样，如如果果P3不不再再存存放放在在WH1仓仓库库，这这时则要删除多个元组：时则要删除多个元组：WH1E1P3 WH1E2P3 WH1 E4P3排列成关系 例例如如，职职工工E4新新分分配配到到WH1仓仓库库工工作作，这时必须插入如下这时必须插入如下3个元组：个元组：WH1E4P1 WH1 E4P2 WH1E4P3本讲稿第八十三页，共一百一十页8484多值依赖的定义 定义3.10 设有关系模式R(U)，X、Y、Z是U的子集，Z=U-X-Y，如果对于X的一个给定值，存在一组Y值与其对应，而Y的这组值又不以任何方式与Z的值相关，则说Y多值依赖于X，记为XY。若Z=（即Z为空），则将多值依赖XY称为平凡的多值依赖。本讲稿第八十四页，共一百一十页8585在该表所示的关系上：给定一个仓库号值，有一组职工号与其对应，而这组职给定一个仓库号值，有一组职工号与其对应，而这组职工号值与设备号值没有任何依赖关系，所以工号值与设备号值没有任何依赖关系，所以仓库号仓库号职工号职工号；同样同样仓库号仓库号设备号设备号；多值依赖具有对称的性质，即如果多值依赖具有对称的性质，即如果XY，并且，并且Z=U-X-Y，则，则XZ也成立。也成立。本讲稿第八十五页，共一百一十页8686 函数依赖可以看作是多值依赖的特例。本讲稿第八十六页，共一百一十页8787第四范式 定义3.11.11 设关系模式R(U,D)1NF1NF，若若对对每每个个非非平平凡凡 的的 多多 值值 依依 赖赖X XY Y，X X都都含含 有有 侯侯 选选 关关 键键 字字，则则R R(U,D)4 4NFNF。从定义可以看出，从定义可以看出，从定义可以看出，从定义可以看出，4NF4NF限定了在关系模式的属性间不允许有非平限定了在关系模式的属性间不允许有非平限定了在关系模式的属性间不允许有非平限定了在关系模式的属性间不允许有非平凡、且非函数依赖的多值依赖。凡、且非函数依赖的多值依赖。凡、且非函数依赖的多值依赖。凡、且非函数依赖的多值依赖。这是因为，若这是因为，若这是因为，若这是因为，若X XY Y是非平凡的多值依赖，且是非平凡的多值依赖，且是非平凡的多值依赖，且是非平凡的多值依赖，且X X含有侯选关键含有侯选关键含有侯选关键含有侯选关键字，则有字，则有字，则有字，则有X XY Y，所以，所以，所以，所以4NF4NF所允许的非平凡的多值依赖实际上就是函所允许的非平凡的多值依赖实际上就是函所允许的非平凡的多值依赖实际上就是函所允许的非平凡的多值依赖实际上就是函数依赖。数依赖。数依赖。数依赖。4NF4NF自然是自然是自然是自然是BCNFBCNF 本讲稿第八十七页，共一百一十页8888 非非4NF关系到关系到4NF关系的转换仍然是通过分解，上表所示的关系显关系的转换仍然是通过分解，上表所示的关系显然不是然不是4NF（有非平凡的多值依赖，但多值依赖的左部有非平凡的多值依赖，但多值依赖的左部不包含候选不包含候选关键字关键字），可以分解为：），可以分解为：职工职工(仓库号仓库号,职工号职工号)存放存放(仓库号仓库号,设备号设备号)分解结果都是分解结果都是4NF关系。关系。本讲稿第八十八页，共一百一十页8989规范化小结本讲稿第八十九页，共一百一十页9090模式分解模式分解的准则3NF无损连接和保持函数依赖算法使分解后的关系模式数最少本讲稿第九十页，共一百一十页9191模式分解的准则n模式分解具有无损连接性；n模式分解能够保持函数依赖。本讲稿第九十一页，共一百一十页9292无损连接的形式定义：本讲稿第九十二页，共一百一十页9393保持函数依赖的形式定义：定义3.13 若 ，则R(U,F)的分解=R1(U1,F1),Rk(Uk,Fk)保持函数依赖。本讲稿第九十三页，共一百一十页9494 设有关系模式设有关系模式R（U，F），），U=emp，wh，city，F=empwh，whcity，其中，其中emp是职工号，是职工号，wh是是仓库号，仓库号，city是仓库所在城市；从是仓库所在城市；从F中可以看出，一名中可以看出，一名职工只能在一个仓库工作，一个仓库只能位于一个城市职工只能在一个仓库工作，一个仓库只能位于一个城市。看看如如下下的的三三个个分分解解是是否否满满足足无无损损连连接接和和保保持持函函数数依依赖赖的特性：的特性：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 R R R2 2 2 2(emp,city,empcity)(emp,city,empcity)(emp,city,empcity)(emp,city,empcity)3 3=R=R1 1(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)本讲稿第九十四页，共一百一十页9595 为了得到更高范式的关系进行的模式分解，是否总为了得到更高范式的关系进行的模式分解，是否总能既保证无损连接、又保持函数依赖？能既保证无损连接、又保持函数依赖？如如果果要要求求分分解解保保持持函函数数依依赖赖，那那么么模模式式分分解解总总可可以达到以达到3NF，但是不一定能达到，但是不一定能达到BCNF；如如果果要要求求分分解解具具有有无无损损连连接接的的特特性性，那那么么一一定定可可以达到以达到BCNF；如如果果要要求求分分解解既既保保持持函函数数依依赖赖、又又具具有有无无损损连连接接的的特特性性，那那么么分分解解可可以以达达到到3NF，但但是是不不一一定定能能达到达到BCNF。本讲稿第九十五页，共一百一十页9696例：设有关系模式设有关系模式R（U，F），），U=A，B，C，F=ABC，CB，该关系模式是，该关系模式是3NF的，因为存的，因为存在一个主属性对非主属性的函数依赖在一个主属性对非主属性的函数依赖CB，所以该模，所以该模式不是式不是BCNF。为了达到为了达到BCNF就必须进行分解，但是就必须进行分解，但是任何任何分解都会破坏函数依赖分解都会破坏函数依赖ABC。所以为了保持所以为了保持函数依赖，就必须放弃函数依赖，就必须放弃BCNF。本讲稿第九十六页，共一百一十页9797 在在实实践践中中BCNF的的意意义义并并不不大大，因因为为我我们们对对模模式式分分解解的的要要求求总总是是既既要要保保证证无无损损连连接接、又又要要保保持持函数依赖。那么，当一个关系是函数依赖。那么，当一个关系是3NF时：时：l l关键字是单属性时关键字是单属性时，该模式，该模式自然是自然是BCNF；l l关关键键字字是是复复合合属属性性，并并且且不不存存在在主主属属性性对对非非主主属属性的函数依赖性的函数依赖，则该模式，则该模式自然是自然是BCNF；l l关关键键字字是是复复合合属属性性，并并且且至至少少存存在在一一个个主主属属性性对对非非主主属属性性的的函函数数依依赖赖，则则为为了了保保持持函函数数依依赖赖，模模式式分解无法达到分解无法达到BCNF。本讲稿第九十七页，共一百一十页9898 判判断断一一个个分分解解是是否否保保持持函函数数依依赖赖，可可以以根根据据函函数数依依赖赖的的最最小小覆覆盖盖和和等等价价来判断。来判断。本讲稿第九十八页，共一百一十页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(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)本讲稿第九十九页，共一百一十页1001003NF无损连接和保持函数依赖算法本讲稿第一百页，共一百一十页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中中中中出出出出现现现现的的的的属属属属性性性性（即即即即与与与与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按按按按具具具具有有有有相相相相同同同同左左左左部部部部的的的的原原原原则则则则进进进进行行行行分分分分组组组组（假假假假定定定定分分分分为为为为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 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的的的的一一一一个个个个保保保保持持持持函函函函数数数数依依依依赖赖赖赖的的的的分分分分解解解解，并并并并且且且且每每每每个个个个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 从从从从中中中中去去去去掉掉掉掉，或或或或U U U Ui i i i X X X X，则则则则将将将将RiRiRiRi从从从从中去掉；中去掉；中去掉；中去掉；最后最后最后最后就是所求分解。就是所求分解。就是所求分解。就是所求分解。3NF保持函数依赖和无损连接的分解算法本讲稿第一百零一页，共一百一十页1021023NF无损连接和保持函数依赖算法举例本讲稿第一百零二页，共一百一十页103103设有函数依赖集合设有函数依赖集合：F=ABF=AB，ACAC，BABA，BCBC，AEDAED，BDGBDG，DEDE利用算法利用算法3.2求得的最小覆盖集是：求得的最小覆盖集是：F=AB，BA，BC，AED，BDG，DE按照算法按照算法3.3得到的模式分解是得到的模式分解是：=R R1 1(A，B B，CC，BACBAC，AB)AB)，R2(A，E，D，AED，DE)，R3(B，D，G，BDG)本讲稿第一百零三页，共一百一十页104104使分解后的关系模式数最少本讲稿第一百零四页，共一百一十页105105算法3.3已经保证了：n3NF分