精华内容
下载资源
问答
  • 数据库模式分解是否为无损连接和是否保持函数依赖的判断方法
    千次阅读
    2021-04-21 12:08:25

    是否为无损连接

    方法一:无损连接定理

    关系模式R(U,F)的一个分解,ρ={R1<U1,F1>,R2<U2,F2>}具有无损连接的充分必要条件是:

    U1∩U2→U1-U2 €F+ 或U1∩U2→U2 -U1€F+

    方法二:算法

    ρ={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是无损连接。

    举例2: 已知R<U,F>,U={A,B,C,D,E},F={A→C,B→C,C→D,DE→C,CE→A},R的一个分解为R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE),判断这个分解是否具有无损连接性。

    ① 构造一个初始的二维表,若“属性”属于“模式”中的属性,则填aj,否则填bij

    ② 根据A→C,对上表进行处理,由于属性列A上第1、2、5行相同均为a1,所以将属性列C上的b13、b23、b53改为同一个符号b13(取行号最小值)。

    ③ 根据B→C,对上表进行处理,由于属性列B上第2、3行相同均为a2,所以将属性列C上的b13、b33改为同一个符号b13(取行号最小值)。

    ④ 根据C→D,对上表进行处理,由于属性列C上第1、2、3、5行相同均为b13,所以将属性列D上的值均改为同一个符号a4。

    ⑤ 根据DE→C,对上表进行处理,由于属性列DE上第3、4、5行相同均为a4a5,所以将属性列C上的值均改为同一个符号a3。

    ⑥ 根据CE→A,对上表进行处理,由于属性列CE上第3、4、5行相同均为a3a5,所以将属性列A上的值均改为同一个符号a1。

    ⑦ 通过上述的修改,使第三行成为a1a2a3a4a5,则算法终止。且分解具有无损连接性。


    是否保持函数依赖

    方法一:算法
    对于关系模式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,则该分解保持函数依赖.

    更多相关内容
  • 非常好的讲解了模式分解保持函数依赖的意义,来自知网于思江和王小兵老师,资源很好!
  • R的一个分解为R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE),判断这个分解是否具有函数依赖性。 分解出的R1 F1{A—>D} R2 F2{Q} R3 F3{Q},R4(CDE) F4(DE->C,C->D} A->C、B->C、CE->A没有被覆盖。...

    前言

    定义1:设R(U,F)是一个关系模式,F是函数依赖集,若F + ^+ += ( U U U i = 1 k F i ) _{i=1}^{k}F_i) i=1kFi) + ^+ +,则R<U, F>的分解ρ={ R1<U1, F1>,R2<U2, F2>,…,Rk<Uk, Fk> } ,则分解ρ保持函数依赖。
    定义2:分解前函数依赖的闭包和分解后各个函数依赖并集的闭包相等;即分解不能丢失函数依赖
    保持函数依赖性判断完全可以根据定义及Armstrong公理进行判断。对于不能简单的推算出是否保持函数依赖,则需要通过以下算法实现。

    判断算法

    判断一个模式分解是否保持函数依赖,假设R(U,F)分解为R1(U1,F1)、R2(U2,F2)… R n _n n(U n _n n,F n _n n
    其中:U 1 _1 1 ∪ ∪ U 2 _2 2 ∪ ∪ U n _n n=U,F 1 _1 1、F 2 _2 2、F n _n n分别是F在U 1 _1 1、U 2 _2 2…U n _n n上的投影。处理步骤如:
    第一步:设F’=F 1 _1 1UF 2 _2 2…UF n _n n;判断F’是否覆盖了F,若包含了F中所有的函数依赖,则一定是保持函数依赖的,判断结束,否则进入第二步
    第二步:对F’中没显式包含的函数依赖依据armstrong公理做初步判断,F’蕴含了该函数依赖,F’覆盖了该函数依赖。如不能判断得出,使用以下算法去实现,只要有一个函数依赖没有覆盖的到,则不保持函数依赖。是否蕴含了某个函数依赖判断的算法如下:

    假设:需要判断是否蕴含了 α α α-> β β β函数依赖;
    令 Result= α α α
    开始扫描R i _i i,T=(Result ∩ R ∩R R i _i i) F + _F^+ F+∩Ri
    令:Result=Result ∪ ∪ T
    Result包含了 β β β,则: α α α-> β β β成立,算法终止
    Result有变化,但还没包含 β β β,继续下一轮
    Result无变化,且不包含 β β β,则: α α α-> β β β不成立,分解不覆盖 α α α-> β β β,说明不保持函数依赖

    示例

    例1:已知R<U,F>,U={A,B,C,D,E},F={A—>C,B—>C,C—>D,DE—>C,CE—>A},
    R的一个分解为R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE),判断这个分解是否具有函数依赖性。
    解:
    求投影:R 1 _1 1 F 1 _1 1{A—>D} ,R 2 _2 2 F 2 _2 2{ Ø Ø Ø} ,R 3 _3 3 F 3 _3 3{ Ø Ø Ø},R 4 _4 4(CDE), F 4 _4 4(DE->C,C->D}
    F’=F − - (F 1 _1 1UF 2 _2 2UF 3 _3 3UF 4 _4 4)={A->D、DE->C,C->D}
    A->C、B->C、CE->A这些函数依赖需要进一步的判断是否被覆盖到

    根据Armstrong公理简单判断不出,F’是否蕴含了A->C、B->C、CE->A等函数依赖

    转入求闭包操作:
    A->C:
    第一轮
    令: Result={A}
    Result与R1求交,为{A}, 求A的闭包:A F + _F^+ F+={ACD}, 则T={ACD} ∩ ∩ R 1 _1 1={AD}; Result= Result ∪ ∪ T={AD}
    Result与R2求交,为{A}, 求A的闭包:A F + _F^+ F+={ACD}, 则T={ACD} ∩ ∩ R 2 _2 2={A}; Result= Result ∪ ∪ T={AD}
    Result与R3求交,为{ Ø Ø Ø}, Result= Result ∪ ∪ T={AD}
    Result与R4求交,为{D}, 求D的闭包:D F + _F^+ F+={D}, 则T={D} ∩ ∩ R 4 _4 4={D} Result= Result ∪ ∪ T={AD}
    Result与R5求交,为{A}, 求A的闭包:A F + _F^+ F+={ACD}, 则T={ACD} ∩ ∩ R 5 _5 5={A} Result= Result ∪ ∪ T={AD}
    第一轮,开始Result={A},最后得到Result={AD},Result发生变化,开始第二轮
    第二轮
    此时, Result={AD}
    Result与R1求交,为{AD}, 求AD的闭包:AD F + _F^+ F+={ACD}, 则T={ACD} ∩ ∩ R 1 _1 1={AD}; Result= Result ∪ ∪ T={AD}
    Result与R2求交,为{A}, 求A的闭包:A F + _F^+ F+={ACD}, 则T={ACD} ∩ ∩ R 2 _2 2={A}; Result= Result ∪ ∪ T={AD}
    Result与R3求交,为{ Ø Ø Ø}, Result= Result ∪ ∪ T={AD}
    Result与R4求交,为{D}, 求D的闭包:D F + _F^+ F+={D}, 则T={D} ∩ ∩ R 4 _4 4={D} Result= Result ∪ ∪ T={AD}
    Result与R5求交,为{A}, 求A的闭包:A F + _F^+ F+={ACD}, 则T={ACD} ∩ ∩ R 5 _5 5={A} Result= Result ∪ ∪ T={AD}
    第二轮,开始Result={AD},最后得到Result={AD},Result无变化且Result不包含C,不能覆盖A->C,无需做其他两个验证了。
    所以:此模式分解不保持函数依赖性。

    例2:给定关系模式R(U,F),U={A,B,C,D} F={A->B, B->C, C->D, D->A}
    分解为R1:{AB}、R2{BC}、R3{CD},判断此分解是否具有依赖保持性
    解:求投影
    R 1 _1 1 F 1 _1 1{A->B,B->A} ,
    R 2 _2 2 F 2 _2 2{C->B,B->C} ,
    R 3 _3 3 F 3 _3 3{C->D,D->C},
    F’=(F 1 _1 1UF 2 _2 2UF 3 _3 3UF 4 _4 4)={A->B,B->A,C->B,B->C,C->D,D->C}
    缺少: 函数依赖D->A;
    D F ′ + _F'^+ F+={DCBA};表示F’蕴含了D->A,F’与F是等价的;所以保持函数依赖性
    完毕。

    我们可以使用第三步方法再验证一下F’是否蕴含了D->A
    第一轮
    令: Result={D}
    Result与R1求交,为{ Ø Ø Ø}, 求 Ø Ø Ø的闭包得到 Ø Ø Ø,T={ Ø Ø Ø} ∩ ∩ R 1 _1 1={ Ø Ø Ø}; Result= Result ∪ ∪ T={D}
    Result与R2求交,为{ Ø Ø Ø}, 求 Ø Ø Ø的闭包得到 Ø Ø Ø,T={ Ø Ø Ø} ∩ ∩ R 2 _2 2={ Ø Ø Ø}; Result = Result ∪ ∪ T={D}
    Result与R3求交,为{D}, 求D的闭包,D F + _F^+ F+={ABCD},T={ABCD} ∩ ∩ R 3 _3 3={CD}; Result= Result ∪ ∪ T={CD}
    由于最后的Result={CD}和最初的Result={D}不同,我们开始第二轮
    第二轮
    Result={CD}
    Result与R1(AB)求交,为{ Ø Ø Ø}, 求 Ø Ø Ø的闭包得到 Ø Ø Ø,T={ Ø Ø Ø} ∩ ∩ R 1 _1 1={ Ø Ø Ø}; Result= Result ∪ ∪ T={CD}
    Result与R2(BC)求交,为{C}, 求C的闭包C F + _F^+ F+={ABCD},T={ABCD} ∩ ∩ R 2 _2 2={BC}; Result= Result ∪ ∪ T={BCD}
    Result与R3(CD)求交,为{CD}, 求CD的闭包,DC F + _F^+ F+={ABCD},T={ABCD} ∩ ∩ R 3 _3 3={CD}; Result= Result ∪ ∪ T={BCD}
    由于最后的Result={BCD}和最初的Result={CD}不同,我们开始第三轮
    第三轮
    Result={BCD}
    Result与R1(AB)求交,为{B}, 求B的闭包B F + _F^+ F+={ABCD},T={ABCD} ∩ ∩ R 1 _1 1={AB}; Result= Result ∪ ∪ T={ABCD}
    此时:result已经包含了A,说明F’是否蕴含了D->A
    F’与F等价,保持函数依赖性。

    结论

    保持函数依赖性,就是做模式分解后的F’(各个子模式函数依赖的并集)是否与F(原有的函数依赖集)等价,F’包含所有的F中的函数依赖则可以得出保持函数的依赖性(充分条件),如果F’不显式包含F中的函数依赖,还需进一步判断,判断方法有两条,第一种是通过F’中的属性闭包去求,是否蕴含函数依赖(这种方法要求做函数投影时,不能缺项);第二种使用给定的算法去求,对投影要求简单,但过程特别麻烦。

    展开全文
  • 给定函数依赖集合F={ A2→(A3,A5); (A1, A3)→A6; (A2,A6)→ A4 },则关于R既保持 依赖又无损连接地分解成第三范式,分解正确 的是 A.p={R1(A2,A3, A5), R2(A1,A3,A6), R3(A2,A4,A6) } B.p={R1(A2,A3, A5), R2(A1...

    是否保持函数依赖

    如果F上的每一个函数依赖都在其分解后的某一个关系上成立,则这个分解是保持依赖的(这是一个充分条件)

    无损连接定理

    关系模式R(U,F)的一个分解,ρ={R1<U1,F1>,R2<U2,F2>}具有无损连接的充分必要条件是:U1∩U2→U1-U2 €F+ 或U1∩U2→U2 -U1€F+

    验证算法
      ρ={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(A1, A2, A3, A4, A5,A6),给定函数依赖集合F={ A2→(A3,A5); (A1,A3)→A6; (A2,A6)→ A4 },则关于R既保持依赖又无损连接地分解成第三范式,分解正确的是_____
    A.p={R1(A2,A3, A5), R2(A1,A3,A6), R3(A2,A4,A6) }
    B.p={R1(A2,A3,A5),R2(A1,A3,A6),R3(A2,A4,A6),R4(A1,A2) }
    C.p= {R1(A2,A3.A5), R2(A1,A2,A3,A4,A6)}
    D.p={R1(A1,A2,A3,A5),R2(A2,A4,A6)}

    问题解析:可以求出候选码为(A1,A2),得出函数F的最小函数依赖集为F={ A2→(A3,A5), (A1,
    A3)→A6, (A2,A6)→ A4 },ρ={R1(A2A3A5),R2(A1A3A6),R3(A2A4A6)};经过判断此关系不满足无损分解的条件,因此把候选码A1A2加入关系中,就达到满足了保持了函数依赖和无损连接性的目的

    2、

    给定关系模式R(U, F),其中U={A1, A2,A3,A4,A5,A6},给定函数依赖集合F=A1→(A2,A3); A3→A4; (A2,A3)→(A5,A6);A5→A1 },有一个分解r=R1(A1,A2,A3,A4),
    R2(A2,A3,A5,A6)},问该分解____
    A、既具有无损连接性,又保持函数依赖
    B、不具有无损连接性,但保持函数依赖
    C、具有无损连接性 ,但不保持函数依赖
    D、既不具有无损连接性,又不保持函数依赖

    问题解析:
    分成了两个关系属性时,找出两个关系中的共同属性,即A2,A3因此A2,A3为函数依赖集的候选码。
    ①在函数依赖集F中有(A2,A3)→(A5,A6),因此该分解具有无损连接性。
    ②R1(A1,A2,A3,A4)与A1→(A2,A3); A3→A4相对应而R2(A2,A3,A5,A6)没有与(A2,A3)→(A5,A6);A5→A1 相对应,因此该分解不保持函数依赖。

    3、

    给定关系模式R(U, F), 其中U={A1, A2,
    A3,A4,A5,A6},给定函数依赖集合
    F=A1→(A2,A3); A3→A4; (A2,A3)→(A5,A6);
    A6→A1 },有一个分解r=R1(A1 ,A2,A3,A4),
    R2(A3,A4,A5,A6)},问该分解___
    A、既具有无损连接性,又保持函数依赖
    B、不具有无损连接性,但保持函数依赖
    C、具有无损连接性,但不保持函数依赖
    D、既不具有 无损连接性, 又不保持函数依赖

    问题解析:
    分成了两个关系属性时,找出两个关系中的共同属性,即A3,A4因此A3,A4为函数依赖集的候选码。
    ①在函数依赖集F中没有有(A2,A3)→A 因此该分解不具有无损连接性。
    ②R1(A1,A2,A3,A4)与A1→(A2,A3); A3→A4相对应而R2(A3,A4,A5,A6)没有与(A2,A3)→(A5,A6),A6→A1 相对应,因此该分解不保持函数依赖。

    4、

    对连锁商店的管理,设计了关系模式:商店(商店,商品部,商品,商品部经理),下 列说法正确的是__
    A、不满足第2范式
    B、满足第2范式但不满足第3范式
    C、满足第3范式
    D、其他都不对

    问题解析:
    可以得到函数依赖集:(商店,商品)→商品部,(商店,商品部)→商品部经理,求得候选码为(商店,商品),从依赖集中看出不存在部分函数依赖,但是存在传递依赖,因此满足第2范式但不满足第3范式

    5、

    一般情况,企业会将从一个供应商处一次所进的多种货物办理一次入库,因此设计了关系模式:入库单(单号,日期,库房,供应商,物品,数量,金额),下列说法正确的是___
    A、不满足第2范式
    B、满足第2范式但不满足第3范式
    C、 满足第3范式
    D、其他都不对

    问题解析:可以得到函数依赖集 单号→(日期,库房,供应商),物品→(金额),(单号,物品)→数量,求得候选码为(单号,物品),因为存在部分函数依赖,因此该依赖集只满足1NF即不满足第二范式。

    6、

    设有关系模式W(C,P,S,G,T,R),其中各属性的含义是: C课程,P教师,S学生,G成绩, T时间,R教室,根据定义有如下数据依赖集D={ C→P, (S,C)→G, (T,R)→C, (T,P)-→R,
    (T,S)-→R}。关系模式W的一个候选键是__W的规范化程度最高达到____

    A、(S,C), 1NF
    B、(T,R), 3NF
    C、(T,P), 4NF
    D、(T,S),2NF

    问题解析:容易求得候选键为(T,S),可以看出在依赖集D中不存在部分函数依赖,因此最起码是达到2NF。因为候选键为(T,S),有(S,T)→(S,T,R,C,G)在函数依赖集中却有C→P, (T,R)→C,(T,S)-→R得到(S,T)→C→P,因此该函数依赖集中存在传递依赖不符合3NF的条件。

    7、

    关系模式R(A1, A2, A3,A4,A5,A6),如果A1→(A3,A4); (A2, A4)→A5; (A3,A5)→A6,则关于R的说法正确的是___
    A、即不存在对候选键的部分函数依赖,又不存在对候选键的传递函数依赖
    B、存在对候选键的部分函数依赖,但不存在对候选键的传递函数依赖
    C、不存在对候选键的部分函数依赖,但存在对候选键的传递函数依赖
    D、既存在对候选键的部分函数依赖,又存在对候选键的传递函数依赖

    问题解析:可以求得候选码为(A1,A2),因为A1→(A3,A4),所以存在对候选键的部分函数依赖,因为候选码为(A1,A2),有(A1,A2)→(A1,A2,A3,A4,A5,A6),又因为在依赖集中有(A3,A5)→A6,因此就会有(A1,A2)→(A3,A5)→A6即存在对候选键的传递函数依赖

    8、

    关系模式R(A1,A2, A3, A4, A5, A6),如果A1→(A3, A4);
    (A2,A4)→A5; (A3,A5)→A6,则R的候选键为___
    A、A1
    B、(A1, A2)
    C、(A1, A2, A4)
    D、(A1, A3, A5)

    9、

    在关系模式R(U,F)中,如果X-→Y,存在X
    的真子集X1,使X1-→Y,称函数依赖X-→Y为___
    A、平凡函数依赖
    B、部分函数依赖
    C、完全函数依赖
    D、传递函数依赖.

    展开全文
  • 3NF既具有无损连接性又保持函数依赖的分解算法,基于SQL Server数据库,若有不足之处,望IT同僚指出、批评。
  • 数据库模式分解----如何判断保持无损连接性和保持函数依赖 书上的算法写的太抽象了!看了半天!简单用人话解释一下! 在之前首先要了解一下属性集的闭包的概念 属性集的闭包 令α为一属性集。我们称在函数依赖集F下...

    书上的算法写的太抽象了!看了半天!简单用人话解释一下!

    在之前首先要了解一下属性集的闭包的概念

    属性集的闭包

    令α为一属性集。我们称在函数依赖集F下由α函数确定的所有属性的集合为F下α的闭包,记为α+。简单说闭包就是由一个属性集直接或间接推到出的所有属性的集合。

    例如关系模式R的属性集U={A,B,C,D,E},F={A→B, B→C, D→E}是R上的函数依赖集,设α={A,E},属性A根据函数依赖F能得到闭包a+ = {A,B,C,E}

    保持无损连接性判断

    当分解ρ只有两组的时候

    R1∩R2→R1-R2或R1∩R2→R2-R1

    这两个条件只要满足任何一个就是无损连接,都不满足则为有损连接

    例题:设有关系模式R(U,V,W,X,Y,Z),其函数依赖集:F={U→V,W→Z,Y→U,WY→X},现有下列分解:ρ={UVY,WXYZ}

    1. R(UVY) ∩ R(WXYZ) 得出 Y,R1-R2 得出 UV,R2-R1 得出WXZ(Ri-Rj计算差集就是以第一个Ri为基准有相同项去除保留不同项)
    2. 证明Y → UVY → WXZ 至少有一个成立
    3. 根据 F={U→V,W→Z,Y→U,WY→X}得出Y→U, U→VY → UV成立
    4. Y WXZ 无法推出 但Y → UV 成立 即可判断为无损连接

    当分解ρ大于两组的时候

    需要列出**初始判断表,**根据已知条件在初始判断表里修改, 在某次修改后或者最终表里如果有一行为a1,a2,…,an的即为无损连接。

    例题:U=(A,B,C,D,E) F={A→D,E→D,D→B,BC→D,DC→A} 判断ρ={AB,AE,CE,BCD,AC}是否为无损连接分解

    初始表(左侧第一列为ρ 第一行为U) ,规则为:左侧的ρ包含U即为ai不包含则为bji i为第几列 j为第几行

    ρ/UABCDE
    ABa1a2b13b14b15
    AEa1b22b23b24a5
    CEb31b32a3b34a5
    BCDb41a2a3a4b45
    ACa1b52a3b54b55

    列出初始表后根据 **F={A→D,E→D,D→B,BC→D,DC→A}**条件依次修改表,修改规则为:找函数依赖于的列的相同项,将确定的依赖列的相应项的值修改,如果有ai则改为ai,没有则看bji,相同则以满足条件对应的第一行为基准,如果被修改为bji时需要添加特殊标记*,那么该列有特殊标记*的再次更改时该列所有*bji也需要修改

    A→D:找出A列存在的相同项a1,D列中没有a以满足条件对应的第一行为基准,修改的值是b所以将被修改的值加标记

    ρ/UABCDE
    ABa1a2b13b14b15
    AEa1b22b23*b14a5
    CEb31b32a3b34a5
    BCDb41a2a3a4b45
    ACa1b52a3*b14b55

    E→D:相同项a5,D列满足条件对应的第一行为b14,将修改的值添加标记*

    ρ/UABCDE
    ABa1a2b13b14b15
    AEa1b22b23*b14a5
    CEb31b32a3*b14a5
    BCDb41a2a3a4b45
    ACa1b52a3*b14b55

    D→B:相同项b14,B列对应a2 ,改的是a不用加标记

    ρ/UABCDE
    ABa1a2b13b14b15
    AEa1a2b23*b14a5
    CEb31a2a3*b14a5
    BCDb41a2a3a4b45
    ACa1a2a3*b14b55

    BC→D:需要满足BC列相同(相同项为a2,a3) D列改为BC列对应的a4,因为此时修改到标记过得*b14的数据,所以该列所有*b14都需要修改

    ρ/UABCDE
    ABa1a2b13b14b15
    AEa1a2b23a4a5
    CEb31a2a3a4a5
    BCDb41a2a3a4b45
    ACa1a2a3a4b55

    DC→A:满足DC列相同(相同项为a3,a4),A列改为DC列 对应的a1

    ρ/UABCDE
    ABa1a2b13b14b15
    AEa1a2b23a4a5
    CEa1a2a3a4a5
    BCDa1a2a3a4b45
    ACa1a2a3a4b55

    判断最终表只要存在一行a1,a2,…,an则为无损连接 没有即为有损连接(修改过程中如果存在一行a1,a2,…,an也可判断具有无损连接性,可以终止算法)

    ρ/UABCDE
    ABa1a2b13b14b15
    AEa1a2b23a4a5
    CEa1a2a3a4a5
    BCDa1a2a3a4b45
    ACa1a2a3b14b55

    CE行为a1…a5所以ρ为无损连接分解

    保持函数依赖判断

    如果F上的每一个函数依赖都在其分解后的某一个关系上成立,则这个分解是保持依赖的(充分条件)。

    如果上述判断失败,并不能断言分解不是保持依赖的,因为上面只是充分条件,还要使用下面的算法来做进一步判断。

    对F上的每一个α→β使用下面的过程:

    result:=α;
    while(result发生变化)do
    	for each 分解后的Ri
    		t=(result∩Ri)+ ∩Ri
    		result=result∪t
    

    这里的属性闭包是在函数依赖集F下计算出来的。如果result中包含了β的所有属性,则函数依赖α→β成立,这时分解是保持依赖的当且仅当上述过程中F的所有依赖都被保持。

    例题:关系模式R(A,B,C,D)分解{R1(A,B),R2(B,C),R3(C,D)},函数依赖集F={A→B,B→C,C→D,D→A}

    R1中包含A→B

    R2中包含B→C

    R3中包含C→D

    用函数依赖集和分解后的R1,R2,R3的并集做差,得到缺少D→A依赖,进一步使用算法判断

    result={D}

    进入do-while循环

    for-each遍历分解后的R关系

    ​ 第一次R1,t=(result∩R1)+ ∩R1得到t=({D}∩{A,B})+ ∩{A,B},{Ø}+空集的闭包还是空集,交{A,B}为t空,result={D}∪t={D}

    ​ 第二次R2,t=(result∩R2)+ ∩R2得到t=({D}∩{B,C})+ ∩{B,C},跟第一次同理,result={D}

    ​ 第三次R3,t=(result∩R3)+ ∩R3得到t=({D}∩{C,D})+ ∩{C,D},{D}+求D的闭包,根据F推出D的闭包是{A,B,C,D},跟{C,D}做交集得到t={C,D},result={D}∪{C,D}={C,D}

    for-each循环结束,此时判断while-result发生了变化,所以再次进入do-while循环,继续执行for-each遍历分解后的R关系

    ​ 第一次R1,t=(result∩R1)+ ∩R1得到t=({C,D}∩{A,B})+ ∩{A,B}={Ø},result={C,D}∪{Ø}={C,D}

    ​ 第二次R2,t=(result∩R2)+ ∩R2得到t=({C,D}∩{B,C})+ ∩{B,C}={C}+ ∩{B,C}={A,B,C,D}∩{B,C}={B,C},result={C,D}∪{B,C}={B,C,D}

    ​ 第三次R3,t=(result∩R3)+ ∩R3得到t=({B,C,D}∩{C,D})+ ∩{C,D}={A,B,C,D}∩{C,D}={C,D},result={B,C,D}∪{C,D}={B,C,D}

    for-each循环结束,此时判断while-result发生了变化,所以再次进入do-while循环,继续执行for-each遍历分解后的R关系

    ​ 第一次R1,t=(result∩R1)+ ∩R1得到t=({B,C,D}∩{A,B})+ ∩{A,B}={B}+ ∩{A,B}={A,B,C,D}∩{A,B}={A,B}, result={B,C,D}∪{A,B}= {A,B,C,D} [包含了所有属性,到这里后面循环的result就不变了,result={A,B,C,D}包含了属性A,已经可以判断这个分解保持函数依赖,后面的计算过程跟上面都一样不写了]

    ​ 第二次…

    ​ 第三次…

    for-each循环结束,此时判断while-result发生了变化,所以再次进入do-while循环,继续执行for-each遍历分解后的R关系

    ​ 第一次…

    ​ 第二次…

    ​ 第三次…

    for-each循环结束,此时判断while-result不变,循环结束

    得到的result={A,B,C,D}包含了属性A,所以该分解保持了函数依赖

    展开全文
  • 系模式中是否为无损连接 2)是否保持函数依赖   一、无损连接的判定: 1) 如果分解后的的关系模式是形如{U1,U2}这,里面只有两个,那很好做,就判断    或 是否成立,成立的话肯定是  无损...
  • 一个是最小依赖函数集,一个是求候选码,一个是求闭包,一个是要把关系模式分解成3NF且保持函数依赖,一个是分解成3NF且保持函数依赖和无损连接。 记录一下我对这几个问题的求法。可能会有哪里有漏洞,希望可以指...
  • 判断保持函数依赖 U1=ABCD,F1+={A→BC,B→D} U2=EFA,F2+={EF→A} 丢失了CD→E,BE→F,因此没有保持函数依赖。 用算法判断是否无损连接 设有关系模式R(U,V,W,X,Y,Z),其函数依赖集:F={U→V,W→Z,Y→U,...
  • 模式分解的本质是将一个大的模式分解为几个小的模式,在模式分解至少应达到3NF,而且要保证是无损连接性的,分解时尽可能保持函数依赖。事实证明,保持无损连接和保持函数依赖,可以达到3NF,但不一定能达到BCNF。...
  • 模式分解是否保持函数依赖的判断方法以及例子

    千次阅读 多人点赞 2020-04-05 12:16:23
    如果F上的每一个函数依赖都在其分解后的某一个关系上成立,则这个分解是保持依赖的(充分条件)。 如果上述判断失败,并不能断言分解不是保持依赖的,因为上面只是充分条件,还要使用下面的通用方法来做进一步判断...
  • 判断模式分解是否保持函数依赖? 判断模式分解是否保持函数依赖? 判断模式分解是否保持函数依赖
  • 数据库保持函数依赖的分解.ppt
  • 这里给一个分解算法: 转换为3NF既有无损连接又保持函数依赖的分解 算法如下: 对函数依赖集进行极小化处理。 找出不在F中出现的属性,将这样的属性构成一个关系模式。(此情况较少见) 对F按具有相同左部的原则...
  • 【专讲】 保持函数依赖.doc
  • 判断分解的无损连接性和保持函数依赖

    万次阅读 多人点赞 2019-06-29 21:36:41
    丢失了CD→E,BE→F,因此没有保持函数依赖。 (1) {ABC,BD,BEF} a.判断无损连接分解 ①构造一个初始的二维表,若“属性”属于“模式”中的属性,则填aj,否则填bij。   A B C ...
  • 保持函数依赖分解

    千次阅读 2019-02-01 08:56:20
    对关系分解时, 原关系的闭包与分解后关系闭包的并集相等 函数依赖不能丢失的特性,不能破坏原来的语义
  • 步骤 1.假如给出的依赖集F存在...3.不包含的话为3NF且保持函数依赖,假如要转为3NF且无损分解且保持函数依赖,只要加上一个候选键即可(原先就有候选键的不用加,因为已经是3NF且无损分解且保持函数依赖) 4.将关系模式
  • 【牛客网数据库原理题目】设关系模式R(A,B,C),F是R上成立的FD集,F={A→B,C→B},ρ={AB,AC}是R的一个分解,那么分解ρ( )?...( A ) 保持函数依赖集F ( B ) 丢失了A→B ( C ) 丢失了C→B ( D ) 丢失了B→C
  • 联系(Relationship)1:1联系:如果实体集E1中的每个实体最多只能和实体集E2中一个...函数依赖(FunctionDependency)定义设关系模式R(U),属性集合U={A1,A2,…,An},X,Y为属性集合U的子集,如果对于关系模式R(U)...
  • 保持函数依赖的分解指的是对关系分解时,原关系的闭包与分解后关系闭包的并集相等。   从定义来看,可以得到不严格但好理解的—— 保持无损连接的模式分解,每个Ui必须包含作为连接的属性。故无损....
  • 判断是否保持函数依赖

    万次阅读 2017-06-15 15:52:09
    如果F上的每一个函数依赖都在其分解后的某一个关系上成立,则这个分解是保持依赖的(这是一个充分条件)。 如果上述判断失败,并不能断言分解不是保持依赖的,还要使用下面的通用方法来做进一步判断。 该方法的...
  • 转换成3NF既有无损连接性又保持函数依赖的分解

    千次阅读 多人点赞 2019-06-30 21:32:27
    转换为3NF的保持函数依赖的分解 步骤: 1、求关系模式R<U,F>的最小依赖集Fm。 2、找出所有不在Fm中出现的属性,这些属性构成R0<U0,F0>。把这些属性从U中去掉,剩余的属性仍记为U。 3、若Fm中存在X→A...
  • 数据库范式1NF 2NF 3NF BCNF实例分解 ... 数据库中的无损连接分解和是否保持函数依赖的判定 https://blog.csdn.net/legendaryhaha/article/details/80649234 数据库学习之模式分解 https...
  • 1.转换成3NF的保持函数依赖的分解

    万次阅读 多人点赞 2017-03-04 15:23:37
    1.转换成3NF的保持函数依赖的分解例1:关系模式R,F>,其中U={C,T,H,R,S,G},F={CS→G,C→T,TH→R,HR→C,HS→R},将其分解成3NF并保持函数依赖。 解:根据算法进行求解 (一)计算F的最小函数依赖集 ① 利用分解规则...
  • 3NF:不存在非主属性对码的传递函数依赖或部分函数依赖。 如AB-C,A->C 码为(A,B),A,B是主属性,C是非主属性,C部分函数依赖于码,即不满足3NF BCNF:每个决定因素都包含码(相比于3NF,优点是加上了对主...
  • ## 答:候选码 A,是无损分解,不保持 FD。 -------------------------------- ## F={A→BC,C→AD},ρ={ABC, AD} ## 答:候选码 A 和 C,是无损分解,保持 FD。 请问这两个答案是不是都正确?怎么得到的?

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 259,714
精华内容 103,885
关键字:

保持函数依赖