数据库概论

关系数据库规范化理论

2020-01-01 00:13 CST
2020-01-01 00:13 CST
CC BY-NC 4.0

关系数据库规范化理论

8.1 概述

  • 模式设计质量的评价指标:数据冗余度,插入/删除等更新异常

  • 为什么要研究关系的规划化设计:规范化的目的与手段

    8.2 规范化理论

    8.2.1 函数依赖(FD)

  • 函数依赖的定义

  • 如何寻找函数依赖:函数依赖与数据完整性约束的关系

  • 完全/部分FD,平凡/非平凡FD,直接/传递FD

  • Armstrong公理系统:3条基本规则 + 3条扩充规则

  • 基于函数依赖的关键字定义

  • 属性集闭包的计算算法

  • 关键字的计算算法

    8.2.2 与函数依赖有关的范式

  • 范式定义:1NF,2NF,3NF,BCNF

  • 理解各级范式与数据冗余度、插入/删除异常的关系

    8.2.3 多值依赖与第四范式

  • 多值依赖,平凡多值依赖,非平凡多值依赖

  • 多值依赖与函数依赖的关系

  • 4NF

    8.3 规范化所引起的一些问题

  • 函数依赖的逻辑蕴涵,函数依赖集的等价

  • 最小函数依赖集及其判定方法

  • 最小函数依赖集的计算算法

  • 模式分解的无损联结性、依赖保持性及其判定方法

  • 直接到3NF且满足无损联结性和依赖保持性的模式分解算法

  • 从3NF到BCNF、4NF的分解方法

概述

好的关系模型设计:有合理的数据冗余度,又没有插入和删除等操作异常现象

在一个关系中,属性之间的内在依赖有两种:函数依赖与多值依赖

在每个关系中,属性与属性之间的语义连续需要满足一定的要求,称为关系的规范化

对属性间所存在的内在语义的不同可以将关系的规范化分为几个等级,称为范式。

规范化理论

规范化的途径:将一个关系分解成多个子关系

规范化的途径:

  • 竖向规范化:采用投影和联接运算,将一个关系模式的属性集分解成若干个子关系模式,有关理论形成了关系数据库的规范化理论,模式分解理论有:无损联接性依赖保持性
  • 水平规范化:采用选择和并运算,将一个关系元组集合分解成若干个子集,从而构成若干个与原来关系模式相同的子模式,尚未形成成熟的规范化理论

函数依赖(FD)

函数依赖: 一个关系中两组属性之间的某种取值约束

给定一个关系R,X和Y是关系R的两个子集,如果说每一个X值都有唯一的一个Y值与之对应(即如果两元组X值相同则Y值相同,反之则不一定),那么我们说X函数决定Y(Y函数依赖于X),其中X称为决定因素,Y称为依赖因素

如果一个函数依赖关系$X \rightarrow Y$ 满足Y不是X的子集,则称这个函数依赖为非平凡的函数依赖,否则为平凡函数依赖

在关系函数R(U)中,如果有$X\subset U,Y\subset U$,且$X\rightarrow Y$ ,并且对于任何X的真子集X'有$X'\nrightarrow Y$ ,则称Y完全函数依赖于X,并记作$X\overset{f}{\to} Y$ .如满足前者而不完全依赖则称为部分依赖,并记作$X \overset{P}{\to} Y$(注意此处的真子集不是针对元组讨论,而是针对属性讨论)

Armstrong公理系统

基本规则:

  • 自反规则:若Y是X子集,则Y依赖于X
  • 增广规则:如果$X \to Y$,则$XZ \to YZ$
  • 传递规则:如果$X \to Y$,$Y \to Z$,则$X \to Z$

扩充规则:

  • 分解规则:如果$X\to YZ$,则$X \to Y$ 且$X \to Z$
  • 合并规则:如果$X\to Y$且$X \to Z$,那么$X\to YZ$
  • 伪传递规则:如果$X\to Y$且$WY \to Z$,则$WX\to Z$

如果F是关系的一个函数依赖集,X,Y是R的关系子集,如果能从F中已有的函数依赖出发,根据Armstrong公理系统推出$X\to Y$,则称F逻辑蕴涵$X\to Y$ 。记为$F \models X\to Y$.所有能被F逻辑蕴涵的函数依赖称为F的闭包,记作$F^+$

关键字:在关系模式R(U,F)中,如果有$K \subset U$ 且满足$K \overset{f}{\to} U$ ,则称K为关系R的关键字

在关系R中所有关键字中的属性构成的集合称为主属性集,主属性集中的属性称为主属性,对应的其他属性称为非主属性

如何寻找关键字:

  • 利用Armstrong公理系统推导
  • 利用属性集闭包的概念,寻找满足$K\_F^+ = U$ 的最小属性集合K
  • 利用最小函数依赖集来优化方法二

属性集闭包:$X\_F^+ = {A | F\models X\to A}$

计算属性集X在函数依赖F上的闭包算法(就是对于F中的每一个依赖关系的决定因素,如果决定因素是X+的子集就把对应的依赖因素加入X+,一直重复循环到无法有加入为止)

输入:关系模式R(U,F),属性集X

X+ := X;
repeat
    oldX+ := X+;
    for each functional dependency Y\to Z in F do
        if Y\subset X+ then X+ := X+ \cup Z;
until ( oldX+ = X+ )
return X+;

寻找关键字的方法二:设置初始关键字K为U,对于K中的每一个元素A,考虑(K-A)之后的属性闭包集,如果为U那么删去A

对于方法二的优化:考虑根据最小函数依赖集F,只出现在函数依赖左边或者没有出现在函数依赖关系中的为$U_L$,只出现在右边过的为$U_R$,两边都出现过的为$U_A$。考虑到$U_R$的属性不可能出现在任何一个关键字中,而$U_L$中的属性必然是关键字,所以设置初始关键字为$U-U_R$,然后对$U_A$中的每个元素进行判断即可

set K := U-UR ;
for each attribute A in UA
{
    compute $(K – {A})\_F^+$ ;
    if  $(K – {A})\_F^+$ contains all the attributes in R
        then   set K := K – { A } ;
}
return K ;

与函数依赖有关的范式

第一范式:关系R(U)中的每个属性都不可分割,则称关系模式满足第一范式。每一个关系都必须满足第一范式1NF

第二范式:如果有关系$R(U) \in 1NF$,且其每个非主属性都完全函数依赖于关键字,则称关系满足第二范式(判断第二范式:判断每一个非主属性A与每一个关键字之间是否存在部分函数依赖)

不满足第二范式的:存在非主属性对关键字的部分函数依赖导致出现了数据冗余导致了产生更新异常

模式分解:如果存在一组子关系模式 { R1, R2, …, Rk } 满足下述的两个条件,则我们称 { R1, R2, …, Rk } 是关系模式R的一个分解 (Decomposition):

  • $Head(R) = Head(R1)\cup Head(R2) \cup … \cup Head(Rk)$
  • 设子关系Ri上的函数依赖集为Fi (i=1,2,…,k), 则:$Fi = { X\to Y | X\to Y \in F+ 且 (X∪Y)\in Head(Ri) }$

模式分解的办法:

  • 找出所有不满足范式M要求的函数依赖关系

  • 选择一个不符合要求的函数依赖关系作如下的分解:假设 $X\overset{f}{\to}Y \in F+$ 且不满足范式M的要求,则我们将关系模式R分解为如下的两个子关系:

    • $R1 ( X\cup Y, { X\to Y } )$
    • $R2 ( Head(R) – Y, F2 )$,其中:$F2 = { A\to B | (A \to B) \in F+ 且 (A∪B)\subset Head(R2) }$
  • 对于分解得到的子关系模式R2重复上述的步骤1)和步骤2),直到所有的子关系模式都能满足范式M的要求

    合并那些具有相同关键字的子关系模式

对于2NF,要找到的分解出来的依赖关系是$X\overset{f}{\to} Y$,其中X是某个候选关键字的真子集,Y是非主属性

考虑到模式分解的基础是函数依赖集F,而F不是一个最小函数依赖集的情况下,要将关键词相同的子模式合并,故而可以将分解的方法优化为$Head(R1)=X+,Head(R2)=(Head(R)-X+)\cup X$,其各自的依赖集中属性在Head中

第三范式:有关系$R(U)\in 2NF$,且其每个非主属性都不传递函数依赖于关键字,则称关系模式R(U)满足第三范式

如果关系$R\notin 3NF$,那么在关系R中必然存在以下形式的函数依赖$X\overset{f}{\to} Y $,其中:依赖因素Y是单个的非主属性,而决定因素X则是以下的两种情况之一:

  • X是关系R的某个关键字的真子集($R\notin 2NF$)
  • X并不是关系R的关键字($R \notin 3NF$ )

BCNF:若关系R(U)满足1NF,且若$X\to Y$时X必含有该关系模式的关键字,则称其满足BCNF

满足BCNF的必然是3CNF,但是满足3CNF的不一定是BCNF

多值依赖与第四范式

多值依赖(MVD): 设有关系模式R(U),X, Y是U的子集,如果关系模式R(U)满足下述要求:对X的一个确定值,存在Y的一组值与之对应;且Y的这组值又与关系中的其他属性(U-X-Y)(此处是减号)的取值不相关。此时称Y多值依赖于X,并记为:X→→Y

如果$U-X-Y$是不是空集,则为非平凡的多值依赖,否则为平凡的空值依赖

多值依赖的性质:

  • 如有 X→→Y,则必有 X→→(U-X-Y)
  • 如有 X→Y,则必有 X→→Y (函数依赖是一种特殊的多值依赖)

多值依赖的推导规则:

  • 规则 IR1(自反规则):如果Y是X的子集,则: X → Y
  • 规则 IR2(增广规则):如果 X → Y,则:XZ → YZ
  • 规则 IR3(传递规则):如果 X → Y,Y → Z,则:X → Z
  • 规则 IR4(求补规则):如果 X→→Y,则 X→→(U–X–Y)
  • 规则IR5(多值依赖的增广规则): 如果 X→→Y 且 $W\supseteq Z$,则 WX→→YZ
  • 规则IR6(多值依赖的传递规则):如果 X→→Y,Y→→Z,则 X→→( Z – Y )
  • 规则IR7(转换规则):如果 X→Y,则 X→→Y
  • 规则IR8(结合规则):如果 X→→Y, 且存在另一个属性集合W满足:$W\cap Y = \emptyset, W\to Z, Y \supseteq Z$, 则:X→Z

第四范式:如果在关系模式$R(U)$中,$X\to\to Y$ 是非平凡多值依赖,则X必含有关键字,则称R满足第四范式

满足第四范式的必然满足BCNF,同时意味着对于不是函数依赖的多值依赖必须是平凡多值依赖

规范化所引起的一些问题

如果两个函数依赖集的闭包相等,则称这两个函数依赖集等价

与函数依赖集F相等价的所有函数依赖集中最小者被称为函数依赖集F的最小函数依赖集(也称最小覆盖)

输入函数依赖集F,找到与F等价的最小的函数依赖集G:

  • 消除F中的部分函数依赖,转变为完全函数依赖
  • 消除冗余的函数依赖
  • 以上两部顺序可以对调,但是将部分函数依赖转变为完全函数依赖过程中可能产生新的冗余函数,所以如果先消冗余需要再最后再检查一遍有无冗余函数依赖

具体算法如下: 1. 令 G := F 将 G 中每一个形如 $X\to (A1,A2,…,An)$ 的函数依赖替换为如下一组依赖因素为单个属性的函数依赖:$X\to A1, X\to A2, …, X\to An$

  1. 对 G 中的每一个函数依赖 $X\to A$ 作如下的处理: 对决定因素 X 中的每一个属性 B 作如下处理: 计算属性集的闭包 $(X – B)\_G^+$; 如果 $A\in (X – B)G+$, 则用新的函数依赖 $(X – B)\to A$ 替换原来的函数依赖 $X\to A$;
  2. 对 G 中的每一个函数依赖 $X\to A$ 作如下处理: 令 $N := G – { X\to A }$ ; 计算属性集的闭包 $X\_N^+$ ; 如果 $A\in X\_N^+$ , 那么从G中删去函数依赖 $X\in A$;
  3. 将 G 中每一组形如 $X\to A1, X\to A2, …, X\to An$(决定因素相同)的函数依赖合并为一个函数依赖: $X\to (A1,A2,…,An)$

无损联接性:分解后,原关系中的信息不会丢失.设R是一个关系模式,F是关系模式上R的函数依赖集,$\rho ={R1,R2,…,Rk}$ 是对R的一个分解。如果对R中满足F的每一个关系实例 r 都有:$r = \pi_{R1}(r)\bowtie \pi_{R2}(r) \bowtie …… \bowtie \pi\_{Rk}(r)$ 则称该分解 $\rho$ 相对于F是“无损联接分解”,或称分解 $\rho$ 具有无损联接性。

如果R的分解为 $\rho = {R1,R2}$,F为R所满足的函数依赖集合,分解$\rho$具有无损联接性的充分必要条件是:$R1 \cap R2 \to (R1 – R2)$ 或 $R1 \cap R2 \to (R2 – R1)$

依赖保持性:原有的函数依赖关系再分解后的关系模式上仍然存在.用 $\pi_Z(F)$ 来表示函数依赖集F在子关系Z上的投影: $\pi\_Z(F) = { X\to Y | X\to Y\in F+ 且 (X∪Y) \subseteq Z }$ 如果有:$F+ = (\pi_{R1}(F) \cup \pi_{R2}(F) \cup … \cup \pi_{Rk}(F))^+$. 则称 “分解具有依赖保持性”

在必须同时满足无损连接性和依赖保持性的要求下,一个关系模式最高可以被分解到满足3NF,分解方法如下:

    1. 计算F的最小函数依赖集,并用来代替F进行下面的模式分解;
    1. $S = \emptyset$ ;
    1. 对 F 中的每一个函数依赖 $X\to Y$ 做如下处理:
    2. 如果在集合 S 中找不到满足下述条件的子关系模式Z:$X\cup Y \supseteq Heading (Z) $,则由X和Y合并构成一个新的子关系模式并加入到集合S中
    1. 如果关系 R 的每一个候选关键字 K 都没有出现在分解后的子关系模式中,即:找不到一个原关系R的关键字K和一个子关系模式 Z,且他们之间满足 $K \subseteq Heading(Z)$ 那么,就从关系R中任选一个候选关键字K, 由K中的属性单独构成一个子关系模式并加入到集合S中去。