第三章数据依赖.ppt
《第三章数据依赖.ppt》由会员分享,可在线阅读,更多相关《第三章数据依赖.ppt(62页珍藏版)》请在三一文库上搜索。
1、1,第三章 数 据 依 赖,2,本章的主要内容: 函数依赖的概念及函数依赖公理 函数依赖集的等价和覆盖 多值依赖及多值依赖公理 连接依赖,3,数据依赖 : 函数依赖、多值依赖、连接依赖,数据依赖 是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系 是现实世界属性间相互联系的抽象 是数据内在的性质 是语义的体现,4,3.1 函数依赖(Functional dependency FD) 定义1(FD) 设关系模式R(U),X,Y U,r是R(U)上的任一关系,对任意t1、t2r, 如果 t1X=t2X 有t1Y=t2 Y,称X函数决定Y,或Y函数依赖于X,记为:FD XY。,定义2(FD
2、) 对X中的任一值x,Y(X=x(r) 的值仅有一个元组,则有XY。,定义(平凡/非平凡的FD) 设FD XY,如果YX,则称 FD XY为非平凡的函数依赖;否则,若YX,称FD XY为平凡的函数依赖。,5,定义(完全FD): 设FD XY,如果对任意的XX,XY都不成立,则称XY是完全函数依赖;若对X的真子集X有XX,而XY成立,则称FD XY是部分函数依赖,即Y函数依赖于X的一部分。,函数依赖的例子,学校数据库的语义: 一个系有若干学生, 一个学生只属于一个系; 一个系只有一名主任; 一个学生可以选修多门课程, 每门课程有若干学生选修; 每个学生所学的每门课程都有一个成绩。,R(SNO,C
3、NO,SNAME,GRADE,DEPT,MNG) SNO DEPT, DEPT MNG; SNO,CNOGRADE;,SNO,CNOSNO; SNO,CNOSNAME; SNOMNG,7,3.2 函数依赖公理 3.2.1 函数依赖公理 定义(FD的逻辑蕴涵) : 设关系模式R(U,F),X,YU,如果能从函数依赖集F推导出FD XY,则称 F逻辑蕴涵 FD XY,或称XY逻辑蕴涵于F。记为 F|= XY。,8,Armstrong公理: 设r是R(U)上的一个关系,X、Y、Z、WU。 A1. 自反律: 若YXU, 则 XY; A2. 增广律: 若XY且ZU,则 XZYZ; A3. 传递律: 若X
4、Y, YZ,则 XZ.,9,证明: A1. 自反律: 若YXU, 则 XY; 设r是R的关系,t1, t2是r的任意元组,X、Y、Z U (1) 对X的任意值x,有X(X=x(r)至多有一个元组, 因YX,Y(X=x(r)至多只有一个元组,则有XY,10,证明: A2. 增广律: 若XY且ZU,则 XZYZ; (2) 对任意x值,X(X=x(r)至多有一个 元组。有 : XZ=xz (r) X=x(r),则 Y(XZ=xz(r) Y(X=x(r)。所以, Y (XZ=xz (r)至多有一个元组, r必满足XZY。,11,证明: A3. 传递律: 若XY, YZ,则 XZ. (3) 若XY,则t
5、1X = t2X, t1Y = t2Y 又 YZ,则有t1Y=t2Y, t1Z=t2Z。 显然,XY在r中成立。,12,推论1 若XY,XZ,则XYZ。 证明:若XY X XY XZ XYYZ,XYZ,推论2 若XY且ZY,则XZ。 证明: ZY YZ 推论3 若XY,YZW,则XZW。 证明: XY XZY Z YZ W,XZW,13,示例:SC(SNO,CNO,SNAME,GRADE,DEPT,MN) F= SNO,CNOGRADE, SNO SNAME,DEPT, DEPT MN,SNO SNAME,DEPT,MN SNO,CNO SNAME,DEPT,MN SNO,CNO SNAME,
6、GRADE,DEPT,MN,14,定理1 如果Ai (i =1, 2, , n)是关系模式R的属性,则 X A1 A2 An 成立的充要条件是: X Ai (i =1, 2, , n) 都成立。,15,例: 设F=ABE,AGJ,BEI,EG,GIH 试证:F|= ABGH 证明:用公理系统和F中的函数依赖,推导过程如下: 1. 已知 ABE,EG 则:ABG; (传递律) 2. 已知 ABE 则:ABBE; (增广律) 3. 已知 BEI,又 ABBE 则:ABI (传递律) 4. 由1和3有ABG, ABI 则:ABGI (合成规则) 5. 由4有 ABGI,又 GIH 则:ABH (传递
7、律) 6. 由1和5有 ABH,ABG 则:ABGH (合成规则),16,定义(使用集) 用公理从F推出 XY成立所使用的函数依赖组成的序列称F上的一个推理序列。由推理序列中出现的且包含在F中的函数依赖的集合称推理序列的使用集(use set),记为: U(F, XY),例:U(F, ABGH) =ABE,EG, BEI, GIH,17,3.2.2 公理的完备性 定义(FDs的闭包 F +) 设F是关系r(R)上的FDs,F所蕴含的所有FD的集合称为F的闭包,记作F +。 F + = XY | 所有F |= XY ,18,例:设F=ABC,CB。 F+ 为: F+ = AA, ABA, ACA
8、, ABCA, BB, ABB, BCB,ABCB,CC,ACC,BCC,ABCC,ABAB,ABCAB,ACAC,ABCAC,BCBC, ABCBC, ABCABC, ABC, ABAC, ABBC, ABABC,CB, CBC,ACB ,ACAB,19,定义(属性集的闭包X + ) 设关系模式R(U, F),X U, 所有用公理推出的XAi中Ai的属性集合称X对于F的闭包,记作:X + X += Ai | 用公理推出的XAi 且Ai U,20,定理2 Armstrong公理是完备的。,证明:如果能证明XY不能由公理推出将不会被F所蕴涵,则公理得证。为此,构造一个关系r(R)。 我们将证明两
9、点: (1). F中的所有函数依赖在 r (R)上都成立; (2). XY在r(R)上不成立。,21,22,证明: (1) 设WZF,W在r中有两种情况: (a) W X+。根据属性闭包定义,有XW,又因WZ,根据公理A3有 XZ。因此 ZX+,即 tZ= tZ= ai , 所以,WZ在r上成立。 (b) W X+。则在r中有tW tW,因此,WZ在r上总是成立的。 由(a)和(b)得:r(R)满足F。,(2) 若XY不能由公理推出。即XX+而YX+,由r的构造知,XY在r上不成立,即 XY不被F所蕴涵。,23,3.2.3 函数依赖集闭包及成员测试算法 算法1 计算属性集X的闭包X+的算法 输
10、入:属性集X和函数依赖集F 输出:X的闭包X+,While RESULTVAR do Begin VAR:=RESULT; for every FD WZ in F do if WRESULT then RESULT:=RESULTZ end; return(RESULT) end.,CLOSURE(X, F) Begin VAR:=; RESULT:=X;,24,例: F=AD, ABE, BIE,CDI,EC 求: AE+ 解: AE0 = AE AE1 = AED AE2 = AEDC AE+ = ACDEI,F=A2A1, A3A2, A4A3,AmAm-1 算法改进:每个FD仅考察一
11、次;每个属性仅考察一次,25,计算属性闭包的改进算法: 1. 构造一个LIST表,存放含相同左部属性的FD。 如listA,将存放左部含A的FD; 2. 构造一个计数器COUNT,计数FD的左部属性数。 如: COUNTWZ=|W|; 3. 变量UPDATE记录未考察的属性,使每个属性仅 考察一次, RESULT放中间和最后结果。,26,算法3.2.2 计算属性闭包的改进算法 LINCLOSURE(X, F) . 初始化 for each FD WZ in F do begin COUNTWZ:=W; for each attribute A in W do add WZ to listA e
12、nd; RESULT:=X; UPDATE:=X.,27,. 计算 While UPDATE do begin Choose an A in UPDATE; UPDATE:=UPDATE-A; for each FD WZ in LISTA do begin COUNTWZ:=COUNTWZ-1; if COUNTWZ=0 then begin ADD:=Z-RESULT; RESULT:=RESULTADD UPDATE:=UPDATEADD end end end. . return(RESULT).,28,例: 设F=AD,ABE,BIE,CDI,EC 计算:LINCLOSURE(AE,
13、F)。 解:(1) 初始化: RESULT=AE UPDATE=AE LISTA=AD,ABE COUNTAD=1 LISTB=BIE,ABE COUNTABE=2 LISTC=CDI COUNTBIE=2 LISTD=CDI COUNTCDI=2 LISTE=EC COUNTEC=1 LISTI=BIE (2) COUNTAD=0 COUNTABE=1 RESULT=ADE UPDATE=ED 其余不变。 (3) COUNTEC=0 RESULT=ACDE UPDATE=CD 其余不变。 最后返回结果为ACDEI。,29,定理1: LINCLOSURE算法对输入长度n而言,具有时间复杂度O(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 数据 依赖
链接地址:https://www.31doc.com/p-2597181.html