数据库 关系数据理论 习题

Question

  数据库的《关系数据理论》这一章，有以下几个算法搞不太懂。过几天要考试，每个算法一个题目。题目类型是实际应用，比如第一个算法的题目就是给一个依赖集求闭包，第二个就是给F求Fm。  我们教材里面没有例题，不知道各位有没有例题拿来参考下？谢谢~
------------------------------------------------------------
1.求一个函数依赖集的闭包
2.求数据依赖F的最小依赖集Fm
3. 判别一个分解的无损连接性
4.（合成法）转换为3NF的保持函数依赖的分解。
5.转换为3NF既有无损连接性又保持函数依赖的分解
6.（分解法）转换为BCNF的无损连接分解 

Answer 1

判别一个分解的无损连接性
算法：ρ={R1<U1,F1>,R2<U2,F2>,...,Rk<Uk,Fk>}是关系模式R<U,F>的一个分解，U={A1,A2,...,An}，F={FD1,FD2,...,FDp}，并设F是一个最小依赖集，记FDi为Xi→Alj，其步骤如下：① 建立一张n列k行的表，每一列对应一个属性，每一行对应分解中的一个关系模式。若属性Aj Ui，则在j列i行上真上aj，否则填上bij；② 对于每一个FDi做如下操作：找到Xi所对应的列中具有相同符号的那些行。考察这些行中li列的元素，若其中有aj，则全部改为aj，否则全部改为bmli，m是这些行的行号最小值。如果在某次更改后，有一行成为：a1,a2,...,an，则算法终止。且分解ρ具有无损连接性，否则不具有无损连接性。对F中p个FD逐一进行一次这样的处理，称为对F的一次扫描。③ 比较扫描前后，表有无变化，如有变化，则返回第步，否则算法终止。如果发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有限，因此，循环必然终止。
举例1：已知R<U,F>，U={A,B,C}，F={A→B}，如下的两个分解：① ρ1={AB,BC}② ρ2={AB,AC}判断这两个分解是否具有无损连接性。用无损连接的定理来解。方法一：因为AB∩BC=B，AB-BC=A，BC-AB=C所以B→A F+，B→C F+故ρ1是有损连接。方法二：因为AB∩AC=A，AB-AC=B，AC-AB=C所以A→B F+，A→C F+故ρ2是无损连接。

Answer 2

--1.求一个函数依赖集的闭包 
例子: R(a,b,c,d,e,f) 函数依赖F={ab->c bc->ad d->e cf->b} 求{a,b}的闭包
ab->c x={a b c }(x为一个临时闭包)
bc->ad x={a b c d }
d->e x={a b c d e }
--到此为止 因为没有东西能推出F所以 {a,b}的闭包为{a b c d e }

Answer 3

--2.求数据依赖F的最小依赖集Fm
 例子:R(a,b,c,d,e,f) 函数依赖F={ab->c bc->ad d->e cf->b} 求最小依赖
 因为f没有条件推出 所以F肯定在内 所以FC肯定在内
 这样就有了 fcb 这样bc->ad 推出 ad  d->e 所以 就可以推出 a b c d e f 
 所以FM=cf 
 

Answer 4

例子 R(学号,系,系主任) 产生的函数依赖F={学号->系,系->系主任}
--3. 判别一个分解的无损连接性 
R1=(学号,系) r2=(系主任,学号) 
--4.（合成法）转换为3NF的保持函数依赖的分解。
 这个例子貌似不好举 
--5.转换为3NF既有无损连接性又保持函数依赖的分解 
R1=(学号,系) r2=(系主任,系) 
--6.（分解法）转换为BCNF的无损连接分解 
R1=(学号,系主任) r2=(系主任,系)这个例子也许举得不太好  
最好请楼主去百度