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

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

第一范式

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

非原子域的例子：

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

如果关系模式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}使得

每个关系模式都是**“好的”形式**
分解是无损连接分解
分解是保持依赖

分解验证算法

模式分解总结

规范化-简单版

图示法求候选键

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

将关系的函数依赖关系用有向图表示
找出入度为0的属性，并以该属性集合为起点，尝试遍历所有的图，若能遍历途中所有结点，则该属性集为关系模式的候选键
若入度为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)对应的具体关系通常用小写字母r来表示。
二.函数依赖的一般概念
定义4.1 设R(U)是属性集U={A1, A2, …, An}上的关系模式，X和Y是U的子集。若对R(U)的任一具体关系r中的任意两个元组t1和t2，只要t1[X]=t2[X]就有t1[Y]=t2[Y]。则称“X函数确定Y”或“Y函数依赖于X”(Founctional Dependence)，记作X->Y。在以上定义中，t1[X]和t1[Y]分别表示元组t1在属性X和Y上的取值。“X函数确定Y”的含义是：对关系r中的任意一个元组，如果它在属性集X上的值已经确定，则它在属性集Y上的值也随之确定。因此，定义4.1即是说，在关系模式R(U)的任意一个具体关系r中，不可能存在这样的两个元组，它们在X上的属性值相等，而在Y上的属性值不等。注意：函数依赖不是指关系模式R(U)的某个或某些具体关系满足的约束条件，而是指R(U)的一切具体关系r都要满足的约束条件。
例4.3 设有一个描述学生信息的关系模式: R(Sname, Sex, Birthday, Phone)，其属性名分别代表学生的姓名、性别、出生日期和电话号码属性。它的一个具体关系r如表所示。
如果仅从关系模式R(U)的一个具体关系r出发，由于r没有相同姓名的元组(学生)，所以我们就会得出：对于关系模式R有Sname->Sex，Same->Birthday，Sname->Phone的结论。但这个结论是不正确的。比如，对关系模式R的另外一个具体关系r1，这时，从关系r得出的函数依赖就不成立了。所以，关系模式中的函数依赖是对这个关系模式的任何可能的具体关系都成立的函数依赖。
从例子可知，函数依赖和其它数据依赖一样，是一个语义范畴的概念。我们只能根据属性的语义来确定一个函数依赖。例如Sname(姓名)->Birthday(出生日期)这个函数依赖，只有在没有同姓名学生的条件下才成立。如果允许出现相同姓名的学生，则出生日期就不再函数依赖于姓名了。数据库设计者应在定义数据库模式时，指明属性之间的函数依赖，使数据库管理系统根据设计者的意图来维护数据库的完整性。因此，设计者可以对现实世界中的一些数据依赖作强制性规定. 例如，为了使Sname->Birthday这个函数依赖成立，用户可以强制规定关系中不允许同名同姓的人出现。这样当输入某个元组时，这个元组在Sname上的属性值必须满足规定的函数依赖，若发现新输入元组在Sname上的值与关系中已有元组在Sname上的值相同，则数据库管理系统就拒绝接受该元组。解决的办法是通过人工方式是同名者为不同名者。比如有两个张华，可改为“张华a”，“张华b”等。
在定义4.1的基础上补充以下常用术语和记号： ⑴ 若X->Y，则称X为这个函数依赖的决定(Determinant)因素，简称X是决定因素。 ⑵ 若X->Y且Y->X，则记作X->Y。X->Y 若Y不函数依赖于X，则记作非X->Y 。 ⑷ 若X->Y，但Y->X，则称X->Y是平凡函数依赖。 ⑸ 若X->Y，但Y属于X，则称X->Y是非平凡函数依赖。对于任一关系模式，平凡函数依赖都是必然成立的，但它不反映新的语义。在下面的讨论中，若没有特别声明，“X?Y”都表示非平凡函数依赖。定义4.2设R(U)是属性集U={A1, A2, …, An}上的关系模式。X和Y是U的子集。 ⑴ 如果X->Y，且对于 X的任何一个真子集X?，都有，则称Y对X完全函数依赖(Full Founctional Dependence)或者X完全决定Y,记作:X完全函数决定Y。 ⑵ 如果X->Y，但Y不是完全函数依赖于X，则称Y对X部分函数依赖(Partial Founctional Dependence)，记作：X部分函数决定Y。定义4.3 对于关系模式R(U)，设X、Y和Z都是U的子集。如果X->Y，Y->Z，且Y?X，Z?Y , 则称Z对X传递函数依赖(Transitive Founctional Dependence)，记作: X传递函数决定Z 。在传递函数依赖的定义中加上条件是必要的，因为如果Y?X，则X?Y，即说明X与Y之间是一一对应的，这样导致Z对X的函数依赖是直接依赖，而不是传递函数依赖。定义4.3中的条件主要是强调X?Y和Y?Z都不是平凡函数依赖，否则同样Z对X是直接函数依赖，而不是传递函数依赖。当然，若 X?Z ，则必有X?Z。
例4.4 对于例4.1的关系模式StudyInfo(Sno, Sname, DeptName, DeptHead, Cname, Grade)有如下的一些函数依赖：Sno->Sname, {Sno, Cname}->Grade，Sno->DeptName, DeptName->DeptHead。由最后两个函数依赖还可得出DeptHead传递函数依赖Sno，即 Sno->DeptHead 。如果没有同姓名的学生，还有Sno->Sname等。但显然有Grade->Sname ，{Sno, Cname}->Sname。其实，对关系模式StudyInfo还有Sno->Sname ，{Sno, Cname}->Grade 等。因此，Sno是 Sno->Sname的决定因素，{Sno,Cname}是的决定因素。
三.候选键与主键
定义4.4 对关系模式R(U)，设K?U。如果，则称K为R(U)的候选键或候选关键字(Candidate Key)。通常在R(U)的所有候选键中选定一个作为主键(Primary Key)。主键也称为主码或主关键字。候选键是能够唯一确定关系中任何一个元组(实体)的最少属性集合，主键也是候选键，它是候选键中任意选定的一个。在最简单的情况，单个属性是候选键。最极端的情况是，关系模式的整个属性集全体是候选键，也是主键，这时称为全键或全码(All-key)
例4.5 设有关系模式R(Teacher，Course，Sname)，其属性Teacher，Course，Sname 分别表示教师，课程和学生。由于一个教师可以讲授多门课程，某一课程可由多个教师讲授。学生也可以选修不同教师讲授的不同课程，因此，这个关系模式的候选键只有一个，就是关系模式的全部属性(Teacher，Course，Sname)，即全键(All-key)，它也是该关系模式的主键。为了便于区别候选键中的属性与其它属性，我们可以得到如下定义。
定义4.5对关系模式R(U)，包含在任何一个候选键中的属性称为主属性(Primary Attribute)，不包含在任何候选键中的属性称为非主属性(Nonprimary Attribute)或非码属性(Non-key Attribtute)。
例4.6 在关系模式StudyInfo(Sno，Sname，DeptName、DeptHead、Cname，Grade)中，{Sno, Cname}是其唯一候选键，因此，Sno和Cname都是主属性，而Sname，DeptName、DeptHead，Grade都是非主属性。
定义4.6 对关系模式R(U)，设X属于U。若X不是R(U)的主键，但X是另一个关系模式的主键，则称X是R(U)的外键或外部关键字(Foreign key)。
例4.7 在Reports(Sno, Cname, Grade)中，Sno不是关系模式Reports的主键，但Sno是关系模式Students (Sno, Sname, DeptName)中的主键。因此，Sno是关系模式Reports(Sno, Cname,Grade)的外键。主键与外键提供了一个表示两个关系中元组(实体)之间联系的手段。在数据设计中，经常人为地增加外键来表示两个关系中元组之间的联系。当两个关系进行连接操作时就是因为又外键在起作用。比如，我们需要查看每个学生的姓名、选课名称和成绩时，就涉及到Students(Sno, Sname, DeptName)和Reports(Sno, Cname,Grade)对应关系的连接操作，这时，只要使用第3章介绍的如下SQL命令即可。 SELECT Sname, Cname, Grade FROM Students, Reports WHERE Students.Sno=Reports.Sno。
四.函数依赖的推理规则
在讨论函数依赖时会遇到这样的问题：以知关系模式R(U,F)的函数依赖集F={A->B，B->C}。问A->C是否成立? ，其中属性集U={A, B, C}。这是本节后面将讨论的有关问题，其内容安排如下：函数依赖的逻辑蕴涵 Armstrong公理系统函数依赖推理规则的完备性闭包的计算函数依赖集的等价和覆盖
1.函数依赖的逻辑蕴涵
在介绍函数依赖的推理规则之前，先介绍两个函数依赖的逻辑蕴涵和闭包概念。
定义4.7 对于满足函数依赖集F的关系模式R(U,F)的任意一个具体关系r，若函数依赖X?Y都成立(即对于r中的任意两个元组t，s，若t[X]=s[X]，则有t[Y]=s[Y])，则称F逻辑蕴涵X->Y,记为F=>X->Y。注意，在定义4.7中没有假定函数依赖(X->Y)属于F，X,Y都是属性集U的子集合。定义4.8 被函数依赖集F逻辑蕴涵的函数依赖所构成的集合，称为F的闭包(Closure)，记作F+。即 F+={X->Y \| F=>X->Y}。
通常，F包含于F+。若F=F+，称F是函数依赖完备集。然而，对于给定的函数依赖集F和属性集X，Y，仅有定义4.7和定义4.8还难于回答F是否逻辑蕴涵X?Y的问题。当然，我们可以先计算F+，然后检查X->Y是否属于F+即可。但现在也没有计算一个函数依赖集F的闭包F+的方法。这些问题需要学习了Armstrong公理系统和函数依赖的推理规则等知识以后才能够解决。
2.Armstrong公理系统
通俗说，Armstrong公理系统是函数依赖基本推理规则的集合，又称Armstrong推理规则系统。 Armstrong公理系统设有关系模式R(U, F)，F是只涉及到U中属性的函数依赖集。若X，Y，Z，W均是U的子集，则有以下推理规则： ⑴ 自反律 (Reflexivity Rule)：如果Y?X?U，则X?Y成立，即F?X?Y。 ⑵ 增广律(Augmentation Rule)：如果X?Y成立, 则XZ?YZ 成立(其中XZ是X?Z的简单记法，其它类同)，即若F?X?Y，则F?XZ?YZ。 ⑶ 传递律(Transitivity rule)：如果X?Y，Y?Z成立，则X? Z成立，即若F?X?Y，F?Y?Z，则F若F? X?Z。
定理4.1 Armstrong公理系统中的推理规则⑴，⑵，⑶是正确的，即若X?Y由Armstrong公理导出，则X?Y属于F+。定理4.2 函数依赖的如下三个推理规则是正确的。 ⑴ 合并律(Union Rule)：如果X?Y和X?Z成立，那么X?YZ成立，即若F?X?Y，F?X?Z，则F? X?YZ。 ⑵ 伪传递律(Pseudotransivity Rule)：如果X?Y和WY?Z成立，那么WX?Z成立，即若F?X?Y，F?WY?Z，则F?WX?Z。。 ⑶ 分解律(Decomposition Rule)：如果X?Y和Z?Y成立，那么X?Z成立，即若F?X?Y，Z?Y，则F? X?Z。定义4.9 设F是属性集合U上的一个函数依赖集，X?U，称为属性集X关于F的闭包。在以后的讨论中，如果只涉及一个函数依赖集F，则属性集X关于F的闭包常简记为X+。值得注意的是，定义4.9中的A是U中的单个属性，因此X?X+?U。定理4.3 设F是属性集U上的函数依赖集，X，Y是U的子集，则X?Y能由F根据Armstrong公理导出的充分必要条件是Y? X+。
例4.8 设关系模式R(U,F)，其中U＝{A, B, C}，函数依赖集F＝{A?B, B?C}。则有： A+＝{A, B, C} B+＝{B, C} C+＝{C}
3.闭包的计算
前面我们曾经提到，为了判断函数依赖X?Y是否在F+中，只要计算出F+即可。因为F+是由F根据Armstrong公理导出的函数依赖的集合。因此，原则上说，只要按照Armstrong公理系统中的推理规则就可以计算出F+。但是，闭包F+的计算是一件很麻烦的事情，因为计算F+的问题是一个NP完全问题，即若F={X?A1, X?A2, …, X?An,}，则需要计算F+的O(2n)个函数依赖，因此，当 n比较大时，实际计算F+是不可行的。即使F的元素不多时， F+中的元素也可能很多。此外，闭包F+中也存在许多冗余信息。其实，判断一个函数依赖X?Y是否在F+中，完全不必计算闭包F+，因为，由定理4.3可知，只要判断X?Y能否从F根据Armstrong公理导出，即判断Y?X+是否成立即可。这样就把一个需要计算F+才能解决的问题简化为计算X+就能解决得问题。而计算X+并不太难，它所花费的时间与F中的全部函数依赖的长度成正比。下面介绍一个计算X+的算法。算法4.1 求属性集X?U关于函数依赖集F的闭包X+。输入：有限的属性集合U、它上面的函数依赖集合F和U的一个子集X。输出：X关于F的闭包X+。计算方法和计算步骤： ⑴设置初始值：令X(0)＝空集，X(1)＝X，F'=空集； ⑵如果X(0)≠X(1)，令X(0)＝X(1)，否则转⑷； ⑶构造函数依赖集F'={Y->Z \| (Y->Z)属于F且Y?X(1)}，令 F=F-F' 对F'中的每一个函数依赖Y->Z,令X(1)= X(1)∪Z,转⑵ ⑷ 输出X(1)，它就是X+。例4.10 设有关系模式R(A,B,C,D,E)，其属性集上函数依赖：F={AB->C, B->D, C->E, EC->B, AC->B}，这里的AB->C是{A, B}->{C}的简写。令X={A, B}，求X+。解：计算过程是根据循环次数介绍的。由算法4.1 第一次：⑴ X(0)=空集，X(1)={A, B}，F'=空集； ⑵ 由于X(0)≠X(1)，令X(0)＝X(1)={A, B}； ⑶ 函数依赖集F'={ AB->C, B->D}，令F=F-F'={C->E, EC->B, AC->B}，将F'中的每一个函数依赖的右端属性C,D并入X(1)中，即令X(1)={A, B}∪{C, D}={A, B, C, D}；第二次：⑵ 由于X(0)?X(1)，令X(0)＝X(1)= {A, B, C, D}； ⑶ 函数依赖集F'={C->E, AC->B}，令F=F- F'={EC->B}，将F'中的每一个函数依赖的右端属性E, B并入X(1)中，即令X(1)={A, B, C, D }∪{E, B}={A, B, C, D, E} ；第三次：⑵ 由于X(0)≠X(1)，令X(0)＝X(1)= {A, B, C, D, E } ； ⑶ 函数依赖集F'={EC->B}，令F=F-F'=空集, 将F'中的每一个函数依赖的右端属性B并入X(1)中，即令X(1)={A, B, C, D, E }∪{B}={A, B, C, D, E}；第四次：⑵ 由于X(0)=X(1)，转⑷ ⑷输出X(1)={A, B, C, D, E}=X+。

函数依赖与关系模式的范式

函数依赖

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

传递函数依赖：

关系模式的范式

第一范式

第二范式

第三范式

数据库 - 关系模式函数依赖

数据依赖

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

分解关系模式

规范化

函数依赖

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

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

传递函数依赖