第4章--关系数据库理论.ppt

第4章 关系数据库理论 第一页，编辑于星期五：十六点 三十九分。4.1 规范化问题的提出4.2 函数依赖4.3 关系模式的分解*4.4 关系模式的范式4.5 关系模式的规范化 第二页，编辑于星期五：十六点 三十九分。4.1 规范化问题的提出 4.1.1 规范化理论的主要内容关系数据库的规范化理论 函数依赖范式（Normal Form）模式设计 核心，是模式分解和设计的基础 模式分解的标准 第三页，编辑于星期五：十六点 三十九分。4.1.2 不合理的关系模式存在的存储异常问题 教学管理数据库SCD(SNo，SN，Age，Dept，MN，CNo，Score)在此关系模式中填入一部分具体的数据SNo SN Age Dept MN CNo Score S1 赵亦 17 计算机 刘伟 C1 90S1 赵亦 17 计算机 刘伟 C2 85 S2 钱尔 18 信息 王平 C557S2 钱尔 18 信息 王平 C680S2钱尔18信息王平C7 第四页，编辑于星期五：十六点 三十九分。SNo SN Age Dept MN CNo Score S1 赵亦 17 计算机 刘伟 C1 90S1 赵亦 17 计算机 刘伟 C2 85 S2 钱尔 18 信息 王平 C557S2 钱尔 18 信息 王平 C680S2钱尔18信息王平C7 该表出现的问题该表出现的问题 数据冗余数据冗余 插入异常插入异常 删除异常删除异常 更新异常更新异常 根本原因：属性间存根本原因：属性间存在着在着数据依赖关系数据依赖关系 包罗万象包罗万象 第五页，编辑于星期五：十六点 三十九分。一个好的关系模式应该具备以下四个条件：（1）尽可能少的数据冗余；（2）没有插入异常；（3）没有删除异常；（4）没有更新异常。SCD(SNo，SN，Age，Dept，MN，CNo，Score)S(SNo，SN，Age，Dept)SC(SNo，CNo，Score)D(Dept，MN)关系模式分解：关系模式分解：第六页，编辑于星期五：十六点 三十九分。4.2 函数依赖 4.2.1 函数依赖的定义定义4.1 SNo决定函数（SN，Age，Dept）（SN，Age，Dept）函数依赖于SNo SCD(SNo，SN，Age，Dept，MN，CNo，Score)SNo一个学生一个学生SN，Age，Dept 惟一确定惟一确定 惟一确定惟一确定 第七页，编辑于星期五：十六点 三十九分。4.2.2 函数依赖的逻辑蕴涵定义 定义4.2 设F是在关系模式R(U)上成立的函数依赖集合，X，Y是属性集U的子集，XY是一个函数依赖。如果从F中能够推导出XY，即如果对于R的每个满足F的关系r也满足XY，则称XY为F的逻辑蕴涵（或F逻辑蕴涵XY），记为F|=XY。定义4.3 设F是函数依赖集，被F逻辑蕴涵的函数依赖的全体构成的集合，称为函数依赖集F的闭包（Closure），记为F+。即：F+=XY|F|=XY 第八页，编辑于星期五：十六点 三十九分。函数依赖的推理规则 Armstrong公理自反律：如果YXU，则XY在R上成立如果YXU，则XY在R上成立 增广律：若XY在R上成立，且ZU，则XZYZ在R上也成立 传递律：若XY和YZ在R上成立，则XZ在R上也成立 第九页，编辑于星期五：十六点 三十九分。Armstrong公理推论 合并律（Union rule）若XY和XZ在R上成立，则XYZ在R上也成立 伪传递律（Pseudotransitivity rule）若XY和YWZ在R上成立，则XWZ在R上也成立 分解律（Decomposition rule）若XY和ZY在R上成立，则XZ在R上也成立复合律（Composition）若XY和WZ在R上成立，则XWYZ在R上也成立 第十页，编辑于星期五：十六点 三十九分。4.2.4 完全函数依赖与部分函数依赖 设有关系模式R(U)，U是属性全集，X和Y是U的子集：如果XY，并且对于X的任何一个真子集X，都有X Y，则称Y对X完全函数依赖，记作X Y。如果XY，并且对于X的某个真子集X，有XY，则称Y对X部分函数依赖，记作X Y。在关系模式SCD中，因为SNo Score，且CNo Score，所以有：(SNo，CNo)Score。而SNoAge，所以(SNo，CNo)Age fpffp第十一页，编辑于星期五：十六点 三十九分。4.2.5 传递函数依赖 设有关系模式R(U)，U是属性全集，X，Y，Z是U的子集 若XY，但Y X，而YZ（Y X，Z Y），则称Z对X传递函数依赖，记作：X Z。如果YX，则X Y，这时称Z对X直接函数依赖，而不是传递函数依赖。t函数依赖函数依赖 完全函数依赖完全函数依赖 部分函数依赖部分函数依赖 传递函数依赖传递函数依赖 第十二页，编辑于星期五：十六点 三十九分。4.2.6 属性集的闭包及其算法 X+=属性A|XA在F+中 定理4.3 XY能用函数依赖推理规则推出的充分必要条件是Y X+中 算法4.1 result=X do if F中有某个函数依赖YZ满足Y result then result=result Z while(result有所改变);第十三页，编辑于星期五：十六点 三十九分。4.2.7 候选键的求解理论和算法 关键码的定义 如果XU在R上成立（即XU在F+中），那么称X是R的一个超键。如果XU在R上成立，但对X的任一真子集X都有XU不成立（即XU不在F+中，或者X U），那么称X是R上的一个候选键。快速求解候选键的一个充分条件 对于给定的关系模式R(A1，An)和函数依赖集F，可将其属性分为以下四类：fL类类R类类 N类类 LR类类 第十四页，编辑于星期五：十六点 三十九分。定理4.4 对于给定的关系模式R及其函数依赖集F（1）若X（XR）是L类属性，则X必为R的任一候选键的成员。（2）若X（XR）是L类属性，且X+包含了R的全部属性，则X必为R的惟一候选键。（3）若X（XR）是R类属性，则X不在任何候选键中。（4）若X（XR）是N类属性，则X包含在R的任一候选键中。（5）若X（XR）是R的N类和L类属性组成的属性集，且X+包含了R的全部属性，则X是R的惟一候选键。第十五页，编辑于星期五：十六点 三十九分。多属性函数依赖集候选键的求解算法（1）属性分类（L、R、N和LR）（2）若X+包含了R的全部属性，转（5）；否则，转（3）。（3）在Y中取一个属性A，求(XA)+，若它包含了R的全部属性，则转（4）；否则，调换一属性反复进行这一过程，直到试完所有Y中的属性。（4）如果已找出所有候选键，则转（5）；否则在Y中依次取两个、三个、，求它们的属性集的闭包，直到其闭包包含R的全部属性。（5）停止，输出结果。令令X代表代表L和和N类，类，Y代表代表LR类类第十六页，编辑于星期五：十六点 三十九分。4.2.8 函数依赖推理规则的完备性 定理4.5 函数依赖推理规则A1，A2，A3是完备的（1）证明F中每个函数依赖VW在r上成立。（2）证明XY在关系r上不成立。综合（1）和（2）可知，只要XY不能用推理规则推出，那么F就不逻辑蕴涵XY，也就是推理规则是完备的。从函数依赖集从函数依赖集F使用推理规则推出的函数依赖必定在使用推理规则推出的函数依赖必定在F+中中 F+中的函数依赖都能从中的函数依赖都能从F集使用推理规则集推出集使用推理规则集推出 正确性：正确性：完备性：完备性：第十七页，编辑于星期五：十六点 三十九分。4.2.9 函数依赖集的等价、覆盖和最小函数依赖集 等价定义4.8 关系模式R(U)的两个函数依赖集F和G，如果满足F+=G+，则称F和G是等价的函数依赖集。记作：FG。如果F和G等价，就说F覆盖G，或G覆盖F。无关定义4.9 设F是属性集U上的函数依赖集，XY是F中的函数依赖。函数依赖中无关属性：（1）如果AX，且F逻辑蕴涵(F-XY)(X-A)Y，则称属性A是XY左部的无关属性。（2）如果AX，且(F-XY)X(Y-A)逻辑蕴涵F，则称属性A是XY右部的无关属性。（3）如果XY的左右两边的属性都是无关属性，则函数依赖XY称为无关函数依赖。第十八页，编辑于星期五：十六点 三十九分。定义4.10 设F是属性集U上的函数依赖集。如果Fmin是F的一个最小函数依赖集，那么Fmin应满足下列四个条件：（1）Fmin+=F+；（2）每个函数依赖的右边都是单属性；（3）Fmin中没有冗余的函数依赖（即在Fmin中不存在这样的函数依赖XY，使得Fmin与Fmin-XY等价），即减少任何一个函数依赖都将与原来的F不等价；（4）每个函数依赖的左边没有冗余的属性（即Fmin中不存在这样的函数依赖XY，X有真子集W使得Fmin-XY WY与Fmin等价），减少任何一个函数依赖左部的属性后，都将与原来的F不等价。第十九页，编辑于星期五：十六点 三十九分。算法4.3 计算函数依赖集F的最小函数依赖集G（1）对F中的任一函数依赖XY，如果Y=Y1,Y2,，Yk（k2）多于一个属性，就用分解律，分解为XY1，XY2，XYk，替换XY，得到一个与F等价的函数依赖集G，G中每个函数依赖的右边均为单属性。（2）去掉G中各函数依赖左部多余的属性。（3）在G中消除冗余的函数依赖。第二十页，编辑于星期五：十六点 三十九分。4.3 关系模式的分解*4.3.1 模式分解问题 定义4.11 设有关系模式R(U)，R=R1R2Rk，=R1，R2，Rk。这里称为R的一个分解，也称为数据库模式。泛关系模式泛关系模式泛关系泛关系数据库模式数据库模式数据库实例数据库实例 Rr=R1，R2，Rk=模式分解示意图模式分解示意图 衡量关系模式的分解是否可取衡量关系模式的分解是否可取分解是否具有无损连接分解是否具有无损连接分解是否保持了函数依赖分解是否保持了函数依赖第二十一页，编辑于星期五：十六点 三十九分。4.3.2 无损连接分解 定义4.12设有R，F是R上的函数依赖集，=R1，R2，Rk。如果对R中满足F的每一个关系r，有r=R1(r)R2(r)Rk(r),那么就称分解相对于F是“无损连接分解”；否则称为“损失分解”。定理4.6 设=R1，R2，Rk是关系模式R的一个分解，r是R的任一关系，ri=Ri(r)（1ik）,那么有下列性质：（1）r m(r)；（2）若s=m(r)，则Ri(s)=ri；（3）m(m(r)=m(r)，这个性质称为幂等性。第二十二页，编辑于星期五：十六点 三十九分。4.3.3 无损分解的测试算法（1）构造一个k行n列的表格R，表中每一列对应一个属性Aj（1jn），每一行对应一个模式Ri（1ik）。如果Aj在Ri中，则在表中的第i行第j列处填上符号aj，否则填上bij。（2）把表格看成模式R的一个关系，根据F中的每个函数依赖，在表中寻找X分量上相等的行，分别对Y分量上的每一列做修改：如果列中有一个是aj，那么这一列上（X相同的行）的元素都改成aj；如果列中没有aj，那么这一列上（X相同的行）的元素都改成bij（下标ij取i最小的那个）。对F中所有的函数依赖，反复地执行上述的修改操作，一直到表格不能再修改为止（这个过程称为“追踪”过程）。（3）若修改到最后，表中有一行全为a，即a1a2an，那么称相对于F是无损连接分解。第二十三页，编辑于星期五：十六点 三十九分。例4-11 设有关系模式R(A，B，C，D)，R分解成=AB，BC，CD，如果R上成立的函数依赖集F=BA，CD，那么相对于F是否为无损连接分解？ABCDABa1a2 b13 b14 BCb21 a2 a3 b24 CDb31b32 a3 a4 BA a1CD a4修改后的表格中的第二行修改后的表格中的第二行为为a1a2a3a4，因此，因此，相对于相对于F是无损是无损连接分解连接分解。第二十四页，编辑于星期五：十六点 三十九分。定理4.7 设=R1，R2是关系模式R的一个分解，F是R上成立的函数依赖集，那么分解相对于F是无损分解的充分必要条件是：(R1R2)(R1-R2)或(R1R2)(R2-R1)当模式R分解成两个模式R1和R2时，若两个模式的公共属性（除外）能够函数决定R1（或R2）中的其他属性，这样的分解具有无损连接性。第二十五页，编辑于星期五：十六点 三十九分。4.3.4 保持函数依赖的分解 定义4.13 设有关系模式R(U)，F是R(U)上的函数依赖集，Z是属性集U上的一个子集，=R1，R2，Rk是R的一个分解。F在Z上的一个投影用Z(F)表示：Z(F)=XY|XYF+XYZ；F在Ri上的一个投影用Ri(F)表示：=R1(r)R2(r)Rk(r)；如果有F+=()+，则称是保持函数依赖集F的分解。一个无损连接分解不一定是保持函数依赖的一个无损连接分解不一定是保持函数依赖的一个保持函数依赖的分解也不一定是无损连接的一个保持函数依赖的分解也不一定是无损连接的第二十六页，编辑于星期五：十六点 三十九分。4.4 关系模式的范式 各种范式之间的关系 第二十七页，编辑于星期五：十六点 三十九分。4.4.1 第一范式 定义4.14 如果关系模式R所有的属性均为简单属性，即每个属性都是不可再分的，则称R属于第一范式，简称1NF，记作R1NF。1NF是关系模式应具备的最起码的条件。第一范式可能具有大量的数据冗余，具有插入异常、删除异常和更新异常等弊端。如关系模式SCD属于1NF，它既存在完全函数依赖，又存在部分函数依赖和传递函数依赖。克服这些弊端的方法是用投影运算将关系分解，去掉过于复杂的函数依赖关系，向更高一级的范式进行转换。第二十八页，编辑于星期五：十六点 三十九分。4.4.2 第二范式 第二范式的定义 如果关系模式R1NF，且每个非主属性都完全函数依赖于R的主关系键，则称R属于第二范式，简称2NF，记作R2NF。如：关系模式TCS（T，C，S）关系键 （T，C，S）；主属性 T、C、S 不存在非主属性对主关系键的部分函数依赖，因此属于2NF。从从1NF关系中消除非主属性对主关系键的部分函数依赖，则可得到关系中消除非主属性对主关系键的部分函数依赖，则可得到2NF如果如果R的关系键为单属性，或的关系键为单属性，或R的全体属性均为主属性，则的全体属性均为主属性，则R 2NF 第二十九页，编辑于星期五：十六点 三十九分。2NF规范化 2NF规范化是指把1NF关系模式通过投影分解，转换成2NF关系模式的集合。例4-15 将SCD(SNo，SN，Age，Dept，MN，CNo，Score)规范为2NF。学生学生SD(SNo,SN,Age,Dept,MN)学生与课程联系学生与课程联系SC(SNo,CNo,Score)SCD非主属性对主键完全函数依赖。因此，非主属性对主键完全函数依赖。因此，SD 2NF，SC 2NF。第三十页，编辑于星期五：十六点 三十九分。2NF的缺点 数据冗余数据冗余 插入异常插入异常 删除异常删除异常 更新异常更新异常 每个系名和系主任的名字存储的次数等于该系的学生人数每个系名和系主任的名字存储的次数等于该系的学生人数 当一个新系没有招生时，有关该系的信息无法插入当一个新系没有招生时，有关该系的信息无法插入 某系学生全部毕业而没有招生时，删除全部学生的记录也某系学生全部毕业而没有招生时，删除全部学生的记录也随之删除了该系的有关信息随之删除了该系的有关信息 更换系主任时，仍需改动较多的学生记录更换系主任时，仍需改动较多的学生记录 第三十一页，编辑于星期五：十六点 三十九分。4.4.3 第三范式 第三范式的定义 如果关系模式R2NF，且每个非主属性都不传递函数依赖于R的主关系键，则称R属于第三范式，简称3NF，记作R3NF。如：SC(SNo，CNo，Score)函数依赖为(SNo，CNo)Score，非主属性Score不传递函数依赖于主关系键（SNo，CNo），因此，SC3NF。又如：SD(SNo，SN，Age，Dept，MN)SNoDep和DeptMN SNo MN 非主属性MN与主关系键SNo间存在着传递函数依赖，所以SD 3NF。主关系键主关系键 非主属性非主属性 t非主属性非主属性 主关系键主关系键 第三十二页，编辑于星期五：十六点 三十九分。3NF规范化算法4.6 把一个关系模式分解为3NF，使它具有保持函数依赖性。（1）如果Fmin中有一函数依赖XA，且XA=R，则输出=R，转（4）。（2）如果R中某些属性与Fmin中所有依赖的左部和右部都无关，则将它们构成关系模式，从R中将它们分出去，单独构成一个模式。（3）对于Fmin中的每一个函数依赖XA，都单独构成一个关系子模式XA。若Fmin中有XA1，XA2，XAn，则可以用模式XA1A2An取代n个模式XA1，XA2，XAn。（4）停止分解，输出。第三十三页，编辑于星期五：十六点 三十九分。算法4.7 把一个关系模式分解为3NF，使它既具有无损连接性又具有保持函数依赖性。（1）根据算法4.6求出保持函数依赖的分解：=R1，R2，Rk。（2）判定是否具有无损连接性，若是，转（4）。（3）令=X=R1，R2，Rk，X，其中X是R的候选键。（4）输出。例4-17 将SD(SNo，SN，Age，Dept，MN)规范到3NF。（1）根据算法4.6求出保持函数依赖的分解：=S(SNo，SN，Age，Dept)，D(Dept，MN)。第三十四页，编辑于星期五：十六点 三十九分。（2）判定是否具有无损连接性SD分解为=S(SNo，SN，Age，Dept)，D(Dept，MN)时，S、D都属于3NF，且既具有无损连接性又具有保持函数依赖性。3NF解决了2NF中存在的四个问题：SNo SN Age DeptMN S(SNo，SN，Age，Dept)a1 a2 a3 a4 b15 D(Dept，MN)b21 b22 b23 a4 a5 DeptMN a5a1a2a3a4a5，相对于相对于F是无损连接分解是无损连接分解数据冗余降低了数据冗余降低了 不存在删除异常不存在删除异常 不存在更新异常不存在更新异常 不存在插入异常不存在插入异常 第三十五页，编辑于星期五：十六点 三十九分。4.5 关系模式的规范化 一个低一级范式的关系模式，通过模式分解转化为若干个高一级范式的关系模式的集合，这种分解过程叫作关系模式的规范化。关系模式规范化的目的和原则规范化的目的就是使结构合理，消除存储异常，使数据冗余尽量小，便于插入、删除和更新。规范化的基本原则就是遵循“一事一地”的原则。第三十六页，编辑于星期五：十六点 三十九分。4.5.2 关系模式规范化的步骤规范化过程规范化过程 第三十七页，编辑于星期五：十六点 三十九分。4.5.3 关系模式规范化的要求 保证分解后的关系模式与原关系模式是等价的等价的三种标准：分解要具有无损连接性；分解要具有函数依赖保持性；分解既要具有无损连接性，又要具有函数依赖保持性。保证不丢失信息保证不丢失信息 减轻或解决各种异减轻或解决各种异常情况常情况 第三十八页，编辑于星期五：十六点 三十九分。