重邮版第五章

第5章关系数据库的设计理论本章要点：函数依赖关系模式的规范化模式分解关系模式形式化表示为R(U,D,dom,F)U：组成该关系的属性名集合D：属性组U中属性所来自的域dom：属性向域的映象集合，如属性的类型、长度F：属性间数据的依赖关系集合由于D和Dom对设计关系模式的作用不大，在讨论关系规范化理论时可以把它们简化掉，从而关系模式可以用三元组来表示为R<U,F>。数据依赖（DataDependency）是关系模式的要素，是同一关系中属性间的相互依赖和相互制约。数据依赖包括函数依赖（FunctionalDependency，FD）、多值依赖（MultivaluedDependency，MVD）和连接依赖（JoinDependency），数据依赖是关系规范化的理论基础。

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

例如，对于关系模式服装销售<U,F>：U={服装编号,顾客编号,购买日期,数量,型号,品牌};F={服装编号→型号,型号→品牌,(服装编号,顾客编号)→购买日期,(服装编号,顾客编号)→数量}相关概念及表示：（1）X→Y，但YX，则称X→Y是非平凡的函数依赖。若不特别声明，总是讨论非平凡的函数依赖。（2）X→Y，但Y⊆X，则称X→Y是平凡的函数依赖。（3）若X→Y，则X叫做决定因素（Determinant），Y叫做依赖因素（Dependent）。（4）若X→Y，Y→X，则记作X←→Y。（5）若Y不函数依赖于X，则记作XY。完全函数依赖与部分函数依赖完全函数依赖：在R(U)中，如果X→Y，并且对于X的任何一个真子集X‘，都有X’Y，则称Y对X完全函数依赖，记作：。部分函数依赖：若X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作。例如，在以上购买记录模式中，（顾客编号，服装编号）数量，（顾客编号，服装编号）型号。传递函数依赖在R(U)中，如果X→Y，(YX)，YX，Y→Z，则称Z对X传递函数依赖。传递函数依赖记作

。在购买记录模式中，因为存在服装编号→型号，型号→品牌，所以也存在服装编号品牌。候选码候选码：设K为R〈U，F〉中的属性或属性组合，若KU，则K为R的候选码。若候选码多于一个，则选定其中的一个为主码（Primarykey）。包含在任何一个候选码中的属性，叫做主属性（Primeattribute)。不包含在任何码中的属性称为非主属性（Nonprimeattribute）。若整个属性组是码，称为全码（All-key）关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码（Foreignkey）也称外码。主码与外码提供了一个表示关系间联系的手段。Armstrong公理Armstrong公理系统是函数依赖的一个有效而完备的公理系统。蕴含：对于满足一组函数依赖F的关系模式R<U，F>，其任何一个关系r，若函数依赖X→Y都成立（即r中任意两元组，若t[X]=s[X]，则t[Y]=s[Y])，则称F蕴含X→Y。为了求得给定关系模式的码，并且从一组函数依赖求得蕴含的函数依赖，例如已知依赖集F，要证明X→Y函数是否为F所蕴含，就需要一套推理规则，这组推理规则是1974年首先由Armstrong提出来的。Armstrong公理系统（Armstrong’saxiom）：设U为属性集总体，F是U上的一组函数依赖，于是有关系模式R<U，F>。对R<U，F>来说有以下的推理规则：A1.自反律（Reflexivityrule）：若Y⊆X，X⊆U，则X→Y在R上成立。（此处X→Y是平凡函数依赖）A2.增广律（Augmentationrule）：若X→Y在R上成立，且Z⊆U，则XZ→YZ在R上成立。A3.传递律（Transitivityrule）：若X→Y和Y→Z在R上成立，则X→Z在R上成立。其他的所有函数依赖的推理规则可以使用这三条规则推导出。根据A1、A2、A3这三条推理规则可以得到以下三条很有用的推理规则：合并规则：若X→Y，X→Z同时在R上成立，则X→YZ在R上也成立。分解规则：若X→W在R上成立，且属性集Z包含于W，则X→Z在R上也成立。伪传递规则：若X→Y在R上成立，且WY→Z，则XW→Z。根据合并规则和分解规则，很容易得到这样一个重要事实：引理5.1：X→A1A2···Ak成立的充分必要条件是X→Ai成立（i=1，2，···，k）。闭包及其计算闭包：在关系模式R<U，F>中为F所逻辑蕴含的函数依赖的全体叫做F的闭包（closure），记为F+。Armstrong公理系统是有效的、完备的。Armstrong公理的有效性指的是：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中；完备性指的是F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。设F为属性集U上的一组函数依赖，X⊆U，XF+={A|X→A能由F根据Armstrong公理导出}。XF+称为属性集X关于函数依赖集F的闭包。引理5.2：设F为属性集U上的一组函数依赖，X，Y⊆U，X→Y能由F根据Armstrong公理导出的充分必要条件是Y⊆XF+。算法5.1：求属性集X（X⊆U）关于U上的函数依赖集F的闭包XF+。输入：X，F输出：XF+

步骤：例5-1已知关系模式R<U，F>，U={A,B,C,D,E},F={AB→C,B→D,C→E,EC→B,AC→B}。求(AB)F+。解：由算法5.1，设X(0)=AB;计算X(1)，逐一扫描F中各个函数依赖，找出左部为A，B或AB的函数依赖。得到两个：AB→C，B→D。于是X(1)=AB∪CD=ABCD。因为X(0)

≠X(1)，所以再找出左部为ABCD子集的那些函数依赖，又得到C→E，AC→B，于是X(2)=X(1)

∪BE=ABCDE。因为X(2)已经等于全部属性集，所以(AB)F+=ABCDE。对于算法5.1，令αi=|X(i)|，{αi}形成一个步长大于1的严格递增的序列，序列的上界是|U|，因此该算法最多需要|U|-|X|次循环就会终止。覆盖：如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。引理5.3：F+=G+的充分必要条件是F⊆G+且G⊆F+。证：必要性显然，只证充分性。（1）若F⊆G+，则XF+⊆XG+。（2）任取X→YF+则有Y⊆XF+⊆XG+。所以X→Y(G+)+=G+。即F+⊆G+。（3）同理可证G+⊆F+，所以F+=G+。而要判定F⊆G+，只需逐一对F中的函数依赖X→Y，考察Y是否属于XG+即可。引理5.3给出了判断两个函数依赖集等价的可行算法。最小覆盖最小覆盖：如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖（minimalcover）。（1）F中任一函数依赖的右部仅含有一个属性。（2）F中不存在这样的函数依赖X→A,使得F与F-{X→A}等价。（3）F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X→A}∪{Z→A}与F等价。例5-2考察关系模式R<U,F>，其中U={服装编号，顾客编号，购买日期，数量，型号，品牌}；F={服装编号→型号，型号→品牌，（服装编号，顾客编号）→购买日期，（服装编号，顾客编号）→数量}。设F’={服装编号→型号，型号→品牌，服装编号→品牌，（服装编号，顾客编号）→购买日期，（服装编号，顾客编号）→数量，（服装编号，顾客编号）→服装编号}。根据定义5.10可以验证F是最小覆盖，F’不是。因为F’-{服装编号→品牌}与F’等价，F’-{（服装编号，顾客编号）→服装编号}与F’等价。定理5.2每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集。证：这是一个构造性的证明,分三步对F进行“极小化处理”,找出F的一个最小依赖集来。（1）逐一检查F中各函数依赖FDi：X→Y,若Y=AlA2···Ak，k>2，则用{X→Aj|j=1，2，···，k}来取代X→Y。（2）逐一检查F中各函数依赖FDi：X→A，令G=F-{X→A}，若A∈XG+，则从F中去掉此函数依赖（因为F与G等价的充要条件是A∈XG+）。（3）逐一取出F中各函数依赖FDi：X→A，设X=BlB2···Bm,逐一考查Bi(i=1,2,···,m)，若A∈(X-Bi)F+，则以X-Bi取代X(因为F与F-{X→A}∪{Z→A}等价的充要条件是A∈ZF+，其中Z=X-Bi)。最后剩下的F就一定是最小依赖集，并且与原来的F等价。因为对F的每一次“改造”都保证了改造前后的两个函数依赖集等价。F的最小依赖集不一定是唯一的，它与对各函数依赖FDi以及X→A中X的各属性的处置顺序有关。例5-3F={A→B,B→A,B→C,A→C,C→A}Fml={A→B,B→C，C→A}Fm2={A→B,B→A,A→C,C→A}这里给出了F的两个最小依赖集Fml、Fm2。关系模式的规范化关系数据库的设计主要是关系模式的设计，关系模式设计的好坏将直接影响数据厍设计的成败。将关系模式规范化，使之达到较高的范式是设计好关系模式的惟一途径。否则，设计得不好的关系数据库会产生一系列的问题。关系模式应满足的基本要求（1）元组的每个分量必须是不可分的数据项。（2）数据库中的数据冗余应尽可能少。（3）关系数据库不能因为数据更新操作而引起数据不一致问题。（4）当执行数据插入操作时，数据库中的数据不能产生插入异常现象。（5）数据库中的数据不能在执行删除操作时产生删除异常问题。（6）数据库设计应考虑查询要求，数据组织应合理。关系规范化的必要性对于关系模式购买记录<U，F>，U={服装编号，顾客编号，购买日期，数量，型号，品牌};F={服装编号→型号，型号→品牌，（服装编号，顾客编号）→购买日期，（服装编号，顾客编号）→数量}。可知此关系模式的码为（服装编号，顾客编号）该关系存在着如下问题:（1）数据冗余大（2）插入异常（3）删除异常（4）更新异常关系数据库中的关系是要满足一定程度的规范化要求的，满足不同程度要求的关系称为不同范式。若把范式这个概念理解成符合某一种级别的关系模式的集合，则R为第几范式可以写成R∈xNF。5NF4NFBCNF3NF2NF1NF一个低一级范式的关系模式，可以通过模式分解（schemaposition）转换为若干个高一级范式的关系模式的集合，这个过程就叫做规范化（normalization）。第一范式（1NF）关系的第一范式是关系要遵循的最基本的范式。第一范式：如果关系模式R，其所有的属性均为简单属性，即每个属性都是不可再分的，则称R属于第一范式（FirstNormalForm，简称1NF），记作R∈1NF。例如，购买记录模式中所有的属性都是不可再分的简单属性，则服装销售关系模式∈1NF。不满足第一范式条件的关系称之为非规范化关系第二范式（2NF）第二范式：若R∈1NF，且每一个非主属性完全依赖于码，则R∈2NF。关系模式“购买记录”的函数依赖集为：服装编号→型号，型号→品牌，（服装编号，顾客编号）→购买日期，（服装编号，顾客编号）→数量}该关系模式的码是（服装编号，顾客编号），（服装编号，顾客编号）型号，即存在非主属性部分函数依赖于码，“购买记录”不属于2NF。用投影分解法把购买记录关系分解为两个关系模式：服装（服装编号，型号，品牌），销售（服装编号，顾客编号，购买日期，数量）。服装的码是服装编号，其函数依赖集为：服装编号→型号，服装编号→品牌。销售的码是（服装编号，顾客编号），其函数依赖集为：（服装编号，顾客编号）→购买日期，（服装编号，顾客编号）→数量则由定义可知，服装∈2NF，销售∈2NF。第三范式（3NF）第三范式:关系模式R〈U，F〉中若不存在这样的码X、属性组Y及非主属性Z（ZY）使得X→Y、Y

Ⅹ、Y→Z成立，则称R属于第三范式，记作R∈3NF。由以上定义可以证明，若R∈3NF，则每一个非主属性既不部分函数依赖于码，也不传递函数依赖于码。3NF是一个可用的关系模式应满足的最低范式。分析以上服装（服装编号，型号，品牌），因为服装编号→型号，型号→品牌，即非主属性品牌传递函数依赖于码，所以该模式不是3NF。可通过投影分解法，把服装关系分解为服装-型号（服装编号，型号）和型号-品牌（型号，品牌），则前者的码是服装编号，后者的码是品牌，均不存在非主属性对码的传递函数依赖和部分函数依赖，故此两模式都是3NF。BC范式（BCNF）BCNF范式：若有关系模式R∈1NF且有X→Y和YX时，X必含有码，则R〈U,F〉∈BCNF。也就是说，关系模式R(U,F)中，若每一个决定因素都包含码，则R(U,F)∈BCNF。由BCNF的定义可以得到结论，一个满足BCNF的关系模式有：1）所有非主属性对每一个码都是完全函数依赖；2）所有的主属性对每一个不包含它的码，也是完全依赖；3）没有任何属性完全函数依赖于非码的任何一组属性。如果R属于BCNF，由于R排除了任何属性对码的传递依赖与部分依赖，所以R一定属于3NF。但是，若R∈3NF，则R未必属于BCNF。

BCNF和3NF的区别主要反映在以下两点:（1）BCNF不仅强调其他属性对码的完全的直接依赖，而且强调主属性对码的完全的直接的依赖，它包括3NF，即R∈BCNF，则R一定属于3NF。如果一个实体集中的全部关系模式都属于BCNF，则实体集在函数依赖范畴已实现了彻底地分离，消除了插入和删除异常问题。（2）3NF只强调非主属性对码的完全直接依赖，这样就可能出现主属性对码的部分函数依赖和传递函数依赖。有些关系模式属于3NF，但不属于BCNF。例如关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示课程。语义为：每一教师只讲授一门课程，每门课程由若干教师讲授；每门70课程可由多名学生选修；每个学生可选修多门课程，每个学生选修某门课程就对应一个固定的教师。可得其函数依赖为F={（S，J）→T，（S，T）→J，T→J}。显然，（S，J）和（S，T）都是关系模式的码，关系的主属性是{S，T，J}，非主属性集为空集。由于该关系模式无非主属性，所以它属于3NF；但因为存在T→J，其决定因素T不是码，所以该模式不属于BCNF。那些不属于BCNF的关系模式仍然有不合适的地方，比如STJ中，某教师讲授某课程的信息本该只存储一次，但这里有几名学生选修该教师的课程，该信息就要重复几次。可以通过模式分解法将其转换成BCNF。把STJ分解为ST（S，T）和TJ（T，J）两个模式。ST和TJ都属于BCNF。33模式的分解分解的目的解决冗余和异常，提高范式等级分解的概念用原关系模式的若干个投影构成新的关系模式，即34关系模式分解应满足的特性无损连接性(Losslessjoin)保持函数依赖性(Preservedependency)相互独立性分解后的关系模式中，当修改某一个关系数据时，不会影响其他关系35例子分析设S-C-M（学号，班级，班主任）F={学号班级，班级班主任，学号班主任存在传递依赖，为2NF有三种分解：该关系属于几范式？范式？3NF三种特性?36算法：检验一个分解是否具有无损连接性37ABCDEa1a2a3b14b15b21b22a3a4b25b31b32b33a4a5ABCDEa1a2a3a4a5b21b22a3a4a5b31b32b33a4a5初始表：最后结果：R1R2R3R1R2R3122例子：判断无损连接性38ABCDEa1a2a3a3a4a4a5ABCDEa1a2a3a4a5a3a4a5a4a5初始表：最后结果：R1R2R3R1R2R3122简易方法：只画关注数据39例子R(A,B,C),F={AB,CB}分解1={(A,B){AB},(A,C)}分解2={(A,B){AB},(B,C){CB}}分析两种分解的无损连接性？分解1只具有无损连接性,分解2不具有无损连接性ABCa1a2a1a3ABACa2ABCa1a2a2a3ABBC40算法：检验一个分解是否

具有保持函数依赖性41例子R(A,B,C),F={AB,CB}分解1={(A,B){AB},(A,C)}分解2={(A,B){AB}),(B,C){CB}}分析两种分解的依赖保持性？分解1：只有AB，显然，分解1不具有依赖保持性分解2：保留了所有函数依赖，具有依赖保持性42简单练习：

判定无损连接性和函数依赖性设S-C-M（S学号，C班级，M班主任）F={S学号C班级，C班级M班主任，S学号M班主任}43

几个命题一个无损连接的分解不一定具有依赖保持性，反之亦然若要求模式