第3讲函数依赖和公理

《第3讲函数依赖和公理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章数据依赖函数依赖是数据库理论中最主要的组成部分，是设计规范的数据库模式的理论基础。数据依赖表示数据间存在的一种制约或约束关系。有多种数据依赖，常见的数据依赖有：函数依赖、多值依赖、连接依赖。1本章的主要内容：函数依赖的概念及函数依赖公理函数依赖集的等价和覆盖多值依赖及多值依赖公理连接依赖23.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

2、中的任一值x，ΠY(σX=x(r))的值仅有一个元组，则有X→Y。3练习1设关系r如下所示：r(ABCDE)a1b1c1d1e1a1b2c2d2e1a2b1c3d3e1a2b1c4d3e1a3b2c5d1e1说明r上函数依赖：A→D,AB→D,C→BDE，E→A是否成立？4定义(平凡/非平凡的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函

3、数依赖于X的一部分。练习1中函数依赖AB→D是完全依赖还是部分依赖？思考：如果X只有一个属性，X→Y是否一定是完全函数依赖？定义(传递FD):设关系模式R，X、Y、Z是R的属性子集，若FDX→Y，Y→X，Y→Z，则有FDX→Z，称FDX→Z为传递函数依赖。函数依赖、完全依赖、传递依赖等基本概念是第四章关系数据库范式的基础。5函数依赖的例子学校数据库的语义：⒈一个系有若干学生，一个学生只属于一个系；⒉一个系只有一名主任；⒊一个学生可以选修多门课程，每门课程有若干学生选修；⒋每个学生所学的每门课程都有一个成绩。R(SNO,CNO,SNAME,GRADE,DEPT,MNG)（1）找出其中

4、基本的函数依赖？（2）哪些是平凡依赖？指出哪些是完全依赖？哪些是部分依赖？哪些是传递依赖？SNO→DEPT,DEPT→MNG;SNO,CNO→GRADE;SNO,CNO→SNO;SNO,CNO→SNAME;SNO→MNG63.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

5、=X→Y。7已知函数依赖集F，如何判断一个函数X→Y是否逻辑蕴涵于F？需要哪些推理法则（包括3个

6、公理和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。8推论1（合成规则）：若X→Y，X→Z，则X→YZ。证明：若X→YX→XYX→ZXY→YZX→YZ（增广和传递律推论2（分解规则）：若X→Y且ZY，则X→Z。证明：ZY

7、Y→Z（自反和传递律）推论3（伪传递规则）若X→Y，YZ→W，则XZ→W。证明：X→YXZ→YZYZ→WXZ→W（增广和传递律）9示例：SC(SNO,CNO,SNAME,GRADE,DEPT,MN)F={SNO,CNO→GRADE，SNO→SNAME，DEPT，DEPT→MN}F

8、=SNO,CNO→SNAME,GRADE,DEPT,MN？SNO→SNAME，DEPT，MN（分解规则，传递律，合成规则）SNO,CNO→SNAME，DEPT，MN（自反律和传递律）SNO,CNO→SNAME,GRADE,DEPT,MN（合成规则）思考：由最后一个依赖关系，那否得出是SNO,CNO关

9、系SC的键？10定理1如果Ai(i=1,2,…,n)是关系模式R的属性，则X→A1A2…An成立的充要条件是：X→Ai(i=1,2,…,n)都成立。3.2.2公理的完备性定理2Armstrong公理是完备的。即：F所蕴涵的函数依赖X→Y一定能被公理推出。11例：设F={AB→E，AG→J，BE→I，E→G，GI→H}试证：F

10、=AB→GH证明：用公理系统和F中的函数依赖，推导过程如下：1.已知AB→E，E→G则：AB→G；(传递律)2.已知AB→E则：AB→BE；(增