逻辑蕴含、函数依赖集的闭包、Armstrong公理、属性集闭包

一、引言

Armstrong公理-从给定的函数依赖集得到关系模式的完整依赖集

二、逻辑蕴含

1、定义

设F是关系模式R上的函数依赖集，X、Y是R的属性子集，对于R的每个满足F的关系实例r，若函数

依赖都成立，则称F逻辑蕴含。

记为：

F逻辑蕴含的所有函数依赖的集合，称为函数依赖集F的闭包，并记为。

记为：{}

三、Armstrong公理

1、定义

1974年Armstrong提出一套推理规则，被称为Armstrong公理

2、作用

利用推理规则从给定的函数依赖中推导出其蕴含的函数依赖

3、内容

包含三条基本规则和三条扩充规则

4、实例

关系模式R（U，F）:

（1）U为R的属性集

（2）F是U上的函数依赖集

（3）X、Y、Z、W是U的子集

（4）子集X、Y的并集记为XY

四、Armstrong公理的内容

1、三条基本推理规则

（1）自反律

若，则

（2）增广律

若为F所蕴含，则

（3）传递律

若、为F所蕴含，则

2、三条扩充推理规则

（1）合并规则

若、，则（增广律，传递律）

（2）伪传递规则

若、，则（增广律、传递律）

（3）分解规则

若、，则（自反律、传递律）

3、合并规则和分解规则可得一个重要的事实

引理1：

成立的充分必要条件是成立（i=1,2，...，k）

五、属性集闭包

1、引言

对于一个函数依赖集，其闭包中所包含的函数依赖有很多，从函数依赖集F求其闭包是很困难的，

对于任意的函数依赖，通过判断是否在闭包中来判断该函数依赖是否为函数依赖集F所逻辑蕴含是

很困难的，于是引入了属性集闭包的概念

2、属性集闭包的定义

在R(U,F)中，F是属性集U上的一组函数依赖，，则属性集X关于函数依赖集F的闭包

定义为：

是中所有函数依赖于属性集X的所有属性的集合

3、引理2：

由引理2，就可以将是否属于F的闭包的问题转化为判断Y是否为X关于F的闭包的子集的问题，而X关于F的闭包可由算法帮助实现

六、使用算法求解属性集闭包

1、明确概念

（1）函数依赖集F的闭包是F所蕴含的函数依赖的集合

（2）属性集X关于函数依赖集F的闭包是F的闭包中的函数依赖的决定因素是属性集X的属性的集合，以下简称为属性集闭包

2、求（X的属性集闭包）的一个算法

输入：属性集X和和函数依赖集F

输出：属性集X关于函数依赖集F的闭包

算法实现流程：

（1）开始

（2）给赋初值X

（3）判断的值与上一次相比是否改变，如果改变，执行（4），没改变，执行（5）

（4）对F中的每一个函数依赖，如果，则将Z并入到中，执行（3）

（5）输出，结束

3、举例：使用算法计算属性集X的闭包

七、举例：通过属性集闭包来判断函数依赖是否在函数依赖集F的闭包中

八、小结

1、Armstrong公理的有效性

从F中已有的函数依赖利用Armstrong公理导出的每一个函数依赖

2、Armstrong公理的完备性

函数依赖集F所蕴含的函数依赖，即中的每一个函数依赖都可以利用Armstrong公理推导出来