讲函数依赖公理体系新.pptVIP

第2讲 函数依赖的公理体系 主要内容 阿姆斯特朗公理及推论 X关于F的闭包及其计算 最小函数依赖集 候选键的求解方法 一、阿姆斯特朗公理及推论 是一系列推理规则 最早出现在1974年W.W.Armstrong的论文里 他人与1977年提出改进形式 1、阿姆斯特朗公理 设有关系模式R(U,F)，U={A1,A2,…,An}是R的属性集，F是R的属性集U上的FD集，X、Y、Z、W是U的子集。 阿姆斯特朗公理为： A1 自反律：若Y?X，则X?Y A2 增广律：若X?Y，则XZ?YZ A3 传递律：若X?Y,Y?Z，则X?Z 2、定理5.1 Armstrong公理是正确的。 方法：从函数依赖的定义出发 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。 3、 阿姆斯特朗公理的推论 合并规则：若X?Y且X?Z，则X?YZ 分解规则：若X?Y，且Z?Y，则X?Z 伪传递规则：若X?Y且WY?Z，则WX?Z 4、定理5.2 如果Ai(i=1,…,n)是关系模式R的属性,则X?A1A2…An成立的充分必要条件是X?Ai(i= 1,…,n)均成立。 二、X关于F的闭包及其计算 例：已知关系模式R(A,B,C)，其函数依赖集为F={A→B，B→C}，求函数依赖集F的闭包F+。 1、X关于F的闭包 设有关系模式R(U,F)和属性集U={A1,A2,…,An}的子集X。则称所有用阿姆斯特朗公理从F推导出的函数依赖X→Ai的属性Ai组成的集合称为X关于F的闭包，记为XF+，通常简记为X+。即 XF+={Ai|用公理从F推出的X→Ai} 2、定理5.3 设有关系模式R(U，F)，U={A1,A2,…,An}是R的属性集，F是R的属性集U上的函数依赖集，X、Y是U的子集，则 X?Y能用Armstrong公理从F导出?Y?X＋。 3、X关于F的闭包X＋的计算 算法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+。 4、举例 例5.4 已知R(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）=ABCDEG 三、最小函数依赖集 一个函数依赖集F的闭包F＋通常包含很多函数依赖，有些函数依赖是无意义的，如平凡的函数依赖，还有一些是可以推导出的，即无关的函数依赖。如果将每一个函数依赖看作是对关系的一个约束，要检查F＋中的每一个函数依赖对应的约束，显然是一件很繁重的任务。如果能找出一个与F等价的、包含较少数目函数依赖的函数依赖集G，则可以简化此工作。最小函数依赖集的概念由此而提出。 1、函数依赖集的等价与覆盖 定义5.5 设F和G是两个函数依赖集，如果F＋＝G＋，则称F和G等价。如果F和G等价，则称F覆盖G，同时也称G覆盖F。 定理 定理5.7 F＋＝G＋的充要条件是F?G＋和G?F＋。 推论 每一个函数依赖集F都被其右端只有一个属性的函数依赖组成的依赖集G所覆盖。 2、最小函数依赖集 满足下列条件的函数依赖集F称为最小函数依赖集。 ① F中每一个FD的右端都是单个属性； ② 对F中任何FD:X?A，F-{X?A}不等价于F； ③ 对F中的任何FD:X?A和X的任何真子集Z， (F-{X?A})∪{Z?A}不等价于F。 求解方法 （1）用分解规则将F中的所有函数依赖分解成右端为单个属性的函数依赖； 求解方法（续一） （2）去掉F中冗余的函数依赖 对于F中任一FD：X?Y ① G