数据库设计理论

数据库的设计理论

第一节，关系模式的设计问题

一 概念 ：

1. 关系模型：用二维表来表示实体集，用外键来表示实体间的联系，这样的数据模型，叫做关系数据模型。

关系模型包含内涵和外延两个方面：

外延：就是关系或实例、或当前值。它与时间有关，随时间的变化而变化。（主要是由于元组的插入、删除、修改等操作引起的）

内涵：内涵是与时间独立的，它包括关系属性、以及域的一些定义和说明。还有数据的各种完整性约束。

数据的完整性约束分为静态约束和动态约束。

静态约束包括数据之间的联系（称为数据依赖），主键的设计和各种限制。

动态约束主要定义如插入、删除和修改等操作的影响。

通常我们称内涵为关系模式。

2. 关系模式：是对一个关系的描述，二维表的表头那一行称为关系模式，又称为表的框架或记录类型。

关系模式的定义包括：模式名、属性名、值域名和模式的主键。关系模式仅仅是对数据特征的描述。

关系模式的一般形式为 R ( U , D , DOM , F )

R 是关系名。

U 是全部属性的集合。

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

D 是属性域的集合。

DOM 是 U 和 D 之间的映射关系，关系运算的安全限制。 F 是属性间的各种约束关系，也称为数据依赖。

关系模式可以表示为：

关系模式 （ 属性名1，属性名2 ，……，属性名n ）

示例 ： 学生 （ 学号，姓名，年龄，性别，籍贯 ）。

当且仅当 U 上的一个关系 r 满足 F 时 ，r 就称为关系模式 R（U，F）上的一个关系，R是关系的型，r 是关系的值，每个值称为R 的一个关系。

关系数据库模式：

一个数据库是由多个关系构成的。

一个关系数据库对应多个不同的关系模式，关系数据库模式是一个数据库中所有的关系模式的集合。它规定了数据库的全局逻辑结构。

关系数据库模式可以表示为：

S = { Ri < Ui , Di , DOM , Fi > | i = 1,2,…, n }

3. 关系子模式

关系子模式是用户所用到的那部分数据的描述。

外模式是关系子模式的集合。

4. 存储模式

存储模式及内模式。

关系数据库理论的主要内容：

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

（1）数据依赖。 数据依赖起着核心的作用。 （2）范式 。

（3）模式的设计方法。

如何设计一个合理的数据库模式：

（1）与实际问题相结合。

泛关系模式：把现实问题的所有属性组成一个关系模式 泛关系：泛关系模式的实例称为泛关系。

泛关系模式中存在的问题：

a 数据冗余 b 更新异常，c 插入异常 d 删除异常 。 （2）数据库设计理论：

借助近代代数工具，把抽象的数据理论同实际问题结合起来。 理论基础：数据依赖 （数据的相关性）。

二 ， 关系模式及其评价。

1 . 关系数据库设计的核心 ： 关系模式的设计。

2 . 关系模式的设计：

按照一定的原则，从数量众多的而又互相关联的数据中构造出一组即能较好的反映现实世界，而又有良好的操作性能的关系模式。

3. 关系模式的优劣、评价、改进：

冗余度高 修改困难 插入问题 删除问题

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

这些问题的产生原因是：属性间的约束关系太强，即数据间的依赖关系太强。

解决的方法：将关系模式分解为一组较理想的关系模式。

第二节 函数依赖

一，函数依赖 Functional Dependency

函数依赖是数据依赖的一种，反映属性或属性之间的依存、互相制约的关系，既反映现实世界的约束关系。

二 ， 函数依赖的定义

设 R ( U ) 是属性 U 上的一个关系模式 ，X 和 Y 均为 U = { A1,A2 ,…An} 的子集，r 为 R 的任一关系，如果对于 r 中的任意两个元组 u 和 v ，只要有 U[X] = V[X] , 就有U[Y] = V[Y] ，则称 X 函数决定 Y ，或称Y 函数依赖于X，记作：

X → Y 。

三 ， 函数依赖的语义范畴：

1. 语义：数据所反映的现实世界事务本质的联系。 2．根据语义来确定函数依赖型的存在与否。

3．函数依赖反映属性之间的一般规律，必须在关系模式 F 的任何一个关系 r 都满足约束条件。

回顾概念

键 ：由一个或多个属性组成。

设 R (U) 为一个关系模式，F 为 R 的函数依赖集，X 为 属性集U的子集 。

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

（1）超键 ：能唯一标识元组的属性集。

如果 X → U ∈ F ，则 X 是 R 的超键 。

（2）候选键 ：不含有多余属性的超键

a X 是 R 的超键 。

b 且不存在 X 的真子集 Y ，使得 Y → U ∈ F+

则称 X 是 R 的候选键

（3）主键 ：用户选作元组标识的一个候选键。 （4）主属性：包含任何一个候选键的属性。 （5）非主属性：不包含任何一个候选键的属性。

（6）外键：如果关系 R 的某一个属性组不是该关系本身的候选键，而是另一个关系的候选键，则称该属性组是R的外来关键码，或称为外键（外码） 。

如何确定候选码？

（1）如果有属性不在函数依赖集中出现，那么它必定包含在候选码中。

（2）如果有属性不在函数依赖集中任何函数依赖的右边出现，那么它必定包含在候选码中。

（3）如果该属性或属性组能唯一标识元组，则它就是候选码。

根据对数据库的语义描述，确定其中候选码，同时还可以写出该关系模式的函数依赖集。

四 ， 函数依赖的关系

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

属性间的关系决定函数依赖关系。

设 X 和 Y 都是 U 的子集 ：

1 X 和 Y 的联系是 1 ：1 则 X → Y , Y → X .

2 X 和 Y 的联系是 M ：1 ( M > 1 ) 则 X → Y .

3 X 和 Y 的联系是 M ：N ( M ,N > 1 ) 则，X、Y之间不存在函数依赖。

五 函数依赖 图 ： FD 图。

六 完全函数依赖 和部分函数依赖

在 R (U) 中，如果 X → Y ，并且对于 X 的任何真子集 X ` ，都不存在 X` → Y ，则称 Y 完全依赖于 X ，记作

X → Y ( 箭头上加个 F 表示 FULL 完全函数依赖 )

否则，如果 X → Y ，且 X 中存在一个真子集 X`, 使得 X` → Y ，则 Y 部分函数依赖 X 。

X → Y ( 箭头上面加一个P，表示 PART，部分函数依赖 )

七 平凡函数依赖 和非平凡函数依赖

设 X , Y 均为某关系的属性集，并且 X → Y ,

若 Y 包含于 X ，则称 X → Y 为平凡函数依赖 （ Y 是 X 的子集）。

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

若 Y 不包含于 X ，则称 X → Y 为非平凡函数依赖（Y不是X的子集）

第三节 函数依赖的蕴涵与公理体系

一，函数依赖的逻辑蕴含

定义 ：设有关系模式 R ( U )，及其函数依赖集 F，如果对于 R 的任何一个满足 F 的关系 r ，函数依赖 X → Y 都成立，则称 F 逻辑蕴含 X → Y 或称 X → Y 可以由 F 推出，记作 ：

例题 ：关系模式 R = ( A, B, C ) ，函数依赖集 F = { A→B , B→C } 则 F 逻辑蕴含 A→C 记作：

二 ，F 闭包

定义： 若 F 为关系模式 R ( U ) 的函数依赖集，我们把 F 以及所有被 F 逻辑蕴含的函数依赖的集合称为 F 的闭包，记作 F+ 。

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

F+ = { X→Y | F ╠ X→Y }

三，Armstrong 公理

F1 自反律 ： 若Y 包含于X ，则 X → Y （Y 是 X 的子集 ）

F2 增广律 ： 若 X→Y为F所蕴含，则 XZ→YZ 在R上成立。

F3 传递律 ： 若 X→Y，Y→Z在R上成立，则 X→Z 在R上成立。

F4 伪增律 ：Z是W的子集，X→Y为F所蕴含，则 XW→YZ 在R上成立。

F5 伪传律 ：若 X→Y，YW→Z为F所蕴含，则 XW→Z 在R 上成立。

F6 合并律 ：若 X→Y , X→Z 为F所蕴含，则 X→YZ 在 R 上成立。

F7 分解律 ：若 Z 是Y的子集，X→Y为F所蕴含，则 X→Z在R上成立。

四，属性集的闭包

定义：若 F 为关系模式 R ( U ) 的函数依赖集，X 是 U 的子集，则由Armstrong 公理推导出来的所有 X → Ai 所形成的属性集 { Ai | i=1,2,…,n } 称为 X 关于 F 的闭包 记为 X + 。

属性集闭包的举例 ：

设： R = ABC , F = { A→B, B→C } 当X分别是 A , B , C ,时，求 X+

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

解： 当 X = A 时，X+ = ABC 当 X = B 时，X+ = BC 当 X = C 时，X+ = C

定理 ：X → Y 能根据 Armstrong 推理规则导出的充要条件是：

只要 Y 是 X+ 的子集 ，则 X → Y 。 只要 X → Y ，则 Y 一定是 X+ 的子集 。

定理 ： Armstrong 公理的完备性定理

函数依赖推理规则系统（自反律、增广律、传递律）是完备的。

函数依赖公理体系

Armstrong 公理体系

由于Armstrong公理的完备性，Armstrong公理及其推论构成了一个完备的逻辑推理体系，称为Armstrong公理体系：

A ，一套形式推理规则。

B ，利用这些推理规则可以求出给定关系模式的关键字。

C ，而且可以从关系模式的一组已知函数依赖出发，求得它蕴含的所有函数依赖。

D ，或者对于给定的 F 和 X → Y ，判断 X → Y 是否在 F+ 中。 E ，是关系规范化理论的依据。

23

页脚内容

喀斯特石漠化预警分析及其灾害风险决策系统

计算 X+ 的算法

1）

依据 ：

若 F 为关系模式 R ( U ) 的函数依赖集，X , Z , W 是 U的子集，对于任意的 Z → W ∈ F , 若 Z 是 X 的子集 ，则 X→XW

2）

输入 ：关系模式 R 上的子集 X ，R 上的函数依赖 F 输出：X 关于 F 的闭包 X+ 3）算法：

a． 令 X (0) = φ , X+ = X ;

b. 如果 X(0) ≠ X+ ,置 X(0) = X+ ，否则，转到 d ； c．对于 f 中的每个未被访问过的函数依赖 Y → Z ，若 Y 包含于 X+ ，则令

X+ = X+ ∪ Z ，为被访问过的函数依赖设置访问标志，转 b ； d．输出 X+

算法的实现

结论

判定函数依赖 X → Y 是否能由 F 导出的问题，可以转化为求 X+ 的闭包，并判定 Y 是否是 X+ 子集的问题。

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

即求闭包的问题可以转化为求属性集的问题。

判定给定函数依赖 X → Y 是否蕴含与函数依赖集 F 算法实现：

输入：函数依赖集 F ， 函数依赖 X → Y 输出：若 X → Y ∈F+ ，输出真，否则输出假 。

四 ，函数依赖的等价和覆盖

定义： 设 F 和 G 是关系模式 R ( U ) 上的两个函数依赖集，如果F+ = G+ ,则称 F 等价于 G ，亦称 F 覆盖 G 或者 G 覆盖F ，记作：

F ≡ G

定理1 , 设 F 和 G 是关系模式 R ( U ) 的两个函数依赖集，那么 F+ = G+ 的充分必要条件是：

定理2， 设 F 和 G 是关系模式 R ( U ) 的两个函数依赖集，那么 F+ = G+ 的充分必要条件是

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

定理3 ，每个函数依赖集 F 都可以被一个右部只有单属性的函数依赖集 G 所覆盖。

五，最小函数依赖集

设 F 是函数依赖集，如果 F 满足

（1） F中每个函数依赖 X→Y的右边均为单个属性。 （2） F中的任何一个函数依赖X→A ,其 F－( X→A ) 都与 F 不等价。

（3） F中的任何一个函数依赖X→A , Z为X的真子集 ，

( F － { X→A } ) ∪ { Z → A } 都与 F 不等价。

则称 ， F 为最小函数依赖集。

（2）是消除右侧冗余。 （3）是消除左侧冗余。

因为 （2），（3）没有先后顺序，所以，最小函数依赖不是唯一的。

第四节 关系模式的分解

一 ，关系模式分解的衡量标准

（1）仅具有无损连接性 。 （不增减信息）

（2）仅保持函数的依赖集。 （不破坏属性间存在的依赖关系）

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

（3）即具有无损连接性，又保持函数依赖集。

二，分解的无损连接性：

1．定义： 设 F 是关系模式 R 的函数依赖集

σ = { R1 ( U1 , F1 ) , R2 ( U2 , F2 ) , …, Rk ( Uk , Fk ) } 是 R 的一个 分解，

或者

如果 R 满足 F 的任何 一个关系均有

则分解具有无损连接性。

定理 ：设 σ = （ R1 < U1,F1 > , R2 < U2 , F2 > , …,Rk ） 为关系模式的一个分解 ，r 为 R 的任何一个关系 ri = πui (r) 则：

（1）

（2） 如果 S = mσ(r) 则 πui(S) = ri

(3) mσ(mσ(r))= mσ(r)

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

结论 ：

分解后的关系作自然联结必包含分解前的关系 。即分解不会丢失信息，但可能增加信息。 只有 r = mσ(r) 时，分解才具有无损连接性。

为什么要进行关系分解？

一个关系分解后，可以存放原来不能存放的信息（通常称为“悬挂”的元组），这是实际所需要的，正是分解的优点。

在做自然联结时，这类“悬挂”元组自然丢失了，但不是信息的丢失，而是合理的。

检验分解无损联结的算法

设关系模式 R ( A1 , A2 , …,An) F 是他的函数依赖集 ，

σ = { R1 , R2 , R3 , …, Rk } 为 R 的一个分解 。 算法

（1）构造初始表

构造一个k行n列的初始表，其中每列对应于R的一个属性，每行用于表示分解后的一个模式组成。如果属性 Aj 属于关系模式 Ri ，则在表的第 i 行第 j 列置符号 aj ，否则，置符号 bij .

（2）根据 F 中的函数依赖修改表的内容

考察 F 中的每一个函数依赖 X → Y ，在属性组 X 所在的那些列上寻找具有相同符号的行，如果找到这样的两行或更多行，则修改这些行，使这些行上的属性组 Y 所在的列上的元素相同。

修改规则：如果 Y 所在的要修改的行中有一个为 aj ，则这些元素均变为 aj ，

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

否则，改动为 bmj , 其中 m 为这些行的最小行号。

注意：若某个 bij被改动，则该列中凡是与 bij相同的符号均作相同的改动。 循环的对 F 中的函数依赖进行逐个处理，直到发现表中有一行变为 ： a1 , a2 , a3 ,…, an 或者不能再被修改为止。

（3）

断分解是否无损联结

如果通过修改，发现表中有一行变为a1,a2 , … , an ，则分解是无损联结的，否则，分解不具有无损联结性。

定理 ：检验分解无损联结的算法，能够正确判定一个分解是否具有无损联结性。

定理 ：设 σ = （ R1 , R2 ） 是模式 R 的一个分解， F 是 R 的函数依赖集，那么，σ 是 R ( 关于 F 的 ) 的无损分解的充要条件是：

（R1 ∩ R2）→ R1 － R2 ∈F 或者

( R1 ∩ R2 ) → R2 － R1 ∈F

保持函数依赖的分解

定义 ：设 F 是关系模式 R 在所有属性集 U 上的函数依赖集，Z 是 U 的子集，F 在 Z 上的一个投影用 πz ( F ) 表示，定义为：

πz ( F ) ={ X→Y | X→Y ∈F+ 且 XY 是Z 的子集}

设关系模式 R 的一个分解 σ = { R1 , R2 , … , Rk }

如果 Fi = πRi 的并集

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

（ F1 ∪ F2 ∪ … Fk ）+ = F+

则，分解保持函数依赖集F

关系模式满足的确定条件称为范式 。根据满足的约束条件不同，范式可以分为 1NF、2NF、3NF、BCNF、4NF、5NF 等。

不同的范式，性质不同。

关系模式规范化：把一个低一级的关系模式分解为高一级的关系模式的过程。

回顾概念

1． 2．

超键：能唯一标识元组的属性集。 候选键：不含有多余属性的超键

a. X 是 R 的超键。

b. 且不存在X的真子集Y，使得 Y→U ∈F+ 则称 X 是R 的候选键

3． 4． 5． 6．

主键：用户选作元组标识的一个候选键。 主属性：包含在任何一个候选键中的属性。

非主属性：不包含在任何一个候选键中的属性。

外键：如果关系R的某一个属性组，不是该关系本身的候选

关键字，而是另一关系的候选关键字，则称该属性组是 R 的外来关键字

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

或外部关键字。

完全函数依赖和部分函数依赖

在 R ( U ) 中，如果 X → Y ，而且对于 X 的任意真子集 X’ ，都不存在 X’ → Y ，则称 Y 完全依赖于 X ，否则，如果 X → Y , 且存在 X 的真子集 X’，使得 X’ → Y 成立，则 Y 部分函数依赖于 Y 。

如何确定关系模式中的候选码？

（1）如果有属性不在函数依赖集中出现，那么它必须包含在候选码中。 （2）如果有属性不在函数依赖集中任何函数依赖的右边出现，那么它必定包含在候选码中。

（3）如果该属性或属性组能唯一的标识元组，则它就是候选码。

未给出关系模式的函数依赖集，如何确定其中的候选码？

根据对数据库的语义描述，确定其中的候选码，同时还可以写出该关系模式上的函数依赖集。

第一范式：1NF

关系模式的所有域为简单域，其元素不可再分，是数据项而不是数据组，这样的关系模式称为第一范式 ：1NF

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

存在的问题：数据冗余，插入异常，删除异常，修改异常。

第二范式 ：2NF

给定关系模式 R 及其上的函数依赖集 F ，如果 R 上的任何一个非主属性都完全依赖于他的每一个候选关键字，则称 R 是第二范式 ：2NF

若关系模型 H 包含的每个关系模式都是 2NF 的，则称该关系模型是 2NF 的。

存在的问题：可能存在数据冗余 ，插入异常，删除异常，修改异常。

结论：若 R ∈ 1NF ，且 R 中所有的候选码为单一属性，则 R ∈ 2NF 。

传递函数依赖

在 R ( U ) 中，如果 X → Y ，Y → Z ，并且 Z 不是 Y 的子集 ，那么称 X → Z 传递函数依赖，即 Z 传递函数依赖于 X >

第三范式

给定关系模式 R 及其上的函数依赖 F ，如果 R 的任何一个非主属性都不传递函数依赖于他的任何一个候选码，则称 R 是第三范式 3NF 。

若关系模型 H 包含的每一个关系模式都是 3NF 的，则称该关系模式是 3NF 的。

定理：一个 3NF 的关系模式必定是 3NF 的 。

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

BCNF ( 改进了的 3NF )

给定关系模式 R 及其上的函数依赖集 F ，如果 F 中每一个非平凡函数依赖 X → Y 的左部 （ 决定因素 ） X 中必含有候选码，则称 R 是 Boyde /Codd 范式，简称 BCNF 。

R ∈ 1NF 若 X → Y 且 Y 不是 X 的子集，X 中必含有候选码。 则

R ∈ BCNF

BCNF 的内涵

（1）非主属性对候选码完全函数依赖。 （2）主属性对不含他的候选码完全函数依赖。 （3）没有属性完全函数依赖于一组非主属性。 （4）主属性不传递函数依赖于任何一个候选码。 （5）主属性不传递函数依赖于任何一个候选码。

定理： BCNF 满足 3NF 。

重叠的候选码

一个模式有两个非单属性的候选码，且二者的交集非空，则称这两个候选码是重叠的。

若模式中没有重叠的候选码时，则 2NF 一定是 BCNF 。

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

只有当模式中有重叠的候选码时，3NF 不一定是 BCNF 。

总结： 1NF

↓ 消除了非主属性对候选码的部分函数依赖。 2NF

↓ 消除了非主属性对候选码的传递函数依赖。 3NF

↓ 消除了主属性对候选码的部分和传递函数依赖。 BCNF

规范化的基本思想

逐步消除不合适的函数依赖，使数据库的各个关系模式达到某种程度上的分离。

模式分解的算法

模式分解的基本要求：

分解后的关系模式与分解前的关系模式等，即分解必须

（1） 具有无损联结性， （2） 保持函数依赖。

逐步分解的定理：

设 F 是关系模式 R 的函数依赖集

ρ = { R1 , R2 , … , Rk } 是R关于 F 的一个无损连接分解。

1． 若 ρ1 = { S1 , S2 , … , Sm } 是 Ri 关于 Fi 的一个无损连接分解，其中 Fi =

πRi (F) ,则 ρ2 = { R1,…Ri-1,S1,…,Sm,Ri+1,…,Rk } 是 R 关于 F 的无损分

2． 设 ρ3 = { R1,…,Rk,Rk+1,…,Rn } 是 R 的一个分解，其中ρ是ρ3的子集，，

页脚内容

解。

23

喀斯特石漠化预警分析及其灾害风险决策系统

则ρ3 也是关于 F 的无损联结分解。

面向 BCNF 且具有无损联结的分解

算法1 ：输入 ：关系模式 R ，函数依赖集 F ，

输出 ：R 的一个无损联结的分解，其中每一个子模式都满足 F 在其上投影的 BCNF .

算法实现：

反复运用逐步分解定理，逐步分解关系模式 R 使得每次分解都具有无损联结性。而且每次分解出来的子关系模式都至少有一个具有 BCNF范式。

（1）置初值ρ = { R } ，

（2）检查ρ 中的关系模式，如果均属 BCNF 则转到第4步。

（3）在ρ中找出不属于BCNF的关系模式 S ，那么 S中必能找出一个

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

函数依赖 X→A ∈F （A不包含于X）且X不是S的候选码。因此，XA必然不包含 S 的全部属性。

把 S 分解为 { S1 , S2 } ,设 S1 = XA , S2 = S－A ,并以 { S1 , S2 } 代替 R 中的 S ，返回 （2）。

（4） 终止分解 ，输出ρ .

算法出现的问题 ：

（1） 分解结果不是唯一的。 （2） 分解不保证保持函数依赖。

面向 3NF 且保持函数依赖的分解

算法2 输入：关系模式 R 及其上的最小函数依赖集 F .

输出： R 的保持函数依赖的分解，其中每个关系模式是关于 F 在其上投影的 3NF 。

算法实现 ：

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

（1） 如果 R 中存在一些不在 F 中出现的属性，则将他们单独构成一个关系模式，并从关系模式 R 中消去。

（2） 如果 F 中有一个函数依赖 X → A ，且 XA = R ，则 R 不用分解，算法终止。

（3） 对 F 中的每个函数依赖 X → A ，构造一个关系模式 XA 。 如果 X → A1 , X → A2 , …, X → An 均属于 F , 则构造一个关系模式 XA1A2…An 。

本算法注意 ，必须是最小函数依赖集 F ，否则出错。

面向 3NF 既有无损联结性，又保持函数依赖分解

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

算法 ： 输入： 关系模式 R 及其上的最小函数依赖集 F 。 输出： R 的具有无损联结性及保持函数依赖的分解。

算法实现：

（1） 按算法2对关系模式 R 进行分解，设结果为ρ ρ = { R1 ,R2 , Rk }

（2） X 是 R 的候选码 t =ρu { x } 是 R 的一个分解。

（3） 求 t 的最小集合 。（ 当 Ri 是 Rj 的子集 ∈t 时，消去Ri ）

定理 算法的正确性。

设 X 是 R 的候选码 ，则 t =ρ u{x} 是 R 的一个分解，且所有的关系都满足 3NF ，同时具有无损联结性，和保持函数依赖性 。

由于ρ 中全部模式均为 3NF ， X 中属性之间不存在传递和部分函数依赖， 即 X 也是 3NF 的， 分解t 也具有无损联结性。由于 X 是 R 的候选码， 验证表中模式 X 所对应的行，经修改后全部由 a 组成。

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

模式设计的原则

关系模式 R 相对于函数依赖 F 分解成数据库模式

ρ = { R1 , R2 ,…,Rk } 一般具有下面 4 个特性。

（1）ρ 中的每个关系模式 Ri 上应具有某种范式的性质。 （ 如 3NF , BCNF ） （2）无损联结性。 （3）保持函数依赖集。

（4）最小性 ，即ρ中模式个数应最少，且模式中属性总数应最少。

一个好的模式设计方法应符合下了三条原则。

（1）表达性 。 （2）分理性 。 （3）最小冗余性 。

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

多值依赖

函数依赖有效的表达了属性之间的多对一联系，但不能表达属性之间的一对多联系 ，更不能表达属性之间的多对多之间的联系。

定义

设 R ( U ) 是属性 U 上的一个关系模式 ，X , Y , Z 均为 U={ A1,A2,…,An } 的子集 ，并且 Z = U－X－Y ，用小些字母 x, y, z 分别代表属性集 X ,Y ,Z 的值，只要 r 为 R 的关系 ，r 中存在元组 （ x , y , z ） 和 （ x , y2 , z ），那么称多值依赖于 X →→ Y 在 R 中成立。

函数依赖是多值依赖的特列。

平凡多值依赖和非平凡多值依赖

对于属性集 U 上的一个多值依赖 X→→Y ， （ X , Y 均为U的子集） ，如果 X 包含 Y 或者 Z = U－X－Y = φ , 则称 X→→Y 为平凡多值依赖。

23

页脚内容

喀斯特石漠化预警分析及其灾害风险决策系统

若 Z = U－X－Y ≠ φ ， 则称 X→→Y 为非平凡多值依赖。

函数依赖和多值依赖的区别

（1）函数依赖在小范围内成立，则在大范围内一定成立，多值依赖在小范围成立，在大范围上未必成立。

（2）若函数依赖 X → Y 在 R ( U ) 上成立，则对于任何真子集 Y’ ，均有 X → Y’ 也成立

对于多值依赖 X→→ Y 在 R ( U ) 上成立，都不能断言对于任何真子集 Y’ 均有 X→→ Y’ 也成立 。

第四范式 4NF

设R 是一个关系模式 ， D 是 R 上的多值依赖集合。如果 D 中成立非平凡多值依赖 X →→ Y 时，X 必包含 R 的候选键 ，那么，称 R 是第四范式 。

算法四 面向4NF 且具有无损联结性的分解

输入：关系模式R ，及其函数依赖和多值依赖集 F 。

输出：R 相对于 D 的一个无损联结分解，其中每个子关系模式都是 4NF 。

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

算法实现

（1） 置初值 ρ = { R } ;

（2）检查ρ中的关系模式均属于 4NF 则转 （4）；

（3）在ρ中找出不属于 4NF 的关系模式 S ，那么 S 中必能找出一个非平凡的多值依赖 X →→ Y ， 且 X 不是 S 的候选码 ，因此可以把 S 分解为 { S1 , S2 } ,设 S1 = XY ， S2 = S － Y ,并以 { S1 , S2 } 代替ρ中的 S ,返回 （2）。

（4）终止分解 ，输出ρ 。

总结： 1NF

↓ 消除了非主属性对候选码的部分函数依赖

页脚内容

23

喀斯特石漠化预警分析及其灾害风险决策系统

2NF

↓ 消除了非主属性对候选码的传递函数依赖。 3NF

↓ 消除了主属性对候选码的部分和传递函数依赖 BCNF

↓ 消除了非平凡且非函数依赖的多值属性 4NF

规范化的基本思想

逐步消除了不合适的函数依赖，使数据库中的各个关系模式达到某种程度的分离。

页脚内容

23