范式几个重要算法.doc

几个重要算法：
算法求属性集关于函数依赖的属性闭包
输入：的属性集，在上的函数依赖的子集输出：的属性闭包
方法：计算（）…
））X）u
其中是这样的属性：在中寻找尚未用过的左边是（）子集的函数依赖:
•••
其中，属于（）；
几个重要算法：
算法求属性集关于函数依赖的属性闭包
输入：的属性集，在上的函数依赖的子集输出：的属性闭包
方法：计算（）…
））X）u
其中是这样的属性：在中寻找尚未用过的左边是（）子集的函数依赖:
•••
其中，属于（）；
即在中寻找（）中未出现过的属性集合
（）判断是否有（）X）,若是转（）；否则转（）
（）输出（）即为
对于（）的计算停止条件，以下几种方法是等价的：
（）X）X）
（）发现（）包含了全部属性时
（）在中未用过的函数依赖左边属性已经没有（）子集
算法2．计算最小依赖集．
输入•一个函数依赖集F
输出：的一个等价最小依赖集G
方法：
（）应用分解规则，使中每一个依赖的右部属性单一化
（）去掉各依赖左部多余的属性。具体做法是：一个一个地检查中左边是非单属
性的依赖例如一，现在要判断是否为多余的，则以一代替一是否等价？
只要在中求•若包含，则是多余的属性•否则不是多余属。依次判断其
他属性即可消除各依赖左边的多余属性。
（）去掉多余的依赖、具体做法是。从第一个依赖开始从中去掉它（假设该依赖为一。然后在剩下的依赖中求•看是否包含，若是，则去掉—Y若不包含，则不能去掉一，
这样依次做下去。
算法：检验无损连接性。
输入；关系模式（，・。。。），它的函数依赖集以及分解输出确定是否具有无损连接性。
方法：
（）构造一个行列的表，第行对应于关系模式第列对应于属性
如果
在中，则在第行第列上放符号a，否则放符号。
(2)、其方法如下：取得中一

号，如果其中有aj则将改为a；若其中无a,则改为。
()这样反复进行•如果发现某一行变成了al,a2,・・・ak，则分解具有无损连接性.
如果中所有函数依赖都不能再修改表中的内容，且没有发现这样的行，则分解不具有
无损连接性。
算法把一个关系模式分解为，使它具有依赖保持性。
输入；关系模式和的最小依赖集F。
输出：的一个分解为(1-k)，具有依赖保持性。
方法:
如果1'，则输出{}，转()(
(2)如果中某些属性与'
从中将它们分出去：
()对于'中的每一个一，都构成一个关系子模式：
()停止分解，输出。
算法：把一个关系模式分解为，使它既具有无损连接性又具有依赖保持性。输人：关系模式和的最小依赖集’。
输出：的一个分解，为(…)具有无损连接性和依赖保持性。输输输输方法输:输输输(输1输)根据上个算法求出依赖保持性分解：输
(2)判定是否具有无损连接性•若是，转()；
()令{}。其中是的候选关键字；
()输出。
算法：把关系模式无损分解成输入：关系模式R和函数依赖集。
输出：R的一个无损分解
,RR2•••Rk
方法：
）令
{R
2）如果
中