精华内容
下载资源
问答
  • 无损分解

    2019-02-01 08:54:45
    对关系模式分解时,原关系模型下任一合法的关系值在分解之后可以通过自然联接运算恢复。

    对关系模式分解时,原关系模型下任一合法的关系值在分解之后可以通过自然联接运算恢复。

    展开全文
  • 无损分解和保持依赖

    千次阅读 2020-04-23 14:01:40
    (注:在准备软考过程中,遇到一道判断无损分解和保持依赖的试题,于是找到了这篇很通俗的文章,特收藏并学习之。微笑) 大部分是对一个关系模式分解成两个模式的考察,分解为三个以上模式时无损分解和保持依赖的...

    相关系列:
    ER图转为关系模式
    无损分解和保持依赖
    3NF分解与BCNF分解
    正则覆盖与候选码
    如何设计ER图(弱实体集)
    如何设计ER图(映射基数)


    (注:在准备软考过程中,遇到一道判断无损分解和保持依赖的试题,于是找到了这篇很通俗的文章,特收藏并学习之。微笑)

    大部分是对一个关系模式分解成两个模式的考察,分解为三个以上模式时无损分解和保持依赖的判断比较复杂,考的可能性不大,因此我们只对“一个关系模式分解成两个模式”这种类型的题的相关判断做一个总结。

    以下的论述都基于这样一个前提:

    R是具有函数依赖集F的关系模式,(R1 ,R2)是R的一个分解。
    

    首先我们给出一个看似无关却非常重要的概念:属性集的闭包。
    令α为一属性集。我们称在函数依赖集F下由α函数确定的所有属性的集合为F下α的闭包,记为α+
    下面给出一个计算α+的算法,该算法的输入是函数依赖集F和属性集α,输出存储在变量result中。

    算法一:
    result:=α;
    while(result发生变化)do
        for each 函数依赖β→γ in F do
        begin
            if β∈result then result:=result∪γ;
        end
    

    属性集闭包的计算有以下两个常用用途:

    • 判断α是否为超码,通过计算α+(α在F下的闭包),看α+是否包含了R中的所有属性。若是,则α为R的超码。
    • 通过检验是否β∈α+,来验证函数依赖是否成立。也就是说,用属性闭包计算α+,看它是否包含β。

    (请原谅我用∈符号来表示两个集合之间的包含关系,那个表示包含的符号我找不到,大家知道是什么意思就行了。)

    看一个例子吧,2005年11月系分上午37题:

    给定关系R(A1,A2,A3,A4)上的函数依赖集F={A1→A2,A3→A2,A2→A3,A2→A4},R的候选关键字为________。
    (37)A. A1  B. A1A3  C. A1A3A4  D. A1A2A3

    首先我们按照上面的算法计算A1+
    result=A1,
    由于A1→A2,A1∈result,所以result=result∪A2=A1A2
    由于A2→A3,A2∈result,所以result=result∪A3=A1A2A3
    由于A2→A4,A2∈result,所以result=result∪A3=A1A2A3A4
    由于A3→A2,A3∈result,所以result=result∪A2=A1A2A3A4

    通过计算我们看到,A1+=result={A1A2A3A4},所以A1是R的超码,理所当然是R的候选关键字。此题选A 。

    好了,有了前面的铺垫,我们进入正题。


    无损分解的判断。

    如果R1∩R2是R1或R2的超码,则R上的分解(R1,R2)是无损分解。这是一个充分条件,当所有的约束都是函数依赖时它才是必要条件(例如多值依赖就是一种非函数依赖的约束),不过这已经足够了。


    保持依赖的判断。

    如果F上的每一个函数依赖都在其分解后的某一个关系上成立,则这个分解是保持依赖的(这是一个充分条件)。
    如果上述判断失败,并不能断言分解不是保持依赖的,还要使用下面的通用方法来做进一步判断。
    该方法的表述如下:

    算法二:
    对F上的每一个α→β使用下面的过程:
    result:=α;
    while(result发生变化)do
        for each 分解后的Ri
            t=(result∩Ri)+ ∩Ri
            result=result∪t
    

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

    下面给出一个例题,2006年5月系分上午43题:

    设关系模式R<U, F>,其中U={A, B, C, D, E},F={A→BC,C→D,BC→E,E→A},
    则分解ρ={R1(ABCE),R2(CD)}满足 (43) 。
    (43)
    A.具有无损连接性、保持函数依赖
    B.不具有无损连接性、保持函数依赖
    C.具有无损连接性、不保持函数依赖
    D.不具有无损连接性、不保持函数依赖

    先做无损链接的判断。R1∩R2={C},计算C+

    Result=C
    由于C→D,C∈result,所以result=result∪D=CD
    可见C是R2的超码,该分解是一个无损分解。

    再做保持依赖的判断。
    A→BC,BC→E, E→A都在R1上成立(也就是说每一个函数依赖左右两边的属性都在R1中),C→D在R2上成立,因此给分解是保持依赖的。

    选A。


    再看一个复杂点的例题。2007年5月数工40-41题。

    给定关系模式R<U, F>,U={A, B, C, D, E},F={B→A,D→A,A→E,AC→B},
    其候选关键字为 (40),则分解ρ={R1(ABCE),R2(CD)}满足 (41) 。
    (40)
    A.ABD
    B.ABE
    C.ACD
    D.CD
    (41)
    A.具有无损连接性、保持函数依赖
    B.不具有无损连接性、保持函数依赖
    C.具有无损连接性、不保持函数依赖
    D.不具有无损连接性、不保持函数依赖

    看见了吧,和前面一题多么的相像!
    对于第一问,分别计算ABCD四个选项的闭包,
    (ABD)+= { ABDE }
    (ABE)+ = { ABE }
    (ACD)+ = { ABCDE }
    (CD)+ = { ABCDE }
    选D。

    再看第二问。
    先做无损链接的判断。R1∩R2={C},计算C+

    result=C
    因此C既不是R1也不是R2的超码,该分解不具有无损分解性。

    再做保持依赖的判断。
    B→A,A→E,AC→B在R1上成立,D→A在R1和R2上都不成立,因此需做进一步判断。
    由于B→A,A→E,AC→B都是被保持的(因为它们的元素都在R1中),因此我们要判断的是D→A是不是也被保持。

    对于D→A应用算法二:
    result=D
    对R1,result∩R1=ф(空集,找不到空集的符号,就用这个表示吧),t=ф,result=D
    再对R2,result∩R2=D,D+ =ADE ,t=D+ ∩R2=D,result=D
    一个循环后result未发生变化,因此最后result=D,并未包含A,所以D→A未被保持,该分解不是保持依赖的。

    选D。

    展开全文
  • 无损分解指的是对关系模式分解时,原关系模型下任一合法的关系值在分解之后应能通过自然联接运算恢复起来。反之,则称为有损分解。 设R是一个关系模式,F是R上的一个依赖集,R分解为关系模式的集合p={R1(U1),R2(U2)...

    概念

    无损分解指的是对关系模式分解时,原关系模型下任一合法的关系值在分解之后应能通过自然联接运算恢复起来。反之,则称为有损分解。

    设R是一个关系模式,F是R上的一个依赖集,R分解为关系模式的集合p={R1(U1),R2(U2),....,Rn(Un)}。如果对于R中满足F的每一个关系r,都有r=πR1(r)⋈πR2(r)⋈..πRn(r)则称分解相对于F是无损连接分解,否则有有损连接。

    怎么测试是否为无损连接

    1. 构造一个k行n列的表格,每列对应一个属性Aj(j=1,2,..n),每行对应一个模式Ri(Ui)=(i=1,2...k)的属性集合。如果Aj在Ui中,那么表格的第i行j列处添上记号aj,否则添上记号bij.
    2. 复查F的每一个函数依赖,并且修改表格中的元素,直到表格不能修改为止。
    • 取F中函数依赖X->Y,如果表格中总有两行在X分量上相等,在Y分量上不相等,则修改Y分量的值,使这两行在Y分量上相等,有以下两种情况:
    • 如果Y分量中有一个是aj,则另一个也变成aj
    • 如果Y分量中没有aj,就用下标较小的bij替换另一个符号。

    3.修改结束后一行全是a,则p相对于F是无损分解。

    例题

    设有关系模式R(U,F),其中U={A,B,C,D,E},F={A->C,B->C,C->D,{D,E}->C,{C,E}->A}。R(U,F)的一个模式分解\rho={R1(A,D),R2(A,B),R3(B,E),R4(C,D,E),R5(A,E)}。下面用列表格法来判断是否为无损分解。

    第一步,构造一个k行n列的表格,每列对应一个属性Aj(j=1,2,..n),每行对应一个模式Ri(Ui)=(i=1,2...k)的属性集合。如果Aj在Ui中,那么表格的第i行j列处添上记号aj,否则添上记号bij.

      A B C D E
    {A,D} a1 b12 b13 a4 b15
    {A,B} a1 a2 b23 b24 b25
    {B,E} b31 a2 b33 b34 a5
    {C,D,E} b41 b42 a3 a4 a5
    {A,E} a1 b52 b53 b54 a5

    第二步根据F中A->C,由于第一行,第二行,第五行在A列中的值为a1相同,在C列中的值不相同,所以根据 如果Y分量中没有aj,就用下标较小的bij替换另一个符号,把C列中的值都变为最小的bij,即b13,表格如下:

      A B C D E
    {A,D} a1 b12 b13 a4 b15
    {A,B} a1 a2 b13 b24 b25
    {B,E} b31 a2 b33 b34 a5
    {C,D,E} b41 b42 a3 a4 a5
    {A,E} a1 b52 b13 b54 a5

    第三步根据F中B->C,由于第二行,第三行,第五行在B列中的值为a2相同,在C列中的值不相同,所以根据 如果Y分量中没有aj,就用下标较小的bij替换另一个符号,把C列中的值都变为最小的bij,即b13,表格如下:

      A B C D E
    {A,D} a1 b12 b13 a4 b15
    {A,B} a1 a2 b13 b24 b25
    {B,E} b31 a2 b13 b34 a5
    {C,D,E} b41 b42 a3 a4 a5
    {A,E} a1 b52 b13 b54 a5

    第四步根据F中C->D,由于第一行,第二行,第三行,第五行在B列中的值为b13相等,在D列中的值不相同,所以根据 如果Y分量中有一个是aj,则另一个也变成aj,第一行中在D列的值为a4,所以第二行,第三行,第五行也要变成a4,表格如下: 

      A B C D E
    {A,D} a1 b12 b13 a4 b15
    {A,B} a1 a2 b13 a4 b25
    {B,E} b31 a2 b13 a4 a5
    {C,D,E} b41 b42 a3 a4 a5
    {A,E} a1 b52 b13 a4 a5

    第五步根据F中{D,E}->C,由于第三行,第四行,第五行在D列和E列中的值分别为a4和a5相等,在C列中的值不相同,所以根据 如果Y分量中有一个是aj,则另一个也变成aj,第四行中在C列的值为a3,所以第三行,第五行也要变成a3,表格如下:

      A B C D E
    {A,D} a1 b12 b13 a4 b15
    {A,B} a1 a2 b13 a4 b25
    {B,E} b31 a2 a3 a4 a5
    {C,D,E} b41 b42 a3 a4 a5
    {A,E} a1 b52 a3 a4 a5

     第六步根据F中{C,E}->A,由于第三行,第四行,第五行在C列和E列中的值分别为a3和a5相等,在C列中的值不相同,所以根据 如果Y分量中有一个是aj,则另一个也变成aj,第六行中在A列的值为a1,所以第三行,第四行也要变成a1,表格如下:

     

      A B C D E
    {A,D} a1 b12 b13 a4 b15
    {A,B} a1 a2 b13 a4 b25
    {B,E} a1 a2 a3 a4 a5
    {C,D,E} a1 b42 a3 a4 a5
    {A,E} a1 b52 a3 a4 a5

    到以上几步我们第三行就全部为a,所以这个模式分解是无损的。 

    展开全文
  • 如果r = mρ(r)那么就称ρ为R的无损分解无损分解的检验算法:输入:关系模式 R = A1 A2 …An ,函数依赖集合F,分解ρ = (R1,R2 …Rk) 方法:1、构造k行n列的表,如果Aj 属于Ri 就在对应的二维表格处填写aj否则...
    • 设关系模式R 的分解ρ = (R1,…,Rk ) mρ(r)=πRi(r)连接 ;如果r = mρ(r)那么就称ρ为R的无损分解。
      无损分解的检验算法:输入:关系模式 R = A1 A2 …An ,函数依赖集合F,分解ρ = (R1,R2 …Rk)
      方法:1、构造k行n列的表,如果Aj 属于Ri 就在对应的二维表格处填写aj否则填写bij ;
      2、对于任意 β->γ in F ,修改表,即如果β的属性相同的行,γ属性同样相同。
      3、修改表的过程中,若发现某一行全部为a1…an,则为无损连接。
      我们一般是将一张表分解为2个,假设R分解为R1,R2 检验:若R1∩R2 ->R1 - R2 或者R2-R1 属于F+ 则ρ关于F无损连接。

    • 设关系模式R,分解为ρ = (R1,…Rk)函数依赖为F。如果F中任何β->γ ,有β、γ属于Ri,则 有分解ρ保持依赖分解。

      知识:属性闭包:x+ 表示 {Ai| x 通过依赖F->Ai} 利用属性闭包可以判断一个依赖x->y是否属于某个依赖集合F 方法只需判断y是否属于x+。而这里同样需要判断各个子模式形成的函数依赖G是否包含了F的任何依赖。

    检验算法:对于F中的任一依赖β->γ;
    				result = β;
    				while(result 变化)
    					for i ->k do
    						result = result ∪ ((result ∩ Ri)+ ∩ Ri)
    				
    如果 γ属于 result 那么β-> γ属于G
    
    展开全文
  • 判断无损分解的例子

    2019-05-09 09:15:25
    转 判断无损分解的例子 2018年07月02日 10:18:15 黑脉金 阅读数:2099 ...
  • 一、前言 《大数据和人工智能交流》头条号向广大初学者新增C 、Java 、Python 、Scala、javascript 等目前流行的计算机、大数据编程语言,希望...二、关系模式分解无损分解示例 设关系模式R(U , F),其中R上的属...
  • 【数据库】解剖式学习无损分解

    千次阅读 热门讨论 2018-10-24 09:39:33
    无损分解是数据库中一个比较重要的知识点,这个还是比较值得总结的!其中有些东西我们还是容易模糊的,如果你想彻底搞明白无损分解,可以认真的看下面的内容! 1、为什么会有分解 因为分解能消除数据冗余和操作...
  • 如果一个R的分解D={R1,R2}有函数依赖F,判断该分解是否属于无损分解。 对于一个二元分解(只分解成两个关系),判断条件非常简单,不需要列表去做 只要满足以下之一的条件,即可判定该分解是无损分解: FD(...
  • 如何测试某关系模式的分解属于无损分解
  • 无损分解的测试

    千次阅读 热门讨论 2013-10-13 15:58:19
    如果R上成立的函数依赖集是F1={B→A,C→D},那么ρ相对于F1是否无损分解?如果R上成立的函数依赖集是F2={ A→B,C→D}呢? 第一步,构造表格: 第一行为关系模式R的每一个属性A B C D,第一列为R的分解AB BC CD,...
  • 复习要点-无损分解

    2011-07-30 16:39:08
    重点:理解无损分解、损失分解、寄生元组、悬挂元组、Chase过程、两个无损分解相关的定理 无损分解和损失分解 设R是一个关系模式,F是R上的一个FD集,R分解成数据库模式ρ={R1,...,Rk}。如果对R中满足F的每一个...
  • 关系模式无损分解的测试方法

    千次阅读 热门讨论 2014-11-03 10:40:48
    关系模式无损分解的测试方法 上周在看数据库原理的时候,对于无损分解的测试方法,看完两遍还是不明其中的真意,和同学探讨了一下,此博文说说我的理解。  先明确无损分解中的“损”指的是信息的丢失。 分解的优点 ...
  •       批评一下自己,昨天又贪玩了,啥都没干。... 这几天做了几份数据库方面的试题,其他的没什么好说的,在无损分解这里每次都不知道怎么做。主要原因是书上对这一块讲...
  • 上篇记录了范式相关的概念和...无损连接和无损分解 上例子: 关系模式R=(A,B,C,D,E),R1 = (A,D),R2 = (A,B),R3= (B,E),R4= (C,D,E),R5=(A,E) F={A→C,B→C,C→D,DE→C,CE→A}, 分解r ={R1,R2,R3,R4,R...
  • 一、前言 《大数据和人工智能交流》头条号向广大初学者新增C 、Java 、Python 、Scala、javascript 等目前流行的计算机、大数据编程语言,希望...二、关系模式分解无损分解示例 设关系模式R(U , F),其中R上的属...
  • 无损分解和保持依赖的判断

    千次阅读 2013-03-24 19:19:26
    (注:在准备软考过程中,遇到一道判断无损分解和保持依赖的试题,于是找到了这篇很通俗的文章,特收藏并学习之。) 大部分是对一个关系模式分解成两个模式的考察,分解为三个以上模式时无损分解和保持依赖的判断...
  • 步骤 1.假如给出的依赖集F存在...3.不包含的话为3NF且保持函数依赖,假如要转为3NF且无损分解且保持函数依赖,只要加上一个候选键即可(原先就有候选键的不用加,因为已经是3NF且无损分解且保持函数依赖) 4.将关系模式
  • 规范化理论:无损分解的测试算法

    千次阅读 2019-05-16 21:11:35
    什么是模式分解? 设有关系模式R(U),,,...,都是R的子集(此处把关系模式看成是属性的集合),R=UU…U,关系模式的集合用表示,={, , … ,}。用代替R过程称为关系模式的分解。这里称为R的一个分解,也称为数据库...
  • 无损分解规则 (Rule for Lossless Decomposition) There must be functional dependency relationship in between the attributes of the relation, i.e., if A, B, and C are the attributes of the relation R ...
  • 目录 1NF范式 2NF范式 3NF范式 BCNF范式 分解成BCNF范式(且是无损分解) 分解成3NF 算法一:将关系R转化3NF的保持函数依赖的分解 算法二:将关系R转化3NF的既有无损连接性又保持函数依赖的分解 根据函数依赖求最小...
  • 以下的论述都基于这样一个前提:R是具有函数依赖集F的关系模式,(R1 ,R2)是R的一个分解。首先我们给出一个看似无关却非常重要的概念:属性集的闭包。令α为一属性集。我们称在函数依赖集F下由α函数确定的所有属性...
  • 1NF----表中每一列都不能再分解了(stomic) 2NF----满足1NF,并且非主键属性不能不分依赖于主键 e.g A B C D E 其中A和B为主键,如果A能单独决定C的属性,那么就不符合2NF. BTW:如果主键只有一个,那肯定2nf 3NF...
  • https://blog.csdn.net/long_h_zhu/article/details/94358402
  • 因此C既不是R1也不是R2的超码,该分解不具有无损分解性。  再做保持依赖的判断。  B→A,A→E,AC→B在R1上成立,D→A在R1和R2上都不成立,因此需做进一步判断。  由于B→A,A→E,AC→B都是被保持的(因为...
  • 在此简单的可以理解为可以还原的为无损分解,如果不可以还原,则为有损分解。 那么,判断是否为无损分解,则判断是否能还原即可。下面以一例题讲解。 首先,行为R中的元素,列为R1-R5。 ...

空空如也

空空如也

1 2 3 4 5 ... 18
收藏数 342
精华内容 136
关键字:

无损分解