数据库系统原理-函数依赖和关系模式分解

学习本章相关理论知识可以为优化我们设计的数据库模型

第一范式

如果某个域中元素被认为是不可分的，则这个域称为是原子的

非原子域的例子：

• 复合属性：名字集合
• 多值属性：电话号码
• 复杂数据类型：面向对象的

如果关系模式R的所有属性的域都是原子的，则R称为属于第一范式

（1NF）

非原子值存储复杂并易导致数据冗余，在数据库系统中我们创建的表基本都属于第一范式

如何处理非原子值

• 对于组合属性：让每个子属性本身成为一个单独的属性
• 对于多值属性：为多值集合中的每个项创建一条元组（再建表）

原子性

原子性实际上是由域元素在数据库中如何被使用决定的

例如，字符串通常会被认为是不可分割的，假设学生被分配这样的标识号：CS0012或SE1127，如果前两个字母表示系，后四位数字表示学生在该系内的唯一号码，则这样的标识号不是原子的（字符串+数字）

当采用这种标识号时，是不可取的。因为这需要额外的编程，而且信息是在应用程序中而不是在数据库中编码

关系数据库设计中易犯的错误

关系数据库设计要求我们找到一个好的关系模式集合。一个坏的

设计可能导致以下问题

• 数据冗余
• 插入、删除、修改异常

假设，我们用以下模式代替instructor模式和department模式：

inst_dept(ID, name, salary, dept_name, building, budget)

这样的关系模式存在以下问题

• 数据冗余

• 更新异常

更新复杂，容易导致不一致问题。例，修改dept_name，很多相关元组都需要修改

• 插入/删除异常

使用空值(null)：存储一个不知道所在系的教师信息，可以使用空值表示dept_name, building, budget数据，但是空值难以处理

模式分解

例：可以将关系模式(A,B,C,D)分解为：(A,B)和(B,C,D)，或(A,C,D)和

(A,B,D)，或(A,B,C)和(C,D)，或(A,B)、(B,C)和(C,D)，或 (A,D)和

(B,C,D)

例：将关系模式inst_dept分解为：

― *instructor*(*ID,name,dept_name,salary*)  

― *department*(*dept_name,building,budget*) 

无损连接分解

优化关系模式的步骤

判断关系模式好坏—>若是后者—>关系模式分解解成模式集合{R1**, R**2, …, Rn}使得：每个关系模式都是“好的形式”且分解是无损连接分解

我们优化关系模式的理论基于

• 函数依赖（ functional dependencies ）
• 多值依赖（ multivalued dependencies ）

函数依赖

函数依赖定义

一种完整性约束，表示特定的属性值之间的关系，可以用来判断模式规范化和建议改进

这里解释以下，候选码是最小超码

函数依赖使我们可以表达用超码无法表达的约束，考虑模式

inst_dept(ID,name,salary,dept_name,building,budget) 
/*budget表示预算*/
/*building表示部门地点*/

我们期望下列函数依赖成立：

dept_name -->building
ID --> building

而不期望下列函数依赖成立：

dept_name --> salary

函数依赖的使用

• 函数依赖集：多条函数依赖（A->B）的集合
• 可以这么理解，A列相同的值对应C列相同的值如a1->c1 a2->c2…

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mfD8YTDp-1574005601262)()]

R是关系模式
r是关系

函数依赖集的闭包

Armstrong公理

利用Armstrong公理来找出函数依赖集的闭包

Armstrong公理二级定律

闭包计算算法

属性集的闭包

属性闭包的用法

正则覆盖

无关属性

检测属性是否无关

正则覆盖

规范化-模式分解

当R 不是“好的”形式时，将它分解成模式集合{R1, R2, …, Rn}使得

• 每个关系模式都是**“好的”形式**

• 分解是无损连接分解

• 分解是保持依赖

分解验证算法

模式分解总结

规范化-简单版

图示法求候选键

条件：给出函数依赖集，求候选键

1. 将关系的函数依赖关系用有向图表示
2. 找出入度为0的属性，并以该属性集合为起点，尝试遍历所有的图，若能遍历途中所有结点，则该属性集为关系模式的候选键
3. 若入度为0的属性集不能遍历途中所有的结点，则需要尝试性的将 一些中间结点（既有入度，也有出度的结点）并入入度为0的属性集中，直至该集合能遍历所有结点，集合求候选键

主属性和非主属性

组成候选码的属性是主属性、其他的就是非主属性

第一范式（1NF）

在上面

第二范式（2NF）

当且仅当关系模式R是第一范式（1NF），且每一个非主属性完全依赖（A->B->C）候选键（没有不完全依赖（部分依赖（AB->C/A->C））时），则称关系模式R为第二范式

例子：关系模式SC（学号、课程号、成绩、学分），其中（学号，课程号）->成绩，

课程号->学分

分析：因为存在部分依赖，故不满足第二范式

解决：分解成（学号、课程号、成绩）（课程号，学分）

第三范式（3NF）

在2NF上取消完全依赖

例子：

学生关系（学号、姓名、系号、系名、系位置）

分析：该模式存在完全函数依赖（学号->系号–>系名）

解决：分解成（学号、姓名、系号） （系号、系名、系位置）

BC范式（BCNF）

设R是一个关系模式，F是它的依赖集，R属于BCND当且仅当其F中每个依赖的决定因素必定包含R的某个候选码（取消主属性对候选键的部分和传递依赖）

模式分解-保持函数依赖分解

原则：两个关系模式之间不能乱推，得看依赖集

模式分解-无损分解

关系数据库逻辑设计
针对具体问题，如何构造一个适合于它的数据模式
数据库逻辑设计的工具──关系数据库的规范化理论
关系模式由五部分组成，即它是一个五元组：

                    R(U, D, DOM, F)
R：      关系名
U：       组成该关系的属性名集合
D：       属性组U中属性所来自的域
DOM： 属性向域的映象集合
F：       属性间数据的依赖关系集合

数据依赖

一个关系内部属性与属性之间的约束关系
现实世界属性间相互联系的抽象
数据内在的性质
语义的体现
2. 数据依赖的类型
函数依赖（Functional Dependency，简记为FD）
多值依赖（Multivalued Dependency，简记为MVD）
其他

关系模式R（U, D, DOM, F）
    简化为一个三元组：
                    R（U, F）
当且仅当U上的一个关系r满足F时，r称为关系模式 R（U, F）的一个关系

数据依赖对关系模式的影响

[例1]建立一个描述学校教务的数据库：
    学生的学号（Sno）、所在系（Sdept）
    系主任姓名（Mname）、课程名（Cname）
    成绩（Grade）

单一的关系模式 ：   Student <U、F>
U ＝｛ Sno, Sdept, Mname, Cname, Grade ｝

   属性组U上的一组函数依赖F：
    F ＝｛ Sno → Sdept,  Sdept → Mname, 
                (Sno, Cname) → Grade ｝

关系模式Student(U, F)中存在的问题
1. 数据冗余太大
2. 更新异常（Update Anomalies）
3. 插入异常（Insertion Anomalies）
4. 删除异常（Deletion Anomalies）
结论：
Student关系模式不是一个好的模式。
“好”的模式：
不会发生插入异常、删除异常、更新异常，
数据冗余应尽可能少
原因：由存在于模式中的某些数据依赖引起的（这也是对关系
模式进行分解的根本理由）
解决方法：通过分解关系模式来消除其中不合适的数据依赖

分解关系模式

把这个单一模式分成3个关系模式：
     S（Sno，Sdept，Sno → Sdept）;
     SC（Sno，Cno，Grade，（Sno，Cno） → Grade）;
     DEPT（Sdept，Mname，Sdept→ Mname）

规范化

规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。最终使各关系模式达到某种程度的分离，即“一事一地”的模式设计原则

函数依赖

函数依赖（Functional Dependency,FD）
平凡函数依赖与非平凡函数依赖
完全函数依赖与部分函数依赖
传递函数依赖

   设R(U)是一个属性集U上的关系模式，X和Y是U的子集。
    若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等， 而在Y上的属性值不等， 则称 “X函数确定Y” 或  “Y函数依赖于X”，记作X→Y。  

设有关系模式R（U），X和Y是属性集U的子集，函数依赖（functional dependency，简记为FD）是形为X→Y的一个命题，若对于R(U)的任意一个可能的关系r ，对r中任意两个元组t和s，都有t［X］＝s［X］蕴涵
    t［Y］＝s［Y］，那么称FD X→Y在关系模式R（U）中成立。

1. 所有关系实例均要满足
2. 语义范畴的概念

例如：姓名→年龄这个函数依赖只有在该部门没有
同名人的条件下成立

平凡函数依赖与非平凡函数依赖

在关系模式R(U)中，对于U的子集X和Y，
如果X→Y，但Y  X，则称X→Y是非平凡的函数依赖
若X→Y，但Y  X,   则称X→Y是平凡的函数依赖
例：在关系SC(Sno, Cno, Grade)中，
            非平凡函数依赖： (Sno, Cno) → Grade
            平凡函数依赖：     (Sno, Cno) → Sno 
                                          (Sno, Cno) → Cno

若X→Y，则X称为这个函数依赖的决定属性组，也称为决定因素（Determinant）。
若X→Y，Y→X，则记作X←→Y。
若Y不函数依赖于X，则记作X→Y。

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

在R(U)中，如果X→Y，并且对于X的任何一个真子集X’，都有X’     Y, 则称Y对X完全函数依赖，记作
     X F  Y。
  若X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作X   P   Y。

[例1] 中(Sno,Cno)→Grade是完全函数依赖，
             (Sno,Cno)→Sdept是部分函数依赖
              因为Sno →Sdept成立，且Sno是（Sno，Cno）的真子集

传递函数依赖

在R(U)中，如果X→Y，(Y X) ,Y→X Y→Z，Z ∈Y, 则称Z对X传递函数依赖。
    记为：X → Z

 注: 如果Y→X， 即X←→Y，则Z直接依赖于X。

例: 在关系Std(Sno, Sdept, Mname)中，有：
      Sno → Sdept，Sdept → Mname
      Mname传递函数依赖于Sno

一，第一范式

如果某个域中元素被认为是不可分的，则这个域称为是原子的

• 非原子域的例子:
  ---- 复合属性：名字集合
  ---- 多值属性：电话号码
  ---- 复合数据类型：面向对象的

如果关系模式R中的所有属性的域是原子的，则R称为属于第一范式（1NF）

非原子值存储复杂并易导致数据冗余

• 我们假定所有关系都属于第一范式

如何处理非原子值

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

原子性实际上是由域元素在数据库中被使用决定的

• 例，字符串通常是被认为是不可分割的
• 假设学生被分配这样的标识号：CS0012或EE1127，如果前两个数字表示系所，后四位表示学生在该系所内的唯一号码，则这样的标识号不是原子的
• 当采用这种标识号时，是可取的。因为这需要额外的编程，而且信息是在应用程序中，而不是在数据库中编码。

二，关系数据库设计中易犯的错误

关系数据库设计要求我们找到一个“好的”关系模式集合。一个坏的设计可能导致：

• 数据冗余
• 插入、删除、修改异常

假设我们用以下模式代替instructor模式和department模式：

inst_dept(ID, name, salary, dept_name, building, budget)

2.1 数据冗余

每个系的dept_name，building，budget数据都要重复一次
缺点：浪费空间，可能会导致不一致问题

2.2 插入、删除、修改异常

更新异常

• 更新复杂，容易导致不问题。
• 例修改dept_name，很多相关元组都需要修改。

插入/删除异常

• 使用空值null：存储一个不知道所在系所的教师信息，可以使用空值表示dept_name，building，budget数据，但是空值难以处理。

三，模式分解（I）

例，可以将关系模式（A,B,C,D）分解为：（A,B）和（B,C,D）,或（A,C,D）和（A,B,D）,或（A,B），（B,C）和（C,D）等等…

例，将关系模式inst_dept分解为：

• instructor(ID, name, dept_name, salary)
• department(dept_name, building, budget)

原模式（R）的所有属性都必须出现在分解后的（R₁，R₂）中：R = R₁ ∪ R₂

无损连接分解

• 对关系模式R上的所有可能的关系r
  

目标：设计一个理论

• 以判断关系模式R是否为“好的”形式（不冗余）
• 当R不是“好的”形式时，将它分解为模式集合{ R₁，R₂，…，R_n }使得：
  ---- 每个关系模式都是“好的”形式
  ---- 分解是无损链接分解
• 我们的理论基于：
  ---- 函数依赖（function dependencies）
  ---- 多值依赖（multivalue dependencies）

四，函数依赖（FD）

4.1 什么是函数依赖

设R是一个关系模式，且有属性集 α包含于R，β包含于R

在R上成立当且仅当对任意合法关系r(R)，若r的任意两条元组t₁和t₂在属性集α上的值相同，则它们的属性集β上的值也相同。

• 即：t₁[α] = t₂[α] → t₂[β] = t₂[β]
• 称：β函数依赖于α，α函数决定β
• 如下图，图中的α和β满足函数依赖关系
  

函数依赖：一种完整性约束，表示特定的属性值之间的关系，可以用来判断模式规范化和建议还进

• 函数依赖是码概念的推广
• K是关系模式R的超码，当且仅当 K → R
• K是R的候选码当且仅当
  ---- K → R，并且
  ---- 没有 α 包含于 K，使 α → R（不存在K的真子集α，使之满足 α → R）

函数依赖使我们可以表达用超码无法表达的约束，考虑模式

inst_dept(ID, name, salary, dept_name, building, budget)

• 我们希望下列函数依赖成立：
  ---- dept_name → building
  ---- ID → building（码是一个比较特殊的FD，可以函数决定所有的属性）
• 而不希望下列函数依赖成立：
  ---- dept_name → salary

4.2 函数依赖的使用

若果在关系模式R上所有合法关系都满足F，则称F在R上成立。

• 其中 R = { r₁®，r₂®，… }

注：容易判断一个r是否满足给定的F。不易判断F是否在R上成立。不能仅由某个r推断出F。R上的函数依赖F，通常由定义R的语义决定。

被所有的关系实例所满足的函数依赖称为平凡的

• 例，A → A，AB → A，（ID，name）→ ID，ID → ID
• 一般的，若β包含于α，则α → β是平凡的。即，
  平凡的函数依赖：若β包含于α，α → β。
  非平凡的函数依赖：若β不包含于α，α → β。

4.3 函数依赖集的闭包

Armstrong 公理

计算 F⁺

下列过程计算函数依赖集F的闭包：

F+ = F
repeat
	for each F+中的函数依赖f
			 对应f应用'自反率'和'增补率'，将结果函数依赖加入F+
	for each F+中的一对函数依赖f1和f2
			 if f1和f2可以使用'传递性'结合起来，则将结果函数依赖加入F+
until F+不再变化

由于包含n个元素的集合含有2ⁿ子集，因此共有 2ⁿ * 2ⁿ个可能的函数依赖。
后边会介绍完成此任务的另一过程。

五，属性集的闭包

如何判断集合α是否为超码

• 一种方法是：计算F⁺，在F⁺中找出所有的α → β，检查{ β₁β₂β₃ … } = R；
  但这么做开销很大，因为F⁺可能很大。
• 另一种方法是：计算α的闭包。

5.1 什么是属性集的闭包

定义：给定一个属性集α，在函数依赖集F下由α函数确定的所有属性的集为F下α的闭包（记作α⁺）

• 检查函数依赖α → β是否属于F⁺ ↔ β包含于α⁺
• 判断α是否为超码：α → β属于F⁺ ↔ R包含于α⁺

计算α⁺的算法

result := a;
while(result有变化) do
	for each β → γ in F do
		begin
			if β包含于result
			then result := result ∪ γ
		end
	a+ := result

避免了找F⁺（反复使用公理）的麻烦。
示例讲解

最终，AG可以表示R中的所有属性，则说AG是R的一个key。

5.2属性闭包的用途

六，正则覆盖

数据库管理系统（DBMS）总是检查确保数据库更新不会破坏任何函数依赖。但如果F很大，其开销就会很大。因此我们需要简化函数依赖集

直观地说，F的正则覆盖（记作F_c）是指与F等价的“极小的”函数依赖集合

• F_c中任何函数依赖都不包含无关属性
• F_c中函数依赖的左半部都是唯一的
• 例，α₁ → β₁，α₁ → β₂，可以写为α₁ → β₁β₂

无关属性

定义：考虑函数依赖集合F及其中的函数一来α → β

• 如果A∈α并且F逻辑蕴含F’ =（F - { α → β }）∪ {（α → A ）→ β}，则称A在α中是无关的
  ---- 例，给定F = { A → C，AB → C }，其中B在AB → C中是无关的，因为A → C逻辑蕴含了AB → C。
• 如果A∈β并且F’ =（F - { α → β }）∪ { α →（α → A ）}逻辑蕴含F，则称A在β中是无关的
  ---- 例，给定F = { A → C，AB → CD }，其中C在AB → CD中是无关的，因为即使删除C也能推出A → C。

检测属性是否无关

计算F的正则覆盖

repeat
 	对F中的依赖利用'合并'规则
 	α1 → β1 和 α1 → β2 替换成 α1 → β1β2
 	找出含有无关属性的函数依赖 α → β（在α或β中）
 	如果找到无关属性，从α → β中删除
until F不再变化

注：删除某些无关属性之后，可能导致合并规则可以使用，则必须重新应用。

七，模式分解（II）

规范化的目标

• 以判断关系模式R是否为“好的”形式（不冗余，误插入，删除，更新异常）
• 当R不是“好的”形式时，将他分解成模式集合{ R₁，R₂，…，R_n }使得：
  – 每个关系模式都是“好的”形式
  – 分解是无损连接分解
  – 分解是保持依赖的

分解应有的特性

八，总结

• 描述了原子域和第一范式假设；
• 给出了数据库设计中易犯的错误，这些错误包括信息重复和插入、删除、修改异常；
• 介绍了函数依赖的概念，展示了如何用函数依赖进行推导；
• 理解F⁺，α⁺，F_C；
• 介绍了如何分解模式，一个有效的分解都必须是无损的；
• 如何分解是保持依赖的，则给定一个数据库更新，所有的函数依赖都可以由单独的关系进行验证，无须计算分解后的关系链接。