算法:
对于关系模式R(U,F), 设P = {R1(U1,F1) , R2(U2,F2) , ... , Rn(Un,Fn)}是R的一个分解,若F+ = (UFi)+ ,则称分解P是保持函数依赖。
注:U:并集
例:R ={A,B,C,D,E},F = {B → A , D → A , A → E , AC → B},判断分解P ={R1(ABCE) , R2(CD)}是否保持函数依赖
解:
首先,我们需要将R1和R2的函数依赖F1,F2找到。显然有
F1 = {B → A ,A → E , AC → B} ,F2 = { }
注:这样就找全了吗?其实不然,在这一步中最容易漏掉部分函数依赖,比如传递依赖等关系会因为F的分组而丢失。因此,在这一步,我的习惯是计算一下左边属性的闭包
B+ ={B,A,E} 显然 B 和 E存在传递依赖 即 B → E,同理
D+={D,A,E} ,发现D+没有C,即D推不出C
A+={A,E}
(AC)+ = {A ,C , B, E},显然 AC → A , AC→ E
综上,F1 更新为 F1 = {B → A ,A → E , AC → B, B → E,AC → A , AC→ E}
F2依旧是空集
令 G = F1 ∪ F2 = {B → A ,A → E , AC → B, B → E,AC → A , AC→ E}
我们检查一下F中的函数依赖,是否在G中全部都出现,如果出现,则算法结束,保持函数依赖
发现,D → A 不在G中,此时,我们需要计算元素D在G下的闭包
显然,D+ ={D} 不包含A,因此该分解不保持函数依赖。
注:如果D+ ={D ,A },包含了A,则该分解保持函数依赖。