数据库系统 | 第六章 关系数据理论
问题的提出
-
关系数据库逻辑设计
- 针对具体问题,如何构造一个适合于它的数据模式
- 数据库逻辑设计的工具──关系数据库的规范化理论
-
关系模式由五部分组成,是一个五元组:
R(U, D, DOM, F)
- 关系名R是符号化的元组语义
- U为一组属性
- D为属性组U中的属性所来自的域
- DOM为属性到域的映射
- F为属性组U上的一组数据依赖
-
由于D、DOM与模式设计关系不大,因此在本章中把关系模式看作一个三元组:R<U,F>
-
当且仅当U上的一个关系r满足F时,r称为关系模式R<U,F>的一个关系
-
作为二维表,关系要符合一个最基本的条件:每个分量必须是不可分开的数据项。满足了这个条件的关系模式就属于第一范式(1NF)
-
数据依赖
- 是一个关系内部属性与属性之间的一种约束关系
- 通过属性间值的相等与否体现出来的数据间相互联系
- 是现实世界属性间相互联系的抽象
- 是数据内在的性质
- 是语义的体现
-
数据依赖的主要类型
- 函数依赖(Functional Dependency,简记为FD)
- 多值依赖(Multi-Valued Dependency,简记为MVD)
-
函数依赖普遍存在于现实生活中
- 描述一个学生关系,可以有学号、姓名、系名等属性。
- 一个学号只对应一个学生,一个学生只在一个系中学习
- “学号”值确定后,学生的姓名及所在系的值就被唯一确定。
- Sname=f(Sno),Sdept=f(Sno)
- 即Sno函数决定Sname
- Sno函数决定Sdept
- 记作Sno→Sname,Sno→Sdept
-
[例6.1] 建立一个描述学校教务的数据库。涉及的对象包括:
- 学生的学号(Sno)
- 所在系(Sdept)
- 系主任姓名(Mname)
- 课程号(Cno)
- 成绩(Grade)
-
假设学校教务的数据库模式用一个单一的关系模式Student来表示,则该关系模式的属性集合为:U ={Sno, Sdept, Mname, Cno, Grade}
- 现实世界的已知事实(语义):
- 一个系有若干学生, 但一个学生只属于一个系;
- 一个系只有一名(正职)负责人;
- 一个学生可以选修多门课程,每门课程有若干学生选修;
- 每个学生学习每一门课程有一个成绩。
- 现实世界的已知事实(语义):
-
由此可得到属性组U上的一组函数依赖F:
F={Sno→Sdept, Sdept→ Mname, (Sno, Cno)→ Grade} -
关系模式Student<U, F>中存在的问题:
(1)数据冗余- 浪费大量的存储空间
- 每一个系主任的姓名重复出现,重复次数与该系所有学生的所有课程成绩出现次数相同。
(2)更新异常(Update Anomalies)
- 数据冗余 ,更新数据时,维护数据完整性代价大。
- 某系更换系主任后,必须修改与该系学生有关的每一个元组。
(3)插入异常(Insertion Anomalies)
- 如果一个系刚成立,尚无学生,则无法把这个系及其系主任的信息存入数据库。
(4)删除异常(Deletion Anomalies)
- 如果某个系的学生全部毕业了, 则在删除该系学生信息的同时,把这个系及其系主任的信息也丢掉了。
- 浪费大量的存储空间
-
结论
- Student关系模式不是一个好的模式。
- 一个“好”的模式应当不会发生插入异常、删除异常和更新异常,数据冗余应尽可能少。
-
原因
由存在于模式中的某些数据依赖引起的。 -
解决方法
用规范化理论改造关系模式来消除其中不合适的数据依赖 -
把这个单一的模式分成三个关系模式:
- S(Sno,Sdept,Sno → Sdept);
- SC(Sno,Cno,Grade,(Sno,Cno) → Grade);
- DEPT(Sdept,Mname,Sdept → Mname);
-
这三个模式都不会发生插入异常、删除异常的问题,数据的冗余也得到了控制。
规范化
函数依赖
-
定义6.1
设R(U)是一个属性集U上的关系模式,X和Y是U的子集。若对于R(U)的任意一个可能的关系r,r 中不可能存在两个元组在X上的属性值相等, 而在Y上的属性值不等, 则称“X函数确定Y”或“Y函数依赖于X”,记作X→Y。
-
[例] Student(Sno, Sname, Ssex, Sage, Sdept),
假设不允许重名,则有:
Sno → Ssex, Sno → Sage
Sno → Sdept, Sno ←→ Sname
Sname → Ssex, Sname → Sage
Sname → Sdept
但Ssex →Sage, Ssex→ Sdept若X→Y,并且Y→X, 则记为X←→Y。
若Y不函数依赖于X, 则记为X→Y。 -
X→Y,但Y⊈X则称X→Y是非平凡的函数依赖。
-
X→Y,但Y⊆X 则称X→Y是平凡的函数依赖。
-
对于任一关系模式,平凡函数依赖都是必然成立的,它不反映新的语义。
若不特别声明, 我们总是讨论非平凡函数依赖。 -
若X→Y,则X称为这个函数依赖的决定因素(Determinant)。
若X→Y,Y→X,则记作X←→Y。
若Y不函数依赖于X,则记作X↛Y。
- 定义6.3 在R(U)中,如果X→Y(Y⊈X),Y↛X,Y→Z,Z⊈Y, 则称Z对X传递函数依赖(transitive functional dependency)。记为:X → Z。
注: 如果Y→X, 即X←→Y,则Z直接依赖于X,而不是传递函数依赖。
[例] 在关系Std(Sno, Sdept, Mname)中,有:
Sno → Sdept,Sdept → Mname,
Mname传递函数依赖于Sno
码
-
定义6.4
设K为R<U,F>中的属性或属性组合。若K → U,则K称为R的一个候选码(Candidate Key)。唯一标识实体的属性或属性组合称为码
如果U部分函数依赖于K,即K → U,则K称为超码 (Surpkey)。候选码是最小的超码,即K的任意一个真子集都不是候选码。 -
若关系模式R有多个候选码,则选定其中的一个做为主码(Primary key)。
-
主属性与非主属性
包含在任何一个候选码中的属性 ,称为主属性 (Prime attribute)
不包含在任何码中的属性称为非主属性(Nonprime attribute)或非码属性(Non-key attribute) -
全码:整个属性组是码,称为全码(All-key)
-
主码=主键=主关键字,
关键字=候选码
候选关键字=候选码中除去主码的其他候选码 -
[例6.2]S(Sno, Sdept, Sage),单个属性Sno是码
SC(Sno, Cno, Grade)中,(Sno, Cno)是码 -
[例6.3] R(P,W,A) P:演奏者 W:作品 A:听众
一个演奏者可以演奏多个作品
某一作品可被多个演奏者演奏
听众可以欣赏不同演奏者的不同作品
码为(P,W,A),即All-Key -
定义6.5 关系模式 R中属性或属性组X 并非 R的码,但 X 是另一个关系模式的码,则称 X 是R 的外部码(Foreign key)也称外码。
- SC(Sno,Cno,Grade)中,Sno不是码
- Sno是 S(Sno,Sdept,Sage)的码,则Sno是SC的外码
-
主码与外部码一起提供了表示关系间联系的手段
范式
-
范式是符合某一种级别的关系模式的集合。
-
作为二维表,关系要符合一个最基本的条件:每个分量必须是不可分开的数据项。满足了这个条件的关系模式就属于第一范式(1NF)
-
关系数据库中的关系必须满足一定的要求。满足 不同程度要求的为不同范式。
-
范式的种类
- 第一范式(1NF)
- 第二范式(2NF)
- 第三范式(3NF)
- BC范式(BCNF)
- 第四范式(4NF)
- 第五范式(5NF)
-
各种范式之间存在联系:
某一关系模式R为第n范式,可简记为R∈nNF。 -
一个低一级范式的关系模式,通过模式分解(schema decomposition)可以转换为若干个高一级范式的关系模式的集合,这种过程就叫规范化(normalization)。
2NF
-
定义6.6 若关系模式R∈1NF,并且每一个非主属性都完全函数依赖于任何一个候选码,则R∈2NF
-
[例6.4] S-L-C(Sno,Sdept,Sloc,Cno,Grade), Sloc为学生的住处,并且每个系的学生住在同一个地方。S-L-C的码为(Sno,Cno)。
函数依赖有- (Sno,Cno)→Grade
- Sno→Sdept, (Sno,Cno)→Sdept
- Sno→Sloc, (Sno,Cno)→Sloc
- Sdept→Sloc
-
一个关系模式不属于2NF,会产生以下问题:
- 插入异常
如果插入一个新学生,但该生未选课,即该生无Cno,由于插入元组时,必须给定码值,因此插入失败。 - 删除异常
如果S4只选了一门课C3,现在他不再选这门课,则删除C3后,整个元组的其他信息也被删除了。 - 修改复杂
如果一个学生选了多门课,则Sdept,Sloc被存储了多次。如果该生转系,则需要修改所有相关的Sdept和Sloc,造成修改的复杂化。
- 插入异常
-
出现这种问题的原因
- 例子中有两类非主属性:
- 一类如Grade,它对码完全函数依赖
- 另一类如Sdept、Sloc,它们对码不是完全函数依赖
- 例子中有两类非主属性:
-
解决方法:
- 用投影分解把关系模式S-L-C分解成两个关系模式
- SC(Sno,Cno,Grade)
- S-L(Sno,Sdept,Sloc)
- 用投影分解把关系模式S-L-C分解成两个关系模式
-
SC的码为(Sno,Cno),SL的码为Sno,这样使得非主属性对候选码都是完全函数依赖了,单关键字的数据库表都符合第二范式
3NF
-
定义6.7(无传递函数依赖即3NF)
设关系模式R<U,F>∈1NF,若R中不存在这样的码X、属性组Y(非码)及非主属性Z(Z ⊈ Y), 使得X→Y(Y⊈X,Y ↛ X),Y→Z成立,则称R<U,F> ∈ 3NF。
- SC没有传递依赖,因此SC ∈ 3NF
- S-L中Sno →Sdept( Sdept ↛ Sno), Sdept→Sloc,可得Sno → Sloc。
- 解决的办法是将S-L分解成
- S-D(Sno,Sdept)∈ 3NF
- D-L(Sdept,Sloc)∈ 3NF
-
基于2NF,非主属性不能函数依赖于非码。此外,非主属性只能存在一个表中,不应该存在多个表中;
BCNF
-
BCNF(Boyce Codd Normal Form)由Boyce和Codd提出,比3NF更进了一步。通常认为BCNF是修正的第三范式,有时也称为扩充的第三范式。
-
定义6.8
设关系模式R<U,F>∈1NF,若X →Y且Y ⊆ X时X必含有码,则R<U,F>∈BCNF。
-
换言之,在关系模式R<U,F>中,如果每一个决定属性集都包含候选码,则R∈BCNF。
-
BCNF的关系模式所具有的性质
- 所有非主属性都完全函数依赖于每个候选码(2NF)
- 所有主属性都完全函数依赖于每个不包含它的候选码(BCNF)
- 没有任何属性完全函数依赖于非码的任何一组属性(3NF+)
-
如果一个关系数据库中的所有关系模式都属于BCNF,那么在函数依赖范畴内,它已实现了模式的彻底分解,达到了最高的规范化程度,消除了插入异常和删除异常。
-
[例6.5]考察关系模式C(Cno,Cname,Pcno)
-
[例6.6] 关系模式S(Sno,Sname,Sdept,Sage),
- 假定Sname也具有唯一性,那么S就有两个码,这两个码都由单个属性组成,彼此不相交。
- 其他属性不存在对码的传递依赖与部分依赖,所以S∈3NF。
- 同时S中除Sno,Sname外没有其他决定因素,所以S也属于BCNF。
-
[例6.7] 关系模式SJP(S,J,P)中,S是学生,J表示
课程,P表示名次。每一个学生选修每门课程的成绩有一定的名次,每门课程中每一名次只有一个学生(即没有并列名次)。-
由语义可得到函数依赖: (S,J)→P;(J,P)→S(S,J)与(J,P)都可以作为候选码。
-
关系模式中没有属性对码传递依赖或部分依赖,所以 SJP∈3NF。
-
除(S,J)与(J,P)以外没有其他决定因素,所以SJP∈BCNF。
-
-
[例6.8] 关系模式STJ(S,T,J)中,S表示学生,T表示教师,J表示课程。每一教师只教一门课。每门课有若干教师,某一学生选定某门课,就对应一个固定的教师。
- 由语义可得到函数依赖:(S,J)→T;(S,T)→J;T→J
- 因为没有任何非主属性对码传递依赖或部分依赖,STJ ∈ 3NF。
- 因为T是决定因素,而T不包含码,所以STJ ∈ BCNF关系。BCNF每个属性均完全依赖于每个候选码(不含它)
-
对于不是BCNF的关系模式,仍然存在不合适的地方。
-
非BCNF的关系模式也可以通过分解成为BCNF。例如STJ可分解为ST(S,T)与TJ(T,J),它们都是BCNF。
-
3NF和BCNF是在函数依赖的条件下对模式分解所能达到的分离程度的测度。
- 一个模式中的关系模式如果都属于BCNF,那么在函数依赖范畴内,它已实现了彻底的分离,已消除了插入和删除的异常。
- 3NF的“不彻底”性表现在可能存在主属性对码的部分依赖和传递依赖。
规范化小结
-
在关系数据库中,对关系模式的基本要求是满足第一范式。
-
规范化程度过低的关系不一定能够很好地描述现实世界
- 可能存在插入异常、删除异常、修改复杂、数据冗余等问题
- 解决方法就是对其进行规范化,转换成高级范式。
-
一个低一级范式的关系模式,通过模式分解可以转换为若干个高一级范式的关系模式集合,这种过程就叫关系模式的规范化。
-
关系数据库的规范化理论是数据库逻辑设计的工具。
-
规范化的基本思想
- 是逐步消除数据依赖中不合适的部分,使模式中的各关系模式达到某种程度的“分离”。
- 即采用“一事一地”的模式设计原则
- 让一个关系描述一个概念、一个实体或者实体间的一种联系。
- 若多于一个概念就把它“分离”出去。
- 因此 规范化实质上是概念的单一化。
数据依赖的公理系统
-
一套推理规则,是模式分解算法的理论基础
-
用途
- 求给定关系模式的码
- 从一组函数依赖求得蕴涵的函数依赖
-
Armstrong公理系统 设U为属性集总体,F是U上的一组函数依赖, 于是有关系模式R <U,F >。对R <U,F> 来说有以下的推理规则:
- A1 自反律(reflexivity rule):若Y X U,则X →Y 为F所蕴涵。
- A2 增广律(augmentation rule):若X→Y为F所蕴涵,且Z U,则XZ→YZ 为F所蕴涵。
- A3 传递律(transitivity rule):若X→Y及Y→Z为F所蕴涵,则X→Z 为F所蕴涵。
-
根据A1,A2,A3这三条推理规则可以得到下面三条推理规则:
- 合并规则(union rule):
由X→Y,X→Z,有X→YZ。 - 伪传递规则(pseudo transitivity rule):
由X→Y,WY→Z,有XW→Z。 - 分解规则(decomposition rule):
由X→Y及ZY,有X→Z。
- 合并规则(union rule):
-
定义6.12
在关系模式R<U,F>中为F所逻辑蕴涵的函数依赖的全体叫作F的闭包,记为F +。
-
定义6.13
设F为属性集U上的一组函数依赖,X、Y U, XF+={ A|X→A能由F根据Armstrong公理导出},XF+称为属性集X关于函数依赖集F的闭包。
-
有效性与完备性的含义
- 有效性:由F 出发根据Armstrong公理推导出来的每一个函数依赖一定在F +中
- 完备性:F +中的每一个函数依赖,必定可以由F出发根据Armstrong公理推导出来
小结
- 若要求分解具有无损连接性,那么模式分解一定能够达到4NF。
- 若要求分解保持函数依赖,那么模式分解一定能够达到3NF,但不一定能够达到BCNF。
- 若分解既具有无损连接性,又保持函数依赖,则模式分解一定能够达到3NF,但不一定能够达到BCNF。
掘金:前端LeBron
知乎:前端LeBron
持续分享技术博文,关注微信公众号👇🏻