关系数据理论

一、问题的提出

关系数据库逻辑设计

• 针对具体问题，如何构造一个适合于它的数据模式
• 数据库逻辑设计的工具──关系数据库的规范化理论

关系模式由五部分组成，是一个五元组：

R(U, D, DOM, F)

• 关系名R是符号化的元组语义
• U为一组属性
• D为属性组U中的属性所来自的域
• DOM为属性到域的映射
• F为属性组U上的一组数据依赖

数据依赖

• 是一个关系内部属性与属性之间的一种约束关系
  • 通过属性间值的相等与否体现出来的数据间相互联系
• 是现实世界属性间相互联系的抽象
• 是数据内在的性质
• 是语义的体现

数据依赖的主要类型

• 函数依赖（Functional Dependency，简记为FD）
• 多值依赖（Multi-Valued Dependency，简记为MVD）

函数依赖普遍存在于现实生活中

• 描述一个学生关系，可以有学号、姓名、系名等属性。
  • 一个学号只对应一个学生，一个学生只在一个系中学习
  • “学号”值确定后，学生的姓名及所在系的值就被唯一确定。
• Sname=f(Sno)，Sdept=f(Sno)
  • 即Sno函数决定Sname
  • Sno函数决定Sdept
  • 记作Sno→Sname，Sno→Sdept

[例] 建立一个描述学校教务的数据库。涉及的对象包括：

• 学生的学号（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);

这三个模式都不会发生插入异常、删除异常的问题，数据的冗余也得到了控制。

二、规范化

1、函数依赖

1.1.函数依赖

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

函数依赖是语义范畴的概念，只能根据数据的语义来确定一个函数依赖。

例如“姓名→年龄”这个函数依赖只有在不允许有同名人的条件下成立

1.2.平凡函数依赖与非平凡函数依赖

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。

1.3.完全函数依赖与部分函数依赖

定义在R(U)中，如果X→Y，并且对于X的任何一个真子集X’, 都有 X’ ↛ Y, 则称Y对X完全函数依赖，记作X → Y。

若X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作X → Y

1.4.传递函数依赖

定义 在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

2、码

定义 设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）

[例]S(Sno, Sdept, Sage)，单个属性Sno是码

SC(Sno, Cno, Grade)中，(Sno, Cno)是码

定义 关系模式 R中属性或属性组X 并非 R的码，但 X 是另一个关系模式的码，则称 X 是R 的外部码（Foreign key）也称外码。

SC(Sno,Cno,Grade)中，Sno不是码

Sno是 S(Sno,Sdept,Sage)的码，则Sno是SC的外码

主码与外部码一起提供了表示关系间联系的手段

3、范式

范式是符合某一种级别的关系模式的集合。

关系数据库中的关系必须满足一定的要求。满足 不同程度要求的为不同范式。

范式的种类：

各种范式之间存在联系：

某一关系模式R为第n范式，可简记为R∈nNF。

一个低一级范式的关系模式，通过模式分解（schema decomposition）可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化（normalization）。

4、2NF

定义 若关系模式R∈1NF，并且每一个非主属性都完全函数依赖于任何一个候选码，则R∈2NF

[例] S-L-C(Sno,Sdept,Sloc,Cno,Grade)， Sloc为学生的住处，并且每个系的学生住在同一个地方。S-L-C的码为(Sno,Cno)。

函数依赖有：

非主属性Sdept、Sloc并不完全依赖于码

关系模式S-L-C不属于2NF

一个关系模式不属于2NF，会产生以下问题：

插入异常

如果插入一个新学生，但该生未选课，即该生无Cno，由于插入元组时，必须给定码值，因此插入失败。

删除异常

如果S4只选了一门课C3，现在他不再选这门课，则删除C3后，整个元组的其他信息也被删除了。

修改复杂

如果一个学生选了多门课，则Sdept，Sloc被存储了多次。如果该生转系，则需要修改所有相关的Sdept和Sloc，造成修改的复杂化。

出现这种问题的原因

例子中有两类非主属性：

• 一类如Grade，它对码完全函数依赖
• 另一类如Sdept、Sloc，它们对码不是完全函数依赖

解决方法：

用投影分解把关系模式S-L-C分解成两个关系模式

SC(Sno,Cno,Grade)

S-L(Sno,Sdept,Sloc)

5、3NF

定义 设关系模式R<U,F>∈1NF,若R中不存在这样的码X、属性组Y及非主属性Z（Z ⊇ Y）, 使得X→Y，Y→Z成立，Y ↛ X不成立，则称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

6、BCNF

BCNF（Boyce Codd Normal Form）由Boyce和Codd提出，比3NF更进了一步。通常认为BCNF是修正的第三范式，有时也称为扩充的第三范式。

定义 设关系模式R<U,F>∈1NF，若X →Y且Y ⊆ X时X必含有码，则R<U,F>∈BCNF。

在关系模式R<U,F>中，如果每一个决定属性集都包含候选码，则R∈BCNF。

BCNF的关系模式所具有的性质

• 所有非主属性都完全函数依赖于每个候选码
• 所有主属性都完全函数依赖于每个不包含它的候选码
• 没有任何属性完全函数依赖于非码的任何一组属性

如果一个关系数据库中的所有关系模式都属于BCNF，那么在函数依赖范畴内，它已实现了模式的彻底分解，达到了最高的规范化程度，消除了插入异常和删除异常。

7、多值依赖

定义 设R(U)是属性集U上的一个关系模式。X,Y,Z是U的子集，并且Z=U-X-Y。关系模式R(U)中多值依赖X→→Y成立，当且仅当对R(U)的任一关系r，给定的一对(x,z)值，有一组Y的值，这组值仅仅决定于x值而与z值无关。

多值依赖的另一个等价的定义

在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。

平凡多值依赖和非平凡的多值依赖

• 若X→→Y，而Z＝Ф，即Z为空，则称X→→Y为平凡的多值依赖。
• 否则称X→→Y为非平凡的多值依赖。

多值依赖的性质

（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→→YZ。

（5）若X→→Y，X→→Z，则X→→Y∩Z。

（6）若X→→Y，X→→Z，则X→→Y-Z，X→→Z -Y。

8、4NF

定义 关系模式R<U,F>∈1NF，如果对于R的每个非平凡多值依赖X→→Y（Y ⊈ X），X都含有码，则R<U,F>∈4NF。

4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。4NF所允许的非平凡多值依赖实际上是函数依赖。

9、规范化小结

规范化的基本思想

• 是逐步消除数据依赖中不合适的部分，使模式中的各关系模式达到某种程度的“分离”。
• 即采用“一事一地”的模式设计原则
  • 让一个关系描述一个概念、一个实体或者实体间的一种联系。
  • 若多于一个概念就把它“分离”出去。
• 因此 规范化实质上是概念的单一化

三、数据依赖的公理系统

定义 对于满足一组函数依赖F的关系模式 R <U,F>，其任何一个关系r，若函数依赖X→Y都成立（即r中任意两元组t、s，若t[X]=s[X]，则 t[Y]=s[Y]），则称F逻辑蕴涵X →Y

Armstrong公理系统

• 一套推理规则，是模式分解算法的理论基础
• 用途
  • 求给定关系模式的码
  • 从一组函数依赖求得蕴涵的函数依赖

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所蕴涵。

  注意：由自反律所得到的函数依赖均是平凡的函数依赖, 自反律的使用并不依赖于F。

定义 在关系模式R<U,F>中为F所逻辑蕴涵的函数依赖的全体叫作F的闭包，记为F +。

定义 设F为属性集U上的一组函数依赖，X、Y U， XF+={ A|X→A能由F根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F的闭包。

求闭包的算法

求属性集X（X 包含于 U）关于U上的函数依赖集F的闭包XF+

输入：X，F

输出：XF+

步骤：

[例] 已知关系模式R<U, F>，其中

U={A, B, C, D, E}；

F={AB→C, B→D, C→E, EC→B, AC→B}。

求(AB)F+ 。

小结

关系模式的规范化，其基本思想：

• 若要求分解具有无损连接性，那么模式分解一定能够达到4NF。
• 若要求分解保持函数依赖，那么模式分解一定能够达到3NF，但不一定能够达到BCNF。
• 若分解既具有无损连接性，又保持函数依赖，则模式分解一定能够达到3NF，但不一定能够达到BCNF。

规范化理论为数据库设计提供理论的指南和工具

仅仅是指南和工具

并不是规范化程度越高，模式就越好

必须结合应用环境和现实世界的具体情况合理地选择数据库模式