数据库原理 | 7. 关系数据理论

思维导图

• 关系数据理论
  • 问题的提出
  • 函数依赖
    • 函数依赖
    • 平凡函数依赖与非平凡函数依赖
    • 完全函数依赖与部分函数依赖
    • 传递函数依赖
  • 码
  • 范式
    • 1NF
    • 2NF
      • SLC不是一个好的关系模式
      • 原因及解决办法
      • 2NF的定义
    • 3NF
      • 解决方法
      • 3NF的定义
    • BC 范式
      • 解决方法
      • 3NF与BCNF的关系
      • BCNF的关系模式所具有的性质
    • 规范化
      • 关系模式规范化的基本步骤
      • 规范化的基本思想
  • 数据依赖的公理系统
    • Armstrong公理系统
    • 导出规则
    • 函数依赖闭包
      • 关于闭包的引理
    • 函数依赖集等价
      • 最小依赖集
      • 极小化过程

问题的提出

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

函数依赖

函数依赖

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

1. 函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。
2. 函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。
   例如“姓名→年龄”这个函数依赖只有在不允许有同名人的条件下成立
3. 数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖“姓名→年龄”成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在， 则拒绝装入该元组。

例
Student(Sno, Sname, Ssex, Sage, Sdept)
假设不允许重名，则有:
$Sno \rightarrow Ssex$， $Sno \rightarrow Sage$ , $Sno \rightarrow Sdept$，
$Sno \leftarrow \rightarrow Sname, Sname \rightarrow Ssex, Sname \rightarrow Sage$
$Sname \rightarrow Sdept$
但$Ssex \rightarrow Sage$
若$X\rightarrow Y$，并且$Y\rightarrow X$, 则记为$X\leftarrow \rightarrow Y$。
若Y不函数依赖于X, 则记为$X\not\rightarrow Y$。

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

在关系模式$R(U)$中，对于$U$的子集$X$和$Y$，
如果$X\rightarrow Y$，但$Y\not\subseteq X$，则称X→Y是非平凡的函数依赖
若$X\rightarrow Y$，但$Y\subseteq X$, 则称$X\rightarrow Y$是平凡的函数依赖

例
在关系$SC(Sno, Cno, Grade)$中，

1. 非平凡函数依赖： $(Sno, Cno) \rightarrow Grade$
2. 平凡函数依赖： $(Sno, Cno) \rightarrow Sno$, $(Sno, Cno) \rightarrow Cno$

任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别声明， 我们总是讨论非平凡函数依赖。

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

在关系模式$R(U)$中，如果$X\rightarrow Y$，并且对于X的任何一个真子集$X'$，都有

• 若$X'\not\rightarrow Y$, 则称$Y$完全函数依赖于$X$，记作$X\mathop{\rightarrow}\limits^{f} Y$。
• 若$X\rightarrow Y$，但Y不完全函数依赖于X，则称Y部分函数依赖于$X$，记作$X \mathop{\rightarrow}\limits^{P} Y$。

传递函数依赖

在关系模式$R(U)$中，如果$X\rightarrow Y$，$Y\rightarrow Z$，且$Y\not\subseteq X$，$Y\rightarrow X$，则称$Z$传递函数依赖于$X$。
注: 如果$Y\rightarrow X$， 即$X\leftarrow \rightarrow Y$，则$Z$直接依赖于$X$。

例
在关系$Std(Sno, Sdept, Sloc)$中，有：
$Sno \rightarrow Sdept$，$Sdept \rightarrow Sloc$
$Sloc$传递函数依赖于$Sno$

码

设K为关系模式$R<U,F>$中的属性或属性组合。若$K \mathop{\rightarrow}\limits^{f} U$，则K称为R的一个候选码（Candidate Key）。若关系模式R有多个候选码，则选定其中的一个做为主码（Primary key）。

范式

• 范式是符合某一种级别的关系模式的集合。
• 关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。
• 范式的种类：
  • 第一范式(1NF)
  • 第二范式(2NF)
  • 第三范式(3NF)
  • BC范式(BCNF)
  • 第四范式(4NF)
  • 第五范式(5NF)
• 各种范式之间存在联系：
  • $1\mathrm{NF} \supset 2\mathrm{NF} \supset 3\mathrm{NF} \supset \mathrm{BCNF} \supset 4\mathrm{NF} \supset 5\mathrm{NF}F$
• 某一关系模式R为第n范式，可简记为$R\in n\mathrm{NF}$。

1NF

• 1NF的定义
  • 如果一个关系模式R的所有属性都是不可分的基本数据项，则$R\in 1\mathrm{NF}$。
  • 第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。
  • 但是满足第一范式的关系模式并不一定是一个好的关系模式。

2NF

• 例: 关系模式 SLC(Sno, Sdept, Sloc, Cno, Grade)

• Sloc为学生住处，假设每个系的学生住在同一个地方。
  

• 函数依赖包括：

  • $(Sno, Cno) \mathop{\rightarrow}\limits^f Grade$
  • $Sno \mathop{\rightarrow} Sdept$
  • $(Sno, Cno) \mathop{\rightarrow}\limits^P Sdept$
  • $Sno \mathop{\rightarrow} Sloc$
  • $(Sno, Cno) \mathop{\rightarrow}\limits^P Sloc$
  • $Sdept \mathop{\rightarrow} Sloc$

• SLC的码为(Sno, Cno)
• SLC满足第一范式。
• 非主属性Sdept和Sloc部分函数依赖于码(Sno, Cno)

SLC不是一个好的关系模式

1. 插入异常
   假设Sno＝95102，Sdept＝IS，Sloc＝N的学生还未选课，因课程号是主属性，因此该学生的信息无法插入SLC。
2. 删除异常
   假定某个学生本来只选修了3号课程这一门课。现在因身体不适，他连3号课程也不选修了。因课程号是主属性，此操作将导致该学生信息的整个元组都要删除。
3. 数据冗余度大
   如果一个学生选修了10门课程，那么他的Sdept和Sloc值就要重复存储了10次。
4. 修改复杂
   例如学生转系，在修改此学生元组的Sdept值的同时，还可能需要修改住处（Sloc）。如果这个学生选修了K门课，则必须无遗漏地修改K个元组中全部Sdept、Sloc信息。

原因及解决办法

• Sdept、 Sloc部分函数依赖于码。
• SLC分解为两个关系模式，以消除这些部分函数依赖
  • SC（Sno， Cno， Grade）
  • SL（Sno， Sdept， Sloc）
    

2NF的定义

• 若关系模式R∈1NF，并且每一个非主属性都完全函数依赖于R的码，则R∈2NF。

  • $SLC(Sno, Sdept, Sloc, Cno, Grade) \in 1NF$
  • $SLC(Sno, Sdept, Sloc, Cno, Grade) \in 2NF$
  • $SC(Sno, Cno, Grade) \in 2NF$
  • $SL(Sno, Sdept, Sloc) \in 2NF$

• 采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。

• 将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。

3NF

• 例：2NF关系模式SL(Sno, Sdept, Sloc)中
  函数依赖：

• $Sno\rightarrow Sdept$

• $Sdept\rightarrow Sloc$

• $Sno\rightarrow Sloc$
  Sloc传递函数依赖于Sno，即SL中存在非主属性对码的传递函数依赖。
  

解决方法

采用投影分解法，把SL分解为两个关系模式，以消除传递函数依赖：

• SD（Sno, Sdept）
• DL（Sdept, Sloc）
  SD的码为Sno， DL的码为Sdept。
  

3NF的定义

关系模式$R<U,F>$中若不存在这样的码X、属性组Y及非主属性Z（$Z\not\subseteq Y$）, 使得$X\rightarrow Y,Y\rightarrow X,Y\rightarrow Z$，成立，则称$R<U,F>\in 3NF$。

• $SL(Sno, Sdept, Sloc) \in 2NF$
• $SL(Sno, Sdept, Sloc) \in 3NF$
• $SD(Sno, Sdept) \in 3NF$
• $DL(Sdept, Sloc)\in 3NF$

---

• 若$R\in 3NF$，则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。
• 如果$R\in 3NF$，则R也是2NF。
• 采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。
• 将一个2NF关系分解为多个3NF的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。

BC 范式

• 设关系模式$R<U,F>\in 1NF$，如果对于R的每个函数依赖$X\rightarrow Y$，若Y不属于X，则X必含有候选码，那么$R\in BCNF$。
• 若$R\in BCNF$
  • 每一个决定属性集（因素）都包含（候选）码
  • R中的所有属性（主，非主属性）都完全函数依赖于码
  • $R\in 3NF$（证明）
  • 若$R\in 3NF$ 则 $R$不一定$\in BCNF$
    例：在关系模式$STJ(S,T,J)$中，S表示学生，T表示教师，J表示课程。
    每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称 ： $(S,J)\rightarrow T,(S,T)\rightarrow J,T\rightarrow J$
    

解决方法

• 将STJ分解为二个关系模式：
• $SJ(S,J) \in BCNF， TJ(T,J)\in BCNF$
• 没有任何属性对码的部分函数依赖和传递函数依赖

3NF与BCNF的关系

• 如果关系模式$R\in BCNF$，必定有$R\in 3NF$
• 如果$R\in 3NF$，且R只有一个候选码，则必定$R\in BCNF$。

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

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

规范化

• 关系数据库的规范化理论是数据库逻辑设计的工具。
• 一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。
• 规范化程度可以有多个不同的级别
• 规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题
• 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化

关系模式规范化的基本步骤

规范化的基本思想

• 消除不合适的数据依赖
• 使模式中的各关系模式达到某种程度的“分离”
• 采用“一事一地”的模式设计原则
  • 让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它“分离”出去
• 所谓规范化实质上是概念的单一化
• 不能说规范化程度越高的关系模式就越好
• 在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式
• 上面的规范化步骤可以在其中任何一步终止

数据依赖的公理系统

对于满足一组函数依赖$F$的关系模式$R<U,F>$，其任何一个关系$r$，若函数依赖$X\rightarrow Y$都成立, 则称F逻辑蕴含$X\rightarrow Y$。

Armstrong公理系统

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

---

关系模式R <U，F >来说有以下的推理规则：

• 自反律（Reflexivity）：若$Y \subseteq X \subseteq U$，则$X\rightarrow Y$为$F$所蕴含。
• 增广律（Augmentation）：若$X\rightarrow Y$为F所蕴含，且$Z \subseteq U$，则$XZ\rightarrow YZ$为$F$所蕴含。
• 传递律（Transitivity）：若$X\rightarrow Y$及$Y\rightarrow Z$为$F$所蕴含，则$X\rightarrow Z$为$F$所蕴含。

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

导出规则

根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：

• 合并规则：由$X\rightarrow Y, X\rightarrow Z$，有$X\rightarrow YZ$。
• 伪传递规则：由$X\rightarrow Y, WY\rightarrow Z$，有$XW\rightarrow Z$。
• 分解规则：由$X\rightarrow Y$及 $Z\subseteq Y$，有$X\rightarrow Z$。

---

• 引理：$X→A_1,A_2\cdots A_k$成立的充分必要条件是$X\rightarrow A_i$成立$(i=l,2,\cdots,k)$。

函数依赖闭包

• 在关系模式R<U，F>中为F所逻辑蕴含的函数依赖的全体叫作F的闭包，记为$F^+$。
• 设F为属性集U上的一组函数依赖，$X\subseteq U$， $X_F^+$ ={A|X→A能由F根据Armstrong公理导出}，$X_F^+$称为属性集X关于函数依赖集F的闭包。

关于闭包的引理

• 内容：设$F$为属性集$U$上的一组函数依赖，$X,Y \subseteq U$，$X\rightarrow Y$能由F 根据Armstrong公理导出的充分必要条件是$Y\subseteq X_F^+$
• 用途：将判定$X\rightarrow Y$是否能由$F$根据Armstrong公理导出的问题，就转化为求出$X_F^+$ ，判定$Y$是否为$X_F^+$的子集的问题。

函数依赖集等价

如果$G^+=F^+$，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。

最小依赖集

如果函数依赖集$F$满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。

• $F$中任一函数依赖的右部仅含有一个属性。
• $F$中不存在这样的函数依赖$X\rightarrow A$，使得$F$与$F-{X\rightarrow A}$等价。
• $F$中不存在这样的函数依赖$X\rightarrow A$， X有真子集$Z$使得$F-{X\rightarrow A}\cup{Z\rightarrow A}$与$F$等价。

极小化过程

每一个函数依赖集$F$均等价于一个极小函数依赖集$F_m$。此$F_m$称为$F$的最小依赖集。