范式几个重要算法.doc

几个重要算法：算法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）的计算停止条件，以下几种方法是等价的：（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）去掉多余的依赖、具体做法是。从第一个依赖开始 从F中去掉它（假设该依赖为XY。然后在剩下的依赖中求X+看X+是否包含Y，若是，则去掉XY；若不包含Y则不能去掉XY。这样依次做下去。算法3：检验无损连接性。输入；关系模式R（AI，A2。An），它的函数依赖集F以及分解p输出 确定P是否具有无损连接性。方法：（1） 构造一个k行n列的表，第1行对应于关系模式Ri,第j列对应于属性Aj。如果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，使它具有依赖保持性。 输入；关系模式R和R的最小依赖集F。 输出：R的一个分解p. Ri为3NF（1k），p具有依赖保持性。 方法: (1)如果F中有一依赖XA且XA=R，则输出P=R，转（4）（ （2）如果R中某些属性与F中所有依赖的左部和右部都无关则允它们构成关系模式从R中将它们分出去： （3）对于F中的每一个XiAi，都构成一个关系子模式Ri=XiAi：（3） 停止分解，输出 p。算法5：把一个关系模式分解为3NF，使它既具有无损连接性又具有依赖保持性。 输人：关系模式R和R的最小依赖集F。 输出：R的一个分解P，Ri为3NF（I=l k），P具有无损连接性和依赖保持性。 方法: （1）根据上个算法求出依赖保持性分解： （2）判定P是否具有无损连接性若是，转（4）； （3）令p=pUX。其中X是R的候选关键字；（4） 输出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) 途中点：又有引出线又有引入线的点，LR类4) 孤立点：又无引出线又无引入线的点，N类5) 关键点：原始点和孤立点6) 关键属性：关键点对应的属性7) 独立回路：不能被其它节点到达的回路单属性依赖集图论求解法：输入：关系模式R。依赖集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） 在Y中取一属性A，求XA+。若包含了