范式几个重要算法.doc

《范式几个重要算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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,2…k)其中，Yj属于X（i）；即在Zj中寻找X（i）中未出现过的属性集合A（3）判断是否有X（i+1）=X（i），若是转（4）；否则转（2）（4）输出X（i）,即为X+对于（3）的计算停止条件，以下几种方法是等价的：（1）

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

3、赖、具体做法是。从第一个依赖开始从F中去掉它（假设该依赖为X—>Y。然后在剩下的依赖中求X+．看X+是否包含Y，若是，则去掉X—>Y；若不包含Y．则不能去掉X—>Y。这样依次做下去。算法3：检验无损连接性。输入；关系模式R（AI，A2．。。。An），它的函数依赖集F以及分解p输出确定P是否具有无损连接性。方法：（1）构造一个k行n列的表，第1行对应于关系模式Ri,第j列对应于属性Aj。如果Aj在Ri中，则在第i行第j列上放符号aj,否则放符号bij。（2）逐个检查F中的每一个函数依赖．并修改表中的元素、其方法如下：取得F中一个函数依

4、赖X－>Y．在X的分量中寻找相同的行．然后将这些行中Y的分量改为相同的符号，如果其中有aj，则将bij改为aj；若其中无aj，则改为bij。（3）这样反复进行．如果发现某一行变成了a1,a2,…ak，则分解p具有无损连接性．如果F中所有函数依赖都不能再修改表中的内容，且没有发现这样的行，则分解P不具有无损连接性。算法4:把一个关系模式分解为3NF，使它具有依赖保持性。输入；关系模式R和R的最小依赖集F’。输出：R的一个分解p.Ri为3NF（1…k），p具有依赖保持性。方法:(1)如果F’中有一依赖X－>A．且XA=R，则输出P=｛R

5、｝，转（4）（（2）如果R中某些属性与F’中所有依赖的左部和右部都无关．则允它们构成关系模式．从R中将它们分出去：（3）对于F’中的每一个Xi－>Ai，都构成一个关系子模式Ri=XiAi：（1）停止分解，输出p。算法5：把一个关系模式分解为3NF，使它既具有无损连接性又具有依赖保持性。输人：关系模式R和R的最小依赖集F’。输出：R的一个分解P，Ri为3NF（I=l…k），P具有无损连接性和依赖保持性。方法:（1）根据上个算法求出依赖保持性分解：（2）判定P是否具有无损连接性．若是，转（4）；（3）令p=pU｛X｝。其中X是R的候选关

6、键字；（2）输出p。算法6：把关系模式无损分解成BCNF。输入：关系模式R和函数依赖集F。输出：R的一个无损分解P={R1，R2，…Rk},方法：1）令P={R}；2）如果P中所有模式都是BCNF，则转（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)途中点：又有引出

7、线又有引入线的点，LR类4)孤立点：又无引出线又无引入线的点，N类5)关键点：原始点和孤立点6)关键属性：关键点对应的属性7)独立回路：不能被其它节点到达的回路单属性依赖集图论求解法：输入：关系模式R。依赖集F输出：R的所有关键字方法：（1）求F的最小依赖集F’（2）构造函数依赖图（3）从图中找出关键属性集X（可为空）（4）查看G中有无独立回路，若无则输出X，转（6）（5）从各回路中各取一节点对应的属性与X组成一候选关键字，并重复这一过程取尽所有可能的组合，即为R的全部候选关键字。（6）结束多属性依赖集图论求解法：输入：关系模式R。

8、依赖集F输出：R的所有关键字方法：（1）将R的所有属性分为L，R，LR和N四类。并令X代表L，N两类，Y代表LR类。（2）求X+，若X+包含了R的全部属性，X为R的唯一候选关键字，转（5）（3）在Y中取一属性A，求XA+。若包含了R的