精华内容
下载资源
问答
  • 判断是否保持函数依赖
    万次阅读
    2017-06-15 15:52:09

    保持依赖的判断。
    如果F上的每一个函数依赖都在其分解后的某一个关系上成立,则这个分解是保持依赖的(这是一个充分条件)。
    如果上述判断失败,并不能断言分解不是保持依赖的,还要使用下面的通用方法来做进一步判断。
    该方法的表述如下:
    算法二:
    对F上的每一个α→β使用下面的过程:
    result:=α;
    while(result发生变化)do
    for each 分解后的Ri
    t=(result∩Ri)+ ∩Ri
    result=result∪t

    更多相关内容
  • 是否为无损连接 方法一:无损连接定理 关系模式R(U,F)的一个分解,ρ={R1<U1,F1>,R2<U2,F2>}具有无损连接的充分必要条件是: U1∩U2→U1-U2 €F+ 或U1∩U2→U2 -U1€F+ 方法二:算法 ρ={R1<U1,...

    是否为无损连接

    方法一:无损连接定理

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

    展开全文
  • 系模式中是否为无损连接 2)是否保持函数依赖   一、无损连接的判定: 1) 如果分解后的的关系模式是形如{U1,U2}这,里面只有两个,那很好做,就判断    或 是否成立,成立的话肯定是  无损...

    首先了解一下几个概念:

    1)把一个关系模式分解成若干个关系模式的过程,称为关系模式的分解。

    2)把低一级的关系模式分解为若干个高一级的关系模式的方法不是唯一的。

    3)只有能够保证分解后的关系模式与原关系模式等价,分解方法才有意义。

     

    对于第一句话,为什么需要分解关系模式?因为原来的关系模式可能造成数据冗余或

    给数据库带来潜在的不一致性。对于第二句话,根据不同语义,分解的原则也不尽相

    同,所以方法肯定是不唯一的,譬如U={A,B,C},根据不同原则(随便你自己定),

    可能分成(A,B)(A,C)也可能分成(B,C)(A,C)。对于第三句话,则是本文所要

    讲的内容。

     

    为了保证分解后的关系模式与原关系模式等价,我们要判定 1)分解后形成的行的关

    系模式中是否为无损连接  2)是否保持函数依赖

     

    一、无损连接的判定:

    1)如果分解后的的关系模式是形如{U1,U2}这,里面只有两个,那很好做,就判断

           或 是否成立,成立的话肯定是

          无损连接。

    2)如果是两个以上{U1,U2,U3....}这种,那就比较麻烦了,比如,有属性集,

    ABCDEF,存在这样的函数依赖集{A->BC , CD->E , B->D , BE->F , EF->A},然后有

    这样的分解{ABC , BD , BEF}。

    例如:

    设U1=ABC,U2=BD,U3=BEF,根据提供的函数依赖集,我们可得U1存在这样的

    函数依赖A->BC,U2上的函数依赖是 B->D, U3的函数依赖是BE->F。

     

    1)于是可构造这样的表格。

    GABCEF  
    A->BC      
    B->D      
    BE->F      

     

    2)各自判断A,B,C,D,E,F是否有在G列的函数依赖中,如果有记为ai,i表示第几列,否

    则记为bji,表示第j行第i列

    如:

     

    GABCEF
    A->BCa1(A有在函数依赖中,此行为第一行)     
    B->D      
    BE->Fb31(A没有,此列为第一列)     

    这样我们可得到图

     

    GABCEF
    A->BCa1a2a3b14b15b16
    B->Db21a2b23a4b25b26
    BE->Fb31a2b33b34a5a6

     

     3)接下来是关键的,如果我们经过一系列变换得到有一行是这样的排序

     

    {a1,a2,a3,a4,a5,a6...},即不存在bji,那我们就认为,该分解是无损连接。

     

     4)变换过程:为了方便,我们可以按A->BC, B->D,BE->F这个顺序来(随你喜

    欢)。

    第一遍,根据A->BC,我们知道主健是能唯一标识一个元组的,也就是说如果

    A中存在着两个属性值是相同的,毫无疑问,他们推出的BC的值肯定也是相同的。从

    表格中我们遍历A列,没有发现有相同的属性组,那就跳过。

     

    第二遍, 根据B->D,因为B列属性值相同,那我们修改D列。修改时遵照这样的一个

    规则,如果D中有ai这样的值,那么宣布修改为ai,如果没有,修改成该列的第一行的

    第一个值。从表格中我们可以发现D中有a4,那么修改后变成:

     

    GABCEF
    A->BCa1a2a3a4b15b16
    B->Db21a2b23a4b25b26
    BE->Fb31a2b33a4a5a6

     

    第三遍,根据BE->F,找一组BE相同的值,发现不存在,即不存在类似

     

    {a1,a2,a3,a4,a5,a6}这样的序列,即该分解不是无损连接分解。

     

    二、是否保持函数依赖?

     

    这个的判断方法就比较简单了,还是这道题,有属性集,ABCDEF,存在这样

    的函数依赖集{A->BC , CD->E , B->D , BE->F , EF->A},然后有这样的分解

    {ABC , BD , BEF}。

    设U1=ABC,A->BC,U2=BD,B->D ,U3=BEF,BE->F ,即我们不能推出 CD->E 

    EF->A,所以也不具有保持函数依赖的特性

    展开全文
  • 判断模式分解是否保持函数依赖? 判断模式分解是否保持函数依赖? 判断模式分解是否保持函数依赖
  • 模式分解是否保持函数依赖的判断方法以及例子

    千次阅读 多人点赞 2020-04-05 12:16:23
    如果F上的每一个函数依赖都在其分解后的某一个关系上成立,则这个分解是保持依赖的(充分条件)。 如果上述判断失败,并不能断言分解不是保持依赖的,因为上面只是充分条件,还要使用下面的通用方法来做进一步判断...

    保持依赖的判断。 

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

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

    过程表述如下: 

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

     

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

    例1:考虑关系模式R(A,B,C,D)分解{R1(A,B),R2(BC),R3(C,D)},

    函数依赖集F={A→B,B→C,C→D,D→A}

    显然,AB包含于R1,BC包含于R2,CD包含于R3。因此,只需要验证是否有D→A呗分解p所保持。为此,我们使用算法。

    首先,result={D}进入 repeat循环,当i=1时不改变,因为{D}U(({D}∩{A,B})+∩{A,B})仍是{D}。

    同样方法,当i=2时Z不变。然而,i=3时,我们得到

    result={D}U(({D}∩{C,D})+∩{C,D}

    ={D}U({D}+∩{C,D})={D}U({A,B,C,D}∩{C,D})

    ={C,D}

    再次执行 repeat的循环体,当i=2时产生result={B,C,D}而第三遍,当i=1时置result为{A,B,C,D}。此后,T不再改变。这样,result={A,B,C,D}它包含A,因此,D→A被分解所保持。从而是保持函数依赖的分解。

    例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),判断这个分解是否具有函数依赖性。

    先看F中每一个函数依赖,R4有C->D,DE->C。A->C,B->C,CE->A。这三个函数依赖分解模式里均未能覆盖。

    开始使用算法进行检测:

    首先对于A->C,result = A,(A)+ = ACD ,T=AD,result=AD,result改变,进入下一个循环:result = AD,(ABD)+ = ABCD ,t=AB,result=ABD。

    result改变:result = ABD, (ABD)+ = ABCDE, t=BE,result=ABDE。

    result改变:result = ABDE,(ABCD)+=ABCDE,t=CDE,result=ABCDE。

    result改变:(从这一步就能看出来,保持了函数依赖了,因为已经包含C了)result = ABCDE,(ABCDE)+=ABCDE,t=AE,result=ABCDE。

    result未改变。退出循环。、由于result=ABCDE,包含了C,所以分解保持函数依赖。
     

    展开全文
  • 【牛客网数据库原理题目】设关系模式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
  • 这里给一个分解算法: 转换为3NF既有无损连接又保持函数依赖的分解 算法如下: 对函数依赖集进行极小化处理。 找出不在F中出现的属性,将这样的属性构成一个关系模式。(此情况较少见) 对F按具有相同左部的原则...
  • 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没有被覆盖。...
  • 给定函数依赖集合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...
  • 是否保持函数依赖。 (1){ABCD,EFA} a.判断无损连接分解 U1∩U2=A, U1-U2=BCD, U2-U1=EF 存在A→BCD∈F+,所以分解是无损连接分解。 b.判断保持函数依赖 U1=ABCD,F1+={A→BC,B→D} U2=EFA,F2+={EF→A} 丢失了CD→...
  • ## 答:候选码 A,是无损分解,不保持 FD。 -------------------------------- ## F={A→BC,C→AD},ρ={ABC, AD} ## 答:候选码 A 和 C,是无损分解,保持 FD。 请问这两个答案是不是都正确?怎么得到的?
  • 保持函数依赖分解

    千次阅读 2019-02-01 08:56:20
    对关系分解时, 原关系的闭包与分解后关系闭包的并集相等 函数依赖不能丢失的特性,不能破坏原来的语义
  • 非常好的讲解了模式分解保持函数依赖的意义,来自知网于思江和王小兵老师,资源很好!
  • 输入:关系模式R的函数依赖集F和...输出:P是否保持函数依赖的判定。 方法: (1)for(每个x→y∈F)do (2)begin (3) if(不存在i使得XYR)then / * 检验X→Y是否被分解p所保持 * / (4) begin (5) Z<-X; (6) repeat (7) ...
  • 无损分解和保持依赖

    千次阅读 多人点赞 2020-04-23 14:01:40
    (注:在准备软考过程中,遇到一道判断无损分解和保持依赖的试题,于是找到了这篇很通俗的文章,特收藏并学习之。微笑) 大部分是对一个关系模式分解成两...R是具有函数依赖集F的关系模式,(R1 ,R2)是R的一个分解...
  • 3NF既具有无损连接性又保持函数依赖的分解算法,基于SQL Server数据库,若有不足之处,望IT同僚指出、批评。
  • 数据库保持函数依赖的分解.ppt
  • 联系(Relationship)1:1联系:如果实体集E1中的每个实体最多只能和实体集E2中一个...函数依赖(FunctionDependency)定义设关系模式R(U),属性集合U={A1,A2,…,An},X,Y为属性集合U的子集,如果对于关系模式R(U)...
  • 判断分解的无损连接性和保持函数依赖

    万次阅读 多人点赞 2019-06-29 21:36:41
    是否保持函数依赖。 (1) {ABCD,EFA} a.判断无损连接分解 U1∩U2=A, U1-U2=BCD, U2-U1=EF 存在A→BCD∈F+,所以分解是无损连接分解。 b.判断保持函数依赖 U1=ABCD,F1+={A→BC,B→D} U2=EFA,F2+={EF→...
  • 【专讲】 保持函数依赖.doc
  • 数据库模式分解----如何判断保持无损连接性和保持函数依赖 书上的算法写的太抽象了!看了半天!简单用人话解释一下! 在之前首先要了解一下属性集的闭包的概念 属性集的闭包 令α为一属性集。我们称在函数依赖集F下...
  • 模式分解的本质是将一个大的模式分解为几个小的模式,在模式分解至少应达到3NF,而且要保证是无损连接性的,分解时尽可能保持函数依赖。事实证明,保持无损连接和保持函数依赖,可以达到3NF,但不一定能达到BCNF。...
  • 一个是最小依赖函数集,一个是求候选码,一个是求闭包,一个是要把关系模式分解成3NF且保持函数依赖,一个是分解成3NF且保持函数依赖和无损连接。 记录一下我对这几个问题的求法。可能会有哪里有漏洞,希望可以指...
  • 求解函数依赖是否保持中的投影算法

    千次阅读 多人点赞 2020-10-25 23:58:46
    求解函数依赖是否保持中的投影算法 ** 文章目录求解函数依赖是否保持中的投影算法前言一、第一步求H在每个分解上的投影1.求F12.求F2二、看H+是否等价于G+ 前言 在学习数据库时,我们总会遇到求解一个分解是否满足...
  • 函数依赖性判断

    2022-02-11 15:07:47
    (2)如果每个依赖都包含在分解的某个模式中,则结束算法,判断出保持函数依赖 (3)如果第二部中某几个函数依赖并不包括在任一分解模式中则执行如下算法 对函数依赖α→β使用下面的过程:result:=α;while...
  • 保持函数依赖的分解指的是对关系分解时,原关系的闭包与分解后关系闭包的并集相等。   从定义来看,可以得到不严格但好理解的—— 保持无损连接的模式分解,每个Ui必须包含作为连接的属性。故无损....
  • 函数依赖

    千次阅读 2021-04-17 14:13:50
    函数依赖 定义 设R(U)是属性集U上的关系模式,X,Y是U的子集。若对于R(U)的任意一个可能的关系r,r中不可能存在两个元组在X上的属性值相等而在Y上的属性值不相等,则称X函数确定Y或Y函数依赖于X ,记作X->Y,X...
  • ③判断最后的依赖集是否包含候选键,不包含的话为3NF且保持函数依赖 3.不包含的话为3NF且保持函数依赖,假如要转为3NF且无损分解且保持函数依赖,只要加上一个候选键即可(原先就有候选键的不用加,因为已经是3NF且...

空空如也

空空如也

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

是否保持函数依赖