函数依赖的公理系统.ppt

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

1、数据库原理与应用第四章关系数据理论《数据库系统概论》4.3函数依赖的公理系统为了以下目的，需要建立函数依赖的推理系统:(1)求关系模式的候选码(2)判断关系模式的范式级别(3)给定一组函数依赖，需要导出另外一些函数依赖，或判断另外的函数依赖是否成立。例如FD={AB，BC}，判断AC是否成立？本节内容:1.逻辑蕴涵；2.Armstrong函数依赖公理系统；3.函数依赖集的闭包；4.属性集闭包；5.函数依赖集的等价和覆盖；6.最小函数依赖集。逻辑蕴涵定义4.11关系模式R，F是其函数依赖集，X、Y是U的属性子集，r是R的任何一个关系，如果从F的函数依赖

2、能够推出XY，则称F逻辑蕴涵XY，记作F├XY。示例:R,U={X,Y},F={XY}则F逻辑蕴涵以下函数依赖:XX，XY，YY,XYX，XYY，XYXY函数依赖集的闭包F+定义4.12在关系模式R中，被F所逻辑蕴涵的函数依赖的全体所构成的集合称作F的闭包，记作F+={XY

3、F├XY}显然，FF+。F+的计算很麻烦，F不大，其F+也可能很大。例如：设R,U={X,Y,Z},F={XY,YZ}F+={XX，XY，XZ,YY,YZ,ZZ,XYX，XYY，XYXY,XZ→X,……}Armstro

4、ng公理系统函数依赖公理系统由Armstrong于1974年首先提出。设关系模式R，U为属性全集，F是U上的一组函数依赖，X、Y、Z是U的属性子集，对R有以下推理规则：A1自反律(reflexivity)：若YX,则XY。A2增广律(augmentation)：若XY，则XZYZ。A3传递律(transitivity)：若XY，YZ，则XZ。注意:由自反律所得到的函数依赖是平凡的,自反律的使用并不依赖于函数依赖集F。传递律与传递依赖？A公理系统的正确性和完备性Armstrong公理的正确性(即有效性)及完备性。正确性：用Armstrong公理

5、从F中导出的函数依赖必为F所蕴涵。完备性：为F所蕴涵的函数依赖都能用Armstrong公理从F中导出。公理的正确性保证由F出发根据公理推导出的每一个函数依赖一定在F+中。公理的完备性保证用公理能推出所有的函数依赖,即F+中的所有函数依赖都能由F出发用公理推导出来。这个问题很重要,因为,如果F+中居然有一个函数依赖不能用公理推导出来,那么,这些公理就不够用,就不完备,还必须补充新的公理。A公理系统的正确性证明定理4.1Armstrong推理规则是正确的。按函数依赖定义，假设r是R上的任一关系实例，t、s是r的任意两个元组。证明自反律:若YXU，则XY若

6、t[X]=s[X],由于YX,有t[Y]=s[Y],所以有XY。t[X]=s[X]YXt[Y]=s[Y]XY自反律A公理系统：增广律证明t[XZ]=s[XZ]t[X]=s[X]XYt[Y]=s[Y]t[XZ]=s[XZ]t[Z]=s[Z]t[YZ]=s[YZ]XZYZ增广律(2)证明增广律:若XY，则XZYZ。设t[XZ]=s[XZ],则有t[X]=s[X]和t[Z]=s[Z],由于XY,对t[X]=s[X]，就有t[Y]=s[Y],从而有t[YZ]=s[YZ],所以XZYZ成立。A公理系统：传递律证明XYt[X]=s[X]t[Y]=s[Y]Y

7、Zt[Z]=s[Z]XZ传递律(3)证明传递律:若XY及YZ，则XZ。设t[X]=s[X],由于XY,则有t[Y]=s[Y],再由YZ，对t[Y]=s[Y]，有t[Z]=s[Z],所以XZ成立。.A公理系统：推论由Armstrong公理导出的推理规则参见P184.合并律(unionrule)若XY，XZ，则XYZ。分解律(decompositionrule)若XYZ，则XY，XZ。伪传递律(pseudotransitivityrule)若XY，WYZ，则WXZ。引理4.1XA1A2Ak成立XAi成立。(i=1,2,,k)证

8、明：用数学归纳法证明。“”由合并律证明；“”由分解律证明。A公理系统:例示例：R,U={A,B,C,G,H,I},F={AB,AC,CGH,CGI,BH},F逻辑蕴涵以下函数依赖吗？AH？CGHI？AGI？是,∵AB，BH是,∵CGH，CGI是,∵AC,AGCG，CGIA公理系统的完备性Armstrong公理系统是有效的、完备的。有效性即正确性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中，已经证明完备性：F+中的每一个函数依赖必定可以由F出发根据Armstrong公理推导出来。要证明完备性，