关系数据理论是个什么牛马
问题的提出
一、概念回顾
关系：描述实体、属性、实体间的联系。
从形式上看，它是一张二维表，是所涉及属性的笛卡尔积的一个子集。
关系模式：用来定义关系。
关系数据库：基于关系模型的数据库，利用关系来描述现实世界。
从形式上看，它由一组关系组成。
关系数据库的模式：定义这组关系的关系模式的全体。
二、关系模式的形式化定义
关系模式由五部分组成，即它是一个五元组：
1.属性间的联系
1）一对一联系
设 X，Y 为关系中的属性或属性组，它们的所有可能取值组成两个集合。如果对于 X 中的任一具体值 Y 中至多有一个值与之对应，称 X，Y 这两个属性之间是一对一联系。
2）一对多联系
如果属性值集合 X 中的任一个具体值，至多与 Y 中的一个值相对应，而 Y 中的任一个具体值却可以和 X 中的多个值相对应，则称两个属性间从 X 到 Y 为 m:1 的联系或从 Y 到 X 是 1:m 的联系。
注意:这里指的是属性值个数的多少，而不是具有相同属性值的有多少个元组，二者正好相反。
3）多对多联系
在 X，Y 两个属性值集中，如果任一个值都可以至多和另一个属性值集中多个值对应，反之亦然，则称属性 X 和 Y 是 m：n 关系。
三、什么是数据依赖
1. 完整性约束的表现形式
- 限定属性取值范围
- 定义属性值间的相互关连（主要体现于值的相等与否），这就是数据依赖，它是数据库模式设计的关键
2. 数据依赖
- 一个关系内部属性与属性之间的约束关系
- 现实世界属性间相互联系的抽象
- 数据内在的性质
- 语义的体现
3. 数据依赖的类型
- 函数依赖（Functional Dependency，简记为 FD）
- 多值依赖（Multivalued Dependency，简记为 MVD）
- 其他
四、关系模式的简化表示
关系模式 R（U, D, DOM, F），简化为一个三元组：R（U, F） 。
当且仅当 U 上的一个关系 r 满足 F 时，r 称为关系模式 R （U, F）的一个关系。
五、数据依赖对关系模式的影响
【例 1】 建立一个描述学校教务的数据库：
学生的学号（Sno）、所在系（Sdept）、系主任姓名（Mname）、课程名（Cname）、成绩（Grade）
【解析】
单一的关系模式 ：
学校数据库的语义：
⒈ 一个系有若干学生， 一个学生只属于一个系；
⒉ 一个系只有一名主任；
⒊ 一个学生可以选修多门课程， 每门课程有若干学生选修；
⒋ 每个学生所学的每门课程都有一个成绩。
属性组 U 上的一组函数依赖 F：
关系模式 Student<U, F>中存在的问题
1.数据冗余太大
==浪费大量的存储空间==
例：每一个系主任的姓名重复出现
2.更新异常（Update Anomalies）
==数据冗余 ，更新数据时，维护数据完整性代价大==
例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组
3.插入异常（Insertion Anomalies）
==该插的数据插不进去==
例，如果一个系刚成立，尚无学生，我们就无法把这个
系及其系主任的信息存入数据库。
4.删除异常（Deletion Anomalies）
==不该删除的数据不得不删==
例，如果某个系的学生全部毕业了， 我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。
分解关系模式
把这个单一模式分成 3 个关系模式：
规范化
规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。
一、函数依赖
1.函数依赖
设 R(U)是一个属性集 U 上的关系模式，X 和 Y 是 U 的子集。
若对于 R(U)的任意一个可能的关系 r，r 中不可能存在两个元组在 X 上的属性值相等， 而在 Y 上的属性值不等， 则称“X 函数确定 Y” 或 “Y 函数依赖于 X”，记作 X→Y。
若 X→Y，则 X 称为这个函数依赖的决定属性组，也称为决定因素（Determinant）。
函数依赖与属性间的联系类型有关：
(1) 一对一联系：X←→Y
(2) 多对一联系：X→Y
(3) 多对多联系：不存在依赖关系
(4) 可从属性间的联系类型来分析属性间的函数依赖
ps：
函数依赖不是指关系模式 R 的某个或某些关系实例满足的约束条件，而是指 R 的所有关系实例均要满足的约束条件。
函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。
数据库设计者可以对现实世界作强制的规定。
2.平凡函数依赖与非平凡函数依赖
在关系模式 R(U)中，对于 U 的子集 X 和 Y，
如果 X→Y，但 Y⊈X，则称 X→Y 是非平凡的函数依赖
若 X→Y，但 Y⊆X, 则称 X→Y 是平凡的函数依赖
ps：于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别声明， 我们总是讨论非平凡函数依赖。
3.完全函数依赖与部分函数依赖
在 R(U)中，如果 X→Y，并且对于 X 的任何一个真子集 X’，都有 X’ Y, 则称 Y 对 X 完全函数依赖，记作 X F Y。
若 X→Y，但 Y 不完全函数依赖于 X，则称 Y 对 X 部分函数依赖，记作 $X^P→Y$。 $(S,C)^F→G$ ，$(S,C)^P→SN$
4.传递函数依赖
在 R(U)中，如果 $X→Y$，$(Y^{传递}→X)$ ,$Y→X$ ,$Y→Z$，则称 Z 对 X 传递函数依赖。记为：$X → Z$
ps:如果 $Y→X$， 即 $X←→Y$，则 Z 直接依赖于 X。
二、码
设 K 为 R<U,F>中的属性或属性组合。若 K U， 则 K 称为 R 的侯选码（Candidate Key）。
若候选码多于一个，则选定其中的一个做为主码（Primary Key）。
1.主属性与非主属性
- 包含在任何一个候选码中的属性 ，称为主属性（Prime attribute）
- 不包含在任何码中的属性称为非主属性（Nonprime attribute）或非码属性（Non-key attribute）
2.全码
- 整个属性组是码，称为全码（All-key）
3.外部码
关系模式 R 中属性或属性组 X 并非 R 的码，但 X 是另一个关系模式的码，则称 X 是 R 的外部码（Foreign key）也称外码。
主码与外部码一起提供了表示关系间联系的手段
4.关系码的性质
1) 每个关系必有码。
2) 主码具有标识元组的唯一性。主码是用来唯一标识关系中的元组的。
3) 关系码具有最小性。若抽去主码中任意一属性，则主码就失去标识的唯一性。
4) 主码中的任一属性值不能取空。
【返例】
关系模式 S(S# , SN , SD , DEAN , C# , G)
主码：（S#，C#）
函数依赖：
$（S，C）^f→G$
$S → SN，（S，C）^p→SN$
$S → SD，（S，C）^p→ SD$
$SD → DEAN， S→ DEAN$
$（S，C）^p→DEAN$
三、范式
范式是符合某一种级别的关系模式的集合
关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。
范式的种类：
- 第一范式(1NF)
- 第二范式(2NF)
- 第三范式(3NF)
- BC 范式(BCNF)
- 第四范式(4NF)
- 第五范式(5NF)
各种范式之间存在联系：
1NF ⊃ 2NF ⊃ 3NF ⊃ BCNF ⊃ 4NF ⊃ 5NF
某一关系模式 R 为第 n 范式，可简记为 R∈nNF。
一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化
四、2NF
1.1NF 的定义
如果一个关系模式 R 的所有属性都是不可分的基本数据项， 则 R∈1NF
第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库
但是满足第一范式的关系模式并不一定是一个好的关系模式
2.2NF 的定义
若 R∈1NF，且每一个非主属性完全函数依赖于码，则 R∈2NF。
- 采用投影分解法将一个 1NF 的关系分解为多个 2NF 的关系，可以在一定程度上减轻原 1NF 关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。
- 将一个 1NF 关系分解为多个 2NF 的关系，并不能完全消除关系模式中的各种异常情况和数据冗余
五、3NF
3NF 的定义
关系模式 R<U，F> 中若不存在这样的码 X、属性组 Y 及非主属性 Z（Z ⊈ Y）, 使得 X→Y，Y→Z 成立，Y \→ X，则称 R<U，F> ∈ 3NF。
若 R∈3NF，则每一个非主属性既不部分依赖于码也不传递依赖于码。
(1) 每个非主属性既不部分依赖，也不传递依赖于 R 的任何码。
(2) 从 1NF→2NF：消除非主属性对码的部分函数依赖
(3) 从 2NF→3NF：消除非主属性对码的传递函数依赖
(4) 从一个表中删去不依赖于主码的数据列。
- 采用投影分解法将一个 2NF 的关系分解为多个 3NF 的关系，可以在一定程度上解决原 2NF 关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。
- 将一个 2NF 关系分解为多个 3NF 的关系后，仍然不能完全消除关系模式中的各种异常情况和数据冗余。
六、BCNF
关系模式 R<U，F>∈1NF，若 X→Y 且 Y ⊈ X 时 X 必含有码，则 R<U，F> ∈BCNF。
等价于：每一个决定属性因素都包含码
若 R∈BCNF
▪ 所有非主属性对每一个码都是完全函数依赖
▪ 所有的主属性对每一个不包含它的码，也是完全函数依赖
▪ 没有任何属性完全函数依赖于非码的任何一组属性
3NF 与 BCNF 的关系
如果 R∈3NF，且 R 只有一个候选码
BCNF 的关系模式所具有的性质
1.所有非主属性都完全函数依赖于每个候选码
2.所有主属性都完全函数依赖于每个不包含它的候选码
3.没有任何属性完全函数依赖于非码的任何一组属性
七、多值依赖
1.定义
设 R(U)是一个属性集 U 上的一个关系模式， X、 Y 和 Z 是 U 的子集，并且 Z＝U－X－Y。关系模式 R(U)中多值依赖 X→→Y 成立，当且仅当对 R(U)的任一关系 r， r 在（x，z）上的每个对应一组 Y 的值，这组值仅仅决定于 x 值而与 z 值无关。
2.多值依赖的另一个等价的形式化的定义：
在 R（U）的任一关系 r 中，如果存在元组 t，s 使得 t[X]=s[X]，那么就必然存在元组 w，v r，（w，v 可以与 s，t 相同），使得 w[X]=v[X]=t[X]，而 w[Y]=t[Y]，w[Z]=s[Z]，v[Y]=s[Y]，v[Z]=t[Z]
（即交换 s，t 元组的 Y 值所得的两个新元组必在 r 中），则 Y 多值依赖于 X，记为 X→→Y。 这里，X，Y 是 U 的子集，Z=U-X-Y。
3.平凡多值依赖和非平凡的多值依赖
▪ 若 X→→Y，而 Z＝φ，则称 X→→Y 为平凡的多值依赖
▪ 否则称 X→→Y 为非平凡的多值依赖
4.多值依赖的性质
（1）多值依赖具有对称性
若 X→→Y，则 X→→Z，其中 Z＝U－X－Y
（2）多值依赖具有传递性
若 X→→Y，Y→→Z， 则 X→→Z –Y
（3）函数依赖是多值依赖的特殊情况。
若 X→Y，则 X→→Y。
（4）若 X→→Y，X→→Z，则 X→→Y∪Z。
（5）若 X→→Y，X→→Z，则 X→→Y∩Z。
（6）若 X→→Y，X→→Z，则 X→→Y-Z，X→→Z -Y
5.多值依赖与函数依赖的区别
(1) 有效性
多值依赖的有效性与属性集的范围有关
若 X→→Y 在 U 上成立，则在 W（X Y ⊆ W ⊆ U）上一定成立；反之则不然，即 X→→Y 在 W（W ⊂ U）上成立，在 U 上并不一定成立
▪ 多值依赖的定义中不仅涉及属性组 X 和 Y，而且涉及 U 中其余属性 Z。
▪ 一般地，在 R（U）上若有 X→→Y 在 W（W ⊂ U）上成立，则称 X→→Y 为 R（U）的嵌入型多值依赖
只要在 R（U）的任何一个关系 r 中，元组在 X 和 Y 上的值满足定义（函数依赖），则函数依赖 X→Y 在任何属性集 W（X Y ⊆ W ⊆ U）上成立。
(2)
▪ 若函数依赖 X→Y 在 R（U）上成立，则对于任何 Y' ⊂ Y 均有 X→Y' 成立
▪ 多值依赖 X→→Y 若在 R(U)上成立，不能断言对于任何 Y' ⊂ Y 有 X→→Y' 成立
- 函数依赖规定某些元组不能出现在关系中，也称为相等产生依赖。
- 多值依赖要求某种形式的其它元组必须在关系中，称为元组产生依赖。
八、4NF
关系模式 R<U，F>∈1NF，如果对于 R 的每个非平凡多值依赖 X→→Y（Y ⊈ X），X 都含有码，则 R∈4NF。
如果 R ∈ 4NF， 则 R ∈ BCNF
- 不允许有非平凡且非函数依赖的多值依赖
- 允许的非平凡多值依赖是函数依赖
各级范式的关系
(1) 4NF⊂BCNF⊂3NF⊂2NF⊂1NF
(2) 如果关系满足某个范式要求，也会满足级别较低的所有范式的要求
(3) 较高层次的范式比较低层次的范式更合乎要求
九、规范化小结
- 关系数据库的规范化理论是数据库逻辑设计的工具
- 一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化
- 规范化程度可以有多个不同的级别
- 规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题
- 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化
- 目的：尽量消除插入、删除异常，修改复杂，数据冗余
- 基本思想：逐步消除数据依赖中不合适的部分
实质：概念的单一化
规范化步骤
- 消除不合适的数据依赖
- 使各关系模式达到某种程度的“分离”
- 采用“一事一地”的模式设计原则
让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它“分离”出去
- 所谓规范化实质上是概念的单一化
- 不能说规范化程度越高的关系模式就越好
- 在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式
- 上面的规范化步骤可以在其中任何一步终止
数据依赖的公理系统
一、逻辑蕴含
对于满足一组函数依赖 F 的关系模式 R <U，F>，其任何一个关系 r，若函数依赖 X→Y 都成立, （即 r 中任意两元组 t，s， 若 t[X］=s[X］，则 t[Y］=s[Y］），则称 F 逻辑蕴含 X →Y
二、Armstrong 公理系统
一套推理规则，是模式分解算法的理论基础
用途
- 求给定关系模式的码
- 从一组函数依赖求得蕴含的函数依赖
关系模式 R <U，F >来说有以下的推理规则：
A1.自反律（Reflexivity）：若 Y ⊆ X ⊆ U，则 X →Y 为 F 所蕴含。
A2.增广律（Augmentation）：若 X→Y 为 F 所蕴含，且 Z ⊆ U，则 XZ→YZ 为 F 所蕴含。
A3.传递律（Transitivity）：若 X→Y 及 Y→Z 为 F 所蕴含，则 X→Z 为 F 所蕴含。
注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于 F
三、函数依赖闭包
1.F 的闭包：
在关系模式 R<U，F>中为 F 所逻辑蕴含的函数依赖的全体叫作 F 的闭包，记为 $F^+$。
2.X 关于函数依赖集 F 的闭包：
设 F 为属性集 U 上的一组函数依赖，X ⊆U， XF+ ={ A|X→A 能由 F 根据 Armstrong 公理导出}， $X_F^+$称为属性集 X 关于函数依赖集 F 的闭包
3.关于闭包的引理
引理：
设 F 为属性集 U 上的一组函数依赖，X，Y ⊆ U，X→Y 能由 F 根据 Armstrong 公理导出的充分必要条件是 $Y ⊆ X_F^+$
用途：
将判定 X→Y 是否能由 F 根据 Armstrong 公理导出的问题，转化为求出 XF+ 、判定 Y 是否为 XF+的子集的问题
4.求闭包的算法
求属性集 X（X ⊆ U）关于 U 上的函数依赖集 F 的闭包 X_F^+
输入：X，F 输出：$X_F^+$
步骤：
（1）$令 X^{（0）}=X，i=0$
（2）求 B，这里 $B = { A |(∃ V)( ∃ W)(V→W∈F∧V ⊆ X^{（i）}∧A∈W)}$
（3）$X^{（i+1）}=B∪X^{（i）}$
（4）判断 $X^{（i+1）}= X^ {（i）}$吗?
（5）若相等或 $X^{（i）}=U$ , 则 $X^{（i）}$就是 $X_F^+$, 算法终止。
（6）若否，则 i=i+l，返回第（2）步。
令 ai =|X（i）|，{ai }形成一个步长大于 1 的严格递增的序列，序列的上界是 | U |，因此该算法最多 |U| - |X| 次循环就会终止。
算法（求属性集的闭包）
判定 X→Y 是否能由 F 根据 Armstrong 公理导出，
可转化为求 $XF^+$，判定 $Y⊆XF^+$是否成立。
输入：X，F
输出：
1）开始：$X_F^+$ := X;
2）考察每个 F 中的函数依赖 A→B， 若 $AXF^+$ ，则 $XF^+$:= $X_F^+∪B$
3）继续考察，直到 不再增大为止。
5. Armstrong 公理系统的有效性与完备性
有效性：由 F 出发根据 Armstrong 公理推导出来的每一个函数依赖一定在 F+中
Armstrong 正确
完备性：F+中的每一个函数依赖，必定可以由 F 出发根据 Armstrong 公理推导出来
Armstrong 公理够用，完全
完备性：所有不能用 Armstrong 公理推导出来 f, 都不为真；若 f 不能用 Armstrong 公理推导出来， f∉F+
6. 函数依赖集等价
如果 $G^+=F^+$，就说函数依赖集 F 覆盖 G（F 是 G 的覆盖，或 G 是 F 的覆盖），或 F 与 G 等价。
$F^+ = G^+$ 的充分必要条件是 $F ⊆ G^+$ ，和 $G ⊆ F^+$
7. 最小依赖集
如果函数依赖集 F 满足下列条件，则称 F 为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。记作 Fm：
(1)单属性化： F 中任一函数依赖的右部仅含有一个属性。
(2)无冗余化： F 中不存在这样的函数依赖 X→A，使得 F 与 F-{X→A}等价。
(3)既约化： F 中不存在这样的函数依赖 X→A， X 有真子集 Z 使得 F-{X→A}∪{Z→A}与 F 等价
8. 极小化过程
每一个函数依赖集 F 均等价于一个极小函数依赖集 Fm。此 Fm 称为 F 的最小依赖集。
(1)逐一检查 F 中各函数依赖 FDi：X→Y，若 Y=A1A2 …Ak， k > 2，则用 { X→Aj |j=1，2，…， k} 来取代 X→Y。
(2)逐一检查 F 中各函数依赖 FDi：X→A，令 G=F-{X→A}， 若 A∈XG+， 则从 F 中去掉此函数依赖。
(3)逐一取出 F 中各函数依赖 FDi：X→A，设 X=B1B2…Bm，逐一考查 Bi （i=l，2，…，m），若 A ∈（X-Bi ）F+ ，则以 X-Bi 取代 X。
模式的分解
把低一级的关系模式分解为若干个高一级的关系模式的方法不是唯一的
只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义
三种模式分解等价的定义：
1.分解具有无损连接性
2.分解要保持函数依赖
3.分解既要保持函数依赖，又要具有无损连接性
具有无损连接性的模式分解
- 关系模式 R<U,F>的一个分解 ρ={ R1<U1,F1>，R2<U2,F2>， …， Rn<Un,Fn>}
若 R 与 R1、R2、…、Rn 自然连接的结果相等，则称关系模式 R 的这个分解ρ具有无损连接性（Lossless join）
- 具有无损连接性的分解保证不丢失信息
- 无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题
- 如果一个分解具有无损连接性，则它能够保证不丢失信息
- 如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况
- 分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖；同样，保持函数依赖的分解也不一定具有无损连接性。
小结
- 若要求分解具有无损连接性，那么模式分解一定能够达到 4NF
- 若要求分解保持函数依赖，那么模式分解一定能够达到 3NF，但不一定能够达到 BCNF
- 若要求分解既具有无损连接性，又保持函数依赖，则模式分解一定能够达到 3NF，但不一定能够达到 BCNF
- 规范化理论为数据库设计提供了理论的指南和工具
也仅仅是指南和工具
- 并不是规范化程度越高，模式就越好
必须结合应用环境和现实世界的具体情况合理地选择数据库模式
还未添加个人签名 2021.03.30 加入
还未添加个人简介
评论