第13章 关系数据库规范化理论

第13章关系数据库规范化理论数据库系统原理与应用王瑞金山东大学管理学院[e-mail]1主要内容13.1关系模式规范化的必要性13.2函数依赖13.3规范化与范式213.1关系模式规范化的必要性关系数据库逻辑设计针对具体问题，如何构造一个适合于它的数据库模式－关系模式集合数据库逻辑设计的工具──关系数据库的规范化理论313.1关系模式规范化的必要性一、概念回顾二、关系模式的形式化定义三、什么是数据依赖四、关系模式的简化定义五、数据依赖对关系模式影响413.1关系模式规范化的必要性关系：描述实体、属性、实体间的联系。从形式上看，它是一张二维表，是所涉及域的笛卡尔积的一个有意义的子集。关系模式：用来描述关系。关系数据库的模式：定义这组关系的关系模式的集合，是对数据库的描述。关系数据库：基于关系模型的数据库，利用关系来描述现实世界。从形式上看，它由一组关系组成。一、概念回顾513.1关系模式规范化的必要性二、关系模式的形式化定义关系模式由五部分组成，即它是一个五元组：R(U,D,DOM,F)R：关系名U：组成该关系的属性名集合D：属性组U中属性所来自的域DOM：属性向域的映象集合F：属性间数据的依赖关系集合613.1关系模式规范化的必要性三、关系模式的简化表示●根据关系设计的需要，关系模式R（U,D,DOM,F）简化为一个三元组：R（U,F）●当且仅当U上的一个关系r满足F时，r称为关系模式R（U,F）的一个关系713.1关系模式规范化的必要性四、数据依赖(1/2)1.数据依赖的概念是一个关系中属性间的相互关系是现实世界属性间相互联系的抽象是数据内在的性质是语义的体现813.1关系模式规范化的必要性四、数据依赖（2/2）2.数据依赖的类型函数依赖（FunctionalDependency，简记为FD）多值依赖（MultivaluedDependency，简记为MVD）连接依赖（JoinDependency，简记JD）913.1关系模式规范化的必要性五、数据依赖对关系模式的影响（1/5）例：描述“学生”的数据库：关系模式：Student(U,F)U＝｛Sno,Sdept,Mname,Cname,Grade｝Sno：学生的学号Sdept：所在系Mname:系主任姓名Cname:课程名Grade:成绩“学生”数据库的语义：一个系有若干学生，一个学生只属于一个系；一个系只有一名主任；一个学生可以选修多门课程，每门课程有若干学生选修；每个学生所学的每门课程都有一个成绩。1013.1关系模式规范化的必要性五、数据依赖对关系模式的影响（2/5）属性组U上的一组函数依赖F：F＝｛Sno→Sdept,Sdept→Mname,(Sno,Cname)→Grade｝SnoCnameSdeptMnameGrade1113.1关系模式规范化的必要性五、数据依赖对关系模式的影响（3/5）关系模式Student(U,F)中存在的问题（1/3）⒈数据冗余太大浪费大量的存储空间例：每一个系主任的姓名重复出现⒉更新异常数据冗余，更新数据时，维护数据完整性代价大。例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组。1213.1关系模式规范化的必要性⒊插入异常应输入表中的数据无法输入例：如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。⒋删除异常不该删除的数据不得不删例：如果某个系的学生全部毕业了，我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。五、数据依赖对关系模式的影响（4/5）关系模式Student(U,F)中存在的问题（2/3）1313.1关系模式规范化的必要性结论：•Student关系模式不是一个好的模式。•“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。原因：•由存在于模式中的某些数据依赖引起的。解决方法：•通过分解关系模式来消除其中不合适的数据依赖。五、数据依赖对关系模式的影响（5/5）关系模式StudentU,F中存在的问题（3/3）14规范化理论用于改造不合理关系模式，从而构造良好关系模式的方法。通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。13.1关系模式规范化的必要性1513.2函数依赖一、函数依赖二、平凡函数依赖与非平凡函数依赖三、完全函数依赖与部分函数依赖四、传递函数依赖五、码(键)1613.2函数依赖（续）定义:设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称“X函数确定Y”或“Y函数依赖于X”，记作X→Y。X称为这个函数依赖的决定属性集(Determinant)。一、函数依赖(FunctionDependency,FD)1713.2函数依赖（续）说明：1.函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。2.函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。例如“姓名→年龄”这个函数依赖只有在不允许有同名人的条件下成立。3.数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖“姓名→年龄”成立。4.若X→Y，并且Y→X,则记为X←→Y。5.若Y不函数依赖于X,则记为X→Y。一、函数依赖（续）1813.2函数依赖（续）例:Student(Sno,Sname,Ssex,Sage,Sdept)假设不允许重名，则有:Sno→Ssex，Sno→Sage,Sno→Sdept，Sname→Ssex，Sname→Sage,Sname→SdeptSno←→Sname但Ssex→Sage一、函数依赖（续）19二、平凡函数依赖与非平凡函数依赖定义：在关系模式R(U)中，对于U的子集X和Y：(1)如果X→Y，但YX，则称X→Y是非平凡的函数依赖(2)若X→Y，但YX,则称X→Y是平凡的函数依赖例：在关系SC(Sno,Cno,Grade)中，非平凡函数依赖：(Sno,Cno)→Grade平凡函数依赖：(Sno,Cno)→Sno(Sno,Cno)→Cno对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别声明，我们总是讨论非平凡函数依赖。13.2函数依赖（续）20三、完全函数依赖与部分函数依赖定义：在关系模式R(U)中，如果X→Y，并且对于X的任何一个真子集X，都有XY,则称Y完全函数依赖于X，记作XｆY。若X→Y，但Y不完全函数依赖于X，则称Y部分函数依赖于X，记作XPY。13.2函数依赖（续）21三、完全函数依赖与部分函数依赖（续）例:在关系SC(Sno,Cno,Grade)中，由于：Sno→Grade，Cno→Grade，因此：(Sno,Cno)ｆGrade13.2函数依赖（续）22四、传递函数依赖定义：在关系模式R(U)中，如果X→Y，Y→Z，且YX，Y→X，则称Z传递函数依赖于X。记为XtZ注:如果Y→X，即X←→Y，则Z直接依赖于X。例:在关系Std(Sno,Sdept,Mname)中，有：Sno→Sdept，Sdept→MnameMname传递函数依赖于Sno13.2函数依赖（续）2313.2函数依赖（续）五、函数依赖的逻辑蕴涵从一些已知FD去判断另一些FD是否成立，这类问题称为逻辑蕴涵。定义一：设F是关系模式R(U)的一个函数依赖集，X→Y是一个函数依赖，如果能从F中推出X→Y，则称F逻辑蕴涵X→Y。定义二：被F逻辑蕴涵的全部函数依赖构成的集合称F的闭包，记为F+。2413.2函数依赖（续）六、函数依赖公理(1/2)函数依赖公理指从已知FD集推出其他FD的推理规则，也称为Armstrong公理(W.W.Armstrong,1974)。设U是关系模式R属性集，F是R上成立的只涉及到U中属性的函数依赖集，则有下列推理规则：自反律(Reflexivity):如果YXU，则X→Y在R上成立。增广律(Augmentation):如果X→Y在R上成立，且ZU，则XZ→YZ在R上成立。传递律(Transitivity):如果X→Y和Y→Z在R上成立，则X→Z在R上成立。2513.2函数依赖（续）六、函数依赖公理(2/2)根据上述Armstrong公理三个规则，可导出下列推理规则：合并律:如果X→Y和X→Z成立，则X→YZ成立。伪传递律:如果X→Y和WY→Z成立，则WX→Z成立。分解律:如果X→Y和ZY成立，则X→Z成立。公理的完备性和正确性完备性:用公理可以推出F所蕴涵的全部函数依赖。正确性:用公理推出的F所蕴涵的全部函数依赖都是正确的。2613.2函数依赖（续）七、属性集的闭包(1/3)定义设U是关系模式R属性集，X是U的子集，F是R上的函数依赖集，则所有用公理从F推出的函数依赖X→A中，A的属性集合称为X的属性闭包，记为X+。2713.2函数依赖（续）七、属性集的闭包(2/3)计算方法输入：属性集U，函数依赖集F，属性XU输出：X相对于F的属性闭包X+方法：(1)X(0)=X(2)在F中寻找尚未用过的左边是X(i)的子集的函数依赖：Yj→Zj(其中：YjX(i))在Zj中寻找X(i)中未出现过的属性集合A：如找到，则求：X(i+1)=X(i);否则转(4)(3)判断是否有X(i+1)=X(i)，是否则转(4);否则转(2)(4)输出X(i),结束。2813.2函数依赖（续）七、属性集的闭包(3/3)举例：设有关系模式R(U，F)，其中U={A,B,C,D,E,I}，F={A→D，AB→E，BI→E，CD→I，E→C}，计算(AE)+(1)X(0)=(AE)(2)在F中寻找尚未用过的左边是(AE)的子集的函数依赖：A→D，E→C所以：X(1)=X(0)DC=(ACDE)(3)显然X(1)≠X(0)，继续运算，在在F中寻找尚未用过的左边是(ACDE)的子集的函数依赖：CD→I所以：X(2)=X(1)I=(ACDEI)(4)虽然X(2)≠X(1)，但在F中未用过的函数依赖的左边属性已没有X(2)的子集，运算结束。(5)(AE)+=(ACDEI)2913.2函数依赖（续）八、码(键)码(键)定义：设K为关系模式R(U,F)的属性集合，若K→U，则K称为R的超码（SuperKey）。如果不存在K'K，使得K'→U成立，则K称为R的一个侯选码（CandidateKey）。若关系模式R有多个候选码，则选定其中的一个做为主码（Primarykey）。主属性：候选码中包含的属性称为主属性非主属性：不能构成候选码的属性称为非主属性3013.2函数依赖（续）外码(外键)定义：关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外码（Foreignkey）也称外键。主码又和外码一起提供了表示关系间联系的手段。八、码(键)3113.2函数依赖（续）属性的分类对于给定的关系R(A1,A2,……,An)和函数依赖集F，可将属性分为四类：L类：仅出现在F的函数依赖左部的属性R类：仅出现在F的函数依赖右部的属性N类：在F的函数依赖的左右均未出现的属性LR类：在F的函数依赖的左右均出现的属性九、候选码(候选键)的求解算法3213.2函数依赖（续）定理一对于给定的关系R和函数依赖集F，若X(X∈R)是L类属性，则X必为R的任一候选码的成员。推论对于给定的关系R和函数依赖集F，若X(X∈R)是L类属性，且X+包含了R的全部属性，则X必为R的惟一候选码。九、候选码(候选键)的求解算法3313.2函数依赖（续）举例设有关系模式R(A,B,C,D)，其函数依赖集F={D→B,B→D,AD→B,AC→D}，求R的所有候选码。A，C两属性是L类属性，AC必是R的一候选码的成员(AC)+=ACBD，所以AC是R的惟一候选码九、候选码(候选