[人工智能]《数据库系统概念》学习笔记——关系数据库设计

关系数据库设计

关系数据库设计的目标是生成一组关系模式，使我们存储信息时避免不必要的冗余，并且让我们可以方便地获取信息。
这是通过设计满足适当范式的模式来实现的。
要确定一个关系模式是否属于期望的范式，我们需要数据库所建模的真实企业的信息。
其中的一部分信息存在于设计良好的E-R图中，但是可能还需要关于该企业的额外信息。

好的关系设计的特点

之前看到，可以直接从E-R设计生成一组关系模式。
显然，生成的模式集的好（或差）首先取决于E-R设计的质量。

设计选择：更大的模式

假定用以下这个模式代替instructor模式和department模式
$$inst\_dept(ID,name,salary,dept\_name,building,budget)$$
这表示在instructor和department对应关系上进行自然连接的结果。

上面的设计选择中，存在的问题：

重复存储预算数额，且要承担某些用户可能更新一条元组而不是所有元组中的预算数额，并因此产生不一致的风险。

无法直接表示关于一个系的信息（dept_name, building, budget），除非该系在学校中有至少一位教师。
意味着不能记录新成立的系的信息，直到该系录用了第一位教师为止。
将不得不创建一条building 和 budget 为空值的元组。

设计选择：更小的模式

我们需要写这样一条规则：
如果存在模式(dept_name, budget)，则dept_name可作为主码。这条规则被定义为函数依赖。
$$dep{t}_{n}ame???＞budget$$
由于dept_name不能是inst_dept的主码（因为一个系可能在模式 inst_dept上的关系中需要多条元组），因此预算数额可能会重复。

类似于这些观察及由它们导出的规则（在此称为函数依赖）让数据库设计者可发现一个模式应拆分或分解成两个或多个模式的情况。

对有大量属性和多个函数依赖的模式，为找到正确分解，要依靠后面介绍的规范方法。

并不是所有模式分解都是有益的。

考虑把
$employee(ID,name,street,city,salary)$

分解为以下两个模式：

$employee1(ID,name)$
$employee2(name,street,city,salary)$

不足是企业可能有两名同名雇员

我们能指出某个街道，城市，工资属于一个名为x的人，但无法区分是多个x中的那个。

下图所示为这些元组、利用分解产生的模式所生成的元组，以及我们视图用自然连接重新生成原始元组所得到的结果。
如在图中看到的，那两个原始元组伴随着两个新的元组出现于结果中，这两个新的元组将属于这两个名为Kim的职员的数据值错误地混合在一起。
我们能指出某个街道，城市，工资属于一个名为Kim的人，但无法区分是多个Kim中的那个。

将这样的分解称为有损分解，反之，则称为无损分解。

原子域和第一范式

E-R模型允许实体集和联系集的属性有某些程度的子结构。
特别地，它允许多值属性和组合属性。
当从包含这些类型的属性的E-R设计创建表时，要消除这种子结构。

对于组合属性，让每个子属性本身成为一个属性。
对于多值属性，为多值集合中的每个项创建一条元组。

一个域是原子的，如果该域内的元素被认为是不可分的单元。
我们称一个关系模式R属于第一范式，如果R的所有属性的域都是原子的。

名字的集合是一个非原子值的例子。
例如，如果关系employee的模式包含一个属性children，它的域元素是名字的集合，该模式就不属于第一范式。

组合属性，比如包含子属性street、city、state和zip的属性 address，也具有非原子域。

假定整数是原子的，那么整数的集合是一个原子域；然而，所有整数集的集合是一个非原子域。
区别在于，我们一般不认为整数具有子部分，但是我们认为整数的集合具有子部分——构成该集合的那些整数。

认为每个整数是一列有序的数字，那么全部整数的域就是非原子的。

使用函数依赖进行分解

基于码和函数依赖的方法，判断一个关系模式是否该分解。
讨论关系数据库设计的算法时，需针对任意的关系及其模式讨论，而不只是讨论例子。

• 一般情况下，用希腊字母表示属性集。
  用小写的罗马字母后面跟一个用一对圆括号括住的大写字母来指关系模式（例如，r ( R )）
  用r( R )表示该模式是关系ｒ的，Ｒ表示属性集。
  不关心关系名字时常简化为R。
  一个关系模式是一个属性集，但是并非所有属性集都是模式。
  使用小写希腊字母时，指一个可能是模式也可能不是模式的属性集。
  希望指明属性集一定为一个模式时，使用罗马字母。

• 属性集是一个超码时，用K表示它。
  超码属于特殊的关系模式，使用术语“K是 r( R )的超码”。

• 对关系使用小写的名字。

• 一个关系在任意给定时间都有特定的值。
  当明显在讨论一个实例时，可仅用关系的名字（例如 r ）

码和函数依赖

一个数据库对现实世界中一组实体和联系建模。
数据上常存在各种约束（规则）。
一个关系的满足所有约束的实例，称为关系的合法实例。
在一个数据库的合法实例中，所有关系实例都是合法实例。

几种最常用的现实世界约束可以形式化地表示为码（超码、候选码以及主码），或者下面所定义的函数依赖。

鉴于超码是能够唯一标识整条元组的属性集，函数依赖让我们可以表达唯一标识某些属性的值的约束。

考虑一个关系模式r?，令α?R且β?R

• 给定r( R )的一个实例，说这个实例满足（satisfy）函数依赖 α–>β的条件是：
  对实例中所有元组对t1和t2，若t1[α]=t2[α]，则t1[β]=t2[β]。

• 如果在r( R )的每个合法实例中都满足函数依赖α–>β，则我们说该函数依赖在模式r?上成立。

有些函数依赖称为平凡的，因为无论对什么关系模式都会满足。
一般地，如β?α，则形如α–>β的函数依赖是平凡的。

将使用$F^{+}$符号来表示F集合的闭包，也就是能够给定F集合推导出的所有函数依赖的集合。
显然，$F^{+}$包含F中所有的函数依赖。

Boyce-Codd 范式

Boyce-Codd（Boyce-Codd Normal Form, BCNF ）范式：
它消除所有基于函数依赖能够发现的冗余，虽然，可能有其他类型的冗余还保留着。

具有函数依赖集F的关系模式R属于BCNF的条件是，对$F^{+}$中所有形如α–>β的函数依赖（其中α?R且β?R），下面至少有一项成立：

• α–>β是平凡的函数依赖（即β?α）。
• α是模式R的一个超码。

一个数据库设计属于BCNF的条件是，构成该设计的关系模式集中的每个模式都属于BCNF。

分解不属于BCNF的模式的一般规则。
设R为不属于BCNF的一个模式。
则存在至少一个非平凡的函数依赖α–>β，其中α不是Ｒ的超码。
在设计中用以下两个模式取代R：

• (αUβ)
• (R-(β-α))

当分解不属于BCNF的模式时，产生的模式中可能有一个或多个不属于BCNF。
这种情况中，需要进一步分解，直到最终结果是一个BCNF模式集合

BCNF 和保持依赖

多种表达式数据库一致性约束的方式：主码约束、函数依赖、check约束、断言和触发器。

在有些情况下，到BCNF的分解会妨碍对某些函数依赖的高效检查。

由于我们的设计使得该函数依赖的强制实施在计算上很困难，因此我们称为我们的设计不是保持依赖的。

第三范式

具有函数依赖集F的关系模式R属于第三范式（third normal form）的条件是：
对$F^{+}$中所有形如α–>β的函数依赖（其中α?R且β?R）以下至少一项成立：

• α–>β是一个平凡的函数依赖。
• α是R的一个超码。
• β - α 中的每个属性A都包含于R的一个候选码中。

注意上面的第三个条件并没有说单个候选码必须包含 β - α 中的每个属性A可能包含于不同的候选码中。
候选码——任何真子集都不是超码的超码。

3NF定义中的第三个条件看起来很不直观，并且它的用途也不是显而易见的。

在某种意义上，它代表BCNF条件的最小放宽，以确保每一个模式都有保持依赖的3NF分解。

注意任何满足BCNF的模式也满足3NF，因为它的每个函数依赖都将满足前两个条件中的一条。所以BCNF是比3NF更严格的范式。

3NF的定义允许某些BCNF中不允许的函数依赖。
只满足3NF定义中第三个条件的依赖 α→β 在BCNF中是不允许的，但在3NF中是允许的。

当不存在保持依赖的BCNF设计时，必须在 BCNF和 3NF 之间进行权衡。

更高的范式

某些情况下，使用函数依赖分解模式可能不足以避免不必要的信息重复。

多值属性 phone_number 和 child_name 中每个属性对应一个模式：
$(ID,chil{d}_{n}ame)$
$(ID,phon{e}_{n}umber)$

如果合并模式得到：
$(ID,chi{d}_{n}ame,phon{e}_{n}ame)$

该结果属于BCNF，因为只有平凡的函数依赖成立。

考虑有两个孩子和两个电话号码的教师例子：

在合并模式中，我们必须为每个家属重复一次电话号码。

基于函数依赖的范式不足以处理这样的情况，因此定义了另外的依赖和范式。

函数依赖理论

函数依赖集的闭包

给定陌上上的函数依赖集 F ,我们可以证明某些其他的函数依赖在模式上也成立。称这些函数依赖被 F “逻辑蕴涵”。

更正式地，给定关系模式 r ( R )，如果 r ( R )的每一个满足 F 的实例也满足 $f$，则 R 上的函数依赖 $f$被 $r$上的函数依赖集 F 逻辑蕴涵 （logically imply）。

假设给定关系模式 r (A, B, C, G, H, I ) 及函数依赖集：

令 F 为一个函数依赖集。
F 的闭包是被 F 逻辑蕴涵的所有的函数依赖的集合，记作 $F^{+}$。

公理（axiom），或推理规则，提供了一种用于推理函数依赖的更为简单的技术。

在下面规则中，用希腊字母（α， β，．．．）表示属性集，用字母表中从开头其的大写罗马字母表示单个属性。
用αβ表示 αＵβ。

Armstrong公理：

• 自反律（reflexivity rule），若α为一属性集且β?α，则α → β成立。
• 增补律（augmentation rule），若α → β成立且γ为一属性集，则γα → γβ成立。
• 传递律（transitivity rule），若α → β 和 β → γ 成立，则 α → γ 成立。

Armstrong公理是正确有效的，因为它们不产生任何错误的函数依赖。
这些规则是完备的，因为，对于给定函数依赖集 F，它们能产生全部 $F^{+}$。

Armstrong公理的推理：

• 合并律（union rule），若α → β和α → γ成立，，则α → βγ成立。
• 分解律（decomposition ），若α → βγ成立，则α → β和α → γ成立成立。
• 伪传递律（pseudotransitivity rule），若α → β和γβ → δ成立，则αγ → δ成立。

寻找给定函数依赖集合的闭包算法：

属性集的闭包

如果α → β，称属性β被α 函数确定。

要判断集合α是否为超码：

一种方法是计算F的$F^{+}$，找出所有左半部分为α的函数依赖，并合并这些函数依赖的右半部。
但是这么做开销很大，因为 $F^{+}$ 可能很大。

令α为一个属性集。
将函数依赖集Ｆ下被α函数确定的所有属性的集合称为Ｆ下α的闭包，记为${\alpha }^{+}$。
输入是函数依赖集 F和属性集α。
输出存储在变量result 中。

属性闭包算法的多种用途：

• 为了判断α是否为超码， 计算出${\alpha }^{+}$，检查 ${\alpha }^{+}$ 是否包含 R 中的所有属性。
• 通过检查是否 β? ${\alpha }^{+}$ ，可以检查函数依赖 α → β是否成立（换句话说，是否属于$F^{+}$ ）。
• 对任意γ?Ｒ，找出闭包${\gamma }^{+}$；对任意的$Ｓ?{\gamma }^{+}$
  输出一个函数依赖 γ→Ｓ。

正则覆盖

假设在一个关系模式上有一个函数依赖集Ｆ。
每当用户在该关系上执行更新时，数据库系统必须确保此更新不破坏任何函数依赖，也就是说，Ｆ中的所有函数依赖在新数据库状态下仍然满足。

如更新操作破坏了Ｆ上的任一个函数依赖，系统必须回滚该更新操作。

如果去除函数依赖的一个属性不改变该函数依赖集的闭包，则称该属性是无关的。

无关属性的形式化定义如下：
考虑函数依赖集Ｆ及Ｆ中的函数依赖 α → β

• 如Ａ∈α且Ｆ逻辑蕴含 (F - {α → β}) Ｕ{(α - A) → β}，则属性Ａ在α中是无关的。
• 如Ａ∈β且函数依赖集 (F - {α → β}) U {α → (β - A)} 逻辑蕴含Ｆ，则属性Ａ在β中是无关的。

使用无关属性的定义时注意蕴涵的方向：如果将左半部分与右半部分交换，蕴含关系将总是成立的。
也就是说， (F - {α → β}) Ｕ{(α - A) → β} 总是逻辑蕴涵 F，同时 F 也总是逻辑蕴涵 (F - {α → β}) U {α → (β - A)}。

检验一个属性是否无关。
令Ｒ为一关系模式，且Ｆ是在Ｒ上成立的给定函数依赖集。
考虑依赖α → β中的一个属性Ａ

• 如果Ａ∈β，为检验Ａ是否是无关的，考虑集合
  Ｆ’ = (F - {α → β}) U {α → (β - A)}
  并检验α → A是否能由Ｆ’推出。
  计算 F’ 下的${\alpha }^{+}$（α的闭包），如${\alpha }^{+}$包含Ａ，则Ａ在β中是无关的。
• 如Ａ∈α，为检验Ａ是否无关的，令γ=α-{A}，并且检查γ → β是否可由Ｆ推出。
  为此，计算Ｆ下的${\gamma }^{+}$（γ的闭包）；如果${\gamma }^{+}$包含β中的所有属性，则Ａ在α中是无关的。

Ｆ的正则覆盖 $F_c$ 是一个依赖集，使得Ｆ逻辑蕴含$F_c$中的所有依赖，并且$F_c$逻辑蕴含Ｆ中的所有依赖。
此外，$F_c$必须具有如下性质：

• $F_c$中任何函数依赖不含无关属性
• $F_c$中函数依赖的左半部都是唯一的，
• 即$F_c$中不存在两个依赖α１ → β１，α２ → β２，满足α１＝α２
  函数依赖集Ｆ的正则覆盖的计算，可如下图：

给定函数集的正则覆盖未必是唯一的。

无损分解

令 r( R)为一个关系模式， F 为 r( R)上的函数依赖集。
令$R_1$和$R_2$为 R 的分解。
如果用两个关系模式 $r_1(R_1)$ 和 $r_2(R_2)$ 替代 r ( R)时没有信息损失，则称该分解是无损分解（lossless decomposition）。

关系 r 包含与下述SQL查询结果相同的元组集：

select *
from (select R1 from r)
	natural join
	(select R2 from r)

用关系代数可以更简洁的表示为：

$${\Pi }_{R1}(r)?{\Pi }_{R2}(r)=r$$

不是无损分解的分解称为有损分解（lossy decomposition）。
无损连接分解和有损连接分解者两个术语有时用来代替无损分解和有损分解。

可以用函数依赖说明什么情况下分解是无损的。
令R、R1、R2 和 F 如上。R1 和R2是R的无损分解，如果以下函数依赖中至少有一个属于 $F^{+}$：

• R1 ∩ R2 → R1
• R１ ∩ R2 → R2
  即，如果 R1 ∩ R2 是R1 或 R2 的超码，R上的分解就是无损分解。

保持依赖 *****

令F是模式R上的一个函数依赖集，R1, R2, … , Rn构成R的一个分解。

F 是在 $R_i$上的限定是$F^{+}$中所有值包含$R_i$中属性的函数依赖的集合$F_i$。
由于一个限定中的所有函数依赖只涉及一个关系模式的属性，因此判定这种依赖是否满足可以只检查一个关系。

令 $F^{\prime }=F_1\cup F_2\cup ...\cup F_n$。
F’ 是模式R上的一个函数依赖集，不过通常 F’ ≠ F。
但是，即使 F’ ≠ F，也有可能 $F^{\prime +}=F^{+}$。如果后者为真，则F中的所有依赖都被 F’ 逻辑蕴涵，并且，如果我们证明 F’ 是满足的，则就证明了 F 也是满足的。
成具有性质 $F^{\prime +}=F^{+}$ 的分解为保存依赖的分解。

图中给出了判定保持依赖性的算法，
输入是分解的关系模式集 $D=R_1,R_2,...,R_n$和函数依赖集 F 。
因为要计算$F^{+}$，所以这个算法的开销很大。

两种替代方法：

首先，请注意如果F中的每一个函数依赖都可以在分解得到的某一个关系上验证，那么省分解就是保持依赖的。
第二种方法：
该验证方法对F中的每一个 α → β 使用下面的过程：
这里的属性闭包是函数依赖集F下的。如果result 包含β中的所有属性，则函数依赖 α → β 保持。
分解是保持函数依赖的当且仅当上述过程中F的所有依赖都保持。

上述验证方式的两个关键的思想如下：

• 第一个思想是验证F中的每个函数依赖 α → β ，看它是否在 F’ 中保存。
• 第二个思想是使用修改后的属性闭包算法计算 F’ 下的闭包，不用先真正计算出 F’ 。

该判定方法的代价是多项式时间，而不是计算$F^{+}$所需的指数时间的代价。

分解算法

需要能生成属于适当范式的设计的算法。

BCNF 分解

BCNF的定义可以直接用于检查一个关系是否属于BCNF。

如果一个关系不属于BCNF，它可以被分解以创建属于BCNF的关系。

BCNF的判定方法

判定一个关系是否属于BCNF可作如下简化：

• 为检查非平凡的函数依赖 α → β 是否违反BCNF，计算${\alpha }^{+}$（α的属性闭包），并且验证它是否包含Ｒ中所有属性，即验证它是否是 R 的超码。
• 检查关系模式R是否属于BCNF，仅须检查给定集合Ｆ中的函数依赖是否违反BCNF。不用检查$F^{+}$中的所有函数依赖。

为检查Ｒ分解后的关系$R_i$是否属于BCNF，应用如下判定：

• 对$R_i$中属性的每个子集α，确保${\alpha }^{+}$要么不包含$R_i?\alpha$的任何属性，要么包含$R_i$的所有属性。

BCNF分解算法

这个算法利用违反BCNF的依赖进行分解。

3NF 分解

将模式转化为３ＮＦ的保持依赖且无损的分解的算法

算法使用的依赖集$F_c$是Ｆ的正则覆盖。

3NF 算法的正确性

3NF 算法通过为正则覆盖中的每个依赖显式地构造一个模式确保依赖的保持。
该算法通过保证至少有一个模式包含被分解模式的候选码，确保该分解是一个无损分解。

这个算法也称为3NF合成算法，因为它接受一个依赖集合，每次添加一个模式，而不是对初始的模式反复地分解。
该算法的结果不是唯一确定的，因为一个函数依赖集有不止一个正在覆盖，而且，某些情况下该算法的结果依赖于该算法考虑$F_c$中的依赖的顺序。
该算法有可能分解一个已经属于3NF的关系；不过，让然保证分解是属于3NF的。

如有一个关系$R_j$在由该合成算法产生的分解中，则$R_i$属于3NF。
要看$R_i$是否属于3NF，必须确认$R_i$上的任意函数依赖 γ → B 满足3NF定义。

假定该合成算法中产生$R_i$的函数依赖是α → β
因为Ｂ属于$R_i$，而且 α → β 产生$R_i$，所以Ｂ一定属于α或β。

考虑三种可能情况：

• B既属于α又属于β
  此时，依赖α → β将不可能属于$F_c$，否则Ｂ在β中将是无关的。
  所以这种情况不成立。
• B属于β但不属于α
  考虑两种情况：

1. γ 是一个超码。满足3NF的第二个条件。
2. γ不是超码。则α必定包含某些不在 γ 中的属性。
   由于γ → Ｂ在$F^{+}$中，因此它一定是通过使用 γ 上的属性闭包算法从$F_c$推导出来的。

• B属于α但不属于β
  因为α是候选码，所以满足3NF定义中的第三个条件。

BCNF 和 3NF 的比较

3NF的一个优点是我们总可以在满足无损并保持依赖的前提下得到3NF设计。
3NF的一个缺点：我们可能不得不用空值表示数据项间的某些可能有意义的联系，并且存在信息重复的问题。

对应用函数依赖进行数据库设计的目标是：

1. BCNF。
2. 无损。
3. 保持依赖。

在不能得到保持依赖的BCNF分解的情况下，通常倾向于选择BCNF，因为在SQL中检查非主码约束的函数依赖很困难。

使用多值依赖的分解

定义一种新的约束形式，称为多值依赖。

利用多值依赖定义关系模式的一种范式。这种范式称为第四范式（Fourth Normal Form, 4NF），它比BCNF的约束更严格。

每个4NF模式也都属于BCNF，但有些BCNF模式不属于4NF。

多值依赖

函数依赖有时称为相等产生依赖。而多值依赖称为元组产生依赖。

令 r ( R) 为一关系模式，并令 α ? R 且 β ? R。多值依赖（multivalued dependency）。
$$\alpha \to \to \beta$$

在R上成立的条件是，在关系 r( R)的人员合法实例中，对于 r 中任意一对满足 $t_1[\alpha ]=t_2[\alpha ]$的元组对 $t_1$和$t_2$， r 中都存在元组 $t_3$和$t_4$，使得：
多值依赖α →→ β是说 α 和 β之间的联系独立于 α 和 R - β 之间的联系。
若模式R上的所有关系都满足多值依赖 α →→ β，则α →→ β是模式R上平凡的多值依赖。
因此，如果β ? α或β ∪ α =R，则 α →→ β是平凡的。

与函数依赖相同，以两种方式使用多值依赖：

1. 检验关系以确定它们在给定的函数依赖集合多值依赖集下是否合法。
2. 在合法关系集上指定约束；因此，将只考虑满足给定函数依赖集合多值依赖集的关系。

令D表示函数依赖和多值依赖的集合。 D 的闭包 $D^{+}$ 是由D逻辑蕴涵的所有函数依赖和多值依赖的集合。

由多值依赖的定义，可以得出以下规则，对于 α ，β ? R ：

• 若α → β，则α →→ β。
• 若α →→ β，则α →→ R - α - β.

第四范式

函数依赖和多值依赖集为Ｄ的关系模式r( R)属于第四范式（4NF）的条件是，对$D^{+}$中所有形如 α →→ β 的多值依赖（其中α，β?Ｒ），至少有以下之一成立：

• α →→ β是一个平凡的多值依赖。
• α是Ｒ的一个超码。

数据库设计属于4NF 的条件是构成该设计的关系模式集中的每个模式都属于4NF。

令r( R)为关系模式，$r_1(R_1),r_2(R_2),...,r_n(R_n)$为 r( R) 的分解。

考虑函数依赖和多值依赖的集合Ｄ。
Ｄ在$R_i$上的限定是集合${Ｄ}_i$，它包含：

• $D^{+}$中所有只含$R_i$中属性的函数依赖。
• 所有形如$\alpha \to \to \beta \cap R_i$的多值依赖，其中$\alpha ?{Ｒ}_i$，且α →→ β属于$D^{+}$。

4NF 分解

上述算法只产生无损分解，不保持依赖。

学习参考资料：

《数据库系统概念》第6版