第3讲函数依赖和公理
《第3讲函数依赖和公理》由会员分享，可在线阅读，更多相关《第3讲函数依赖和公理（22页珍藏版）》请在文档大全上搜索。
1、1第三章第三章数数 据据 依依 赖赖 函数依赖是数据库理论中最主要的组成部分，是设计规范的数据库模式的理论基础。数据依赖表示数据间存在的一种制约或约束关系。有多种数据依赖，常见的数据依赖有：函数依赖、多值依赖、连接依赖。2本章的主要内容：本章的主要内容：u 函数依赖的概念及函数依赖公理函数依赖的概念及函数依赖公理u 函数依赖集的等价和覆盖函数依赖集的等价和覆盖u 多值依赖及多值依赖公理多值依赖及多值依赖公理u 连接依赖连接依赖 33.1 3.1 函数依赖函数依赖( (Functional dependency FD)Functional dependency FD)定义定义1(1(FD)FD)
2、 设关系模式设关系模式R(U)R(U)，X,Y X,Y U U，r r是是R(U)R(U)上的任一关系，上的任一关系，对任意对任意t t1 1、t t2 2 r, r, 如果如果 t t1 1X=tX=t2 2X X 有有t t1 1Y=tY=t2 2 YY，称称X X函数决定函数决定Y Y，或或Y Y函数依赖于函数依赖于X X，记为：记为：FD XYFD XY。定义定义2（FD的等价定义）的等价定义） 对对X中的任一值中的任一值x，Y(X=x(r) 的的值仅有一个元组，则有值仅有一个元组，则有XY。 4 练习练习1设关系设关系r 如下所示：如下所示：l r( A B C D E )l a1
3、b1 c1 d1 e1l a1 b2 c2 d2 e1l a2 b1 c3 d3 e1l a2 b1 c4 d3 e1l a3 b2 c5 d1 e1l说明说明r r上函数依赖上函数依赖： AD, ABD, CBDEAD, ABD, CBDE，EAEAl是否成立？是否成立？5 定义定义( (平凡平凡/ /非平凡的非平凡的FD)FD):设设FD XYFD XY，如果如果Y Y X X，则称则称 FD FD XYXY为为非平凡的函数依赖非平凡的函数依赖；否则，若；否则，若Y Y X X，称称FD XYFD XY为为平凡平凡的函数依赖的函数依赖。 定义定义( (完全完全FD):FD): 设设FD X
4、YFD XY，如果对任意的如果对任意的X XX X，X X YY都都不成立，则称不成立，则称XYXY是完全函数依赖；若对是完全函数依赖；若对X X的真子集的真子集X X 有有X XX X，而而X X YY成立，则称成立，则称FD XYFD XY是部分函数依赖，即是部分函数依赖，即Y Y函数依赖函数依赖于于X X的一部分。的一部分。 练习练习1 1中函数依赖中函数依赖 ABDABD是完全依赖还是部分依赖？是完全依赖还是部分依赖？ 思考：思考： 如果如果X X只有一个属性，只有一个属性， XYXY是否一定是完全函数依赖？是否一定是完全函数依赖？定义定义( (传递传递FD):FD):设关系模式设关系
5、模式R R，X X、Y Y、Z Z是是R R的属性子集，的属性子集，若若FD XYFD XY，Y XY X，YZYZ，则有则有FD XZFD XZ，称称FD XZFD XZ为为传递函数依赖。传递函数依赖。 函数依赖、完全依赖、传递依赖等基本概念是第四章关系函数依赖、完全依赖、传递依赖等基本概念是第四章关系数据库范式的基础。数据库范式的基础。6函数依赖的例子函数依赖的例子学校数据库的语义：学校数据库的语义： 一个系有若干学生，一个系有若干学生， 一个学生只属于一个系；一个学生只属于一个系； 一个系只有一名主任；一个系只有一名主任； 一个学生可以选修多门课程，一个学生可以选修多门课程， 每门课程有
6、若干学生选修；每门课程有若干学生选修； 每个学生所学的每门课程都有一个成绩。每个学生所学的每门课程都有一个成绩。 R(SNO,CNO,SNAME,GRADE,DEPT,MNG)R(SNO,CNO,SNAME,GRADE,DEPT,MNG) （1 1）找出其中基本的函数依赖？）找出其中基本的函数依赖？（2 2）哪些是平凡依赖？指出哪些是完全依赖？哪些是部分依赖？哪）哪些是平凡依赖？指出哪些是完全依赖？哪些是部分依赖？哪些是传递依赖些是传递依赖 ？ SNO DEPT, DEPT MNG; SNO,CNOSNO DEPT, DEPT MNG; SNO,CNOGRADEGRADE; ; SNO,CNO
7、SNO; SNO,CNOSNO,CNOSNO; SNO,CNOSNAMESNAME; ; SNO SNOMNGMNG 73.2 3.2 函数依赖公理函数依赖公理3.2.1 3.2.1 函数依赖公理函数依赖公理 由关系模式由关系模式R R上的函数依赖组成的集合上的函数依赖组成的集合F F称为称为R R上上的函数依赖集，记为：的函数依赖集，记为： FDs FFDs F。定义定义( (FDFD的逻辑蕴涵的逻辑蕴涵) ) ： 设关系模式设关系模式R(U,F)R(U,F)，X,YX,Y U U，如果能从如果能从函数依赖函数依赖集集F F推导出推导出FD XYFD XY，则称则称 F F逻辑蕴涵逻辑蕴涵
8、FD XYFD XY，或称或称XYXY逻辑蕴涵于逻辑蕴涵于F F。记为记为 F|= XYF|= XY。8 已知函数依赖集已知函数依赖集F F，如何判断一个函数，如何判断一个函数XYXY是否逻辑蕴涵于是否逻辑蕴涵于F F ？需要哪些推理法则（包括？需要哪些推理法则（包括3 3个公理和个公理和3 3个推论）？个推论）？ArmstrongArmstrong公理（三个公理）：公理（三个公理）：设设r r是是R(U)R(U)上的一个关系，上的一个关系，X X、Y Y、Z Z、W W U U。A1. A1. 自反律自反律: : 若若Y Y X X U, U, 则则 XY;XY;A2. A2. 增广律增广律
9、: : 若若XYXY且且Z Z U U，则则 XZYZ;XZYZ;A3. A3. 传递律传递律: : 若若XY, YZXY, YZ，则则 XZ. XZ. 有以上三个公理，可以推出以下有以上三个公理，可以推出以下3 3个推论：个推论：推论推论1 1（合成规则）：（合成规则）： 若若XYXY，XZXZ，则则XYZXYZ推论推论2 2（分解规则）：（分解规则）： 若若XYXY且且Z Z Y Y，则则XZXZ推论推论3 3（伪传递规则）（伪传递规则） 若若XYXY，YZWYZW，则则XZWXZW。9推论推论1 1（合成规则）：（合成规则）： 若若XYXY，XZXZ，则则XYZXYZ。 证明：若证明：若
10、XY X XY XZ XYYZXYZ （增广和传递律增广和传递律推论推论2 2（分解规则）：分解规则）： 若若XYXY且且Z Z Y Y，则则XZXZ。 证明：证明： Z Y YZ （自反和传递律）推论推论3 3（伪传递规则（伪传递规则） 若若XYXY，YZWYZW，则则XZWXZW。 证明：证明： XY XZY Z YZ WXZW（增广和传递律增广和传递律）10示例：示例：SC(SNO,CNO,SNAME,GRADE,DEPT,MN)SC(SNO,CNO,SNAME,GRADE,DEPT,MN) F= SNO,CNOGRADE F= SNO,CNOGRADE， SNO SNO SNAMESN
