数据库课程第6章课件

1、第六章 关系数据库的模式设计,1,PPT学习交流,思考：,任何一个二目关系模式R（A，B）一定属于BCNF吗？一定属于4NF吗？ 关系模式R（A，B，C），ABC一定成立吗？ 一个全是主属性的关系模式一定可以达到第几范式？ 一个全键的关系模式一定可以达到第几范式？,A B B A R4NF？,2,PPT学习交流,解释范式之间的关系(),3NF 2NF 反证：若R3NF， 但R2NF，则按2NF定义，一定有非主属性部分依赖于码， 设X为R的码，则存在X的真子集X，以及非主属性Z（Z X），使得XZ。 于是在R中存在码X，属性组X，以及非主属性Z（Z X) ，使得XX， XZ，XX成立，这与R3N

2、F矛盾。 所以R2NF。,3,PPT学习交流,解释范式之间的关系(),BCNF 3NF 反证：若RBCNF， 但R3NF，则按3NF定义，一定有非主属性对码的传递依赖，于是存在： R的码X ，属性组Y，以及非主属性Z（Z Y），使得XY， Y Z，YX成立 。 由YZ，按BCNF定义，Y含有码，于是YX成立，这与YX矛盾。 所以R3NF。 4NF BCNF,4,PPT学习交流,练习:,(4) 如果下表为R的数据,存在什么错误? C# H R S G C1 周一 101 张 80 C1 周二 203 张 80 C1 周一 101 李 86 C2 周三 204 王 78 C2 周四 301 王 7

3、8 C2 周三 204 张 74,遗漏： （C1 周二 203 李 86） （C2 周四 301 张 74）,5,PPT学习交流,练习:,设有关系模式R(A，B，C，D)，其函数依赖集为F=AB，BA，ACD，BCD，AD C，BDC，ACD，BCD 请回答如下问题： (1)指出R的所有候选键； (2)R属于第4范式吗，为什么?,1) R的候选键为: AC, 或BC, 或AD, 或BD 2) R不属于4NF,6,PPT学习交流,规范化的基本思想： 逐步消除数据依赖中不合适的部分 “一事一地”模式设计原则： 一个关系只说明一个概念、一件事物或事物 间的一种联系，这是规范化的目标,6.2.9 规范

4、化的步骤,7,PPT学习交流,规范化的基本步骤,1NF,2NF,3NF,BCNF,消去非主属性对键的部分函数依赖,消去非主属性对键的传递函数依赖,消去主属性对键的传递函数依赖,4NF,消去非平凡且非函数依赖的多值依赖,8,PPT学习交流,6.3 数据依赖的公理系统,逻辑蕴涵 推理规则 闭包 函数依赖的闭包 属性集的闭包 函数依赖集的覆盖与等价 最小函数依赖集,9,PPT学习交流,1 函数依赖的逻辑蕴涵,定义 设F是关系模式R的一个函数依赖集，X,Y是R的属性子集，如果从F中的函数依赖能够推出XY,则称F逻辑蕴涵XY,记为,10,PPT学习交流,2 函数依赖的推理规则,Armstrong公理 X

5、，Y，Z是属性集， 自反律。若Y X， 则X Y。 增广律。若X Y ，则XZ YZ。 传递律。若X Y， Y Z，则X Z 。 合并律。若X Y，X Z，则X YZ。 分解律。若X YZ ，则X Y，X Z 。 伪传递律。若X Y，WY Z，则XW Z 。,11,PPT学习交流,3 函数依赖的闭包,定义 在关系模式R中，为F所逻辑蕴涵的函数依赖的全体构成的集合称作F的闭包，记作F+。,例：F=XY，YZ，则XZ F+。,闭包的计算是一个复杂的工作，F不大， F+却可能很大。,12,PPT学习交流,4 属性集的闭包,定义： 设F是属性集合U上的一个函数依赖集，X U,则称用Armstrong推

6、理规则推出的函数依赖X A中所有A的集合，称为属性集X关于F的闭包，记为X+,显然： X X+,13,PPT学习交流,4 闭包的计算,目标 通过给定的函数依赖，找出所有的函数依赖 方法 利用FD的规则(传递、合并、分解)，推导出函数依赖的集合，即闭包(closure),14,PPT学习交流,4 闭包的计算,闭包 F的闭包是指F逻辑蕴涵的所有函数依赖的集合，记作F+ 闭包的意义 检验给定的函数依赖是否蕴涵于某个函数依赖集S 从给定的函数依赖，可以推导出蕴涵的函数依赖,15,PPT学习交流,4 闭包的计算,判定XY是否在F中，只要判断XY能否用推理规则从F导出，即判断Y 是否成立。这样就把计算F的

7、问题简化为计算的 问题。,求整个关系的FD集，即求F+将是一个繁杂的过程 例：求关系R(A,B,C)的F+: F+包含 A +、B +、C + AB +、AC +、BC + ABC +,16,PPT学习交流,4 闭包的计算,算法：求属性集X关于函数依赖集F的属性闭包 。 输入：有限的属性集合U,它上面的函数依赖集合F，和U的一个子集X. 输出：X关于F的闭包 。 方法： 1、置初始X(0) =X,i=0; 2、对F中的每一个函数依赖Y Z,若Y X(i),置X(i+1)=X(i)Z 3、如果X(i+1)= X(i),置i=i+1,并转2;否则转4 4、输出X(i),即为,即，将可以被X(i)决

8、定的属性加入到X(i+1)中,17,PPT学习交流,4 闭包的计算,举例：R (A, B, C, D, E), F = ABC, BD, CE, CEB, ACB,计算 。,解：由算法： 第一次： X(0) =AB; 搜索F中的每一个函数依赖，得AB C与B D因为 AB,B X(0),置X(1)=ABCD=ABCD X(1)= X(0)，继续下一轮 第二次： X(1)= ABCD，找到C E,与AC B,置X(2)=ABCD E B=ABCDE X(2)= X(1)，继续下一轮 第三次： 由于X(2)= ABCDE,找到ECB,置X(3)=ABCDE B=ABCDE X(3)= X(2)，转

9、4 4）输出X(2)=X+=ABCDE,X(i)最多到UR终止,18,PPT学习交流,例：对关系R（A,B,C,D,E,F）,给定函数依赖ABC,BCAD,DB,CFB,求 A，B+,4 闭包的计算,AB += AB AB +=ABC/ABC AB +=ABCD/BCAD AB +=ABCD/DB,19,PPT学习交流,所用依赖 AEABE BEAGABEG GDABEGD = ABEGD,4 闭包的计算,示例 RU = (A, B, C, D, E, G), F = AE, BEAG, CEA, GD,计算,20,PPT学习交流,示例 R (A, B, C, G, H, I), F = AB

10、, AC, CGH, CGI, BH,计算 。,4 闭包的计算,21,PPT学习交流,示例 R (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH,计算 。 所用依赖 ABAGB ACAGBC CGHAGBCH CGI AGBCH I = AGBCH I,4 闭包的计算,AG为 候选码,22,PPT学习交流,题型（闭包的计算和应用）,设有关系模式R(A,B,C,D)F是R上成立的FD集，F=ABC, DB，试求属性集AD的闭包(AD)+ 并回答在F的闭包中所有左边为AD的函数依赖有多少。,(AD)+=ABCD 有16个,23,PPT学习交流,5 函数依赖集

11、的等价和覆盖,定义 函数依赖集的等价性 函数依赖集F，G，若F+= G+，则称F与G等价。 F+ = G+ F G+，G F+ 判定： 要判定F G+，只须逐一对F中的函数依赖XY，考察Y是否属于XG+就行了。,24,PPT学习交流,6 最小函数依赖集,定理6.4： 每个函数依赖集F都可以被一个右部只有单属性的函数依赖集G所覆盖。 最小依赖集 满足下列条件的函数依赖集F称为最小函数依赖集合，记作Fmin： 右边单属性化：F中任一函数依赖X A，A必是单属性。 无冗余依赖：F中不存在这样的函数依赖X A，使得F与F X A等价。 无冗余决定属性：F中不存在这样的函数依赖X A，在X中有真子集Z，

12、使得F与（F X A） Z A等价。,25,PPT学习交流,6 最小函数依赖集,算法求解函数依赖集F的最小函数依赖集合Fmin 右边单属性化：逐个检查F中各函数依赖FDi ：XY， 若Y=A1 A2 Ak ，k2，则用诸XAi 代替Y。 无冗余依赖：逐个检查F中各函数依赖XA， 令G = FXA，若A ，则从F中去掉该函数依赖。 无冗余属性：逐个检查F中各函数依赖XA， 设X = B1Bm，逐个考查Bi， 若A ，则以（X Bi）取代X。,1,2,26,PPT学习交流,举例：,求F = ABC，EC，DAEF，ABFBD的最小函数依赖集合。 解：1、右边化为单属性 AB， AC，EC，DA，DE，DF， ABFB, ABFD 2、去掉冗余依赖ABFB(因为AB) 3、去掉冗余属性：因为(AF)+=ABFD，所以AF可以决定D，因此ABFD化简为AFD 最后结果： FMINAB， AC，EC，DA，DE，DF， AFD,27,PPT学习交流,6 最小函数依赖集,举例 F = AB，BA，AC，BC，求Fmin。 检查：右边已是单属性；左边已无冗余属性 检查AB，G=FAB=BA，AC，BC =A，C，B（A）G+ 检查AC，G=FAC=AB，BA，BC =A，B，C，C（A）G+ 所以AC是多余依赖，从F中删