《7c函数依赖理论及闭包与覆盖》由会员分享，可在线阅读，更多相关《7c函数依赖理论及闭包与覆盖（22页珍藏版）》请在金锄头文库上搜索。
1、2018年9月12日星期三,1,数据库系统概念-关系数据库设计,7.4函数依赖,本节要点 逻辑蕴含 函数依赖集的闭包 属性集的闭包 无关属性 正则覆盖 最小覆盖(补) 无损分解 保持依赖,2018年9月12日星期三,2,数据库系统概念-关系数据库设计,7.4.1逻辑蕴含,逻辑蕴含定义 关系模式R(F),如果rR(F)，r一定满足f， 称F逻辑蕴含f， 记作Ff 示例： R(sno,sname,dno,dname,cno,cname,score) F:snosname,dno dnodname cnocname sno,cnoscore 判定F是否逻辑蕴含下列函数依赖： f1:snodname
2、f2:sno,cno,cnameR f3:sno,dnocno,cname,2018年9月12日星期三,3,数据库系统概念-关系数据库设计,7.4.1函数依赖集的闭包,定义： 关系模式R(F)中，F逻辑蕴含的所有函数依赖的集合，称为F的闭包，记作F+ 关系模式R(F)上成立的所有函数依赖的集合 F+的规模： Np 任何计算F+的算法一定是np 思考： 对R(F),是否rR(F) ，r一定满足F+？,2018年9月12日星期三,4,数据库系统概念-关系数据库设计,7.4.1函数依赖,对关系模式R(F),下列说法等价： F F+ 在R(F)上成立,2018年9月12日星期三,5,数据库系统概念-关
3、系数据库设计,7.4.1 Armstrong公理,对关系模式R(F) 如何求F所逻辑蕴含的函数依赖？ 如何计算F+？ Armstrong公理 对关系模式R(F)，,是R的属性集： 自反律(reflexivity)：若，则 增广律(augmentation)：若，则 传递律(transitivity)：若，则,2018年9月12日星期三,6,数据库系统概念-关系数据库设计,7.4.1 Armstrong公理,定理： Armstrong公理具有保真性及完备性； 保真性(sound)(正确性、有效性) 使用Armstrong公理从F中导出的函数依赖f必为F所蕴涵 保真性证明 完备性complete
4、F所蕴涵的函数依赖都能用Armstrong公理从F中导出 完备性证明(学习属性集闭包之后证明),2018年9月12日星期三,7,数据库系统概念-关系数据库设计,7.4.1 Armstrong公理推论,Armstrong公理推论： 合并律(union rule) 若，则 分解律(decomposition rule) 若 ，则， 伪传递律(pseudotransitivity rule) 若，则,2018年9月12日星期三,8,数据库系统概念-关系数据库设计,7.4.1 Armstrong公理,示例： R(sno,sname,dno,dname,cno,cname,score) F:snosna
5、me,dno dnodname cnocname sno,cnoscore 判定F是否逻辑蕴含下列函数依赖： f1:snodname f2:sno,cnoR f3:sno,dnocno,cname,2018年9月12日星期三,9,数据库系统概念-关系数据库设计,7.4.1 计算F+,算法：计算F+ F+=F repeat for each 函数依赖f in F+ 在f上应用自反律和增补律将结果加入到F+ for each 一对函数依赖f1和f2 in F+ if f1和f2可以使用传递律连接起来，将结果加入到F+ until F+不再发生变化 算法的时间复杂性：NP 不可能有计算F+的多项式算
6、法 计算闭包算法的特征： 集合按照一定规则生长、直到不能再生长；,2018年9月12日星期三,10,数据库系统概念-关系数据库设计,7.4.2属性集的闭包：+,定义 关系模式R(F),R： F下函数决定的所有属性的集合 称作属性集(在F下)的闭包,记作 或+ 示例： R(sno,sname,dno,dname,cno,cname,score) F:snosname,dno dnodname cnocname sno,cnoscore 属性集闭包： (sno)+=sno,sname,dno,dname (cno)+=cno,cname (sno,cno)+=R 练习，试计算属性集闭包： (dno
7、)+, (sno,dno)+, (cno,dno)+,2018年9月12日星期三,11,数据库系统概念-关系数据库设计,7.4.2计算+,算法，计算+： result := while (result发生变化）do for each 函数依赖 F do if result then result := result Output result /算法结束时， result即是+ 算法时间复杂性分析： O(n2),2018年9月12日星期三,12,数据库系统概念-关系数据库设计,7.4.2计算+ ：算法正确性证明,证明：算法结束时，result= +(即Armstrong 公理完备性) 证明：
8、0)记算法结束时，result=A1A2Am，R-result=B1B2Bn 1)反证法；假设result+,必有result+，即： 必存在属性(不妨设该属性为B1) ：B1+,B1result； 2)构造如图所示关系r。 3)关系r满足F： 如不然，算法不会结束。 4)关系r不满足B1； 5) B1+,必有B1F+；r不满足F+。 6) r满足F，不满足F+，矛盾； 假设不成立，证毕。,2018年9月12日星期三,13,数据库系统概念-关系数据库设计,7.4.2计算+的作用,计算+的作用： 检验是否为SuperKey 检验是否为CandiditeKey 检验是否为S.K. 如果是S.K.，
9、逐个去掉的一个属性，检验是否依然是SK 如果是S.K. ，去掉的每个属性都不再是S.K.，则为C.K. 求R(F)的一个C.K. 求R(F)的所有候选码 断定是否成立 计算F+的另一种算法 思考： 上述计算/判定算法，哪些是P算法？哪些是NP算法？,2018年9月12日星期三,14,数据库系统概念-关系数据库设计,7.4.3无关属性,无关属性/无关函数依赖提出的背景示例： R(sno,sname,dno,dname) F:snosno,sname,dname sno,snamedno dnodname, sno,dnosname,dname F中，有些函数依赖中的属性是否出现，不影响F的表示能
10、力，这些属性称为无关属性 F中，有些函数依赖是否出现，不影响F的表示能力，这些函数依赖称为无关函数依赖 为检查无关属性/无关函数依赖,DBMS将付出更大代价,2018年9月12日星期三,15,数据库系统概念-关系数据库设计,7.4.3无关属性的定义,无关属性的定义 F中一个函数依赖f,去掉f中的某一个属性，不影响F的表示能力,称该属性为无关属性 对F，去掉f中的某一个属性后，记为F 不影响F的表示能力，即F+=F+ 注意： 对函数依赖集F,一次只能讨论一个属性的无关性 不能同时讨论F中两个属性的无关性 如：R(ABCD),F=ABCD ;BC;CB,则 1)ABCD中B或C均是无关属性 2)不
11、能说BC同时为无关属性,2018年9月12日星期三,16,数据库系统概念-关系数据库设计,7.4.3左无关属性及判定,左无关属性： 记F= (F- )(-A) FF成立时，称A在中左无关 左无关属性的判定： F F 永真 判定左无关只需要判定F F是否成立 关键是判定F (-A)是否成立 判定左无关只需要判定： (-A)F+是否包含 判断左无关属性算法的复杂性：P,2018年9月12日星期三,17,数据库系统概念-关系数据库设计,7.4.3右无关属性及判定,右无关属性： 记F= (F- )(-A) FF成立时，称A在中右无关 右无关属性的判定： FF 永真 判定右无关只需要判定FF 是否成立
12、关键是判定F(A)是否成立 判定右无关只需要判定： ()F+是否包含A 判断右无关属性算法的复杂性：P 注意： 判定左/右无关属性，求属性集闭包分别使用F和F 判定左/右无关属性均不需要计算F+,均是P算法,2018年9月12日星期三,18,数据库系统概念-关系数据库设计,7.4.3正则覆盖CanonicalCover,正则覆盖定义: 关系模式R(F),F 的正则覆盖记为Fc, Fc要满足： FcF，并且： 1)Fc不含无关属性 2)Fc没有两个函数依赖左端相同 示例: R(sno,sname,dno,dname) F:snosno,sname,dname sno,snamedno dnodn
13、ame, sno,dnosname,dname Fc: snosname,dno dnodname,2018年9月12日星期三,19,数据库系统概念-关系数据库设计,7.4.3计算Fc,求Fc的算法 Step1:逐个属性判断是否为无关属性; Step2:发现无关属性，去掉该属性，并重新进行step1;直到没有无关属性； Step3:左端相同的函数依赖合并； 求Fc算法的复杂性 多项式算法,2018年9月12日星期三,20,数据库系统概念-关系数据库设计,7.4.3 Fc的不唯一性,Fc的不唯一性 R(A,B,C)，F=AR,BR,CR 计算Fc 思考：它有几个不同的Fc?,2018年9月12日
14、星期三,21,数据库系统概念-关系数据库设计,7.4.3最小覆盖Fm,最小覆盖定义(补): 关系模式R(F),F 的最小覆盖记为Fm,Fm满足： FmF，并且： 1)Fm不含无关属性 2)Fm中函数依赖右端属性只有一个 示例：R(A,B,C)，F=AR,BR,CR Fc/Fm:AB，BC，CA Fc/Fm:AC，CB，BA Fc:ABC，BA,CA Fm:AB,AC，BA,CA Fc:BAC，AB,CB ,2018年9月12日星期三,22,数据库系统概念-关系数据库设计,7.4函数依赖理论：课外练习,关系模式 R=(SNO,SNAME,CNO,CNAME,TNO,TNAME,BNO,BNAME) 函数依赖集F： SNOSNO,SNAME CNOCNO,CNAME TNOTNO,TNAME BNOBNO,BNAME TNOCNO, CNAME SNO,SNAME,CNO,CNAMETNO,TNAME 1、求F的正则覆盖Fc; 2、求R的一个候选码; 3、你能给出R的所有候选码吗？,
