第3讲函数依赖和公理

*第三章数据依赖函数依赖是数据库理论中最主要的组成部分，是设计 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 的数据库模式的理论基础。数据依赖表示数据间存在的一种制约或约束关系。有多种数据依赖，常见的数据依赖有：函数依赖、多值依赖、连接依赖。*本章的主要内容：函数依赖的概念及函数依赖公理函数依赖集的等价和覆盖多值依赖及多值依赖公理连接依赖*3.1函数依赖(FunctionaldependencyFD)定义1(FD)设关系模式R(U)，X,YU，r是R(U)上的任一关系，对任意t1、t2r,如果t1[X]=t2[X]有t1[Y]=t2[Y]，称X函数决定Y，或Y函数依赖于X，记为：FDX→Y。定义2（FD的等价定义）对X中的任一值x，ΠY(σX=x(r))的值仅有一个元组，则有X→Y。*练习1设关系r如下所示：r(ABCDE)a1b1c1d1e1a1b2c2d2e1a2b1c3d3e1a2b1c4d3e1a3b2c5d1e1说明r上函数依赖：A→D,AB→D,C→BDE，E→A是否成立？*定义(平凡/非平凡的FD):设FDX→Y，如果YX，则称FDX→Y为非平凡的函数依赖；否则，若YX，称FDX→Y为平凡的函数依赖。定义(完全FD):设FDX→Y，如果对任意的XX，X→Y都不成立，则称X→Y是完全函数依赖；若对X的真子集X有XX，而X→Y成立，则称FDX→Y是部分函数依赖，即Y函数依赖于X的一部分。练习1中函数依赖AB→D是完全依赖还是部分依赖？思考：如果X只有一个属性，X→Y是否一定是完全函数依赖？定义(传递FD):设关系模式R，X、Y、Z是R的属性子集，若FDX→Y，Y→X，Y→Z，则有FDX→Z，称FDX→Z为传递函数依赖。函数依赖、完全依赖、传递依赖等基本概念是第四章关系数据库范式的基础。*函数依赖的例子学校数据库的语义：⒈一个系有若干学生，一个学生只属于一个系；⒉一个系只有一名主任；⒊一个学生可以选修多门课程，每门课程有若干学生选修；⒋每个学生所学的每门课程都有一个成绩。R(SNO,CNO,SNAME,GRADE,DEPT,MNG)（1）找出其中基本的函数依赖？（2）哪些是平凡依赖？指出哪些是完全依赖？哪些是部分依赖？哪些是传递依赖？SNO→DEPT,DEPT→MNG;SNO,CNO→GRADE;SNO,CNO→SNO;SNO,CNO→SNAME;SNO→MNG*3.2函数依赖公理3.2.1函数依赖公理由关系模式R上的函数依赖组成的集合F称为R上的函数依赖集，记为：FDsF。定义(FD的逻辑蕴涵)：设关系模式R(U,F)，X,YU，如果能从函数依赖集F推导出FDX→Y，则称F逻辑蕴涵FDX→Y，或称X→Y逻辑蕴涵于F。记为F|=X→Y。*已知函数依赖集F，如何判断一个函数X→Y是否逻辑蕴涵于F？需要哪些推理法则（包括3个公理和3个推论）？Armstrong公理（三个公理）：设r是R(U)上的一个关系，X、Y、Z、WU。A1.自反律:若YXU,则X→Y;A2.增广律:若X→Y且ZU，则XZ→YZ;A3.传递律:若X→Y,Y→Z，则X→Z.有以上三个公理，可以推出以下3个推论：推论1（合成规则）：若X→Y，X→Z，则X→YZ推论2（分解规则）：若X→Y且ZY，则X→Z推论3（伪传递规则）若X→Y，YZ→W，则XZ→W。*推论1（合成规则）：若X→Y，X→Z，则X→YZ。证明：若X→YX→XYX→ZXY→YZX→YZ（增广和传递律推论2（分解规则）：若X→Y且ZY，则X→Z。证明：ZYY→Z（自反和传递律）推论3（伪传递规则）若X→Y，YZ→W，则XZ→W。证明：X→YXZ→YZYZ→WXZ→W（增广和传递律）*示例：SC(SNO,CNO,SNAME,GRADE,DEPT,MN)F={SNO,CNO→GRADE，SNO→SNAME，DEPT，DEPT→MN}F|=SNO,CNO→SNAME,GRADE,DEPT,MN？SNO→SNAME，DEPT，MN（分解规则，传递律，合成规则）SNO,CNO→SNAME，DEPT，MN（自反律和传递律）SNO,CNO→SNAME,GRADE,DEPT,MN（合成规则）思考：由最后一个依赖关系，那否得出是SNO,CNO关系SC的键？*定理1如果Ai(i=1,2,…,n)是关系模式R的属性，则X→A1A2…An成立的充要条件是：X→Ai(i=1,2,…,n)都成立。3.2.2公理的完备性定理2Armstrong公理是完备的。即：F所蕴涵的函数依赖X→Y一定能被公理推出。*例：设F={AB→E，AG→J，BE→I，E→G，GI→H}试证：F|=AB→GH证明：用公理系统和F中的函数依赖，推导过程如下：1.已知AB→E，E→G则：AB→G；(传递律)2.已知AB→E则：AB→BE；(增广律)3.已知BE→I，又AB→BE则：AB→I(传递律)4.由1和3有AB→G，AB→I则：AB→GI(合成规则)5.由4有AB→GI，又GI→H则：AB→H(传递律)6.由1和5有AB→H，AB→G则：AB→GH(合成规则)*定义(使用集)用公理从F推出X→Y成立所使用的函数依赖组成的序列称F上的一个推理序列。在推理序列中出现的且包含在F中的函数依赖的集合称推理序列的使用集(useset)，记为：U(F,X→Y)例：U(F,AB→GH)={AB→E，E→G，BE→I，GI→H}*定义(函数依赖集F的闭包F+)设F是关系r(R)上的函数依赖集，F所蕴含的所有FD的集合称为F的闭包，记作F+。F+={X→Y|所有F|=X→Y}例：设F={AB→C，C→B}。求F+*设F={AB→C，C→B}。F+为：F+={A→A,AB→A,AC→A,ABC→A,B→B,AB→B,BC→B，ABC→B，C→C，AC→C，BC→C,ABC→C，AB→AB，ABC→AB，AC→AC，ABC→AC，BC→BC,ABC→BC,ABC→ABC,AB→C,AB→AC,AB→BC,AB→ABC，C→B,C→BC，AC→B，AC→AB}*为了判定函数依赖集F是否蕴涵X→Y，引入的属性闭包：定义(属性集X的闭包X+)设关系模式R(U,F)，U=A1A2…An,XU,所有用公理和F推出的函数依赖X→Ai中Ai的集合，称X对于函数依赖集F的闭包，记作：X+X+={Ai|F|=X→Ai且AiU}*3.2.1函数依赖集闭包及成员测试算法算法1计算属性集X的闭包X+的算法输入：属性集X和函数依赖集F输出：X的闭包X+WhileRESULT≠VARdoBeginVAR:=RESULT;foreveryFDW→ZinFdoifWRESULTthenRESULT:=RESULT∪Zend;return(RESULT)end.//其中的原理：由WRESULT,由自反律：RESULT→W，再由传递律：RESULT→ZCLOSURE(X,F)BeginVAR:=φ;RESULT:=X;*例：F={A→D,AB→E,BI→E，CD→I，E→C}求：AE+解：AE0=AEAE1=AEDAE2=AEDC(第一轮扫描后的结果）…AE+=ACDEI练习：属性集U为ABCD，F={A→B,B→C,D→B}求：A+,(AD)+,(BD)+*算法3.2.3判定F是否蕴涵X→Y的成员测试算法输入：函数依赖集F和FDX→Y。输出：若F蕴涵X→Y输出为true，否则为falseMEMBER(F,X→Y)beginifYCLOSURE(X,F)thenreturn(true)elesreturn(false)end.*成员测试算法练习练习：F={A→D,AB→DE,CE→G，E→H}判断：（1）F|=AB→CD?（2）F|=AB→EH?*综合练习设F={AB→C,B→D,CD→E,CE→GH,G→A}（1）用成员测试法（MEMBER(F,AB→G))证明AB→G，（2）用推理的方法证明F|=AB→G（3）并比较两种方法更好用语言来实现。*（1）设F={AB→C,B→D,CD→E,CE→GH,G→A}，证明F|=AB→GAB0=ABAB1=ABCAB2=ABCDAB3=ABCDEAB4=ABCDEGHAB+=ABCDEGHGAB+所以，F|=AB→G