《教学课件第09章关系数据理论》由会员分享，可在线阅读，更多相关《教学课件第09章关系数据理论（111页珍藏版）》请在金锄头文库上搜索。
1、第9章 关系数据理论9.1 基本概念9.2函数依赖的公理系统9.3规范化9.4模式分解19.1 基本概念w函数依赖w术语和符号w为什么要讨论函数依赖？w模式分解模式分解2函数依赖Y=f(X)函数Y=sin(X)Y=X+1Y=X2+2X+1省=f(城市)姓名=f(学号)3函数依赖的直观定义： 如果有一个关系模式R(A1,A2,An)，X和Y为A1,A2,An的子集，那么对于关系R中的任意一个X值，都只有一个Y值与之对应，则称X函数决定Y，或Y函数依赖于X，并用XY表示。4例：对仓库关系 仓库(仓库号,城市,面积)有函数依赖：仓库号城市（城市函数依赖于仓库号）仓库号面积（面积函数依赖于仓库号）5函
2、数依赖的严格形式化定义w定义定义9.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注意定义9.1中：t1X=t2X t1Y=t2Y7术语和符号(1) 如果XY，但Y不包含于X，则称XY是非平凡的函数依赖。如不特别说明，我们总是讨论非平凡函数依赖。如：(学号,课程号)成绩如：(学号,所在系)所在系非平凡依赖平凡依赖8术语和符号(2) 如果Y不函数依赖于X，则记作X Y。如学号不函数依赖于性别，则记作性别 学号。9术语和符号
3、(3)如果XY，则X称作决定因素。如学号所在系，则学号称作决定因素10 用U表示关系模式R的属性全集，即U=A1,A2,An，用F表示关系模式R上的函数依赖集，则关系模式R可表示为R(U,F)。术语和符号(4)如U=仓库号,城市,面积 F=仓库号城市,仓库号面积则R(U,F)表示仓库关系11术语和符号(5) 如果K是关系模式R(U,F)的任一候选关键字，X是任一属性或属性集，如果XK，则X称为主属性；否则称为非主属性。 如(仓库号,器件号)是库存关系的关键字，那么仓库号和器件号均是主属性，而数量为非主属性。12术语和符号(6)如果XY，并且YX，则可记作XY。13术语和符号(7) 如果XY，并
4、且对于X的一个任意真子集X/ 都有X/ Y，则称Y完全函数依赖于X，并记作 ；如果X/ Y成立，则称Y部分函数依赖于X，并记作 。如：(学号,课程号)成绩是完全函数依赖而：(学号,所在系)系主任是部分函数依赖14术语和符号(8) 如果XY（非平凡函数依赖，并且Y X）、YZ，则称Z传递函数依赖于X。 如学号专业，专业所在系，则所在系传递函数依赖于学号。1516设有库存关系：w数据冗余问题数据冗余问题w数据更新问题数据更新问题w数据插入问题数据插入问题w数据删除问题数据删除问题17为什么会出现以上种种操作异常现象呢？ 因为这个关系模式没有设计好，在它的某些属性之间存在着“不良”的函数依赖。如何改
5、造这个关系模式？克服以上种种问题，就是我们这一章要解决的根本问题，也是我们要讨论函数依赖的根本原因。18模式分解模式分解 解决各种操作异常现象的方法就是进行模式分解，即把一个关系模式分解成两个或多个关系模式，在分解的过程中消除那些“不良”的函数依赖，从而获得好的关系模式。19分解举例仓库（仓库号，地点）设备（设备号，设备名）库存（仓库号，设备号，库存数量）刚才提到的库存库存关系模式，我们可以把其分解为：20注意：w模式分解不能破坏原来的语义；w模式分解必须遵守：n无损连接分解；n保持函数依赖分解。 无损连接是指分解后的关系经过自然连接可以恢复成原来的关系。 保持函数依赖是指分解后的关系不能破坏
6、原来的函数依赖（不能破坏原来的语义）。21函数依赖的公理系统wAmstrong公理的内容及正确性wAmstrong公理的推论w逻辑蕴涵和闭包逻辑蕴涵和闭包w公理的完备性公理的完备性w闭包的计算闭包的计算w函数依赖集的等价和最小化函数依赖集的等价和最小化22Amstrong公理：公理： 设有关系模式R(U,F)，X、Y、Z均为U的子集，推理规则如下：自反律：如果YX，则XY；增广律：如果XY，则XZYZ；传递律：如果XY、YZ，则XZ 。23定理定理9.1：Amstrong公理是正确的。24证明自反律：设YX U 对关系模式R的任一关系 r 中的任意两个元组t和s，如果tX=sX，由于Y X，所
7、以tY=sY，由定义9.1有XY成立，自反律得证。25证明增广律：设XY，且ZU，r、t、s的含义同上如果tXZ=sXZ，则一定有tX=sX和tZ=sZ又根据XY可有tY=sY由tY=sY和tZ=sZ可得tYZ=sYZ即由tXZ=sXZ推导出了tYZ=sYZ由定义9.1有XZYZ成立，增广律得证。26证明传递律： 设XY、YZ，r、t、s的含义同上 如 果 tX=sX， 由 于 XY， 根 据 定 义 9.1可 得tY=sY 同理由于YZ，可得tZ=sZ 即由tX=sX推导出了tZ=sZ 根据定义9.1XZ成立，传递律得证。27Amstrong公理的推论：推论-合并规则：如果XY、XZ，则XY
8、Z；推论-分解规则：如果XYZ，则XY、XZ；推论-伪传递规则：如果XY、YWZ，则XWZ。28 定理定理9.2：Amstrong公理的三个推论是正确的。29证明合并规则：设XY、XZ根据增广律分别有XXY、XYYZ又根据传递律有XYZ，合并规则得证。30证明分解规则：设XYZ 根据自反律有YZY和YZZ 又根据传递律分别有XY和XZ，分解规则得证。31证明伪传递规则：设XY、YWZ根据增广律有XWYW又根据传递律有XWZ，伪传递规则得证。32引理引理9.1 引引理理9.1：XA1A2An的充分必要条件是XAk成立(k=1,2,n)。 根据合并规则和分解规则可以得出如下重要结论：33逻辑蕴涵和
9、闭包逻辑蕴涵和闭包 有时需要根据给定的一组函数依赖来判断另外一些函数依赖是否成立，这就是函数依赖逻辑蕴涵所要研究的内容。 比如有关系模式R(U,F)，U=A,B,C，F=AB,B C，问A C是否也成立？34逻辑蕴涵 定义定义9.2：设有关系模式R(U,F)，XU、Y U，如果从F中的函数依赖能够推导出XY，则称F逻辑蕴涵XY，或称XY是F的逻辑蕴涵。35闭包定义9.3 在关系模式R(U,F)中，被F 所逻辑蕴涵的函数依赖的全体称作F 的闭包，记为F + 。 36闭包计算举例 假设有关系模式R(U,F)，U=X,Y,Z，F=XY,YZ，则F+ 为：37属性集闭包38计算属性集闭包举例如果X=A
10、，则：A,B,C如果X=B，则B,C如果X=C，则C设有关系模式R(U,F)，U=A,B,C，F=AB,BC39公理的完备性公理的完备性建立一套公理系统必须明确两个问题：一是能否保证按公理推导出的函数依赖都是正确的，即这些函数依赖是否都属于F+；也就是说对于关系模式R(U,F)，只要F中的函数依赖为真，则用公理根据F推导出的函数依赖也一定为真，这就是公理的正确性；另外一个问题是：用公理能否推导出所有的函数依赖？也就是说F+中所有的函数依赖是否都能用公理推导出来？这是一个很重要的问题，因为如果F+中有函数依赖不能用公理推导出来，那么就说明这些公理不够用、不完全，就必须补充新的公理，这就是公理的完
11、备性问题。40引理引理9.241引理9.2充分性证明：42引理9.2必要性证明：43公理的完备性还可以理解为： 所有不能用公理推导出的函数依赖都不为真，即如果XY不能根据F用公理导出，则XY F+ 。或者说存在一个具体的关系r，F+ 中的所有函数依赖都满足r，而不能用公理推导出的XY不满足r。也就是说，不能根据F用公理导出的函数依赖不属于F+ 。如果我们能够找到这样的r，则公理的完备性证明问题就解决了。44定理定理9.3：Amstrong公理是完备的。为了证明公理的完备性，找到了如下具体的关系r： 如果能够证明以下两点，则公理的完备性问题就证明了：在关系r中，F + 中的所有函数依赖都成立；在
12、关系r中，不能根据F用Amstrong公理推导出的函数依赖XY不成立。 45证：在关系r中，F+ 中的所有函数依赖都成立46证：在关系r中，不能根据F用Amstrong公理推导出的函数依赖XY不成立47由公理的完备性和引理9.2有结论：48属性集闭包的计算49算法9.1：50例：设有R（U,F），U=A,B,C,D,E，F=ABC,B D,C E,EC B,AC B求A,B,C,D,E=51函数依赖集的等价和最小化52覆盖和等价的定义定义9.5 设F和G是两个函数依赖集： 如果F +G +，则称G是F的一个覆盖，或称G覆盖F；如果F +G +和G +F +同时成立，即F +=G +，则称F和G
13、等价。53引理引理4.3F +=G +的充分必要条件是F G +并且G F +。必要性证明：充分性证明：54 F+=G+ FG+并且G F+ 为判定两个函数依赖集是否等价提供了简便方法： 可以首先检查F中的每个函数依赖XY是否属于G+（即计算Y是否属于XG+）？如果对F中的每个函数依赖都有XYG+，则有FG+ ；然后用同样的方法再检查GF+是否成立？如果它们都成立则F和G等价。55研究函数依赖集等价的目的研究函数依赖集等价的目的是为了对指定函数依赖集找出它的最小函数依赖等价集，即找出包含函数依赖尽可能少、甚至最少的函数依赖等价集，从而使模式分解简化，分解出最简单的关系模式。56最小函数依赖集的
14、定义定义9.6 如果函数依赖集F 满足如下条件，则称F 为一个最小函数依赖集，也称为极小函数依赖集或最小覆盖： F 中任一函数依赖的右部都仅含有一个属性； F中不存在这样的函数依赖XA，X有真子集Z，使得F与F-XA ZA等价； F中不存在这样的函数依赖XA，使得F与F-XA等价。 57 例例：假设有属性集U=A,B,C,D,E，函数依赖集F=AB,BC,ADE和函数依赖集G=AB,AC,BC,ADE， 问 F和 G是否是最小函数依赖集？答案：F是最小依赖集，G不是最小依赖集。58引理9.4 59引理引理9 9.4必要性证明60引理引理9 9.4充分充分性证明61引理9.5 设XA是F 中任意
15、函数依赖，G=F -XA，F 与G 等价的充分必要条件是 。 必要性证明充分性证明62计算最小覆盖的算法算法9.2 给定函数依赖集F，求其最小覆盖的过程如下：n逐一检查F 中各函数依赖XY，若Y=A1Ak，k=2，则用XAj | j=1,k来取代它（分解规则）；n逐一取出F中各函数依赖XA，若X=B1B2Bm，m=2，则逐一考查Bj（j=1,m），如果 ，则F与F-XA (X-Bj)A等价（引理9.4），故以X-Bj取代X； n逐一检查F中各函数依赖XA，令G=F-XA，根据引理9.5，如果 ，则F与G等价，故从F中去掉XA。 63例例：已知F=AB,BA,BC,AC,CA，求F的最小覆盖。
16、逐一检查F中的函数依赖是否多余，如果多余则可以去除之，最后的结果为：A B,B C,CA64 注意：算法9.2的第2、3两步是不可以颠倒的。65设F=CA,A D,CD B,B A依照算法9.2先既约化后无冗余化既约化令G=F-CD BC B结果G与F等价G= CA,A D,C B,B A无冗余化结果所求最小覆盖为F=A D,C B,B A66设F=CA,A D,CD B,B A先无冗余化后既约化无冗余化结果没有多余的函数依赖既约化结果G= CA,A D,C B,B A它不是最小覆盖，因为CA这时是多余的函数依赖。67规范化 规范化的目的就是要设计“好”的关系，使关系尽量减少操作异常甚至拒绝操
17、作异常现象。68第一范式 每个关系模式都应满足最低要求：所有分量都必须是不可分的最小数据项，并把其称为第一范式（1NF）关系。69非规范化表格和规范化表格70第二范式 定义9.7 如果R(U,F) 1NF，并且R中的每个非主属性都完全函数依赖于关键字，则R(U,F) 2NF。 71库存A关系实例：数据冗余插入异常更新异常删除异常72为了解决操作异常分解后的关系：库存B(仓库号,设备号,数量)仓库B(仓库号,地点)73第三范式第三范式 定义9.8 如果R(U,F) 2NF，并且所有非主属性都不传递依赖于关键字，则R(U,F) 3NF。 74仓库A关系实例数据冗余插入异常更新异常删除异常75为了解
18、决操作异常分解后的关系：仓库B(仓库号,仓库面积,所在城市)城市(省,城市)76BC范式77关系模式实例：管理(仓库号，设备号，职工号)它所包含的语义是：一个仓库可以有多个职工；一名职工仅在一个仓库工作；在每个仓库一种设备仅由一名职工保管（但每名职工可以保管多种设备）。根据以上语义有函数依赖：职工号仓库号(仓库号，设备号)职工号78进一步理解前述语义：79为了解决操作异常现象如何进行分解？任何分解都会破坏函数依赖：（仓库号，设备号）职工号结论：不将3NF分解成BCNF！80如何解决非BCNF带来的操作异常现象？ 不可能靠模式分解来解决问题，只有靠应用程序或设计数据库时建立一些必要的约束来预防操
19、作异常现象的发生。如第6章介绍的触发器。81多值依赖与第四范式 在关系模式上不仅存在函数依赖，还存在着其他的“依赖”影响着关系模式的质量，如多值依赖。 82讨论：三个实体之间的联系v 每个仓库可以存放多种设备，每名职工管理一个仓库中的所有设备；v 每名职工可以管理多个仓库的设备；v 每种设备可以存放在多个仓库。示意数据83w关键字是(仓库号,职工号,设备号)，即All-KeywBCNFw是否还存在操作异常现象？为什么？ 例如，职工E4新分配到WH1仓库工作，这时必须插入如下3个元组：WH1E4P1WH1E4P2WH1E4P3 同样，如果P3不再存放在WH1仓库，这时则要删除多个元组：WH1E1
20、P3WH1E2P3WH1E4P3排列成关系84多值依赖的定义 定义9.10 设有关系模式R(U)，X、Y、Z是U的子集，Z=U-X-Y，如果对于X的一个给定值，存在一组Y值与其对应，而Y的这组值又不以任何方式与Z的值相关，则说Y多值依赖于X，记为XY。 若Z=（即Z为空），则将多值依赖XY称为平凡的多值依赖。 85在下表所示的关系上：给定一个仓库号值给定一个仓库号值，有一组职工号与其对应，而有一组职工号与其对应，而这组职工号值与设备号值没有任何依赖关系，所这组职工号值与设备号值没有任何依赖关系，所以以仓库号仓库号职工号职工号；同样同样仓库号仓库号设备号设备号；多值依赖具有对称的性质，即如果多值
21、依赖具有对称的性质，即如果XY，并且并且Z=U-X-Y，则则XZ也成立。也成立。 86 函数依赖可以看作是多值依赖的特例。 87第四范式 定义9.11 设关系模式R(U,D)1NF，若对每个非平凡的多值依赖XY，X都含有侯选关键字，则R(U,D)4NF。 z从定义可以看出，4NF限定了在关系模式的属性间不允许有非平凡、且非函数依赖的多值依赖。z这是因为，若XY是非平凡的多值依赖，且X含有侯选关键字，则有XY，所以4NF所允许的非平凡的多值依赖实际上就是函数依赖。z4NF自然是BCNF 88 非4NF关系到4NF关系的转换仍然是通过分解，上表所示的关系显然不是4NF，可以分解为：w职工职工(仓库
22、号仓库号,职工号职工号)w存放存放(仓库号仓库号,设备号设备号) 分解结果都是4NF关系。89规范化小结90模式分解模式分解的准则3NF无损连接和保持函数依赖算法使分解后的关系模式数最少91模式分解的准则n模式分解具有无损连接性；n模式分解能够保持函数依赖。92无损连接的形式定义：93保持函数依赖的形式定义：定义9.13 若 ，则R(U,F)的分解=R1(U1,F1),Rk(Uk,Fk)保持函数依赖。94 设有关系模式R（U，F），U=emp，wh，city，F=empwh，whcity，其中emp是职工号，wh是仓库号，city是仓库所在城市；从F中可以看出，一名职工只能在一个仓库工作，一个
23、仓库只能位于一个城市。 看如下的三个分解是否满足无损连接和保持函数依赖的特性：1=R1(emp,),R2(wh, ),R3(city, )2=R1(emp,wh,empwh ), R2(emp,city, empcity )3= R1(emp,wh,empwh ), R2(wh,city, whcity )95 为了得到更高范式的关系进行的模式分解，是否总能既保证无损连接、又保持函数依赖？如果要求分解保持函数依赖，那么模式分解总可以达到3NF，但是不一定能达到BCNF；如果要求分解具有无损连接的特性，那么一定可以达到BCNF；如果要求分解既保持函数依赖、又具有无损连接的特性，那么分解可以达到3
24、NF，但是不一定能达到BCNF。96例：设有关系模式R（U，F），U=A，B，C，F=ABC，CB，该关系模式是3NF的，因为存在一个主属性对非主属性的函数依赖CB，所以该模式不是BCNF。 为了达到BCNF就必须进行分解，但是任何分解都会破坏函数依赖ABC。 所以为了保持函数依赖，就必须放弃BCNF。97 在实践中BCNF的意义并不大，因为我们对模式分解的要求总是既要保证无损连接、又要保持函数依赖。那么，当一个关系是3NF时：n关键字是单属性时，该模式自然是BCNF；n关键字是复合属性，并且不存在主属性对非主属性的函数依赖，则该模式自然是BCNF；n关键字是复合属性，并且至少存在一个主属性对
25、非主属性的函数依赖，则为了保持函数依赖，模式分解无法达到BCNF。98 判断一个分解是否保持函数依赖，可以根据函数依赖的最小覆盖和等价来判断。99 判断一个分解是否具有无损连接特性可以用如下法则：关系模式R分解为R1和R2是无损连接分解的充分必要条件是： R1 R2 R1 - R2或 R1 R2 R2 R11003NF无损连接和保持函数依赖算法101对R（U，F）中的F进行最小化处理，即计算F的最小覆盖，并将最小等价依赖集仍然记为F；若有XA，并且XA=U，则=R，算法终止；找出不在F中出现的属性（即与F中任意函数依赖的左部和右部都无关的属性）， 把这样的属性构成一个关系模式R0（U0，），并
26、把U0从U中去掉，剩余的属性仍然记为U；对F按具有相同左部的原则进行分组（假定分为k组），每一组函数依赖Fi所涉及的全部属性形成属性集Ui，若UiUj（ij），就去掉Ui ；经过以上步骤得到的分解=R0，R1，Rk（R0可能为空，1k可能不连续）构成R的一个保持函数依赖的分解，并且每个Ri均为3NF；设X是R（U，F）的关键字，并令=RX（X，FX） ；若对某个Ui ，如果XUi ，则将RX 从中去掉，或UiX，则将Ri从中去掉；最后就是所求分解。3NF保持函数依赖和无损连接的分解算法1023NF无损连接和保持函数依赖算法举例103使分解后的关系模式数最少104算法9.3已经保证了：n3NF分
27、解；n保持函数依赖分解；n无损连接分解；一般为了操作方便，我们还希望：分解的关系模式数最少105设有函数依赖集合：F=AB，AC，BA，BC，AED，BDG，DE利用算法9.2求得的最小覆盖集是：F=AB，BA，BC，AED，BDG，DE按照算法9.3得到的模式分解是：=R1(A，B，C，BAC，AB)， R2(A，E，D，AED，DE)， R3(B，D，G，BDG)106还是刚才那个依赖集：F=AB，AC，BA，BC，AED，BDG，DE利用算法9.2求得的最小覆盖集是：F=AB，BA，BC，AED，BDG，DE注意：(AE)F+=A,B,C,D,E,G所以AE BD和AE GF+设F”=F
28、AEBD，AEG显然有F与F”等价。根据F”再计算最小覆盖，结果是：Fm=AB，BA，BC，AED，AEG，DE分解结果是：R1(A,B,C)、R2(A,D,E,G)107定义定义9.14：若G是F所有等价集中函数依赖个数最少的，则称G是F的最小等价集。108定义9.15 设(XY,F)=VW|VWF, VW 参与推导XY ，(X,F)=VW| VWF, VX F+, XV F+，则当(XY,F)(X,F)=，YXF+ 时，称X直接决定Y，记为 。 定义中(XY,F)表示包含在F中推导XY时用到的全部函数依赖；(X,F)表示依赖集F中函数依赖的左部与X能相互决定的函数依赖集，或称左部与X等价的
29、函数依赖集。 X直接决定Y也可以叙述为(XY,F)中所有函数依赖的左部都不能决定X 。109算法9.4 设F是无冗余和既约化的函数依赖集，求F的最小等价集的算法如下：1.把F中的函数依赖按左部等价进行分组；2.任一组中，若存在XV，YW并且X直接决定Y，则把它们合并为YVW，直到任一组中都不存在如此依赖对为止。110【本章小节】 本章的内容是关系数据理论，它是关系数据模型的重要理论基础，该理论可以指导关系数据库或关系模式的设计。关系的范式是对关系规范化程度的一个衡量标准，原则上规范化程度越高，关系的质量越好。关系的规范化过程是模式分解的过程，模式分解需要遵守保持函数依赖和无损连接的原则。 111
