函数依赖公理体系新

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

1、第2讲函数依赖的公理体系授课人：李朔Email:chn.nj.ls@gmail.com2021/7/151南晓数信学院回忆以下几个重要概念XYF逻辑蕴涵XYF的闭包F＋,一般地有FF＋。候选键2021/7/152南晓数信学院主要内容阿姆斯特朗公理及推论X关于F的闭包及其计算最小函数依赖集候选键的求解方法2021/7/153南晓数信学院一、阿姆斯特朗公理及推论是一系列推理规则最早出现在1974年W.W.Armstrong的论文里他人于1977年提出改进形式F=X→YF+侯选键X→Y在R中是否成立能从F导出的所有X→Y推导工具？问题引入：2021/7/

2、154南晓数信学院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Z2021/7/155南晓数信学院Armstrong公理是正确的。方法：从函数依赖的定义出发A1自反律：若YX，则XY(增广律,传递律证明类似,P104)证：设u、v为r的任意两个元组。若u[X]=v[X]，则u和v在X的任何子集上必然相等。由条件YX，所以有：u[Y]=v[Y]

3、，由u、v的任意性，并根据函数依赖的定义，可得XY。2、定理5.12021/7/156南晓数信学院3、阿姆斯特朗公理的推论合并规则：若XY且XZ，则XYZ(增广律)分解规则：若XY，且ZY，则XZ(自反律)伪传递规则：若XY且WYZ，则WXZ增广律传递律证：XYWX→ZWX→WYWY→Z2021/7/157南晓数信学院例5.2简化版P105对关系模式R(A,B,C),依赖集F={C->A,AB->C},候选键为AB和CB,证明BC->ABC,AB->ABC证明:已知有C->A,由增广律可得BC->AB,又已知AB->C,由增广律可得A

4、B->ABC综上由传递律可得BC->ABC2021/7/158南晓数信学院作用：将一个FD分解成若干个右边是单属性的FD。用于确定关系的主键。4、定理5.2如果Ai(i=1,…,n)是关系模式R的属性,则XA1A2…An成立的充分必要条件是XAi(i=1,…,n)均成立。2021/7/159南晓数信学院二、X关于F的闭包及其计算例：已知关系模式R(A,B,C)，其函数依赖集为F={A→B，B→C}，求函数依赖集F的闭包F+。(P103)F+=A→，AB→，AC→，ABC→，B→，C→A→A，AB→A，AC→A，ABC→A，B→B，C→CA→

5、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，AB→ABC，AC→ABC，ABC→ABC，BC→BC，2021/7/1510南晓数信学院1、X关于F的闭包设有关系模式R(U,F)和属性集U={A1,A2,…,An}的子集X。则称所有用阿姆斯特朗公理从F推导出的函数依赖X→Ai的属性Ai组成的集合称为X关于F的闭包，记为XF+，

6、通常简记为X+。即XF+={Ai

7、用公理从F推出的X→Ai}集合元素对比F+和X+2021/7/1511南晓数信学院设有关系模式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＋的子集的问题。2、定理5.32021/7/1512南晓数信学院算法5.1求属性集X关于函数依赖集F的闭包X＋输入：关系模式R的全部属性集U,U上的函数依赖集F，U的子集X。输出：X关

8、于F的闭包X＋。计算方法：3、X关于F的闭包X＋的计算2021/7/1513南晓数信学院（1）X(0)=X。（2）从F中找出满足条件VX(i)的所有函数依赖V→W，并把所有的V→W中的属性W组成的集合记为Z；也即从F中找出那些其决定因素是X(i)的子集的函数依赖，并把由所有这样的依赖的被决定因素组成的集合记为Z。（3）若ZX(i)，则转（5）。(当X(i)只决定自己时)（4）否则，X(i+1)=X(i)Z，并转（2）。(传递律)（5）停止计算，输出X(i)，即为X+。3、X关于F的闭包X＋的计算（续）2021/7/1514南晓数信学院例5.4已知R(U

9、),U={A,B,C,D,E,G}，R上的FD集F={AB→C,C