数据库系统概论—判断分解是否保持函数依赖
来源: 程俊伟/
华南师范大学
18643
5
1
2020-04-12

算法:

    对于关系模式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,则该分解保持函数依赖。


登录用户可以查看和发表评论, 请前往  登录 或  注册
SCHOLAT.com 学者网
免责声明 | 关于我们 | 联系我们
联系我们: