数据库复习四

数据库复习四

# 关系模式设计引论

一个完整的关系模型内涵的定义：

• 关系名
• 属性集
• 关系的域
• 属性到域上的映射关系
• 数据依赖

关系模式通常简记为：R (U,F)。

一个没有设计号的关系模式通常会有以下问题：

• 数据冗余太大
• 更新异常
• 插入异常
• 删除异常

# 函数依赖与规范化

规范化：指定义一组关系模式应符合的条件 (范式)，而符合这些条件的关系模式就不存在某些操作异常，冗余也会减少

# 一、函数依赖 (简写 FD)

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

• 若$X\rightarrow Y$，则 X 称为这个函数的决定属性组，也称为决定因素
• 若$X\rightarrow Y,Y\rightarrow X$，则记作$X\leftrightarrow Y$
• 若$Y$ 不函数依赖与$X$，则记作$X\nrightarrow Y$。

在一个关系模式 R (U) 中，对于 U 的子集 X 和 Y

• 若 X 和 Y 有 1:1 关系，则$X\rightarrow Y,Y\rightarrow X$，记作$X\leftrightarrow Y$
• 若 X 和 Y 有 1:m 关系，则记作$Y\rightarrow X$，但$X\nrightarrow Y$。
• 若 X 和 Y 有 n:m 关系，则 X 和 Y 不存在任何函数依赖

# 1、完全函数依赖

定义：在关系模式 R (U) 中，如果$X\rightarrow Y$，并且对于 X 的任何一个真子集$X^\prime$，都有$X^\prime\nrightarrow Y$，则称 Y 完全依赖于 X，记作$X\xrightarrow{F}Y$。

# 2、部分函数依赖

定义：在关系模式 R (U) 中，如果$X\rightarrow Y$，存在 X 的真子集$X^\prime$，有$X^\prime\nrightarrow Y$，则称 Y 部分依赖于 X，记作$X\xrightarrow{P}Y$

# 3、传递函数依赖

定义：在关系模式 R (U) 中，如果$X\rightarrow Y$，($Y\nsubseteq X$)，$Y\nrightarrow X$，$Y\rightarrow Z$，则有$X\rightarrow Z$，称 Z 传递函数依赖于 X，记为:$X\xrightarrow{T}Z$

注意：如果$Y\rightarrow X$，即$X\leftrightarrow Y$，则 Z 直接依赖于 X；如果$Y\subseteq X$，则$X\xrightarrow{P}Z$

定义：设 K 为关系模式 R<U,F> 中的属性或属性组。若$K\xrightarrow{F}U$，则 K 称为 R 的一个候选码。若关系中有多个候选码，则选定其中的一个作为主码。候选码常常简称为码

主码的两个性质：

• 决定性：$K\rightarrow U$
• 最小性：$\lnot\exists K^\prime\subset K$，使得$K^\prime\rightarrow U$

主属性：所有候选码中出现的属性

非主属性：不出现在任何候选码中的属性

全码：由关系模式的所有属性构成码

# 二、关系模式的规范化

# 1、范式

范式是符合某一类满足一定要求的关系模式的集合

(1)$1NF$

定义：如果一个关系模式 R 的所有属性都是不可分的基本数据项，则称关系 R 为第一范式的关系模式，简称关系 R 属于第一范式，记为$R\in 1NF$

注意：第一范式是对关系模式的最起码的要求。不满足第一范式的数据库不能称为关系数据库。(由关系属性的原子性得出)。但是满足第一范式的关系模式并不一定是一个好的关系模式。

(2)$2NF$

定义：若关系模式$R\in 1NF$，并且每一个非主属性都完全函数依赖于 R 的码，则$R\in2NF$。

不属于 2NF 的关系模式存在的问题：

• 插入异常
• 删除异常
• 数据冗余度大
• 修改复杂

(3)$3NF$

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

说明：3NF 是指不含纯粹的非主属性对码的传递依赖的关系模式

不适于 3NF 的关系模式存在的问题：

• 插入异常
• 删除异常
• 数据冗余度大
• 修改复杂

定理：如果$R\in 3NF$，则$R\in 2NF$

证明：$R\in 3NF\Rightarrow R\in 2NF \Leftrightarrow R\notin 2NF\Rightarrow R\notin 3NF$

设$R$ 不属于 2NF，则存在非主属性 A 部分依赖于码 K，$K\xrightarrow{P} A$，即不存在$K^\prime\sub K$，使得$K^\prime\rightarrow A$；又$K^\prime\sub K$，则$K\rightarrow K^\prime$；即存在$K\rightarrow K^\prime,K^\prime\rightarrow A,K^\prime\nrightarrow K,A\nsubseteq K^\prime$，由 3NF 定义，R 不属于 3NF

推论：$R\in 3NF$，则 R 中的每一个非主属性既不部分依赖于码，也不传递依赖于码

总结：

1NF 是指关系模式中所有属性都满足原子性，是关系模式的最低要求

2NF 是指关系模式中不存在非主属性 (组) 对码的部分依赖

3NF 是指关系模式中不存在非主属性 (组) 对码的传递依赖

范式级别越高，其存在的操作异常和数据冗余越小

(4)$BCNF$

定义：设关系模式$R<U,F>\in 1NF$，如果对于 R 的每个函数依赖$X\rightarrow Y(Y\nsubseteq X)$，X 必包含码，则$R\in BCNF$，又称修正 (或扩充) 的第三范式

结论：

• $BCNF\sub 3NF$

  证明：上式可写成$R\in BCNF\Rightarrow R\in 3NF$

  ​ 等价于$R\notin 3NF \Rightarrow R\notin BCNF$

  ​ 若$R\notin 3NF$，则存在码 X，属性组 Y 及非主属性 Z ($Z\nsubseteq Y$) 使得$X\rightarrow Y,Y\rightarrow Z$ 成立，但是 Y 是属性组不一定含码

  ​ 由 BCNF 定义得$R\notin BCNF$，因此结论成立

• 若$R\in BCNF$，则 R 中所有非主属性对每一个码都完全函数依赖 (由 2NF 定义得到)

• 若$R\in BCNF$，则 R 中所有主属性对每一个不包含它的码都完全函数依赖

• 若$R\in BCNF$，则 R 中没有任何属性完全依赖于非码的任何一组属性

不属于 BCNF 的关系模式存在问题：

• 插入异常
• 删除异常
• 数据冗余度大
• 修改复杂

结论：BCNF 消除了主属性对码的部分依赖和传递依赖，在函数依赖的范畴内解决了数据插入异常和删除异常，但可能存在着数据冗余和修改复杂

# 三、数据依赖的公理系统

# 1、函数依赖的公理系统

定义：设关系模式 R<U,F>，其中 F 是属性 U 上的函数依赖集，$X,Y\sub U$，对其任何一个关系实例 r，若函数依赖$X\rightarrow Y$ 都成立，则称 F 逻辑蕴含$X\rightarrow Y$，记为$F\vDash X\rightarrow Y$

• Armstrong 公理系统：

  设关系模式 R<U,F>，其中 F 是属性集 U 上的函数依赖集，对关系模式 R<U,F > 有以下推理规则：

  • 自反律：若$Y\subseteq X \subseteq U$，则$F\vDash X\rightarrow Y$。
  • 增广律：若$F\vDash X\rightarrow Y,Z\subseteq U$，则$F\vDash XZ\rightarrow YZ$
  • 传递率：若$F\vDash X\rightarrow Y,F\vDash Y\rightarrow Z$，则$F\vDash X\rightarrow Z$。
  • 合并规则:$\{X\rightarrow Y,X\rightarrow Z\}\vDash X\rightarrow YZ$
  • 分解规则:$\{ X\rightarrow Y,Z\subseteq Y\}\vDash X\rightarrow Z$。
  • 伪传递规则：$\{X\rightarrow Y,WY\rightarrow Z\}\vDash WX\rightarrow Z$。

• 模式分解的原则

  • 分解保证无损连接性
  • 分解至少应达到 3NF，尽可能达到 BCNF
  • 分解应尽可能保持函数依赖和多值依赖

# 2、函数依赖集的闭包

定义：设关系模式 R<U,F> 中为 F 所逻辑蕴含的函数依赖的全体叫做 F 的闭包，即为$F^+$

$F^+$ 的意义：包含了给定函数依赖集 F (部分) 所蕴含的属性集 U 上的全部函数依赖。缺点：依赖信息太庞杂，难管理属性集的闭包

定义：设 F 为属性集 U 上的一组函数依赖，$X\subseteq U$，X 关于函数依赖集 F 的闭包$X_F^+=\{A\vert X\rightarrow A$ 能由 Armstrong 公理导出$\}$。

求$X_F^+$ 算法：

(1) 令$X^{(0)}=X,i=0$；

(2) 令$X^{(i+1)}=X^{(i)}\cup\{A\vert(\exists V)(\exists W)(V\rightarrow W\in F\land V\subseteq X^{(i)}\land A\in W) \};$

(3) 若$X^{(i+1)}=X^{(i)}$，或$X^{(i+1)}=U$ 算法结束，$X_F^+=X^{(i+1)};$ 否则，令 i=i+1，转 (2)

例：已知关系模式 R<U,F>，其中$U=\{A,B,C,D,E \}.F=\{AB\rightarrow C,B\rightarrow D,C\rightarrow E,EC\rightarrow B,AC\rightarrow B\}$，求$(AB)_F^+$

解：$(AB)^+_F$，由$AB\rightarrow C$ 得到$ABC$，由$B\rightarrow D$ 得到$ABCD$，由$C\rightarrow E$ 得到$ABCDE$，此时$(ABCDE)=U$，结束，因此$(AB)^+_F=$