函数依赖公理体系.ppt

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

1、第2讲函数依赖的公理体系第5章关系数据库模式设计主要内容阿姆斯特朗公理及推论X关于F的闭包及其计算最小函数依赖集候选键的求解方法一、阿姆斯特朗公理及推论是一系列推理规则最早出现在1974年W.W.Armstrong的论文里他人与1977年提出改进形式F=X→YF+侯选键X→Y在R中是否成立能从F导出的所有X→Y推导工具？问题引入：1、阿姆斯特朗公理设有关系模式R(U,F)，U={A1,A2,…,An}是R的属性集，F是R的属性集U上的FD集，X、Y、Z、W是U的子集。阿姆斯特朗公理为：A1自反律：若YX，则XYA2增广律：若XY，则XZYZA3传递律：若XY,YZ，则XZAr

2、mstrong公理是正确的。方法：从函数依赖的定义出发A1自反律：若YX，则XY证：设u、v为r的任意两个元组。若u[X]=v[X]，则u和v在X的任何子集上必然相等。由条件YX，所以有：u[Y]=v[Y]，由u、v的任意性，并根据函数依赖的定义，可得XY。2、定理5.13、阿姆斯特朗公理的推论合并规则：若XY且XZ，则XYZ分解规则：若XY，且ZY，则XZ伪传递规则：若XY且WYZ，则WXZ增广律传递律证：XYWX→ZWX→WYWY→Z作用：将一个FD分解成若干个右边是单属性的FD。用于确定关系的主键。4、定理5.2如果Ai(i=1,…,n)是关系模式R的属性,

3、则XA1A2…An成立的充分必要条件是XAi(i=1,…,n)均成立。二、X关于F的闭包及其计算例：已知关系模式R(A,B,C)，其函数依赖集为F={A→B，B→C}，求函数依赖集F的闭包F+。F+=A→，AB→，AC→，ABC→，B→，C→A→A，AB→A，AC→A，ABC→A，B→B，C→CA→B，AB→B，AC→B，ABC→B，B→C，A→C，AB→C，AC→C，ABC→C，B→BC，A→AB，AB→AB，AC→AB，ABC→AB，BC→，A→AC，AB→AC，AC→AC，ABC→AC，BC→B，A→BC，AB→BC，AC→BC，ABC→BC，BC→C，A→ABC，A

4、B→ABC，AC→ABC，ABC→ABC，BC→BC，1、X关于F的闭包设有关系模式R(U,F)和属性集U={A1,A2,…,An}的子集X。则称所有用阿姆斯特朗公理从F推导出的函数依赖X→Ai的属性Ai组成的集合称为X关于F的闭包，记为XF+，通常简记为X+。即XF+={Ai

5、用公理从F推出的X→Ai}集合元素对比F+和X+设有关系模式R(U，F)，U={A1,A2,…,An}是R的属性集，F是R的属性集U上的函数依赖集，X、Y是U的子集，则XY能用Armstrong公理从F导出YX＋。该定理把判定XY是否能由F根据Armstrong公理导出的问题求出X＋，判定Y是否为X＋的子集

6、的问题。2、定理5.3算法5.1求属性集X关于函数依赖集F的闭包X＋输入：关系模式R的全部属性集U,U上的函数依赖集F，U的子集X。输出：X关于F的闭包X＋。计算方法：3、X关于F的闭包X＋的计算（1）X(0)=X。（2）从F中找出满足条件VX(i)的所有函数依赖V→W，并把所有的V→W中的属性W组成的集合记为Z；也即从F中找出那些其决定因素是X(i)的子集的函数依赖，并把由所有这样的依赖的被决定因素组成的集合记为Z。（3）若ZX(i)，则转（5）。（4）否则，X(i+1)=X(i)Z，并转（2）。（5）停止计算，输出X(i)，即为X+。3、X关于F的闭包X＋的计算（续）例5.4已知R(

7、U),U={A,B,C,D,E,G}，R上的FD集F={AB→C,C→A,BC→D,ACD→B，D→EG,BE→C,CG→BD,CE→AG}，X=BD，求X＋，BD→A是否成立？(1)X（0）=BD。(2)X（1）=BDEG(3)X（2）=BCDEG(4)X（3）=ABCDEGX＋=ABCDEGA∈BD＋，故BD→A成立4、举例Z=EGBD=X(0)一个函数依赖集F的闭包F＋通常包含很多函数依赖，有些函数依赖是无意义的，如平凡的函数依赖，还有一些是可以推导出的，即无关的函数依赖。如果将每一个函数依赖看作是对关系的一个约束，要检查F＋中的每一个函数依赖对应的约束，显然是一件很繁重的任务。如果能

8、找出一个与F等价的、包含较少数目函数依赖的函数依赖集G，则可以简化此工作。最小函数依赖集的概念由此而提出。三、最小函数依赖集定义5.5设F和G是两个函数依赖集，如果F＋＝G＋，则称F和G等价。如果F和G等价，则称F覆盖G，同时也称G覆盖F。1、函数依赖集的等价与覆盖定理5.7F＋＝G＋的充要条件是FG＋和GF＋。F＋=G＋FG＋X→Y所有FG＋定理GF＋X→Y能否由G根据公理导出？YXG+？作用：