模式分解

发布时间：2021-04-19 09:01
最后更新：2021-04-19 09:01
所属分类：
架构知识 数据库设计

模式分解就是将一个大的关系模式$R\langle U, F \rangle$分解为若干小的关系模式。模式分解的过程就是一个系统进行设计时其数据结构和数据结构的设计过程。

模式分解
关系模式$R \langle U, F \rangle$的分解是指$R$被它的一组子集$\rho = \lbrace R_1 \langle U_1, F_1 \rangle, R_2 \langle U_2, F_2 \rangle, \ldots, R_n \langle U_n, F_n \rangle \rbrace$所替代的过程。其中$U=U_1 \cup U_2 \cup \ldots \cup U_n$，并且对于任何$1 \le i, j \le n$，均存在$U_i \not\subseteq U_j$；$F_i$是$F$在$U_i$上的投影，也就是$F_i=\lbrace X \rightarrow Y | X \rightarrow Y \in F^+ \land XY \subseteq U_i \rbrace$。

键

键也称为码，是用来标识其他元组的属性集。通常有以下几种类型。

  • 超键（超码），在关系模式中能唯一标识元组的属性集。
  • 候选键（候选码），在关系模式中，能唯一标识元组并且不包含多余属性的属性集。
  • 主键（主码），在关系模式中的若干个候选键中随意指定的一个候选码作为关键字，这个关键字即为主键。
  • 外键，如果一个关系模式$R$中的属性$F$是其他关系模式的主键，那么$F$在模式$R$中就被称为外键。

从以上定义可以看出来，主键、候选键和超键之间存在着包含关系：$主键 \in 候选键 \in 超键$。

闭包

这里的闭包不是各个编程语言中的闭包，它所指代的意义是关系模式中所有属性集关系的推导结果。以下是闭包的定义。

闭包
令$\alpha$为一个属性集，由$\alpha$确定的的所有属性的集合，即为$\alpha$的闭包，记为$\alpha^+$。

闭包的意义在于如果$\alpha+$中包含关系模式$R$中的所有属性，那么属性集$\alpha$就是$R$的超键。

闭包的示例
例如有一个依赖集：$F = \lbrace A \rightarrow B, B \rightarrow C \rbrace$。那么$F^+$就为以下集合$\lbrace A \rightarrow B, A \rightarrow C, AB \rightarrow A, AB \rightarrow B, AB \rightarrow C, \ldots , ABC \rightarrow ABC \rbrace$

Armstrong公理

一个依赖集的闭包的推算可以通过Armstrong公理来计算。Armstrong公理是一系列的函数依赖推导规则，由三种原始公理和三个补充定律组成。

  • 自反律：若$\beta \subseteq \alpha$，则$\alpha \rightarrow \beta$。
  • 增补律：若$\alpha \rightarrow \beta$，则$\gamma\alpha \rightarrow \gamma\beta$。
  • 传递律，若$\alpha \rightarrow \beta$且$\beta \rightarrow \gamma$，则$\alpha \rightarrow \gamma$。
  • 合并律：若$\alpha \rightarrow \beta$于$\alpha \rightarrow \gamma$成立，则$\alpha \rightarrow \beta\gamma$成立。
  • 分解率：若$\alpha \rightarrow \beta\gamma$成立，则$\alpha \rightarrow \beta$于$\alpha \rightarrow \gamma$成立。
  • 伪传递率：若$\alpha \rightarrow \beta$与$\gamma\beta \rightarrow \delta$成立，则$\alpha\gamma \rightarrow \delta$成立。

现在可以用以上六个定律尝试推导一下前面的示例。

无损连接和函数依赖保持的判定

关系模式的分解必须遵循以下两个准则：

  1. 无损连接：信息不能发生增减，保证不失真。
  2. 保持函数依赖：不破坏属性间存在的依赖关系。

无损连接

无损连接
若$\rho=\lbrace R_1 \langle U_1, F_1 \rangle, R_2 \langle U_2, F_2 \rangle, \ldots, R_n \langle U_n, F_n \rangle \rbrace$是$R\langle U, F \rangle$的一个分解，如果对于$R\langle U, F \rangle$的任何一个关系$r$均有$r=m_p(r)$成立，则分解$\rho$具有无损连接性。

无损连接其实比较好理解，关系模式在分解成比较小的关系模式以后，通过投影、连接以后仍能恢复原来的关系模式，也就是没有丢失信息，则这个分解被称为无损分解，否则就是损失分解。

对于无损分解的检验，一般可以使用以下技巧来进行：如果关系模式$R=\langle U, F \rangle$被分解为$\rho=\lbrace R_1, R_2 \rbrace$，那么如果$R_1 \cap R_2 = R_1 - R_2$或者$R_1 \cap R_2 = R_2 - R_1$，那么这个分解$\rho$就是无损分解。换句话说，$R_1 \cap R_2$是$R_1$或者$R_2$的超键，那么就可以判定分解是无损分解。

如果分解出的关系模式超过两个，例如$\rho=\lbrace R_1, R_2, R_3 \rbrace$，那么就不能采用上述的方法进行快速检验了，只能采用表格列举法来逐个依赖进行推导。

函数依赖保持

函数依赖保持
若$F^+=\left( \bigcup_{i=1}^k F_i \right)^+$，则$R\langle U, F \rangle$的分解$\rho=\lbrace R_1 \langle U_1, F_1 \rangle, R_2 \langle U_2, F_2 \rangle, \ldots, R_n \langle U_n, F_n \rangle \rbrace$保持函数依赖。

简而言之，函数依赖保持实际上就是$F=F_1 \cup F_2 \cup \ldots \cup F_n$，即两者的闭包相等。

对于函数依赖保持的快速判定可以采用以下技巧来进行：如果F上的每一个函数依赖都在其分解后的某一个关系上成立，则这个分解是保持依赖的。

范式

范式是符合某种基本的关系模式的集合。在日常工作中比较经常听到的是第一范式、第二范式、第三范式和BC范式。这四种范式是递进严格的，并且$BCNF \subset 3NF \subset 2NF \subset 1NF$。

更加严格的范式还有第四范式（4NF）和第五范式（5NF），但是它们的规定过于严格，虽然有利于使数据结构达到最简，但是并不一定对日常的查询提供优化，所以在日常设计中很少使用。

第一范式（1NF）

如果关系模式$R$的每个关系$r$的属性都是不可再分的原子值，那么关系模式$R$就是第一范式的模式。用最简单的话说，第一范式对于数据库的设计要求是数据表的每一行都没有重复的数据（冗余数据）。

在实际的数据库结构设计中，第一范式也常常被违反，因为必要的冗余数据可以提高数据库的查询速度，所以这也是在实际应用中为什么会使用反范式设计。

第二范式（2NF）

如果关系模式$R$是1NF，并且每个非主属性都完全函数依赖于候选键，那么关系模式$R$就是第二范式。同样用最简单的话说，第二范式对于数据库设计的要求是所有的非主键数据都完全依赖于主键。

第三范式（3NF）

如果关系模式$R$是1NF，并且每个非主属性都不传递依赖于$R$的候选键，那么关系模式$R$就是第三范式。同样用最简单的话来描述，第三范式对于数据库设计的要求是非主键数据不能依赖于外键。

大部分的数据库结构设计都不能满足第三范式，通常第二范式是最常用的。

BC范式（BCNF）

如果关系模式$R$是1NF，并且每个属性都不传递依赖于$R$的候选键，那么关系模式$R$就是BC范式。简而言之，BC范式要求整个关系模式都不可再分且不能依赖于外键，即所有属性（包括主属性和非主属性）都不能传递依赖于$R$的任何候选码键。

BC范式是四种范式中最严格的存在，是一种最为理想化的数据库设计目标，但是在实际数据库设计中，能够达到BCNF的数据库是及其罕见的。

软考例题

模式分解
有$R=\langle U=\lbrace ABCD \rbrace, F=\lbrace A \rightarrow B, B \rightarrow C, B \rightarrow D, C \rightarrow A \rbrace \rangle$，现将$R$分解为$U_1=\lbrace AB\rbrace$和$U_2=\lbrace ACD\rbrace$两个关系，求$R_1$和$R_2$。

这里可以根据依赖关系，直接推导出$R_1=\langle \lbrace AB \rbrace, \lbrace A \rightarrow B, B \rightarrow A \rbrace$，$R_2=\langle \lbrace ACD \rbrace, \lbrace A \rightarrow C, C \rightarrow A, A \rightarrow D \rbrace$。

无损连接与函数依赖保持判断
设关系模式$R\langle U, F\rangle$，其中$U=\lbrace A, B, C, D, E\rbrace$，$F＝\lbrace A \rightarrow BC, C \rightarrow D, BC \rightarrow E, E \rightarrow A\rbrace$，则分解$\rho=\lbrace R_1(ABCE), R_2(CD) \rbrace$满足（ ） 。
A. 具有无损连接性、保持函数依赖
B. 不具有无损连接性、保持函数依赖
C. 具有无损连接性、不保持函数依赖
D. 不具有无损连接性、不保持函数依赖

首先来确定无损连接性。计算$R_1 \cap R_2$得到$\lbrace C \rbrace$，然后计算其闭包$C^+$。经过计算，$C^+=\lbrace CD \rbrace$，所以$C$是$R_2$的超键，故分解$\rho$是具备无损连接性的。

然后再确定函数依赖保持。$A \rightarrow BC$、$BC \rightarrow E$、$E \rightarrow A$都在$R_1$上成立，$C \rightarrow D$在$R_2$上成立，所以分解是保持函数依赖的。

故这道题选A。

系列文章

  1. 函数依赖
  2. 模式分解
索引标签
架构知识
数据库设计
数据库范式
函数依赖
关系模式分解
模式分解