精华内容
下载资源
问答
  • 关系模式的分解
    千次阅读
    2020-11-27 14:12:26

    模式分解

    存在问题

    模式分解

    • 关系模式R(U)的分解是指用R的一组子集 ρ \rho ρ={R1(U1),…,Rk(Uk)}来代替它。其中U= U1 ⋃ \bigcup U2 ⋃ \bigcup ⋃ \bigcup Uk;Ui ⊈ \nsubseteqq Uj(i ≠ \neq =j)。
    • 注:为便于后面叙述,我们用Ri代替Ri(Ui), R代替R(U)。

    对于关系模式R的任一关系r, 它向 ρ \rho ρ的投影连接记为 m ρ m_\rho mρ(r)

    • m ρ m_\rho mρ(r) = ∏ R 1 \prod_{R1} R1(r) ⋈ \Join ⋈ \Join ∏ R k \prod_{Rk} Rk(r))= ⋈ ( i = 1 , . . . , k ) \Join_{(i=1,...,k)} (i=1,...,k) ∏ R i \prod_{Ri} Ri(

    • 这里: ∏ R i \prod_{Ri} Ri(r)={t[Ri] | t ∈ \in r, i=1,…,k }

    模式分解需要关注:

    • R与 ρ \rho ρ在数据内容方面是否等价:分解的无损连接性;
    • R与 ρ \rho ρ在数据依赖方面是否等价:分解的保持依赖性。

    [引理]:设R为一关系模式, ρ \rho ρ={R1,…,Rk}是R的一个分解,r是R的任一个关系,ri= ∏ R i \prod_{Ri} Ri(r),则有规则成立:

    • (rule 1):r ⫅ \subseteqq m ρ m_\rho mρ(r)
      • 即:所有未分解前的关系,要包含在分解后重新连接得到的关系里
    • (rule 2):若s = m ρ m_\rho mρ(r), 则 ∏ R i \prod_{Ri} Ri(s) = ri(即: ∏ R i \prod_{Ri} Ri( m ρ m_\rho mρ(r)) = ∏ R i \prod_{Ri} Ri(r))
      • 即:所有分解的关系,在连接后还能再分解会去
    • (rule 3): m ρ m_\rho mρ( m ρ m_\rho mρ(r)) = m ρ m_\rho mρ(r)
      • 即:对连接后的关系再拿去让分解后的关系连接,仍然和原关系一样

    无损连接分解

    无损连接分解

    • 对于关系模式R(U, F), U是属性全集,F是函数依赖集合, ρ \rho ρ={R1,…,Rk}是R的一个分解,如果对于R的任何满足函数依赖集F的关系r, 有r= m ρ m_\rho mρ(r),则称 ρ \rho ρ是R相对于F的一个无损连接分解,其中: m ρ m_\rho mρ(r) = ∏ R 1 \prod_{R1} R1(r) ⋈ \Join ⋈ \Join ∏ R k \prod_{Rk} Rk(r) = ⋈ ( i = 1 , . . . , k ) \Join_{(i=1,...,k)} (i=1,...,k) ∏ R i \prod_{Ri} Ri(r)

    无损连接性检验算法

    • Input:关系模式R=A1A2…An, 函数依赖集F, 分解 ρ \rho ρ={R1,…,Rk}

    • Output: ρ \rho ρ是否是无损连接的判断

    • Method:

      • (1) 构造一k行n列的表,可称为 R ρ R_{\rho} Rρ表。其中第j列对应于Aj, 第i行对应于Ri, 若Aj ∈ \in Ri, 则 R ρ R_{\rho} Rρ表中第i行第j列位置填写符号aj, 否则填写bij。
      • (2) 根据 ∀ \forall (X → \rightarrow Y) ∈ \in F, 对 R ρ R_{\rho} Rρ表进行修改:
        • 给定X → \rightarrow Y,在表中寻找对应于X中所有属性分量之列上符号全相同的行。
        • 若能找到,则在这些行的对应于Y中属性的那些列上置相同符号:
          • 若其中有一个行的相应列上为aj,则使其它行同一列上置aj;
          • 若相应列上均为bij(或blj),则使其它行同一列上置某一个bij(或blj,任一个都可,只要相同);
      • (3) 在上述修改的表中,如果发现有一行变成a1, a2,…, an(全a), 则 ρ \rho ρ是无损连接分解,否则 ρ \rho ρ是有损连接分解。
    • 示例:已知 R={ ABCDE }、F = { A → \rightarrow C, B → \rightarrow C, C → \rightarrow D, DE → \rightarrow C, CE → \rightarrow A }、 ρ \rho ρ={R1(AD), R2(AB), R3(BE), R4(CDE), R5(AE)},问: ρ \rho ρ是否具有无损连接性?

      在这里插入图片描述

    [定理] 设F是关系模式R上的一个函数依赖集合。 ρ \rho ρ={R1,R2}是R的一个分解,则:当且仅当R1 ⋂ \bigcap R2 → \rightarrow R1 − - R2 或者 R1 ⋂ \bigcap R2 → \rightarrow R2 − - R1属于F+时, ρ \rho ρ是关于F无损连接的。

    • 证明:由前述算法证明

    在这里插入图片描述

    保持依赖分解

    保持依赖分解

    • 对于关系模式R(U, F), U是属性全集,F是函数依赖集合, ρ \rho ρ={R1,…,Rk}是R的一个分解,如在 ∏ R i \prod_{Ri} Ri(F)中的所有依赖之并集(i=1,…,k)逻辑蕴涵F的每个依赖,则称分解 ρ \rho ρ保持依赖集F。其中 ∏ R i \prod_{Ri} Ri(F)是F在Ri上的投影,即F中的任一投影X → \rightarrow Y,如果X, Y均包含于Ri,则X → \rightarrow Y ∈ \in ∏ R i \prod_{Ri} Ri(F)。Ri指Ri的属性集。
    • 注:
      • (1) 保持依赖的分解可能不是无损连接的。
      • (2) 无损连接的分解可能不是保持依赖的。
      • 示例:
        • R(CSZ), F={ CS → \rightarrow Z, Z → \rightarrow C }, C是城市,S是街区, Z是邮政编码, ρ \rho ρ={R1(SZ), R2(CZ)}为一无损连接分解,但却不保持依赖;
        • R(ABCD), F={A → \rightarrow B, C → \rightarrow D}, ρ \rho ρ={R1(AB), R2(CD)}为一保持依赖分解,但不是无损连接分解。

    保持依赖性检验算法

    • Input:关系模式R=A1A2…An, R上的函数依赖集F, 分解 ρ \rho ρ={R1,…,Rk}

    • Output: ρ \rho ρ是否是保持依赖的判断

    • Method:令G = ⋃ ( i = 1 t o k ) \bigcup_{(i=1 to k)} (i=1tok) ∏ R i \prod_{Ri} Ri, 只需检查G是否覆盖F即可。具体算法如下:

      • 首先对每个X → \rightarrow Y ∈ \in F计算G中的 X G + X^+_G XG+:(如果X不包含于Ri则不需计算了)

        Z = X

        WHILE Z的变化发生 DO

        FOR i =1 to k DO

        Z = Z ⋃ \bigcup ( ( Z ⋂ R i ) + {(Z \bigcap Ri)}^+ (ZRi)+ ⋂ \bigcap Ri)

      • 判断G是否逻辑蕴涵X → \rightarrow Y:前面计算的结果Z便是X+, 如果Z包含Y, 则G逻辑蕴涵X → \rightarrow Y,否则便不逻辑蕴涵。

      • 判断 ρ \rho ρ是否保持依赖:如果G逻辑蕴涵F中的每一个函数依赖,则说 ρ \rho ρ是保持依赖的分解,否则便不是保持依赖的分解。

    示例

    • Input:R(A, B, C, D, E)、F = { A → \rightarrow C, B → \rightarrow C, C → \rightarrow D, DE → \rightarrow C, CE → \rightarrow A } 、 ρ \rho ρ={R1(AC), R2(BC), R3(CDE) }
    • Output: ρ \rho ρ 是否是保持依赖的判断
    • Method:依据题意 ∏ R 1 \prod_{R1} R1(F)={ A → \rightarrow C }, ∏ R 2 \prod_{R2} R2(F)={ B → \rightarrow C } , ∏ R 3 \prod_{R3} R3(F)={ C → \rightarrow D , DE → \rightarrow C },G = { A → \rightarrow C , B → \rightarrow C , C → \rightarrow D , DE → \rightarrow C } ,显然不保持依赖。
      • 对函数依赖A → \rightarrow C ∈ \in F计算G中的 X G + X^+_G XG+:Z = {A } ⋃ \bigcup { C } ⋃ \bigcup { } ⋃ \bigcup { }={A,C}, C包含于Z中,所以A → \rightarrow C被G逻辑蕴涵
      • 对函数依赖DE → \rightarrow C ∈ \in F计算G中的 X G + X^+_G XG+:Z = {D,E} ⋃ \bigcup { } ⋃ \bigcup { } ⋃ \bigcup { C, D }={C,D, E}, C包含于Z中,所以A → \rightarrow C被G逻辑蕴涵
      • 对函数依赖CE → \rightarrow A ∈ \in F计算G中的 X G + X^+_G XG+:Z = {C, E } ⋃ \bigcup { } ⋃ \bigcup { } ⋃ \bigcup {D } = {C, E, D}, A不包含于Z中,所以不被G逻辑蕴涵

    分解成3NF或BCNF

    无损连接分解成BCNF的算法

    • Input:关系模式R(U, F)
    • Output:R的一个无损连接分解 ρ \rho ρ ρ \rho ρ中的每个关系模式都是F在该模式上投影的BCNF。
    • Method:
      • (1) 令 ρ \rho ρ={ R }。
      • (2) 对每个模式s ∈ \in ρ \rho ρ, 若s ∉ \notin /BCNF, 则s上必有X → \rightarrow A成立且X不是s的超键且A ∉ \notin /X,此时用模式s1, s2替代 ρ \rho ρ中的模式s,其中s1由A和X构成,s2由s中除A以外的所有属性构成(可以发现,s1 ∈ \in BCNF)。
      • (3) 重复步骤(2), 直至 ρ \rho ρ中全部关系模式达到BCNF。
      • 注:本算法不能保证一关系模式分解成BCNF而又保持依赖。
    • 证明:无损分解最后给出的定理。
    • 示例:R(A, B, C, D, E, F, G)函数依赖集合{ A → \rightarrow B, A → \rightarrow C, C → \rightarrow D, C → \rightarrow E, E → \rightarrow FG }
      • 候选键:A; 有不依赖于候选键的其他函数依赖,R不满足BCNF。
      • 分解规则:
        • 将左侧不含候选键的函数依赖单独组成一个关系, 将包含候选键的组成一关系 ρ \rho ρ={ R1(A, B, C), R2(CDEFG) }
        • 分解 R2 ,候选键为 C,把不含 C 的关系作为 R3 : R2(CDE)、R3(EFG)
      • 可以看出:R1 ∈ \in BCNF; R2 ∈ \in BCNF; R3 ∈ \in BCNF;

    保持依赖分解成3NF的算法。

    • Input:关系模式R(U, F), F是函数依赖集最小覆盖。

    • Output:R的一个保持依赖分解 ρ \rho ρ ρ \rho ρ中的每个关系模式都是F在该模式上投影的3NF。

    • Method:

      • (1) 把R中不出现在F中的属性去掉并单独组成一模式。
      • (2) 对 ∀ \forall X → \rightarrow A ∈ \in F, 则以XA组成一模式; 若有X → \rightarrow A1, X → \rightarrow A2,…, X → \rightarrow Am都属于F, 则以XA1A2…Am组成一模式(即将n个模式合并为一个模式)。
      • (3)取 ρ \rho ρ为上述模式之集合,则 ρ \rho ρ即为所求之分解。
    • 示例:R(A, B, C, D, E, F, G)函数依赖集合{ A → \rightarrow B, A → \rightarrow C, C → \rightarrow D, C → \rightarrow E, E → \rightarrow FG }

      • 候选键:A; 有传递依赖,R不满足3NF。
      • 分解规则:将每一个函数依赖单独组成一个关系 ρ \rho ρ={ R1(A, B), R2(A, C), R3(C, D) , R4(C, E) , R5(E, F, G) }
      • 可以看出:每一个模式都属于3NF, 且 ρ \rho ρ是保持依赖的
      • 也可以合并一些关系: ρ \rho ρ={ R12(A, B, C), R34(C, D, E) , R5(E, F, G) }

    既保持依赖又无损连接

    • σ \sigma σ是按前述算法构造的R的一个第三范式分解,X是R的候选键,则: τ \tau τ= σ \sigma σ ⋃ \bigcup { X }将是R的一个分解,且该分解中的所有关系模式是第三范式的, τ \tau τ有保持依赖和无损连接性。
    • 即按照保持依赖方法分解后,把候选键相同的合并即可
    • 示例:R(A, B, C, D, E, F, G),函数依赖:A → \rightarrow B, A → \rightarrow C, C → \rightarrow D, C → \rightarrow E, E → \rightarrow FG
      • 保持依赖的分解成3NF然后合并: ρ \rho ρ={ R12(A, B, C), R34(C, D, E) , R5(E, F, G) }
    更多相关内容
  • 关系模式算法关系模式分解无损连接分解保持函数依赖的分解总结案例 关系模式分解 将一个关系模式 R分解为若干个关系模式 R1,R2,…,Rn(其中 U=U1∪U2∪…∪Un,且不存在 Ui⊈Uj,Ri为 F 在 Ui上的投影),...
  • 关系模式分解

    千次阅读 2020-01-02 12:14:10
    模式分解 模式S-C-M (S 学号,C 班级,M 班主任) 该模式设计不好,存在数据冗余、插入异常、删除异常和更新异常 p1 = {S-C(学号,班级),C-M(班级,班主任)} p2 = {S-C(学号,班级),C-M(学号,班主任)} p3 = {S-...

    模式分解


    模式S-C-M (S 学号,C 班级,M 班主任)

    该模式设计不好,存在数据冗余、插入异常、删除异常和更新异常

    p1 = {S-C(学号,班级),C-M(班级,班主任)}
    p2 = {S-C(学号,班级),C-M(学号,班主任)}
    p3 = {S-C(学号,班主任),C-M(班级,班主任)}



    规范化理论:

    1. 检测是否在一个表中聚集了过多的属性的过程
    2. 模式分解来消除违反范式规则而带来的影响(插入、更新、删除异常,冗余大),构造合适的(更好的)数据模式
    3. 概念建模过程中规范化用于检验却总是很有帮助


    数据依赖

    1. 一个关系内部属性与属性之间的一种约束关系(属性值时候相同)
    2. 现实世界属性间相互联系的抽象
    3. 数据内在性质
    4. 语义的体现

    函数依赖FD

    SnoSnameSsexSage
    a valueb1 valuec valued value
    a2 valueb2 valuec2 valued2 value
    an valuebn valuecn valuedn value

    定义: 设 R(U) 是一个属性集 U 上的关系模式, X 和 Y 是 U 的子集。若对于 R(U) 的任意一个可能的关系 r , r 中不可能存在两个元组在 X 上的属性值相等, 而在 Y 上的属性值不等, 则称“ X 函数确定 Y ”或“ Y 函数依赖于 X ”,记作 X → Y
    若 Y 不函数依赖于 X ,则记作 X ↛ Y

    For example:
    Sno → Ssex, Sno → Sage
    假设不允许重名 Sno ←→ Sname


    1. 非平凡函数依赖

      X → Y ,但 Y ⊈ X 则称 X → Y 为非平凡函数依赖
      Y ⊈ X 换为 Y ⊆ X ,则 X → Y 为平凡函数依赖 (对于任一关系模式,必然成立)

    2. 完全函数依赖

      如果 X → Y ,并且对于 X 的任何一个真子集 X’ , 都有 X’ ↛ Y , 则称 Y 对 X 完全函数依赖,

    3. 部分函数依赖
    4. 传递函数依赖

    在这里插入图片描述
    在这里插入图片描述

    多值依赖MVD


    关系模式

    五元组 : R ( U , D , D O M , F ) R(U, D, DOM, F) R(U,D,DOM,F)

    • R:符号化的元组语义
    • U:一组属性
    • F:属性组U中属性所来自的域
    • DOM:属性到域的映射
    • F:属性组U上的一组数据依赖

    把关系模式看作一个三元组: R < U , F > R<U,F> R<U,F>

    U ={Sno, Sdept, Mname, Cno, Grade}// 数据冗余、更新异常、插入异常、删除异常
    // 分解
    S(Sno,Sdept,Sno → Sdept);
    SC(Sno,Cno,Grade,(Sno,Cno) → Grade);
    DEPT(Sdept,Mname,Sdept → Mname)
    

    范式

    范式: 是符合某种基本的关系模式的集合
    在这里插入图片描述
    在这里插入图片描述

    • 1NF:每个分量必须是不可分开的数据项
    • 2NF:符合1NF,每一个非主属性都完全函数依赖于任何一个候选码
    • 3NF:符合2NF,消除非主属性对于码传递函数依赖
    • BCNF:符合3NF,消除主属性对于码的部分与传递函数依赖

    4NF:设R是一个关系模型,D是R上的多值依赖集合。如果D中存在凡多值依赖 X->Y时,X必是R的超码,那么称R是第四范式的模式

    满足BCNF:

    • 实现了模式的彻底分解
    • 最高的规范化程度
    • 消除了插入异常和删除异常。

    规范化: 低级范式的关系模式通过模式分解,可以转换为若干个高一级范式的关系模式集合的过程。

    3NF 和 BCNF的区别
    BCNF:如果关系模式R(U,F)的所有属性(包括主属性和非主属性)都不传递依赖于R的任何候选关键字,那么称关系R是属于BCNF的。或是关系模式R,如果每个决定因素都包含关键字(而不是被关键字所包含),则BCNF的关系模式。
    例:配件管理关系模式 WPE(WNO,PNO,ENO,QNT)分别表仓库号,配件号,职工号,数量。有以下条件
    a.一个仓库有多个职工。
    b.一个职工仅在一个仓库工作。
    c.每个仓库里一种型号的配件由专人负责,但一个人可以管理几种配件。
    d.同一种型号的配件可以分放在几个仓库中。

    分析:由以上得 PNO 不能确定QNT,由组合属性(WNO,PNO)来决定,存在函数依赖(WNO,PNO) -> ENO。由于每个仓库里的一种配件由专人负责,而一个人可以管理几种配件,所以有组合属性(WNO,PNO)才能确定负责人,有(WNO,PNO)-> ENO。因为 一个职工仅在一个仓库工作,有ENO -> WNO。由于每个仓库里的一种配件由专人负责,而一个职工仅在一个仓库工作,有 (ENO,PNO)-> QNT。
    找一下候选关键字,因为(WNO,PNO) -> QNT,(WNO,PNO)-> ENO ,因此 (WNO,PNO)可以决定整个元组,是一个候选关键字。根据ENO->WNO,(ENO,PNO)->QNT,故(ENO,PNO)也能决定整个元组,为另一个候选关键字。属性ENO,WNO,PNO 均为主属性,只有一个非主属性QNT。它对任何一个候选关键字都是完全函数依赖的,并且是直接依赖,所以该关系模式是3NF。

    分析一下主属性。因为ENO->WNO,主属性ENO是WNO的决定因素,但是它本身不是关键字,只是组合关键字的一部分。这就造成主属性WNO对另外一个候选关键字(ENO,PNO)的部 分依赖,因为(ENO,PNO)-> ENO但反过来不成立,而P->WNO,故(ENO,PNO)-> WNO 也是传递依赖。
    虽然没有非主属性对候选关键辽的传递依赖,但存在主属性对候选关键字的传递依赖,同样也会带来麻烦。如一个新职工分配到仓库工作,但暂时处于实习阶段,没有独立负责对某些配件的管理任务。由于缺少关键字的一部分PNO而无法插入到该关系中去。又如某个人改成不管配件了去负责安全,则在删除配件的同时该职工也会被删除。

    解决办法:分成管理EP(ENO,PNO,QNT),关键字是(ENO,PNO)工作EW(ENO,WNO)其关键字是ENO。
    缺点: 分解后函数依赖的保持性较差。如此例中,由于分解,函数依赖(WNO,PNO)-> ENO 丢失了, 因而对原来的语义有所破坏。没有体现出每个仓库里一种部件由专人负责。有可能出现 一部件由两个人或两个以上的人来同时管理。因此,分解之后的关系模式降低了部分完整性约束。


    模式分解实例

    在这里插入图片描述
    在这里插入图片描述

    函数依赖理论

    • 函数依赖集的闭包
      • 用于发现所有蕴含的函数依赖
    • 属性集的闭包
      • 用于判断某属性集能够函数确定的其他因素
    • 最小函数依赖集
      • 用于寻找等价( 闭包相同) 的最小集,便于降低检测开销
    • 无损分解
      • 能够通过自然连接恢复原关系的分解策略
    • 保持依赖
      • 分解后的各子关系函数依赖集并集的闭包与分解前某关系函数依赖集的闭包相同
        在这里插入图片描述

    相关计算

    实例:求解函数依赖集的闭包
    在这里插入图片描述

    算法:求属性集X 关于函数依赖集F 的闭包
    在这里插入图片描述
    实例:

    在这里插入图片描述

    展开全文
  • 讨论了GIS属性数据库设计中关系模式的构造...同时,为使分解过程中不出现信息丢失并维护地学数据的完整性约束,还讨论了关系模式分解应满足的信息无损失连接性的约束条件,以及关系模式分解所应保持的函数依赖的约束因素
  • 数据库系统原理
  • 现有如下关系模式: 其中: Teacher(Tno,Tname,Tel,Department,Bid,Bno, Bname,BorrowDate,Rdate)。 Tno一教师编号, Tname一教师姓名, Tel一电话, Department一所在部门, Bid一图书编码, Bno–图书索书...

    以下通过例题结合算法做详解

    现有如下关系模式:
    其中: Teacher(Tno,Tname,Tel,Department,Bid,Bno, Bname,BorrowDate,Rdate)。
    Tno一教师编号, Tname一教师姓名, Tel一电话, Department一所在部门,
    Bid一图书编码, Bno–图书索书码 Bname一书名, BorrowDate一借书日期, Rdate一还书日期
    该关系模式的属性之间具有通常的语义,例如:
    教师编号是惟一的,可确定教师姓名及教师的相关信息,
    图书索书码可确定书名。图书馆同一索书码的图书可能购买多本,每一本都有唯一的图书编码,当然图书编码也可以决定书名;
    教师每次借阅某本图书都有一个具体的借书日期和还书日期,教师还可多次借阅同一本图书,但借书日期不同。

    1.根据给出的语义,分析该关系模式的函数依赖,
    2. 将该函数依赖集合最小化
    3. 运用闭包算法找出所有的候选码。
    4. 该关系模式最高满足第几范式?并说明理由。
    5. 模式分解要求达到3NF。
    6. 验证分解的无损
    7. 验证分解的保函


    1.根据给出的语义,分析该关系模式的函数依赖

    F={Tno->Tname,  Tno->Tel,  Tno->Department,  Bno->Bname,  Bid->Bname,  Bid->Bno,  (Tno,Bid,BorrowDate)->Rdate}

    这边需要注意的是最后一个函数依赖,一不小心就会想当然的错写成:
    (Tno,Bid)->BorrowDate,Rdate
    由于教师可以多次借阅同一本书,因此(Tno,Bid)不能唯一确定BorrowDate和Rdate。但只要人、书、借书日期确定了,就可以知道此书的还书日期了。

    2. 将该函数依赖集合最小化
    这题可以明显看出函数依赖的传递性,因此去除冗余的函数依赖:Bid->Bname
    最严谨的步骤是利用分解规则,假设冗余求闭包的方法来最小化函数依赖集合。这题比较简单不是重点讲述的题目,因此不做赘述。

    最小化结果如下:
    F={Tno->Tname, Tno->Tel, Tno->Department, Bno->Bname, Bid->Bno, (Tno,Bid,BorrowDate)->Rdate}

    3. 运用闭包算法找出所有的候选码。
    (Tno,Bid,BorrowDate)F+
    X(0)=Tno,Bid,BorrowDate
    X(1)=Tno,Bid,BorrowDate,Tname,Tel,Department,Bno,Bname,Rdata
    ∵X(1)=U
    ∴候选码:(Tno,Bid,BorrowDate)

    4. 该关系模式最高满足第几范式?并说明理由。
    最高满足1NF,因为该关系模式中存在非主属性对码的部分函数依赖。
    如:Tno->Tname等

    该题也存在非主属性对码的传递函数依赖,只不过存在非主属性对码的部分函数依赖已经不满足2NF的要求了,更谈不上判断3NF

    5. 模式分解要求达到3NF。
    这里给一个分解算法:
    转换为3NF既有无损连接又保持函数依赖的分解 算法如下:

    1. 对函数依赖集进行极小化处理。
    2. 找出不在F中出现的属性,将这样的属性构成一个关系模式。(此情况较少见)
    3. 对F按具有相同左部的原则分组,每一组函数依赖所有涉及的全部属性形成一个属性集,分解成一个关系模式。
    4. 对于R的码,形成一个关系模式。
    5. 根据步骤3、4分解的关系模式,消除多余的关系模式

    根据算法:
    1.求最小函数依赖集:
    F={Tno->Tname, Tno->Tel, Tno->Department, Bno->Bname, Bid->Bno, (Tno,Bid,BorrowDate)->Rdate}

    2.由于R中的所有属性均在F中都出现,所以转下一步。

    3_1.对F按具有相同左部的原则分组:
    F={Tno->(Tname,Tel,Department), Bid->Bno, Bno->Bname, (Tno,Bid,BorrowDate)->Rdate}
    3_2.每一组函数依赖所有涉及的全部属性形成一个属性集,分解成一个关系模式:
    R1=(Tno,Tname,Tel,Department)
    R2=(Bid,Bno)
    R3=(Bno,Bname)
    R4=(Tno,Bid,BorrowDate,Rdate)

    4.对于R的码形成一个关系模式:
    R5=(Tno,Bid,BorrowDate)

    5.消除多余的关系模式:
    由于R5包含于R4中,因此R5冗余,删除R5

    所以最终答案为:
    R1=(Tno,Tname,Tel,Department)
    R2=(Bid,Bno)
    R3=(Bno,Bname)
    R4=(Tno,Bid,BorrowDate,Rdate)

    注:这边模式分解时,需把关系模式R(Bid,Bno)写在关系模式R(Bno,Bname)前面,否则在下一问验证分解无损的算法中,会出错。两个关系模式中隐含传递性,按照传递的顺序写关系模式,在下一题的修改表时才能修改完整。

    6.验证分解的无损
    先看算法:
    在这里插入图片描述
    算法比较抽象,我们用实例结合表格做步步分解:
    ρ={R1<U1,F1>,R2<U2,F2>,R3<U3,F3>,R4<U4,F4>}是R<U,F>的一个分解,U={A1,…,An},F={FD1,FD2,FD3,FD4},设F是一极小依赖集,记FDi为Xi->Ali。

    (1)建立n列k行的表,若属性Aj属于Ui,则在列i行交叉处填上aji,否则填上bij:
    在这里插入图片描述
    (2)对每一个FDi做下列操作:找到Xi所对应的列中具有相同符号的那些行,考察这些行中li列的元素。若其中有ali,则全部改为ali;否则全部改为bmli。其中m是这些行的行号最小值。


    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述
    最后一步,对每一行进行扫描:
    在这里插入图片描述
    补充理解,其他博客看到的,大概是这个道理:
    在这里插入图片描述

    7. 验证分解的保函
    这个判断方法其实很简单,对于这道题来说,有
    属性集U={Tno,Tname,Tel,Department,Bid,Bno,Bname,BorrowDate,Rdate},
    F={Tno->Tname,  Tno->Tel,  Tno->Department,  Bno->Bname,  Bid->Bname,  Bid->Bno,  (Tno,Bid,BorrowDate)->Rdate}
    有这样的分解:
    R1=(Tno,Tname,Tel,Department) ,F1={Tno->Tname,  Tno->Tel,  Tno->Department}
    R2=(Bid,Bno),F2={Bid->Bno}
    R3=(Bno,Bname),F3={Bno->Bname}
    R4=(Tno,Bid,BorrowDate,Rdate),F4={(Tno,Bid,BorrowDate)->Rdate}

    我们可以直接推出函数依赖有:Tno->Tname,Tno->Tel,Tno->Department,Bid->Bname,Bno->Bname,(Tno,Bid,BorrowDate)->Rdate
    通过R2、R3中函数依赖的传递性推出:Bid->Bname

    即:F’ = {Tno->Tname,  Tno->Tel,  Tno->Department,  Bno->Bname,  Bid->Bname,  Bid->Bno,  (Tno,Bid,BorrowDate)->Rdate} = F

    所以该分解不丢失函数依赖,分解保持函数依赖的特性。



    以上,若存在缺陷或错误,亟盼读者不吝指正

    展开全文
  • 函数依赖和关系模式分解

    千次阅读 2020-06-23 10:11:40
    文章目录一,第一范式关系数据库设计中易犯的错误数据冗余插入、删除、修改异常模式分解函数依赖(FD)函数依赖的使用函数依赖集的闭包Armstrong 公理计算 F^+^属性集的闭包属性闭包的用途正则覆盖无关属性检测属性...

    一,第一范式

    如果某个域中元素被认为是不可分的,则这个域称为是原子的

    • 非原子域的例子:
      ---- 复合属性:名字集合
      ---- 多值属性:电话号码
      ---- 复合数据类型:面向对象的

    如果关系模式R中的所有属性的域是原子的,则R称为属于第一范式(1NF)

    非原子值存储复杂并易导致数据冗余

    • 我们假定所有关系都属于第一范式

    如何处理非原子值

    • 对于组合属性:让每个子属性本身称为一个属性
    • 对于多值属性:为多值集合中的每个项创建一条元组

    原子性实际上是由域元素在数据库中被使用决定的

    • 例,字符串通常是被认为是不可分割的
    • 假设学生被分配这样的标识号:CS0012或EE1127,如果前两个数字表示系所,后四位表示学生在该系所内的唯一号码,则这样的标识号不是原子的
    • 当采用这种标识号时,是可取的。因为这需要额外的编程,而且信息是在应用程序中,而不是在数据库中编码。

    二,关系数据库设计中易犯的错误

    关系数据库设计要求我们找到一个“好的”关系模式集合。一个坏的设计可能导致:

    • 数据冗余
    • 插入、删除、修改异常

    假设我们用以下模式代替instructor模式department模式

    inst_dept(ID, name, salary, dept_name, building, budget)
    

    2.1 数据冗余

    每个系的dept_namebuildingbudget数据都要重复一次
    缺点:浪费空间,可能会导致不一致问题
    在这里插入图片描述

    2.2 插入、删除、修改异常

    更新异常

    • 更新复杂,容易导致不问题。
    • 例修改dept_name,很多相关元组都需要修改。

    插入/删除异常

    • 使用空值null:存储一个不知道所在系所的教师信息,可以使用空值表示dept_namebuildingbudget数据,但是空值难以处理。

    三,模式分解(I)

    例,可以将关系模式(A,B,C,D)分解为:(A,B)和(B,C,D),或(A,C,D)和(A,B,D),或(A,B),(B,C)和(C,D)等等…

    例,将关系模式inst_dept分解为:

    • instructor(ID, name, dept_name, salary)
    • department(dept_name, building, budget)

    原模式(R)的所有属性都必须出现在分解后的(R1,R2)中:R = R1 ∪ R2

    无损连接分解

    • 对关系模式R上的所有可能的关系r
      在这里插入图片描述

    在这里插入图片描述
    目标:设计一个理论

    • 以判断关系模式R是否为“好的”形式(不冗余
    • 当R不是“好的”形式时,将它分解为模式集合{ R1,R2,…,Rn }使得:
      ---- 每个关系模式都是“好的”形式
      ---- 分解是无损链接分解
    • 我们的理论基于:
      ---- 函数依赖(function dependencies)
      ---- 多值依赖(multivalue dependencies)

    四,函数依赖(FD)

    4.1 什么是函数依赖

    设R是一个关系模式,且有属性集 α包含于R,β包含于R
    函数依赖
    在R上成立当且仅当对任意合法关系r(R),若r的任意两条元组t1和t2在属性集α上的值相同,则它们的属性集β上的值也相同。

    • 即:t1[α] = t2[α] → t2[β] = t2[β]
    • 称:β函数依赖于α,α函数决定β
    • 如下图,图中的α和β满足函数依赖关系
      在这里插入图片描述

    函数依赖:一种完整性约束,表示特定的属性值之间的关系,可以用来判断模式规范化和建议还进
    在这里插入图片描述

    • 函数依赖是码概念的推广
    • K是关系模式R的超码,当且仅当 K → R
    • K是R的候选码当且仅当
      ---- K → R,并且
      ---- 没有 α 包含于 K,使 α → R(不存在K的真子集α,使之满足 α → R)

    函数依赖使我们可以表达用超码无法表达的约束,考虑模式

    inst_dept(ID, name, salary, dept_name, building, budget)
    
    • 我们希望下列函数依赖成立:
      ---- dept_name → building
      ---- ID → building(码是一个比较特殊的FD,可以函数决定所有的属性)
    • 而不希望下列函数依赖成立:
      ---- dept_name → salary

    4.2 函数依赖的使用

    在这里插入图片描述若果在关系模式R上所有合法关系都满足F,则称F在R上成立。

    • 其中 R = { r1®,r2®,… }

    注:容易判断一个r是否满足给定的F。不易判断F是否在R上成立。不能仅由某个r推断出F。R上的函数依赖F,通常由定义R的语义决定。

    被所有的关系实例所满足的函数依赖称为平凡的

    • 例,A → A,AB → A,(ID,name)→ ID,ID → ID
    • 一般的,若β包含于α,则α → β是平凡的。即,
      平凡的函数依赖:若β包含于α,α → β。
      非平凡的函数依赖:若β不包含于α,α → β。

    4.3 函数依赖集的闭包

    在这里插入图片描述

    Armstrong 公理

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    计算 F+

    下列过程计算函数依赖集F的闭包:

    F+ = F
    repeat
    	for each F+中的函数依赖f
    			 对应f应用'自反率''增补率',将结果函数依赖加入F+
    	for each F+中的一对函数依赖f1和f2
    			 if f1和f2可以使用'传递性'结合起来,则将结果函数依赖加入F+
    until F+不再变化
    

    由于包含n个元素的集合含有2n子集,因此共有 2n * 2n个可能的函数依赖。
    后边会介绍完成此任务的另一过程。

    五,属性集的闭包

    如何判断集合α是否为超码

    • 一种方法是:计算F+,在F+中找出所有的α → β,检查{ β1β2β3 … } = R;
      但这么做开销很大,因为F+可能很大。
    • 另一种方法是:计算α的闭包。

    5.1 什么是属性集的闭包

    定义:给定一个属性集α,在函数依赖集F下由α函数确定的所有属性的集为F下α的闭包(记作α+

    • 检查函数依赖α → β是否属于F+ ↔ β包含于α+
    • 判断α是否为超码:α → β属于F+ ↔ R包含于α+

    计算α+的算法

    result := a;
    while(result有变化) do
    	for each β → γ in F do
    		begin
    			if β包含于result
    			then result := result ∪ γ
    		end
    	a+ := result
    

    避免了找F+(反复使用公理)的麻烦。
    示例讲解
    在这里插入图片描述
    最终,AG可以表示R中的所有属性,则说AG是R的一个key。
    在这里插入图片描述
    在这里插入图片描述

    5.2属性闭包的用途

    在这里插入图片描述

    六,正则覆盖

    数据库管理系统(DBMS)总是检查确保数据库更新不会破坏任何函数依赖。但如果F很大,其开销就会很大。因此我们需要简化函数依赖集

    直观地说,F的正则覆盖(记作Fc)是指与F等价的“极小的”函数依赖集合

    • Fc中任何函数依赖都不包含无关属性
    • Fc中函数依赖的左半部都是唯一的
    • 例,α1 → β1,α1 → β2,可以写为α1 → β1β2

    在这里插入图片描述
    在这里插入图片描述

    无关属性

    定义:考虑函数依赖集合F及其中的函数一来α → β

    • 如果A∈α并且F逻辑蕴含F’ =(F - { α → β })∪ {(α → A )→ β},则称A在α中是无关的
      ---- 例,给定F = { A → C,AB → C },其中B在AB → C中是无关的,因为A → C逻辑蕴含了AB → C。
    • 如果A∈β并且F’ =(F - { α → β })∪ { α →(α → A )}逻辑蕴含F,则称A在β中是无关的
      ---- 例,给定F = { A → C,AB → CD },其中C在AB → CD中是无关的,因为即使删除C也能推出A → C。

    检测属性是否无关

    在这里插入图片描述
    计算F的正则覆盖

    repeat
     	对F中的依赖利用'合并'规则
     	α1 → β1 和 α1 → β2 替换成 α1 → β1β2
     	找出含有无关属性的函数依赖 α → β(在α或β中)
     	如果找到无关属性,从α → β中删除
    until F不再变化
    

    注:删除某些无关属性之后,可能导致合并规则可以使用,则必须重新应用。
    在这里插入图片描述

    七,模式分解(II)

    规范化的目标

    • 以判断关系模式R是否为“好的”形式(不冗余,误插入,删除,更新异常
    • 当R不是“好的”形式时,将他分解成模式集合{ R1,R2,…,Rn }使得:
      – 每个关系模式都是“好的”形式
      – 分解是无损连接分解
      – 分解是保持依赖的

    分解应有的特性

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    八,总结

    • 描述了原子域和第一范式假设;
    • 给出了数据库设计中易犯的错误,这些错误包括信息重复和插入、删除、修改异常;
    • 介绍了函数依赖的概念,展示了如何用函数依赖进行推导;
    • 理解F+,α+,FC
    • 介绍了如何分解模式,一个有效的分解都必须是无损的;
    • 如何分解是保持依赖的,则给定一个数据库更新,所有的函数依赖都可以由单独的关系进行验证,无须计算分解后的关系链接。
    展开全文
  • 函数依赖与关系模式分解的一些技巧整理

    万次阅读 多人点赞 2018-01-21 19:58:27
    函数依赖与关系模式分解的一些技巧整理 关系数据库设计理论的核心是数据间的函数依赖,衡量的标准是关系规范化的程度及分解的无损连接性和保持函 数依赖性。 数据依赖是通过一个关系中属性间值的相同与否体现...
  • 关系模式分解为3nf 和bcnf详解

    千次阅读 2022-03-03 09:14:21
    分解为3nf要先求最小函数依赖集,然后找到函数依赖中没有涉及的属性,单独分分解,之后从r中去掉,之后就是对函数依赖集中函数依赖左边相同属性进行合并,若果合并结果有包含关系,去掉小的,这是保持函数依赖的分解,...
  • 数据库系统原理-函数依赖和关系模式分解 目录数据库系统原理-函数依赖和关系模式分解第一范式如何处理非原子值原子性关系数据库设计中易犯的错误模式分解无损连接分解优化关系模式的步骤函数依赖函数依赖定义函数...
  • 数据库中关于关系模式的知识,涉及到模块分解以及相关定义性质,还有算法练习,内涵公理系统的有效性已经相应的推理规则,适合初学者以及数据库爱好者学习,有效掌握数据库关系模式这一块的知识
  • 关系模式分解与范式

    千次阅读 2019-04-20 17:41:41
    为什么要研究数据库关系模式分解? 答:因为现有的模式可能会存在一些数据增删改的弊端,比如说:数据冗余太大,更新异常,插入异常,删除异常。因此为了完善数据库的增删改查的功能,需要寻找一种等价的关系模式...
  • 模式分解之前,首先对于1NF,2NF,3NF,BCNF做一个简明扼要的介绍。 1NF是指数据库表的每一列都是不可分割的基本数据项,即实体中的某个属性不能有多个值或者不能有重复的属性。 2NF要求属性...
  • 分解关系模式:考点:关系模式的基本函数依赖、关系候选键、关系属于第几范式、 关系属于第几NF、分解NF模式集(10分) 要掌握本题首先要掌握很多基本概念,我们来浅看一下吧,只讲要考的和做题会用到的、我不讲书...
  • 模式分解详解,分解为3NF与分解为BCNF

    千次阅读 多人点赞 2020-03-04 23:06:04
    关系模式R,有U={A,B,C,D,E,F,G},F={B->G,CE->B,C->A,CE->G,B->D,C->D}, (1)将关系模式分解为3NF且保持函数依赖 (2)将关系模式分解为BCNF 将关系模式分解为3NF且保持函数依赖: 假设B->G冗余,则(B)+=BD,没有G故...
  • 定义:无损联接分解是将一个关系模式分解成若干个关系模式后,通过自然联接和投影等运算仍能还原到原来的关系模式,则称这种分解为无损联接分解。 无损分解的判定算法 输入:一个关系模式R(A1,A2,A3,...,An),...
  • 数据库管理系统(Database ...大部分DBMS提供数据定义语言DDL(Data Definition Language)和数据操作语言DML(Data Manipulation Language),供用户定义数据库的模式结构与权限约束,实现对数据的追加、删除等操作。
  • 第一范式:如果关系模式R的所有属性的域都是原子的,那么R就是属于第一范式(1NF),目前的关系数据库都是保证1NF 2. 关系数据库设计容易犯的错误 数据冗余 不一致问题 插入,修改,删除异常 3. 未了解决...
  • 一个是最小依赖函数集,一个是求候选码,一个是求闭包,一个是要把关系模式分解成3NF且保持函数依赖,一个是分解成3NF且保持函数依赖和无损连接。 记录一下我对这几个问题的求法。可能会有哪里有漏洞,希望可以指...
  • 关系模式R(A,B,C,D,E) 函数依赖集F={A->C, C->D, B->C, DE->C, CE->A} 首先确定候选码(BE) 在R中找到X->Y,X不属于超键,如选择A->C,A不是超键 把R分为两部分 R1={AC}, R2={ABDE},其中A也...
  • 数据库之关系模式分解(小結)

    千次阅读 2017-03-04 11:53:11
    关系模式的规范化 1NF 第一范式就是无重复的列。2NF 第二范式就是非主属性非部分依赖于主关键字。3NF 第三范式就是属性不依赖于其它非主属性...【图文】第9讲 关系模式分解与范式_百度文库 数据库范式1NF 2NF 3NF BC
  •  第三范式的定义:如果关系模式R中的所有非主属性对任何候选关键字都不存在传递依赖,则称关系R是属于第三范式的。记作R 3NF。  如:学生关系模式S1(学号,姓名,系号,系名,系地址)  (学号)为关键字,因...
  • 本文以广域同步量测数据为基础,提出了一种基于动态模式分解的电力系统机电振荡模态参数提取与分析方法。动态模式分解算法是一种数据驱动的模态分析手段,可以准确捕捉电力系统机电振荡模态信息,并建立相应的动力学...
  • 关系数据理论详解(模式分解与四大范式)

    千次阅读 多人点赞 2020-12-01 07:09:23
    1NF 2NF 3NF BCNF 模式分解
  • 关系模式分解的认识

    千次阅读 2015-12-16 22:29:26
    一个好的关系模式分解应该具有2个性质:无损连接性和依赖保持性。 一:无损连接的分解 分解的各个关系模式做自然连接和原来的关系模式一样。 无损连接性的算法。 如果只有2个分解的关系模式,那么可以用更方便的...
  • 范式:模式分解,一范式分解成二范式、三范式

    万次阅读 多人点赞 2020-07-27 23:19:57
    此处只讲街模式分解的具体方法,讲解参考施伯乐《数据库系统教程》4.4节关系模式的范式。 给定1NF如下: (学号,姓名,系名,系主任,课程名,分数) 一、1NF与2NF的转换 方法定义(引自施伯乐书籍): 设关系...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 119,430
精华内容 47,772
关键字:

关系模式的分解

友情链接: getDate2.rar