开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 深入会用——关系数据理论 [包含详细例题+解析] -> 正文阅读

[数据结构与算法]深入会用——关系数据理论 [包含详细例题+解析]

? 这一部分比较难，做了一点笔记。

● 我们用的教材：
请添加图片描述

一、1NF、2NF、3NF和BCNF的相关例题

消除了部分函数依赖的 1NF 模式，必定是（）。
A. BCNF
B. 2NF
C. 1NF
D. 3NF

答案：B，可能还存在传递依赖，即不一定是 3NF。

设有关系模式 R(A,B,C,D)，其数据依赖集：F={(A,B)→C,C→D}，则关系模式 R 的规范化程度最高达到( )。
A. 3NF
B. BCNF
C. 2NF
D. 1NF

答案：C，若存在传递依赖，即不是 3NF。满足 2NF 的规矩：每一个非主属性完全依赖任何一个候选码。故是 2NF。

若关系模式 R 中没有非主属性，则 R 满足3NF。( )
A. 对
B. 错

答案：A。满足 3NF 的规矩：每一个非主属性即不传递依赖于码，也不部分依赖于码。 非主属性都没有，显然满足 3NF。

若关系模式 R 的主码是全码，则满足BCNF。( )
A. 对
B. 错

答案：A。满足 BCNF 的规矩：每一个决定因素(比如，X → Y，则 X 是决定因素)都包含码。因为它的主码是全码，若存在 “X → Y” 这样的函数依赖，那 X 显然包含码，满足 BCNF 的规矩。

函数依赖指的是关系模式 R 的某个或者某些关系满足的约束条件。( )
A. 对
B. 错

答案：B。由书上定义 6.1 和其定义下面 “注意” 的可知，函数依赖指的是关系模式 R 的所有关系均要满足的约束条件。

二、数据依赖的公理系统

2.1 必要的基础名词解释

● 一些关键定义如下，知道有这些名词即可，在做题时回头来看：

● 函数依赖： 设 R(U) 是一个属性集 U 上的关系模式，X 和 Y 是 U 的子集。若对于 R(U) 的任意一个可能的关系 r，r 中不可能存在两个元组在 X 上的属性值相等，而在 Y 上的属性值不等则称 “X函数确定Y” 或 “Y函数依赖于X”，记作 X→Y。X称为这个函数依赖的决定属性组，也称为决定因素(Determinant)。

● 逻辑蕴含(也可简称为蕴含)： 对于满足一组函数依赖 F 的关系模式 R<U，F>，其任何一个关系 r，若函数依赖 X→Y 都成立（即 r 中任意两元组 t，s，若 t[X]=s[X]，则 t[Y] = s[Y]），则称 F 逻辑蕴含 X→Y。

● Armstrong公理系统： 设 U 为属性集总体，F是 U 上的一组函数依赖，于是有关系模式 R<U，F >。对 R<U，F> 来说有以下的推理规则：

?① 自反律(Reflexivity)：若 Y ? X ? U，则 X →Y 为 F 所蕴含。
?② 增广律(Augmentation)：若 X→Y 为 F 所蕴含，且 Z ? U，则 XZ→YZ 为 F 所蕴含。
?③ 传递律(Transitivity)：若 X→Y 及 Y→Z 为 F 所蕴含，则 X→Z 为 F 所蕴含。

● 闭包 $F^+$ ： 在关系模式 R<U，F> 中为 F 所逻辑蕴含的函数依赖的全体叫作 F 的闭包(closure)，记为 $F^+$ 。

● X关于函数依赖集 F 的闭包 $X_{F^+}$ ： 设F为属性集 U 上的一组函数依赖，X ? U， $X_{F^+}$ ={ A | X→A 能由 F 根据 Armstrong 公理导出}， $X_{F^+}$ 称为属性集 X 关于函数依赖集 F 的闭包。

● 对 闭包 $F^+$ ： 的理解：

请添加图片描述

2.2 算法6.1 ??????

● 关于闭包的引理(引理：为证明某个定理或解某个问题所要用到的命题。引理和定理没有严格的区分)： 设 F 为属性集 U 上的一组函数依赖，X，Y ? U，X→Y 能由 F 根据 Armstrong 公理导出的充分必要条件是 Y? $X_{F^+}$ 。

● 该引理的用途：
?① 将判定 X→Y 是否能由 F 根据 Armstrong 公理导出的问题，就转化为求出 $X_{F^+}$ ，判定 Y 是否为 $X_{F^+}$ 的子集的问题。
?② 如果 $X_{F^+}$ = U，X 是 R<U，F> 的候选码。【参考样例2】

● $X_{F^+}$ 可以用以下算法来求得： 【求属性集 X(X?U) 关于 U 上的函数依赖集 F 的闭包 $X_{F^+}$ 】
?① 令 $X^{(i)}$ =X，i=0；
?② 对 F 中的每一个函数依赖 Y→Z，若 Y?X(i)，令 $X^{(i+1)}$ = $X^{(i)}$ ∪Z。
?③ 若 $X^{(i+1)}$ ≠ $X^{(i)}$ ，则用 i+1 代替 i，转②；
?④ 若 $X^{(i+1)}$ = $X^{(i)}$ ，则 $X^{(i)}$ 即为 X。

● 样例1：
在这里插入图片描述

● 求给定关系模式的码的经验方法： ?? ??
?① 若属性 A 仅出现在所有函数依赖的右部，则它一定不包含在任何候选码中；
?② 若属性 A 仅出现在所有函数依赖的左部，则它一定包含在某个候选码中；
?③ 若属性 A 既出现在函数依赖的右部，又出现在左部，则它可能包含在候选码中；
?④ 在上述基础上求属性闭包。

● 样例2：

在这里插入图片描述

2.3 最小依赖集的定义和求法

● 最小依赖集(也称为极小函数依赖集、最小覆盖)： 如果函数依赖集 F 满足下列条件，则称F为一个最小依赖集：
?① F 中任一函数依赖的右部仅含有一个属性。
?② F 中不存在这样的函数依赖 X→A，使得 F 与 F-{X→A} 等价。【解释：即 F 中的函数依赖均不能由 F 中其他函数依赖导出】
?③ F 中不存在这样的函数依赖 X→A，X 有真子集 Z 使得 F-{X→A}∪{Z→A} 与 F 等价。【解释：F中各函数依赖左部均为最小属性集(不存在冗余属性)】

● 关于 “最小依赖集” 的解法步骤：
?1.将 F 中的所有函数依赖的右边化为单一属性。
?2.去掉 F 中的所有函数依赖左边的冗余属性。
?3.去掉 F 中所有冗余的函数依赖。

● 样例3： 设 R<U, F>，U=ABCD, 函数依赖集 F = {A→BD，AB→C，C→D}。求：F的最小函数依赖集

(1) 将 F 中的所有函数依赖右边化为单一属性
F = {A→BD, AB→C, C→D} ? F = {A→B, A→D, AB→C, C→D}
(2) 去掉 F 中的所有函数依赖左边的冗余属性
因为 $A^+=\{A, B, C, D\}(含C)，B^+=\{B\}$ (不含C)，故在 “AB→C” 中，B 是冗余属性。
所以 F = {A→B, A→D, A→C, C→D}
(3) 去掉 F 中所有冗余的函数依赖关系
因为对于 “F = {A→B, A→C, C→D} ” 而言， $A^+=\{A, B, C, D\}(含D)$ ，所以 “A→D” 是冗余的函数依赖关系
所以 F = {A→B, A→C, C→D}

◆ 注：在上述的 (3) 中，也可以这样：对于 “F = {A→B, A→D, A→C} ” 而言， $A^+=\{A, B, C, D\}(含D)$ ，所以 “C→D” 是冗余的函数依赖关系，故 F = {A→B, A→D, A→C}

◆ 所以 F 的最小依赖集 $F_m$ 不一定是唯一的：

在这里插入图片描述
◆ 为什么有 “C→A”？：因为通过最小依赖集 $F_{m1}$ 或 $F_{m2}$ 能够还原出 F。C→A 如果不包含在最小依赖集当中的话。靠谁来还原出来 C→A？

三、具有无损连接性的模式分解

● 如何判断一个模式分解的无损连接性：

在这里插入图片描述
● 样例4： (考试不要求掌握)

● 特殊情况： 分解仅由 2 个模式组成。

● 定理6.5： 设R (U,F)，有 ρ={R1，R2}，则对于 F，ρ 相对于 F 是无损分解的充分必要条件是：U1∩U2→U1-U2∈F⁺ 或U1∩U2→U2-U1∈F⁺。?? ??

● 样例5： (考试要求掌握) ?? ??

在这里插入图片描述

四、具有函数依赖性的模式分解

● 判断一个分解是否保持依赖：用判断两个函数依赖集是否等价的方法。

● 样例6： (考试要求掌握)
在这里插入图片描述

◆ 注：依赖保持性的分解 ≠ 连接不失真。一个具有依赖保持性的分解不一定具有连接不失真性。反之，一个连接不失真分解也不一定具有依赖保持性。

五、转换为3NF的保持函数依赖的分解(算法6.3 合成法)

● 如果说 R(U, F) 中的 F 已经是最小依赖集了，那么就按下面的流程走。如果不是，就要先把 F 转变为最小依赖集才行。（下图的例题已经是最小依赖集了，考试出题目都会是极小化，不需要大家再做这个动作了）
在这里插入图片描述
● 简而言之：
?① 先求出 F 的最小依赖集，然后把最小依赖集中那些左部相同的 F 合并【比如说，把上面 “2.3” 图例中的 F_m1 中的 “A→B、A→C” 合并为 “A→BC”】。
?② 就是把 “→” 的左右两边组合起来，成为一个个 “子关系”。比如就把 R<U, F> = R<{ABC}, {A→B, B→C}> 分解为 R₁<U₁, F₁>、R₂<U₂, F₂>，其中 R₁<U₁, F₁> = R₁<{AB}, {A→B}>，R₂<U₂, F₂>=R₂<{BC}, {B→C}>。
?③ 如果存在 “A→B₁、A→B₂”，就这样合成：R₃<{AB₁B₂}, {A→B₁，X→B₂}>。

六、转换为3NF的即有无损连接又保持函数依赖的分解(算法6.4)

在这里插入图片描述
● 简而言之： 就是在 “算法6.3” 的基础上，多 ∪ 一个候选码。图中因为 “HSR” 包含了 “HS”，所以并之前和并之后结果一样。

七、结果为BCNF的无损分解算法(算法6.5) ??????

● 这个考试要求掌握： ?? ?? 【理解可能需要花费一定的时间】

在这里插入图片描述

● 样例7：

在这里插入图片描述

● 样例8：【课程C、教师T、时间H、教室R、学生S、成绩G】
在这里插入图片描述

在这里插入图片描述
◆ 解释： HS 是主码。那一开始选出 “CS→G”，因为 “CS” 不含键。【码的意思即是键，含键的意思是包含整个的键(属性的组合)只有一部分的不算含】。当然，也可以首先分解 HR→C，或者首先分解 HT→R 。

在这里插入图片描述
◆ 注：上述结果虽然转换为了 BCNF 的无损分解，但丢失了函数依赖 HT→R。这说明无损连接不一定能保证函数依赖。

八、补充的一些例题

已知关系模式 R(A,B,C,D,E) 及其函数依赖集 F={A->D,B->C,E->A}, 则该关系模式的候选码为（)
A. AB
B. AE
C. BE
D. ABE

答案：C，因为 $BE_{F}^{+}=U$ ，即 $BE_{F}^{+}=\{A,B,C,D,E\}$ ，即通过 BE 就能推导出所有属性或属性组。

根据 Armstrong 公理导出 F 的闭包 F⁺ 是可行的。( )
A. 正确
B. 错误

答案：B。根据 Armstrong 公理导出 F 的闭包 F⁺ 是一个 NP 完全问题，故不可行。

确定关系模式 R 的候选码时，若某属性不在函数依赖集 F 中出现，则该属性必须要包含在候选码中。（）
A. 正确
B. 错误

答案：A。若某属性不在函数依赖集 F 中出现，说明该属性是一个 “独立的属性”，它与其他属性没关系。换句话说。它既不能推导其他属性(或属性组)，也不能由其他属性(或属性组)推导出它。而候选码就是能推导出所有属性(或属性组) 的属性(或属性组)，显然，若 X 不在在函数依赖集 F 中出现。那 X 必须要包含在候选码中。因为 X 可以→ X。

Armstrong 公理系统是有效的、完备的。（）
A. 正确
B. 错误

答案：A。书上的定理6.2可知。

Armstrong 公理系统包括[多选]。( ）
A. 自反律
B. 增广律
C. 传递律
D. 结合律

答案：ABC。书上的定义6.11。

F的最小依赖集不一定是唯一的。（）
A. 正确
B. 错误

答案：A。这篇博客的前面的 “2.3” 讲过。

关系模式不满足 2NF，则一定存在 “非主属性对候选码的局部依赖”。（）
A. 正确
B. 错误

答案：A。满足 2NF 的规矩：每一个非主属性完全依赖任何一个候选码。

使用算法 6.5 转换为 BCNF 的无损连接分解之后得到的模式也一定是保持函数依赖的。（）
A. 正确
B. 错误

答案：B。转换为 BCNF 的无损连接不一定能保证函数依赖。上面的例子有提到反例。

设 R(U, F) 有分解 ρ={R₁, R₂}，则 F，ρ 相对于 F 是无损分解的充分必要条件是：U₁∩U₂ → U₁-U₂∈F⁺或U₁∩U₂→U₂-U₁∈F⁺
A. 正确
B. 错误

答案：A。书上定理6.5.

设有关系模式 R(A，B，C，D，E，F)，其基本函数依赖集 F={A→B, CD→A, BC→D, CE→D,AE→F}。请：
(1)分析 R 的候选码。（不需写推导过程,只需给出结果)
(2)判断 R 是否达到3NF，并说明理由。
(3)如果 R未达到3NF，请将R保持函数依赖和无损地分解为符合3NF的模式集p。（直接给出结果)

◆ 解释： FD 就是 “函数依赖(Functional Dependency)” 的意思。另外，在关系中能唯一标识元组的属性集称为关系模式的超键。一个属性可以为作为一个超键，多个属性组合在一起也可以作为一个超键。满足 3NF 的规矩：每一个非主属性即不传递依赖于码，也不部分依赖于码。