db_5 关系数据理论

问题提出

关系数据库的规范化理论：数据库逻辑设计的有力工具

数据依赖
- 一个关系内部属性值之间相互依赖又相互制约的关系
- 通过属性间值的相等与否体现出的数据间相关联系
- 数据内在性质、语义体现
- 分类
  - 函数依赖
  - 多值依赖

规范化

函数依赖

函数依赖是语义范畴的概念
- 只能根据语义来确定，而不能形式化证明
函数依赖是不随时间而变的
- 若关系R具有函数依赖 $X \to Y$ ，R变 $X \to Y$ 不变

概念

设R(U)是属性集U上的关系模式。X、Y是U的子集。r是R任意一个具体关系，t, s 是r中任意两个元组

如果t[X] = s[X]，则t[Y] = s[Y]，（对于X的每个具体值，Y有唯一的值与之对应）

则称“X函数确定Y”或“Y函数依赖于X”，记作： $X \to Y$

平凡的函数依赖
- $Y \subseteq X ， X \to Y$
非平凡的函数依赖
- $Y \nsubseteq X ， X \to Y$
决定因素
- 对于函数依赖 $X \to Y$ ，则 $X$ 叫做决定因素
不函数依赖
- $X \nrightarrow Y$
$ X \to Y ,Y \to X,\text{则}X\leftarrow\rightarrow Y$

三种函数依赖

完全函数依赖
- $ X \to Y $，且对于任意 $ X $ 的真子集 $ X’ $，都有 $ X’ \not\to Y $，则称 $ X $ 对 $ Y $完全函数依赖，记作 $ X \xrightarrow{F} Y $
部分函数依赖
- $ X \to Y $，$Y$不完全依赖于$X$，记作 $X \xrightarrow{P} Y$ 。
传递函数依赖
- $ X \to Y(Y\nsubseteq X) $，$ Y \to Z(Z\nsubseteq Y) $，且 $ Y \nrightarrow X $，则称 $ Z $ 对 $ X $ 传递函数依赖，记作 $ X \xrightarrow{t} Z $
  
  如果 $Y \rightarrow X$ ，那X、Y等价，就不是传递函数依赖，是一种直接的依赖 $X \rightarrow Z$

码（关系键的形式定义）

候选码
- 主码是任一候选码
- 主码、候选码统称为码
- $ K \xrightarrow{F} U $
- 唯一性
- 最小性
超码
- $ K \xrightarrow{P} U $
- 候选码是最小的超码
主属性
- 包含在任何一个侯选码中的属性
非主属性
- 不包含在任何侯选码中的属性
外部码
- 关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外码

范式

如果一个关系满足某个指定的约束集，则称它属于某种特定的范式

在关系数据库中，都是规范化的关系

规范化：

低一级范式的关系模式可以通过模式分解转换成若干个高一级范式的关系模式的集合

1NF

一个关系只包含原子值这一约束

原子值即为二维表的每一行和列的交叉位置上总是精确地存在一个值，而不是值集

（没有表中套表）

满足“原子值”这一约束条件的关系称为规范化关系，简称范式

2NF

$R\in1NF$
每个非主属性完全依赖于码

注意：

如果关系R的全体属性都是R的主属性，那么$R\in 2NF$
从1NF中消除非主属性对码的部分函数依赖，则可获得2NF关系
- 方法：投影分解
在2NF中，允许主属性部分函数依赖于码
- 例: STC(S, T, C)，S表示学生，T表示教师，C表示课程
- 每位老师只教授一门课,每门课由若干教师教，某一学生选定某门课就确定了一个固定的教师
- T→C，（S，C）→T
- （S，T），（S，C）为候选码
- $(S,T)\xrightarrow{P}C$

3NF

$R\in2NF$
每个非主属性都不传递依赖于R的任何码

关系模式R< U , F >中，若不存在这样的码X，属性组Y及非主属性Z(Z$\nsubseteq$Y)，使得下式成立，X→Y , Y→Z , Y$\nrightarrow$X ,则称R$\in$3NF

如果关系R的全体属性都是R的主属性，那么$R\in 3NF$

投影分解

BCNF

$R\in1NF$
如果对于R的每个函数依赖$X\to Y$，且$Y\nsubseteq X$时，X必含有码

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

4NF

定义1：

R$\in$BCNF，不存在非平凡的非函数依赖的多值依赖
- 当R中只存在函数依赖，则R$\in$4NF
- 或当R中存在平凡的多值依赖时，R$\in$4NF

定义2：

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

模式分解

多值依赖

设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] = s[X] = v[X] = t[X]

w[Y] = t[Y]，v[Y] = s[Y]

w[Z] = s[Z]，v[Z] = t[Z]

（交换s、t的Y值所得的元组一定在r中）

则称Y多值依赖与X，记作X →→Y

平凡的多值依赖
- $X\to\to Y ,Z =$ 空集
非平凡的多值依赖
- $X\to\to Y ,Z \ne$ 空集

对称性
- $X\to\to Y$ ，则$X\to\to Z,Z=U-X-Y$
传递性
- $X\to\to Y, Y\to\to Z$ ，则$X\to\to Z-Y$
$X\to\to Y, X\to\to Z$ ，则$X\to\to YZ$
$X\to\to Y, X\to\to Z$ ，则$X\to\to Y\cap Z$
$X\to\to Y, X\to\to Z$ ，则$X\to\to Y-Z,X\to\to Z-Y$
函数依赖是多值依赖的特殊情况
- $X\to Y$则$X\to\to Y$
函数依赖和多值依赖区别

规范化

规范化的基本思想是逐步消除数据依赖中不合适的部分，使数据库模式中各关系模式达到某种程度的“分离”，使一个关系只描述一个实体或者实体间的一种联系。

即“一事一地”的设计原则。

规范化的实质是概念的单一化。

函数依赖公理系统

函数依赖的逻辑蕴涵

$R$中任意关系$r$，函数依赖$X\to Y$成立

则$F$逻辑蕴含$X\to Y$

Armstrong公理系统

A1自反律：若Y$\subseteq $X $\subseteq $U，则X →Y为F所蕴含（整体决定部分）
A2增广律：若X →Y为F所蕴含，且Z $\subseteq $U则XZ →YZ 为F所蕴含
A3传递律：若X →Y，Y →Z为F所蕴含，则X →Z为 F所蕴含

由自反律得到的都是平凡函数依赖

XZ为$X\cup Z$

证明：

A1:
- 若$t[X] = s[X],X\subseteq Y$，则$t[Y]=s[Y],X\to Y$
A2:
- 若$t[XZ] = s[XZ]$，则$t[X] = s[X],t[Z] = s[Z]$
- $t[X] = s[X],X\to Y$,则$t[Y]=s[Y],t[YZ] = s[YZ],XZ\to YZ$
A3:
- 若$t[X] = s[X]$
- $X\to Y$,则$t[Y] = s[Y]$
- $Y\to Z$,则$t[Z] = s[Z],X\to Z$

Armstrong公理系统的推论

合并规则：$X\to Y、X\to Z$,则$X\to YZ$
伪传递规则：$X\to Y$、$WY\to Z$，则$XW\to Z$
分解规则：$X\to Y,Z\subseteq Y$，则$X\to Z$
$\mathrm{X\to A_1A_2\ldots A_k}\Leftrightarrow\mathrm{X\to A_i}(\mathrm{i=1,~2,~\ldots,k})$