数据库系统概念 - 关系数据库理论

本节内容

• 关系模式
• 函数依赖
• 范式
• 逻辑蕴含与armstrong公理
• 属性集闭包
• 函数依赖的最小覆盖
• 无损连接分解与保持函数依赖的分解

关系模式

关系模式：关系模式是一个五元组 R（U，D，DOM，F），简记为 R<U, F>。

• R：关系名
• U：组成该关系的属性名集合
• D：属性组U中属性所来自的域
• DOM：属性到域的映射
• F：属性间的依赖集合。它限定了组成关系的各个元组必须满足的完整性约束条件。

当且仅当U上的一个关系r满足F，r称为关系模式R<U, F>的一个关系。

关系模式的设计问题：

1. 信息的不可表示问题：插入异常、删除异常
2. 信息的冗余问题：数据冗余、更新异常

函数依赖 ★

设R(U)是属性集U上的关系模式，X , Y 为 U 的子集，r是R(U)上的任意一个关系，如果总有：

$\forall \ t,s \in r, \ t[X] = s[X] \Rightarrow \ t[Y] = s[Y]$

那么称“X函数决定Y”，或“Y函数依赖于X”，记作

$X \rightarrow Y$

说明

• 任意两元组，若在X属性上取值相同，则Y属性上取值也一定相同。
• 不存在两个X属性值相同但Y属性值不同的两个元组。

平凡函数依赖

在R(U)中，若

$X \rightarrow Y, Y \subseteq X$

则称Y平凡函数依赖于X

部分函数依赖

在R(U)中，若

$X \rightarrow Y, \ \forall X' \subseteq X \ (X' \neq X), \ X' \nrightarrow Y$

则称Y完全函数依赖于X，记为

$X \stackrel{f}{\longrightarrow} Y$

否则称Y部分函数依赖于X，记为

$X \stackrel{p}{\longrightarrow} Y$

传递函数依赖

在R(U)中，若

$X \rightarrow Y, Y \rightarrow Z, Y \nrightarrow X, Z \not\sub Y$

则称Z传递函数依赖于X

码

• 候选码：K为 R<U, F> 的属性组，若 $K \stackrel{f}{\longrightarrow} U$，则称K为R的候选码
• 超码：K为 R<U, F> 的候选码，X为 R<U, F> 的属性组，若 $K \sub X$，则称X为R的超码
• 主码：选定的候选码
• 主属性：包含在每一个候选码中的属性
• 全码：整个属性组U

范式 ★

1NF：关系中每一分量不可再分

不良特性

有关系模式 S(S# , SN , SD , DEAN , C# , G)

• 插入异常：如果学生没有选课，关于他的个人信息及所在系的信息就无法插入
• 删除异常：如果删除学生的选课信息，则有关他的个人信息及所在系的信息也随之删除了
• 更新异常：如果学生转系，若他选修了k门课，则需要修改k次
• 数据冗余：如果一个学生选修了k门课，则有关他的所在系的信息重复

2NF：R属于1NF，且每个非主属性完全依赖于码

2NF消除了非主属性对码的部分依赖。

单主属性不存在部分函数依赖，即一个属性组成的属性集X，若Y依赖于X，则一定为完全函数依赖。

不良特性

有关系模式 S_SD(S# , SN , SD , DEAN)

• 插入异常：若系中没有学生，则与系有关的信息就无法插入
• 删除异常：如果学生全部毕业了，则在删除学生信息的同时与系有关的信息也随之删除了
• 更新异常：如果学生转系，不但要修改SD，还要修改DEAN，如果换系主任，则该系每个学生元组都要做相应修改
• 数据冗余：每个学生都存储了所在系的系主任的信息

3NF：在满足2NF的条件下消除非主属性对码的传递函数依赖。

不良特性

STC(S# , T# , C#)，T# -> C#，每位老师只教授一门课;
（S#，C#）-> T#， 某学生选定一门课，就对应一位老师;
（S#，T#）-> C#;
（S#，T#），（S#，C#）为候选码。

• 插入异常：如果没有学生选修某位老师的任课，则该老师担任课程的信息就无法插入
• 删除异常：删除学生选课信息，会删除掉老师的任课信息
• 更新异常：如果老师所教授的课程有所改动，则所有选修该老师课程的学生元组都要做改动
• 数据冗余：每位学生都存储了有关老师所教授的课程的信息

BCNF：关系模式R<U, F>中，对于属性组X、Y，当

$X \to Y, \ Y \not\sub X$

时（即存在X到Y的非平凡函数依赖），X 必含有码（即X是超码）。

属于BCNF的关系一定属于3NF，反之不一定成立；若R属于3NF，且R只有一个候选码，则R属于BCNF。

Armstrong 公理系统

逻辑蕴含

关系模式R，F是其函数依赖，X，Y是其属性子集，如果从F的函数依赖能够推出X -> Y，则称F逻辑蕴涵X -> Y，记作F├ X -> Y 。

F的闭包：被F所逻辑蕴涵的函数依赖的全体所构成的集合称作F的闭包，记作F⁺ = {X -> Y | F├ X -> Y}

Armstrong 公理

若X，Y，Z是属性集，则下列规则成立：

自反律(reflexivity)：

$Y \sube X \Rightarrow X \to Y$

增广律(augmentation)：

$X \to Y \Rightarrow XZ \to YZ$

传递律(transitivity)：

$X \to Y, \ Y \to Z \Rightarrow X \to Z$

推理规则：

合并律：

$X \to Y, \ Y \to Z \Rightarrow X \to YZ$

分解律：

$X \to YZ \Rightarrow X \to Y, \ Y \to Z$

伪传递律：

$X \to Y, \ WY \to Z \Rightarrow WX \to Z$

引理一：

$X \to A_1A_2\cdots A_k \Rightarrow X\to A_i \ (i=1, 2,\cdots ,k)$

属性集的闭包★：X_F⁺ 为属性集X关于F函数依赖集的闭包

$X^+_F = \{ A | X \to A \ 能由 Armstrong 公理导出 \}$

计算属性集的闭包：

引理二★：

$X \to A \ 能由 Armstrong 公理导出 \iff A \sube X_F^+$

用途：

• 判断X是否为超码/候选码：X->U是否成立（超码），X的真子集是否决定U（候选码）
• ★ 判断 F是否逻辑蕴涵 X->Y ：即判断 Y 是否包含于 X_F⁺

函数依赖的等价与最小覆盖 ▲

等价性：函数依赖集F，G，若F⁺=G⁺，则称F和G等价。

最小覆盖Fmin：

1. （右侧）单属性化
2. （左侧）既约化
3. 无冗余化

模式分解

关系模式R<U , F>的一个分解是指

$\rho = \{ R_1<U_1, F_1>, R_2<U_2, F_2>, \cdots, R_n<U_n, F_n> \}$

其中：

$U=\bigcup_{i=1}^n U_i \ , \ 没有 \ U_i \sube U_j \ (1 \leq i,j \leq n)$

F_i是F在U_i上的投影

分解的基本代数运算：投影，自然连接

分解的目标：无损连接分解，保持函数依赖，达到更高级范式

无损连接分解

无损连接分解的充要条件：

$\rho = \{R_1, R_2\} \ 为无损连接分解 \iff R_1 \cap R2 \to R_1 - R_2 \ or \ R_2 - R_1$

保持函数依赖的分解

$\rho = \{R_1, R_2, \cdots , R_n\} \ 为保持函数依赖的分解$

$\iff F^+ = (\bigcup_{i=1}^n \Pi_{R_i} (F))^+$

$\iff F \sube (\bigcup_{i=1}^n F_i)^+$

判定方法：如果没有给定F1，F2，……，Fn，先求之。求所有模式的依赖集的并集

$G = \bigcup_{i=1}^n F_i$

对F中所有函数依赖X -> Y，检查是否在G⁺中，即判断Y是否在X_G⁺中。

---

[例] 设关系模式R(ABCD)，在R上有两个相应的函数依赖集及分解：F =｛A→B，B→C, C→D｝，ρ=｛AB，ACD｝回答下列问题：

1. 确定R的码
2. ρ是否无损分解；
3. ρ是否保持函数依赖；
4. 确定ρ中每一模式的范式级别

[解]

（1） A_F⁺=ABCD， B_F⁺=CD， C_F⁺=BCD， D_F⁺=D。故A是码。

（2）ρ是无损分解

$AB \cap ACD = A,\ AB-ACD = B, A\to B 成立$

（3）ρ不保持函数依赖

$F_1 = \{ A\to B \}, \ F_2 = \{ A\to C, A\to D, C\to D \}, \ G = F_1 \cup F_2$

$\because B\to C \in F, B_G^+=B, C\not\in B_G^+, \ \therefore B\to C \not\in G$

（4）

$R_1 \in BCNF , \ R_2 \in 2NF$

R₂中 D 传递依赖于 A。

---

模式分解算法（略）