2022年范式几个重要算法 .pdf

《2022年范式几个重要算法 .pdf》由会员分享，可在线阅读，更多相关《2022年范式几个重要算法 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、几个重要算法：算法 1. 求属性集 X关于函数依赖 F的属性闭包 X+输入： R的属性集 U ，在 U上的函数依赖 F,U 的子集 X 输出： F的属性闭包 X+方法：计算 X（i ）(I=0,1,2,) (1)X(0)=X (2)X （i+1 ）=X（i ）A 其中 A是这样的属性：在F 中寻找尚未用过的左边是X（i ）子集的函数依赖：Yj-Zj(j=1,2k) 其中， Yj 属于 X（i ） ；即在 Zj 中寻找 X（i ）中未出现过的属性集合A （3）判断是否有 X（i+1 ）=X（i ） ，若是转（ 4） ；否则转（ 2）（4）输出 X（i ）, 即为 X+对于（ 3）的计算停止条件，

2、以下几种方法是等价的：（1） X（i+1 ）=X（i ）（2） 发现 X（i ）包含了全部属性时（3） 在 F 中未用过的函数依赖左边属性已经没有（i ）子集算法 2计算最小依赖集输入一个函数依赖集F。输出： F的一个等价最小依赖集G 。方法：（1） 应用分解规则，使F中每一个依赖的右部属性单一化（2） 去掉各依赖左部多余的属性。具体做法是：一个一个地检查F 中左边是非单属性的依赖例如 XYA，现在要判断 Y 是否为多余的，则以 XA代替 XYA是否等价？只要在 F 中求 X+若 X+包含 A，则 Y是多余的属性否则Y不是多余属。依次判断其他属性即可消除各依赖左边的多余属性。（3）去掉多余的依

3、赖、具体做法是。从第一个依赖开始从 F中去掉它（假设该依赖为 XY。然后在剩下的依赖中求X+看 X+是否包含 Y，若是，则去掉XY；若不包含 Y则不能去掉 XY。这样依次做下去。算法 3：检验无损连接性。输入；关系模式 R （AI，A2 。 。 。An） ，它的函数依赖集F以及分解 p 输出 确定 P是否具有无损连接性。方法：（1） 构造一个 k 行 n 列的表， 第 1 行对应于关系模式Ri, 第 j 列对应于属性 Aj。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共

4、4 页 - - - - - - - - - 如果Aj 在 Ri 中，则在第 i 行第 j 列上放符号 aj, 否则放符号 bij 。（2）逐个检查 F 中的每一个函数依赖并修改表中的元素、其方法如下：取得F中一个函数依赖 XY在 X的分量中寻找相同的行然后将这些行中Y的分量改为相同的符号，如果其中有 aj ，则将 bij改为 aj ；若其中无 aj ，则改为 bij 。（3）这样反复进行如果发现某一行变成了a1,a2, ak，则分解 p 具有无损连接性如果 F 中所有函数依赖都不能再修改表中的内容，且没有发现这样的行， 则分解P不具有无损连接性。算法 4: 把一个关系模式分解为3NF ，使它具

5、有依赖保持性。输入；关系模式 R和 R的最小依赖集 F。输出： R的一个分解 p. Ri为 3NF （1k） ，p具有依赖保持性。方法: (1)如果 F中有一依赖 XA且 XA=R ，则输出 P=R ，转（ 4） （2）如果 R中某些属性与 F中所有依赖的左部和右部都无关则允它们构成关系模式从 R中将它们分出去：（3）对于 F中的每一个 Xi Ai，都构成一个关系子模式Ri=XiAi ：（3） 停止分解，输出 p 。算法 5：把一个关系模式分解为3NF ，使它既具有无损连接性又具有依赖保持性。输人：关系模式 R和 R的最小依赖集 F。输出： R的一个分解 P，Ri 为 3NF （I=l k ）

6、 ，P具有无损连接性和依赖保持性。方法: （1）根据上个算法求出依赖保持性分解：（2）判定 P是否具有无损连接性若是，转（4） ；（3）令 p=pU X 。其中 X是 R的候选关键字；（4） 输出 p。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 算法 6：把关系模式无损分解成BCNF 。输入：关系模式 R和函数依赖集 F。输出： R的一个无损分解P=R1，R2，Rk, 方法：1）令 P=R；2）如果 P中所有模式都是 BCN

7、F ，则转（ 4） ；3）如果 P 中有一个关系模式S 不是 BCNF ，则 S 中必能找到一个函数依赖X-A且 X 不是 S的候选键，且A不属于 X，设 S1=XA,S2=S-A, 用分解 S1，S2代替 S，转（2） ；4）分解结束，输出P。算法 7. 找关键字几个定义：1) 原始点：只有引出线而无引入线的点，L 类2) 终结点：只有引入线而无引出线的点，R类3) 途中点：又有引出线又有引入线的点，LR类4) 孤立点：又无引出线又无引入线的点，N类5) 关键点：原始点和孤立点6) 关键属性：关键点对应的属性7) 独立回路：不能被其它节点到达的回路单属性依赖集图论求解法：输入：关系模式 R

8、。依赖集 F 输出： R的所有关键字方法：（1） 求 F 的最小依赖集 F（2） 构造函数依赖图（3） 从图中找出关键属性集X（可为空）（4） 查看 G中有无独立回路，若无则输出X，转（ 6）（5） 从各回路中各取一节点对应的属性与X组成一候选关键字， 并重复这一过程取尽所有可能的组合，即为R的全部候选关键字。（6） 结束多属性依赖集图论求解法：输入：关系模式 R 。依赖集 F 输出： R的所有关键字方法：（1） 将 R的所有属性分为 L，R，LR和 N四类。并令 X代表 L，N两类，Y代表LR类。（2） 求 X+，若 X+包含了 R的全部属性， X为 R的唯一候选关键字，转（5）（3） 在

9、Y 中取一属性 A，求 XA+。若包含了 R的全部属性，转（ 4） ，否则调换名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 一属性反复进行这一过程，直至试完所有Y的属性。（4） 如果已找到属性，转（ 5） ，否则在 Y中依次取两个，三个，求它们的属性闭包，直至闭包包含了R的全部属性。（5） 停止，输出结果。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -