Chapter06 - 关系数据理论
ch32 关系模式及范式
U和D：不同属性可以拥有相同的域
数据依赖
数据依赖
- 是一个关系内部属性与属性之间的一种约束关系
- 通过属性间值的相等与否体现出来的数据间相关联系是现实世界属性间相互联系的抽象
- 是数据内在的性质
- 是语义的体现
- 数据依赖的主要类型
- 函数依赖（Functional Dependency，简记为FD)
- 多值依赖（Multi-Valued Dependency，简记为MVD)
1NF
但凡是关系，就是1NFF={Sno-→Sdept, Sdept→Mname, (Sno, Cno)→Grade}
关系模式Student<U, F>中存在的问题:
- 数据冗余：不仅浪费空间，也需要统一的完成修改
- 浪费大量的存储空间：每一个系主任的姓名重复出现，重复次数与该系所有学生的所有课程成绩出现次数相同。
- 更新异常(Update Anomalies)
- 数据冗余，更新数据时，维护数据完整性代价大，否则会面临数据不一致的情况。
- 某系更换系主任后，必须修改与该系学生有关的每一个元组。如果有元组没有修改，则会出错-完整性约束条件出错
- 插入异常（Insertion Anomalies)
- 如果一个系刚成立，尚无学生，则无法把这个系及其系主任的信息存入数据库。
- 删除异常（Deletion Anomalies)
- 如果某个系的学生全部毕业了，则在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。
- 结论：Student关系模式不是一个好的模式。
- 一个“好”的模式应当不会发生插入异常、删除异常和更新异常，数据冗余应尽可能少。
- 原因：由存在于模式中的某些数据依赖引起的。
- 解决方法：用规范化理论改造关系模式来消除其中不合适的数据依赖
- 把这个单一的模式分成三个关系模式;
s(Sno,Sdept,Sno → Sdept);
sc(Sno,Cno,Grade,(Sno,Cno)→Grade);
DEPT(Sdept,Mname,SdeptMname);
这三个模式都不会发生插入异常、删除异常的问题，数据的冗余也得到了控制。
- 规范化以后的结果：
- 应该是节约空间的，去除数据的冗余
- 浪费了查询的时间，拥有了更多的表，如果涉及到多张表，需要进行连接操作来进行查询
范式
越往右：越严格，表的划分越细致
ch33 函数依赖与码
函数依赖
定义6.1：设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r 中不可能存在两个元组在X上的属性值相等， 而在Y上的属性值不等， 则称“X函数确定Y”或“Y函数依赖于X”，记作X→Y，X称为这个函数依赖的决定因素（Determinant）。
- 函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。
- 函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。
- 例如“姓名→年龄”这个函数依赖只有在不允许有同名人的条件下成立
- 数据库设计者可以对现实世界作强制的规定。
- 例如规定不允许同名人出现，函数依赖“姓名→年龄”成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在，则拒绝插入该元组。
平凡函数依赖与非平凡函数依赖
举例来说，如果有一个关系模式R(学号，姓名，性别)，那么学号对姓名和性别有非平凡函数依赖，因为学号可以唯一确定姓名和性别，而姓名和性别不是学号的子集。但是学号对学号有平凡函数依赖，因为学号可以由自身确定。同样，姓名对姓名和性别有平凡函数依赖，因为姓名是姓名和性别的子集。
完全函数依赖与部分函数依赖
完全函数：X不可以拿出部分属性，可以增加部分属性变为部分函数依赖。也就是说，X的所有属性一起才能决定Y，去掉任何一个属性都不行
部分函数：X可以拿出部分属性。也就是说，X中的部分属性就可以决定Y，用不着全部
F：完全依赖，P：部分依赖
举例来说，如果有一个关系模式R(学号，姓名，课程号，成绩)，那么：
- 学号和课程号对姓名和成绩有非平凡函数依赖，因为学号和课程号可以唯一确定姓名和成绩，而姓名和成绩不是学号和课程号的子集。
- 学号和课程号对姓名有部分函数依赖，因为学号可以单独决定姓名，而不需要课程号。
- 学号和课程号对成绩有完全函数依赖，因为学号或课程号单独都不能决定成绩，而只有两者一起才能决定成绩
传递函数依赖
一一对应：信息量上可以看做是冗余的
传递性：从业务逻辑上判断，是由需求决定的依赖关系（直接依赖），还是由推导得出来的依赖关系（传递依赖）。
如果我知道了一个学生的学号Sno，那我就能知道他所在的系Sdept。(因为理论上一个学生只属于一个系)
如果我知道了某一个系Sdept，那么我就能知道这个系的系主任的姓名Mname。(一个系只有一个正的系主任。)
也就是说，我知道了一个学生的学号Sno，其实我就知道了他所在系的系主任的姓名Mname。但这个过程中，他们是不存在直接函数依赖的，我需要通过系名称Sdept作为一个桥梁去把二者联系起来的。
码
在这里，是通过函数依赖的概率来定义码
- 如果U完全依赖于K，则称K为R的候选码
- 如果U部分依赖于K，则称K为R的超码
- 候选码是最小的超码
- 如果候选码多于一个，则选定其中的一个为主码
- 候选码的超集是超码，候选码的真子集一定不是超码
- 包含在候选码中的属性称为主属性(prime attribute)：主属性是候选码的并集
- 不包含在任何候选码中的属性称为非主属性(nonprime attribute）或非码属性(non-key attribute)（非主属性->非码属性：不在任何一个候选码中出现过的属性）
- 最简单的情况,单个属性是码；最极端的情况，整个属性组是码，称为全码（all-key)。
在后面的章节中主码或候选码都简称为码。读者可以根据上下文加以识别。
记录数据时，可以记录完备的数据，也可以记录部分数据
- 应用需不需要使用这些数据（要什么记录什么）
主属性与非主属性：
你之所以为你，是有你的个性和你的共性（挑选个性来区分独特的你 – 候选码挑选为主码的过程）
骨架和皮肉（非主属性越多–越具备详细分析的潜在价值，画像越具体）的关系
只有骨架：全码
外码
定义6.5 关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码,则称X是R的外部码（foreign key)，也称外码。
如在SC (Sno,Cno, Grade）中，Sno不是码，但Sno是关系模式S (Sno, Sdept, Sage)的码,则 Sno是关系模式SC的外码。
主码与外码提供了一个表示关系间联系的手段，如例6.2中关系模式S与SC的联系就是通过Sno来体现的。
ch34* 1NF 2NF 3NF
范式
1NF
定义：关系中每一分量不可再分。即不能以集合、序列等作为属性。（也就是不能表中套表，要保证数据的原子性。）
- 如果一个关系模式R的所有属性都是不可分的基本数据项，则R∈1NF。
- 第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。
- 但是满足第一范式的关系模式并不一定是一个好的关系模式。
举例
学生编号 课程编号
| 学生编号 | 课程编号 |
|---|---|
| S01 | {C1，C2，C3} |
| S02 | {C1，C4} |
它就不满足1NF，因为{C1，C2，C3}和{C1，C4}是集合。
修改为符合1NF：
学生编号 课程编号
| 学生编号 | 课程编号 |
|---|---|
| S01 | C1 |
| S01 | C2 |
| S01 | C3 |
| S02 | C1 |
| S02 | C4 |
2NF
分析
虚线：部分函数依赖
一个关系模式R不属于2NF，就会产生以下几个问题:
- 插入异常。假若要插入一个学生Sno=S7，Sdept=PHY，Sloc=BLD2，但该生还未选课，即这个学生无Cno，这样的元组就插不进S-L-C中。因为插入元组时必须给定码值,而这时码值的一部分为空，因而学生的固有信息无法插入。
- 删除异常。假定某个学生只选一门课，如S4就选了一门课C3，现在C3这门课他也不选了，那么C3这个数据项就要删除。而C3是主属性，删除了C3，整个元组就必须一起删除，使得S4 的其他信息也被删除了，从而造成删除异常，即不应删除的信息也删除了。
- 修改复杂。某个学生从数学系（MA）转到计算机科学系（CS)，这本来只需修改此学生元组中的Sdept分量即可，但因为关系模式S-L-C中还含有系的住处Sloc属性，学生转系将同时改变住处，因而还必须修改元组中的Sloc分量。另外，如果这个学生选修了k门课，Sdept、Sloc重复存储了k次，不仅存储冗余度大，而且必须无遗漏地修改k个元组中全部Sdept、Sloc信息，造成修改的复杂化。
旧问题解决
- 插入异常：学生选课和学生基本信息分别在两个表中，所以即使没有选课的学生也可以加入SL。
- 删除异常：删除一个学生的选课记录只影响SC,对SL没有影响，大四老哥（没有选课记录了）不用退学了，好耶！
- 数据冗余度大：选课跟基本信息不在一张表里，重复的都是必要数据，大大降低了数据冗余。修改复杂：数据都不怎么冗余了，修改操作自然也随之减少
新问题出现
SL中仍存在着对于我们简化关系结构有障碍的关系，即Sloc对于Sdept的函数依赖，这个关系我们是不想要的，他看上去很多余，明明已经可以通过Sno确定Sloc，可是Sloc偏偏还和Sdept有不得不说的关系，这个关系也导致SL存在一些问题。
- 插入异常：一个系刚刚成立，还没有学生，那么码Sno就没有数据，这个系就没了，系长哭泣。
- 删除异常：某系决定暂停招生一段时间，把最后一批学生送走时候，删除学生数据，Sno又空了，这个系又没了，系长又哭了。
- 数据冗余大：一个系的所有学生都住在一起，可是Sloc这个属性却每个学生重复一次。
- 修改复杂：同上，Sloc重复的多，如果该系调整住址位置，修改的也多
举例
定义：在1NF基础上，消除非主属性对键的部分依赖，则称它符合2NF。
根据上面对部分依赖的分析，对于Student表：
| 学生编号 | 学生姓名 | 班级编号 | 院系 | 课程编号 | 成绩 |
|---|---|---|---|---|---|
| S01 | 杨明 | D01 | 思齐 | C01 | 90 |
| S02 | 李婉 | D01 | 思齐 | C01 | 87 |
| S01 | 杨明 | D01 | 思齐 | C02 | 92 |
| S03 | 刘海 | D02 | 述圣 | C01 | 95 |
| S04 | 安然 | D02 | 述圣 | C02 | 78 |
| S05 | 乐天 | D03 | 省身 | C01 | 82 |
对于学生姓名、学生所属的班级编号、院系，这三个属性可以直接通过学生编号来确定，在这里课程编号#显得很多余。也就是，学生姓名、班级编号、院系对（学生编号#、课程编号#）部分函数依赖。把Student表进行拆分，可以消除部分依赖。
其中，学生表Student如下：
| 学生编号 | 学生姓名 | 班级编号 | 院系 |
|---|---|---|---|
| S01 | 杨明 | D01 | 思齐 |
| S02 | 李婉 | D01 | 思齐 |
| S01 | 杨明 | D01 | 思齐 |
| S03 | 刘海 | D02 | 述圣 |
| S04 | 安然 | D02 | 述圣 |
| S05 | 乐天 | D03 | 省身 |
学生-课程表如下：
| 学生编号 | 课程编号 | 成绩 |
|---|---|---|
| S01 | C01 | 90 |
| S02 | C01 | 87 |
| S01 | C02 | 92 |
| S03 | C01 | 95 |
| S04 | C02 | 78 |
| S05 | C01 | 82 |
3NF
分析
定义：在2NF基础上，消除非主属性对键的传递依赖，则称它符合3NF。
第二个不分解为Sno,Sloc的原因
- 保持函数依赖性
- 减少数据冗余：这样会出现不同的学号对应相同的sloc
旧问题解决
把Sno和Sloc的直接关系断掉，Sno依然可以通过先找到对应的Sdept，然后再通过Sdept找到Sloc，效果没变，但是减少了无用的关系。
将新的表命名为SD和DL。
这样我们就把SL这个2NF分解成了两个3NF，一定程度上解决了之前提到的问题：
- 插入异常：新建立的系可以直接放入DL中，与学生无关。
- 删除异常：学生数据在SD中，删除不会影响到DL中的内容。
- 数据冗余大：DL中的Sdept和SLoc的内容只会存储一次。
- 修改复杂：同上，Sloc无重复，如果该系调整住址位置，修改只需要修改一条内容即可。
新问题产生
过度拆分为3NF，可能会有以下缺点：
- 查询效率降低：由于数据表被拆分为多个，查询时可能需要进行多表连接，这会增加查询的时间和复杂度。
- 数据完整性难以保证：由于数据表被拆分为多个，更新时可能需要修改多个表，这会增加更新的时间和复杂度，也可能导致数据不一致的风险。
- 数据冗余仍然存在：即使满足了3NF，数据表中仍然可能存在主属性对候选键的部分或传递函数依赖，这会造成数据冗余和异常。
举例
根据上面对传递依赖的分析，对于Student表，学生编号可以唯一确定他所在的院系，但是注意到这中间存在传递过程，即学生编号唯一确定该学生所对应的班级编号，班级编号对应唯一的院系。我们称，院系对学生编号传递函数依赖。
把Student表继续进行拆分，可以消除传递依赖。
其中，学生表Student如下：
| 学生编号 | 学生姓名 | 班级编号 |
|---|---|---|
| S01 | 杨明 | D01 |
| S02 | 李婉 | D01 |
| S01 | 杨明 | D01 |
| S03 | 刘海 | D02 |
| S04 | 安然 | D02 |
| S05 | 乐天 | D03 |
班级-院系表如下：
| 班级编号 | 院系 |
|---|---|
| D01 | 思齐 |
| D02 | 述圣 |
| D03 | 省身 |
符合3NF。
小结
1NF，2NF和3NF都是关系数据库设计中的范式，用来规范数据表的结构，避免数据冗余和异常。简单来说，它们的区别如下：
- 1NF要求数据表中的每一列都是不可拆分的最小单元，也就是确保每一列的原子性。
- 2NF要求在1NF的基础上，消除非主属性对候选键的部分函数依赖，也就是确保每一列都完全依赖于候选键。
- 3NF要求在2NF的基础上，消除非主属性对候选键的传递函数依赖，也就是确保每一列只直接依赖于候选键。
ch35 BCNF
ch36 多值依赖与4NF
多值依赖
判定方法：对于任意关系中，如果存在两个元组（就是行），记为A,B，如果他们的某一属性X的值相等，那么我们交换它们另外的属性Y的值后，得到的新的两个元组，在表中是可以在原来的表中找到与它们相匹配的元组的。
一对多：和函数（多对一）不同
- 用表和表之间的连接，建立多对一的关系
- 通过组合的方式，枚举一对一的关系
对于C的每一个值，T有一组值与之对应，而不论B取何值。因此T多值依赖于C，即C→→T。
- 数据冗余度大：有多少名任课教师，参考书就要存储多少次。
- 增加操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组。
- 删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组。修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组。
- 产生原因: 存在多值依赖
举例
多值依赖与函数依赖的区别
函数依赖：一夫一妻制下，我只能有一个老婆，所以我决定了我的老婆，反之亦然，这就是函数依赖。
多值依赖：我有3个女朋友，5栋房子。女朋友多值依赖于我，房子也多值依赖于我，因为他们各自的选择与另一者无关（选定房子只与我有关，与女朋友无关，另一组同样）。
平凡的多值依赖：未成年人不允许有女朋友，但是可以有5栋房子，即女朋友为空集，这种情况就是平凡的多值依赖。
练习
- 这个关系不符合2NF。原因如下：
- 2NF的定义是：在一个关系模式中，如果每个非主属性都完全函数依赖于候选码，那么这个关系模式就符合2NF。
- 在这个例子中，假设关系模式为R(员工，部门，经理，日期，零件数)，那么候选码是(员工，日期)，因为它可以决定其他所有属性，而且它的任何真子集都不能决定其他所有属性。
- 在这个例子中，部门和经理这两个非主属性都不完全函数依赖于候选码(员工，日期)，而是部分函数依赖于候选码的一部分(员工)。这就违反了2NF的要求。
- 为了使这个关系模式符合2NF，可以将其分解为两个关系模式：这样就可以消除部门和经理的部分函数依赖。
- R1(员工，部门，经理)，其中员工是候选码
- R2(员工，日期，零件数)，其中(员工，日期)是候选码
- 对于R1(员工，部门，经理)，它的最小函数依赖集为{员工→部门，部门→经理}，根据算法，可以构造两个关系模式：
- R11(员工，部门)，其中员工是候选码
- R12(部门，经理)，其中部门是候选码
- 对于R2(员工，日期，零件数)，它的最小函数依赖集为{(员工，日期)→零件数}，根据算法，可以构造一个关系模式：
- R21(员工，日期，零件数)，其中(员工，日期)是候选码
为什么R12不是（员工，经理）
部门→经理是一个函数依赖，所以R12是(部门，经理)。
如果R12是(员工，经理)，那么就没有体现出部门→经理这个函数依赖，也就没有保持函数依赖性。
如果R12是(员工，经理)，那么就会出现数据冗余，因为同一个部门的多个员工都会有相同的经理。