精华内容
下载资源
问答
  • 【数据库原理系列】关系模式分解
    千次阅读
    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属性数据库设计中关系模式的构造...同时,为使分解过程中不出现信息丢失并维护地学数据的完整性约束,还讨论了关系模式分解应满足的信息无损失连接性的约束条件,以及关系模式分解所应保持的函数依赖的约束因素
  • 数据库系统原理-函数依赖和关系模式分解 目录数据库系统原理-函数依赖和关系模式分解第一范式如何处理非原子值原子性关系数据库设计中易犯的错误模式分解无损连接分解优化关系模式的步骤函数依赖函数依赖定义函数...

    数据库系统原理-函数依赖和关系模式分解

    学习本章相关理论知识可以为优化我们设计的数据库模型

    第一范式

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

    非原子域的例子:

    • 复合属性:名字集合
    • 多值属性:电话号码
    • 复杂数据类型:面向对象的

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

    (1NF)

    非原子值存储复杂并易导致数据冗余,在数据库系统中我们创建的表基本都属于第一范式

    如何处理非原子值

    • 对于组合属性:让每个子属性本身成为一个单独的属性
    • 对于多值属性:为多值集合中的每个项创建一条元组(再建表)

    原子性

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

    例如,字符串通常会被认为是不可分割的,假设学生被分配这样的标识号:CS0012或SE1127,如果前两个字母表示系,后四位数字表示学生在该系内的唯一号码,则这样的标识号不是原子的(字符串+数字)

    当采用这种标识号时,是不可取的。因为这需要额外的编程,而且信息是在应用程序中而不是在数据库中编码

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

    关系数据库设计要求我们找到一个好的关系模式集合。一个坏的

    设计可能导致以下问题

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

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

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

    这样的关系模式存在以下问题

    • 数据冗余

    • 更新异常

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

    • 插入/删除异常

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

    模式分解

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

    (A,B,D),或(A,B,C)和(C,D),或(A,B)、(B,C)和(C,D),或 (A,D)和

    (B,C,D)

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

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

    无损连接分解

    优化关系模式的步骤

    判断关系模式好坏—>若是后者—>关系模式分解解成模式集合{R1**, R**2, …, Rn}使得:每个关系模式都是“好的形式”且分解是无损连接分解

    我们优化关系模式的理论基于

    • 函数依赖( functional dependencies )
    • 多值依赖( multivalued dependencies )

    函数依赖

    函数依赖定义

    一种完整性约束,表示特定的属性值之间的关系,可以用来判断模式规范化和建议改进

    这里解释以下,候选码是最小超码

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

    inst_dept(ID,name,salary,dept_name,building,budget) 
    /*budget表示预算*/
    /*building表示部门地点*/
    

    我们期望下列函数依赖成立:

    dept_name -->building
    ID --> building
    

    而不期望下列函数依赖成立:

    dept_name --> salary
    

    函数依赖的使用

    • 函数依赖集:多条函数依赖(A->B)的集合
    • 可以这么理解,A列相同的值对应C列相同的值如a1->c1 a2->c2…

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mfD8YTDp-1574005601262)()]

    R是关系模式
    r是关系
    

    函数依赖集的闭包

    Armstrong公理

    利用Armstrong公理来找出函数依赖集的闭包

    Armstrong公理二级定律

    在这里插入图片描述

    闭包计算算法

    属性集的闭包

    属性闭包的用法

    正则覆盖

    无关属性

    检测属性是否无关

    正则覆盖

    规范化-模式分解

    当R 不是“好的”形式时,将它分解成模式集合{R1, R2, …, Rn}使得

    • 每个关系模式都是**“好的”形式**

    • 分解是无损连接分解

    • 分解是保持依赖

    分解验证算法

    模式分解总结

    规范化-简单版

    图示法求候选键

    条件:给出函数依赖集,求候选键

    1. 将关系的函数依赖关系用有向图表示
    2. 找出入度为0的属性,并以该属性集合为起点,尝试遍历所有的图,若能遍历途中所有结点,则该属性集为关系模式的候选键
    3. 若入度为0的属性集不能遍历途中所有的结点,则需要尝试性的将 一些中间结点(既有入度,也有出度的结点)并入入度为0的属性集中,直至该集合能遍历所有结点,集合求候选键

    主属性和非主属性

    组成候选码的属性是主属性、其他的就是非主属性

    第一范式(1NF)

    在上面

    第二范式(2NF)

    当且仅当关系模式R是第一范式(1NF),且每一个非主属性完全依赖(A->B->C)候选键(没有不完全依赖(部分依赖(AB->C/A->C))时),则称关系模式R为第二范式

    例子:关系模式SC(学号、课程号、成绩、学分),其中(学号,课程号)->成绩,

    课程号->学分

    分析:因为存在部分依赖,故不满足第二范式

    解决:分解成(学号、课程号、成绩)(课程号,学分)

    第三范式(3NF)

    在2NF上取消完全依赖

    例子:

    学生关系(学号、姓名、系号、系名、系位置)

    分析:该模式存在完全函数依赖(学号->系号–>系名)

    解决:分解成(学号、姓名、系号) (系号、系名、系位置)

    BC范式(BCNF)

    设R是一个关系模式,F是它的依赖集,R属于BCND当且仅当其F中每个依赖的决定因素必定包含R的某个候选码(取消主属性对候选键的部分和传递依赖)

    模式分解-保持函数依赖分解

    原则:两个关系模式之间不能乱推,得看依赖集

    模式分解-无损分解

    展开全文
  • 数据库系统原理
  • 现有如下关系模式: 其中: 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

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



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

    展开全文
  • 数据库中关于关系模式的知识,涉及到模块分解以及相关定义性质,还有算法练习,内涵公理系统的有效性已经相应的推理规则,适合初学者以及数据库爱好者学习,有效掌握数据库关系模式这一块的知识
  • 函数依赖与关系模式分解的一些技巧整理

    万次阅读 多人点赞 2018-01-21 19:58:27
    函数依赖与关系模式分解的一些技巧整理 关系数据库设计理论的核心是数据间的函数依赖,衡量的标准是关系规范化的程度及分解的无损连接性和保持函 数依赖性。 数据依赖是通过一个关系中属性间值的相同与否体现...
  • 分解为3nf要先求最小函数依赖集,然后找到函数依赖中没有涉及的属性,单独分分解,之后从r中去掉,之后就是对函数依赖集中函数依赖左边相同属性进行合并,若果合并结果有包含关系,去掉小的,这是保持函数依赖的分解,...
  • 函数依赖和关系模式分解

    千次阅读 2020-06-23 10:11:40
    文章目录一,第一范式关系数据库设计中易犯的错误数据冗余插入、删除、修改异常模式分解函数依赖(FD)函数依赖的使用函数依赖集的闭包Armstrong 公理计算 F^+^属性集的闭包属性闭包的用途正则覆盖无关属性检测属性...
  • 1NF 2NF 3NF BCNF 模式分解
  • 模式分解之前,首先对于1NF,2NF,3NF,BCNF做一个简明扼要的介绍。 1NF是指数据库表的每一列都是不可分割的基本数据项,即实体中的某个属性不能有多个值或者不能有重复的属性。 2NF要求属性...
  • 关系模式分解与范式

    千次阅读 2019-04-20 17:41:41
    为什么要研究数据库关系模式分解? 答:因为现有的模式可能会存在一些数据增删改的弊端,比如说:数据冗余太大,更新异常,插入异常,删除异常。因此为了完善数据库的增删改查的功能,需要寻找一种等价的关系模式...
  • 数据库概论之模式分解理论(理解简单明了)

    千次阅读 多人点赞 2020-04-06 19:53:47
    模式分解理论模式分解模式分解的概念:模式分解的特性:数据内容的等价性:数据约束的等价性模式分解要考虑的问题:模式分解的分类:无损连接分解:无损连接分解概念:无损连接分解的检验算法:无损连接分解算法...
  • 数据库-模式分解

    2021-11-14 23:18:30
    关系模式分解必须遵循的两个准则 分解的无损连接性 不满足无损连接的例子 判断无损连接的算法 保持无损分解的充分必要条件 保持无损分解的例子 分解的函数依赖的保持性 例子1 ...
  • 第一范式:如果关系模式R的所有属性的域都是原子的,那么R就是属于第一范式(1NF),目前的关系数据库都是保证1NF 2. 关系数据库设计容易犯的错误 数据冗余 不一致问题 插入,修改,删除异常 3. 未了解决...
  • 模式分解详解,分解为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故...
  • 规范化理论:模式分解

    千次阅读 2019-05-13 22:51:05
    什么是模式分解? 关系模式R<U, F>的一个分解是指:={<...把低一级的关系模式分解为若干个高一级的关系模式,分解方法并不是唯一的,在这些分解方法中,只有能够保证分解后的关系模式与原关...
  • 定义:无损联接分解是将一个关系模式分解成若干个关系模式后,通过自然联接和投影等运算仍能还原到原来的关系模式,则称这种分解为无损联接分解。 无损分解的判定算法 输入:一个关系模式R(A1,A2,A3,...,An),...
  • 数据库原理-模式分解算法详解(3NF BCNF)

    千次阅读 多人点赞 2020-05-04 12:20:26
    模式分解算法模式分解的要求无损连接保持函数依赖模式分解的算法范式简述3NF的保持依赖性分解3NF的无损连接与依赖保持分解BCNF的无损连接分解 模式分解的要求 无损连接 保持函数依赖 模式分解的算法 范式简述 3NF的...
  • (14)模式分解

    千次阅读 多人点赞 2019-06-30 19:52:27
    目录 0.为什么要进行模式分解 1.什么是模式分解 2.有损分解(分解中的一个问题)和无损分解 3.保持函数依赖的分解 ...对上表职工级别设计关系模式,职工(职工,级别,工资),存在以下问题: 解决方...
  • 在以下给定的关系模式分解中,D→A的依赖是保持下来的: 给定关系模式R,U={A, B, C, D, E,h},F={B→A,D→A,A→E,AC→B,d→h,h→b},则分解ρ={R1(ABCE),R2(CDh),(abh)} 原因是:D→H,H→B,B→A,...
  • 数据库之关系模式分解(小結)

    千次阅读 2017-03-04 11:53:11
    关系模式的规范化 1NF 第一范式就是无重复的列。2NF 第二范式就是非主属性非部分依赖于主关键字。3NF 第三范式就是属性不依赖于其它非主属性...【图文】第9讲 关系模式分解与范式_百度文库 数据库范式1NF 2NF 3NF BC
  • 前言在理解模式分解的时候,发现模式分解算法比较难懂。于是想出了一个通俗易懂的解法,并且配有速记口诀!让模式分解再也难不倒你。知识储备首先在了解模式分解之前,你需要对数据库规范化有一定的了解。这里我列出...
  • 函数依赖集投影 给定关系模式R(U,F),若有Ui...判断一个模式分解是否是好的模式分解应该判断该分解是否满足无损连接性和函数依赖性 如果一个分解具有无损连接性,则它能够保证不丢失信息 如果一个分解保持了函数依赖,则
  • 数据库模式分解(应该比较易懂吧)

    千次阅读 2021-04-29 09:57:20
    数据库模式分解 部分函数依赖 函数依赖的确定 1对1的关系时,有两个函数依赖 1对多时,有一个函数依赖 多对多时,没有函数依赖 函数依赖类型 右边不为左边的子集{非平凡函数依赖(A−>B),yes平凡函数依赖(AB...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 115,805
精华内容 46,322
关键字:

关系模式分解