第6章数据依赖公理系统

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

1、第六章关系数据理论6.1数据依赖6.2规范化6.3数据依赖的公理系统6.3数据依赖的公理系统逻辑蕴含定义6.11对于满足一组函数依赖F的关系模式R，其任何一个关系r，若函数依赖X→Y都成立,则称F逻辑蕴含X→YArmstrong公理系统一套推理规则，是模式分解算法的理论基础用途求给定关系模式的码从一组函数依赖求得蕴含的函数依赖1.Armstrong公理系统关系模式R,X,Y,ZU来说有以下的推理规则：Al.自反律（Reflexivity）：若YX，则X→Y。A2.增广律（Augmentation）：若X→

2、Y，则XZ→YZ。A3.传递律（Transitivity）：若X→Y及Y→Z，则X→Z。注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F2.导出规则1.根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：合并规则：由X→Y，X→Z，有X→YZ。（A2，A3）伪传递规则：由X→Y，WY→Z，有XW→Z。（A2，A3）分解规则：由X→YZ，有X→Y,X→Z。（A1，A3）导出规则2.根据合并规则和分解规则，可得引理6.1引理6.lX→A1A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…

3、，k）。3.定理6.1Armstrong公理是正确的,有效的,完备的3.函数依赖闭包定义6.l2在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作F的闭包，记为F+。定义6.13设F为属性集U上的一组函数依赖，XU，XF+={A

4、X→A能由F根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F的闭包(1)关于闭包的引理引理6.2设F为属性集U上的一组函数依赖，X，YU，X→Y能由F根据Armstrong公理导出的充分必要条件是YXF+用途将判定X→Y是否能由F根据Armstrong公理导出的问题

5、，就转化为求出XF+，判定Y是否为XF+的子集的问题(2)求闭包的算法算法6.l求属性集X（XU）关于U上的函数依赖集F的闭包XF+输入：X，F输出：XF+步骤：（1）令X（0）=X，i=0（2）求B，这里B={A

6、(V)(W)(V→WF∧VX（i）∧AW)}；（3）X（i+1）=B∪X（i）算法6.l（4）判断X（i+1）=X（i）吗?（5）若相等或X（i）=U,则X（i）就是XF+,算法终止。（6）若否，则i=i+l，返回第（2）步。对于算法6.l，令ai=

7、X（i）

8、，{ai}形成一个步长大于1的严格递增的

9、序列，序列的上界是

10、U

11、，因此该算法最多

12、U

13、-

14、X

15、次循环就会终止。(3)计算停止条件,以下四种方法是等价的1.X（i+1）=X(i)2.当发现X(i)包含了全部属性时3.在F中的函数依赖的右边属性中再也找不到X(i)中未出现过的属性4.在F中未用过的函数依赖的左边属性已经没有X(i)的子集U={A,B,C,D};F={AB,BCD};A+=AB.C+=C.(AC)+=ABCD.(4)ExampleACBExampleACDBU={A,B,C,D};AB,BCD.(AC)+=ABCD.函数依赖闭包[例1]已知关系模式R

16、，F>，其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，EC→B，AC→B}。求（AB）F+。解设X（0）=AB；(1)计算X（1）:逐一的扫描F集合中各个函数依赖，找左部为A，B或AB的函数依赖。得到两个：AB→C，B→D。于是X（1）=x(0)∪CD=AB∪CD=ABCD。函数依赖闭包(2)因为X（0）≠X（1），所以再找出左部为ABCD子集的那些函数依赖，又得到AB→C，B→D，C→E，AC→B，于是X（2）=X（1）∪BCDE=ABCDE。(3)因为X（2）=U，算法终止所以（AB）F+=ABCDE。

17、例2已知关系模式R，其中U={A，B，C，D，E,I}；F={AB→E，A→D，CD→I，E→C，BI→E}。求（AE）F+。解设X（0）=AE；(1)计算X（1）:逐一的扫描F集合中各个函数依赖,找左部为A，E或AE的函数依赖。得到两个：A→D，E→C。于是X（1）=x(0)∪CD=AE∪CD=ACDE。(2)因为X（0）≠X（1），所以再找出左部为ACDE子集的那些函数依赖，又得到CD→I于是X（2）=X（1）∪I=ACDEI。(3)因为X（2）≠X（1），但F中未用过的函数依赖在左边属性已经没有X(2)的子集

18、,所以算法终止所以（AE）F+=ACDEI。例3已知关系模式R，其中U={A，B，C，D，E,G}；F={AB→C，C→A，BC→D，ACD→B，BE→C,CG→BD，D→EG，E→AG}。求（BD）F+。解设X（0）=BD；(1)计算X（1）:逐一的扫描F集合中各个函数依赖，找