花于陌上开个人站

第三章 关系规范化 v1.0 ​

第一部分 函数依赖 ​

一、函数依赖简介 ​

1.关系模式 ​

(R(U,D,DOM,F))

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

2.相关定义 ​

设R(U)是属性集U上的关系模式，X,Y是U的子集（易知X,Y也是关系中的属性）

3.函数依赖定义 ​

对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作(X\to Y)

通俗解释：存在属性集X可以唯一确定属性集Y

例如：学号可以唯一确定学生姓名，学生姓名函数依赖于学号

二、几种函数依赖 ​

1.非平凡函数依赖 ​

(X\to Y,但Y\nsubseteq X,则称X\to Y是非平凡的函数依赖)

通俗解释：属性X可以唯一确定Y，且Y不包含于X，如不重名情况下，姓名可以唯一确定学号

2.平凡函数依赖 ​

(X\to Y,但Y\subseteq X,则称X\to Y是平凡的函数依赖)

平凡函数依赖对于任一关系模式是必然成立的，它不反映新的语义，因此不特别声明一般不讨论平凡函数依赖

3.完全函数依赖 ​

(X\to Y,且对任何X的真子集X'都有X'\nrightarrow Y，则称Y对X完全函数依赖，记作X\xrightarrow{F}Y)

通俗解释：X是可以唯一确定Y的最少的属性子集，如不重名情况下，姓名就可以唯一确定性别，不需要姓名和班级两个属性

4.部分函数依赖 ​

(X\to Y,但Y不完全函数依赖于X,则称Y对X部分函数依赖，记作X\xrightarrow{P}Y)

5.传递函数依赖 ​

(如果X\to Y(Y\nsubseteq X),Y\nrightarrow X,Y\to Z,Z\nsubseteq Y则称Z对X传递函数依赖，记为X\xrightarrow{传递}Z)

通俗解释：主码决定一个属性，该属性就能决定另一属性

三、关系的相关名词 ​

属性：描述一个事物常常取若干特征的表述，这些特征称为属性。

域：每个属性的取值范围对应一个值的集合，称为该属性的域。

目或度：关系的属性的个数

超码：从定义上，如果U函数依赖于K，即(K\to U)，则称K为超码

候选码（码）：特殊的超码，若一个关系的某一属性（组）能唯一表示一个元组，则称该属性（组）为候选码。从定义上，为设K为R<U,F>中的属性或属性组合，若(K\xrightarrow{F}U)则K为R的候选码（U完全函数依赖于K）

主码（主键）：若一个关系中有多个候选码，则从候选码中选择其中之一为主码

全码：最极端的情况下，整个属性组是这个关系模式的候选码，称为全码

外部码（外码）：关系模式中的属性（组）非该关系中的码，但其是其他关系中的码，则称该属性为外部码。从定义上，关系模式R中的属性或属性组X并非R的码，但是另一个关系模式的码，则称X是R的外部码

主属性：从定义上，包含在任何一个候选码中的属性称为主属性

非主属性（非码属性）：从定义上，不包含在任何候选码中的属性称为非主属性

第二部分 范式 ​

一、范式概述 ​

1.范式的简介 ​

关系型数据库中的关系要满足一定要求，满足不同程度的要求的为不同范式，满足最低要求的叫第一范式（1NF）

一个低一级范式的关系模式通过模式分解，可以转换为若干个高一级范式的关系模式的集合，称为关系的规范化

2.范式之间的关系 ​

(5NF \subset 4NF \subset BCNF \subset 3NF \subset2 NF \subset1NF)

三大范式：1NF & 2NF & 3NF

二、范式详解 ​

1.1NF ​

要求：表中每一个属性都是不再可分的数据项

存在问题：

  1. 数据冗余
  2. 更新异常（修改操作之后数据不一致）
  3. 插入异常
  4. 删除异常

2.2NF ​

要求：(R\in1NF)，且每一个非主属性都完全函数依赖于任何一个候选码

通俗理解：非主属性完全函数依赖于主关键字，消除非主属性对码的部分函数依赖

不满足2NF（没有属性能由主关键字的子集唯一确定）的情况举例：(1NF)

（学号，课程名称） → （姓名，年龄，成绩，学分）

此数据库表不满足第二范式，因为存在如下决定关系：

（课程名称） → （学分），（学号） → （姓名，年龄）

3.3NF ​

要求：(R\in2NF)，且每一个属性都不存在传递函数依赖

通俗理解：每一个属性都不依赖于除主属性外其它非主属性，消除了非主属性对码的传递函数依赖

不满足3NF（没有属性能由非主属性的值唯一确定）的情况举例：(2NF)

（学号） → （姓名，年龄，所在学院，学院地点，学院电话）

这个数据库是符合2NF的，但是不符合3NF，因为存在如下决定关系：

（学号） → （所在学院） → （学院地点，学院电话）

注：若要求分解保持函数依赖，那么模式分解一定能够达到的最高范式是3NF

4.BCNF ​

要求：(R\in3NF)，数据库表中不存在任何字段对任一候选关键字段的传递函数依赖

通常认为BCNF是修正的第三范式，有时也称为扩充的第三范式，要求每一个决定因素都包含码

通俗理解：每一个非主属性对主属性不存在传递函数依赖，消除了主属性对码的部分函数依赖和传递函数依赖

不满足BCNF（没有关键字字段能决定关键字字段）的情况举例：(3NF)

（仓库ID，存储物品ID，管理员ID，数量），且有一个管理员只在一个仓库工作，一个仓库可以存储多种物品

不满足BCNF，因为存在如下决定关系：

候选关键字：（仓库ID，存储物品ID） → （管理员ID，数量）

候选关键字：（管理员ID，存储物品ID） → （仓库ID，数量）

（仓库ID） → （管理员ID），（管理员ID） → （仓库ID）

注：若只考虑函数依赖，关系模式最高规范化程度是BCNF；若考虑多值依赖，关系模式最高规范化程度是4NF，也就是说，若是一个关系模式中没有多值依赖，就不存在4NF。

注：若要求分解保持无损连接，那么模式分解能够达到的最高范式是BCNF

5.4NF ​

要求：限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖

不满足BCNF（没有一个字段决定多个多值依赖且在同一个关系模式之中）的情况举例：(BCNF)

（学号） →→ （选修课程）

（学号） →→ （兴趣爱好）

（学号，选修课程，兴趣爱好）不属于4NF，（学号，选修课程），（学号，兴趣爱好）属于4NF

6.5NF ​

要求：关系模式R依赖均由R候选码所隐含

第三部分 Armstrong公理系统 ​

一、公理系统 ​

1.推理规则 ​

设关系模式R(U, F)，其中U为属性集，F是U上的一组函数依赖，那么有如下推理规则:

  1. A1自反律：若(Y\subseteq X \subseteq U), 则(X→Y)为F所蕴涵。
  2. A2增广律：若(X→Y)为F所蕴涵， 且(Z\subseteq U), 则(XZ→YZ)为F所蕴涵。
  3. A3传递律：若(X→Y)，(Y→Z)为F所蕴涵，则(X→Z)为F所蕴涵。

根据上述三条推理规则又可推出下述三条推理规则:

  1. 合并规则：若(X→Y)，(X→Z), 则(X→YZ)为F所蕴涵。
  2. 伪传递律：若(X→Y)，(WY→Z)，则(XW→Z)为F所蕴涵。
  3. 分解规则：若(X→Y)，(Z\subseteq Y)，则(X→Z)为F所蕴涵。

二、闭包 ​

1.函数依赖的闭包（F+） ​

定义：关系模式R(U,F)中为F所逻辑蕴含的函数依赖的全体称为F的闭包，记为：F+。

[例]

R(U,F),U=(A,B,C,D),F=

则：F+=

2.属性的闭包（XF+） ​

定义：设F为属性集U上的一组函数依赖，(X\subseteq U)，XF+={A|X→A能由F根据Armstrong公理导出的所有属性}，则称XF+为属性集X关于函数依赖集F的闭包

[例]

R(U,F),U=(A,B,C,D),F=

则：(A)F+=ABCD

计算过程如下：

设(X^{(0)}=AE)

(1)计算(X^{(1)})，逐一扫描F中各个函数依赖，(X^{(1)}=A\cup B)

(2)计算(X^{(2)})，逐一扫描F中各个函数依赖，(X^{(2)}=AB\cup C)

(3)计算(X^{(3)})，逐一扫描F中各个函数依赖，(X^{(3)}=ABC\cup D)

(4)计算(X^{(4)})，逐一扫描F中各个函数依赖，(X^{(4)}=X^{(3)}=ABCD)，算法终止

故((A)^+_F=ABCD)

三、候选码的求解方法 ​

属性集X关于函数依赖集F的闭包为全集的属性集X即为候选码

四、最小函数依赖集 ​

  1. 所有函数依赖的右侧只有一个属性，即不能有类似A→BC
  2. 没有冗余的函数依赖，即不能有类似A→D,D→E,A→E
  3. 所有函数依赖的左侧没有冗余的属性，即不能出现AC→D,A→D

第四部分 模式分解 ​

一、分解 ​

1.无损连接 ​

无损连接是指将一个关系模式分解成若干个关系模式后，通过自然连接和投影等运算仍能还原到原来的关系模式，则称这种分解为无损连接分解。

(R(U,F))分解为(R_1(U_1,F_1),R_2(U_2,F_2))的必要条件：(U_1\cap U_2→U_1-U_2\in F^+)或(U_1\cap U_2→U_2-U_1\in F^+)

[例]

(R(U,F),U={A,B,C},F={A→B})分解(\rho_1={AB,BC},\rho_2={AB,AC})

  • (\rho_1)是否无损

(AB\cap BC=B,AB-BC=C,BC-AB=C)

(B→A\notin F^+,B→C\notin F^+,\rho_1为有损连接)

  • (\rho_2)是否无损

(AB\cap AC=A,AB-AC=B,AC-AB=C)

(A→C\in F^+,\rho_2为无损连接)

2.保持函数依赖 ​

保持函数依赖的分解的要求：分解得到的闭包的并集等于原关系模式的闭包

即：((F_1\cup F_2 \cup F_3\cup ...\cup F_k)^+=F^+)