5 关系数据库设计理论

第五章关系数据库设计理论关系数据库设计理论是关系数据库的指南，也是关系数据库的理论基础。它是数据库领域的专家和学者们总结数据库设计中的经验教训的基础上，借助近代数学工具而提出来的。它把抽象的数学理论和具体的实际问题结合起来，为数据库领域的发展起到了推动作用。意义：提供分析和判断数据库模式好坏的准则；指导设计好的数据库模式。地位：本章是本书最难的部分之一，但对于应用设计十分有用5.1问题的提出－什么是不好的数据库设计实际问题，假定在设计数据库时出现如下的关系模式：Student(Sno,Sname,Dept，Cno,Grade)学生（学号，姓名，院系，课程号，成绩）SnoSnameDeptCnoGrade1000李平计算机001861000李平计算机002971000李平计算机003831001王莉计算机001801001王莉计算机00275上述的关系模式在实际应用中会出现什么样的问题呢？1、数据存在冗余该关系模式中，学生每选一门课，他的名字和院系就要重复存放一次。而且，如果他的院系改变的话，那么对于其的每一个元组的院系都要改变。这样不仅增添了更新代价，而且还有可能出现一个人在不同院系的情况。2、插入（删除）异常该关系模式的主键应该是由学生学号和课程号共同构成。按照常理，新学生登记注册，应该在学生信息库里存在他的资料，但如果此时他还未选课，那么关于这个学生的信息就不能创建，这是违背现实的情况的。3、更新复杂如果某个学生转换所在系，那么和他所有的相关的记录都必须进行修改。而且，容易造成潜在的数据不一致的问题。比如‘李平’的记录，可能会只修改了其中一部分元组。结论：•Student关系模式不是一个好的模式。•“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。原因：由存在于模式中的某些数据依赖引起的解决方法：通过分解关系模式来消除其中不合适的数据依赖。由此可见，一个关系模式如果设计的不合理，将会造成很多问题。如果我们将上述的关系模式进行分解：Student(Sno,Sname，Dept)SC(Sno,Cno,Grade)分解以后可以解决上述的问题。但是上述关系模式在有些情况下也不是最优的。具体的关系模式的设计不仅要结合数据库设计理论，也还要根据实际的应用来决策。关系模式的形式化定义关系模式由五部分组成，即它是一个五元组：R(U,D,DOM,F)R：关系名U：组成该关系的属性名集合D：属性组U中属性所来自的域DOM：属性向域的映象集合F：属性间数据的依赖关系集合什么是数据依赖1.完整性约束的表现形式限定属性取值范围：例如学生成绩必须在0-100之间定义属性值间的相互关连（主要体现于值的相等与否），这就是数据依赖，它是数据库模式设计的关键2.数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系是现实世界属性间相互联系的抽象是数据内在的性质是语义的体现3.数据依赖的类型函数依赖（FunctionalDependency，简记为FD）多值依赖（MultivaluedDependency，简记为MVD）其他5.2规范化理论规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。函数依赖一、属性间的联系客观世界中的事物是彼此联系，相互制约的。这种联系分为两类：一类是实体与实体之间的联系；另一类是实体内部各属性之间的联系。属性之间的联系分为三类：1、1－1：例如果学生关系模式中没有同名现象，则学号和姓名两个属性之间的关系是一对一的关系。2、1－M：例一个院系有多个人，但是单个人只能属于一个院系，那么院系和人的学号之间的关系是一对多的。3、M－N：一个课程号对应于多个学号，一个学号对应于多个课程号，这两个属性之间是多对多的联系。二、函数依赖的定义定义：设有关系模式R(U)，X和Y是属性集U的子集，r是R上的任一具体关系，u和v是r中的任意两个元组。如果由u[X]=v[X]能推导出u[Y]=v[Y]，则称X函数决定Y，或Y函数依赖于X，记为YX:FD例：有一个学习模式R(S#,SNAME,C#,GRADE,TNAME,TAGE)现在规定，每个学号只对应一个具体学生，每个课程号只由一个教师来教，写出函数依赖。GRADE)C#,(S#-TNAMEC#-SNAMES#-三、属性间的联系和函数依赖属性间的联系有三种，但并不是每一种关系中都存在函数依赖，设有属性集X、Y属于关系模式R，如果X和Y之间是‘1－1’关系，则存在函数依赖：XYY,X如果X和Y之间是‘1－M’关系，则存在函数依赖：XY如果X和Y之间是‘N－M’关系，则：X和Y之间不存在函数依赖例：如果人名唯一的话，那么一个人名对应一个学号，则有SNOSNAMESNAME,SNO例：院系和学号之间的联系是一对多的，那么存在的FD为SDEPTSNO四、FD的逻辑蕴涵定义：设F是在关系模式R上成立的函数依赖集，是一个FD。如果对于R的每个满足F的关系也满足,则称F逻辑蕴涵，记为定义：被F逻辑蕴涵的函数依赖的全体构成的集合，称为函数依赖集的闭包，记为F+。YXYXYXYX|F五、FD的推理规则从已知的FD集推导未知的FD，可以使用的推导规则（Armstrong）设有关系模式R（U），X、Y、Z是U的子集：A1(自反性)：如果，则有在R上成立。A2(增广性)：如果在R上成立，那么有A3(传递性)：如果在R上成立，则有XYYXYXYZXZZY和YXZX证明Armstrong公理，用FD定义：A1：设u,v是r中的任意两个元组，如果u[X]=v[X]，则u,v中的X的任意子集也必然相等，由条件中u[Y]=v[Y]，根据函数依赖的定义，可以得到YXA2：设u,v是r中的任意两个元组，设u[XZ]=v[XZ]，即u[X]u[Z]=v[X]v[Z]，则u[X]=v[X],u[Z]=v[Z]，由条件根据函数依赖定义有u[Y]=v[Y],则u[YZ]=u[Y]u[Z]=v[Y]v[Z]=v[YZ]这样在u[XZ]=v[XZ]的基础上推出了u[YZ]=v[YZ]，得证。A3：设u,v是r中的任意两个元组，对于u[X]=v[X]，因为，则有u[Y]=v[Y]，又因为则根据定义可以得出u[Z]=v[Z]，因此得到YXZYZX例题：已知关系R(X,Y,Z)以及其上的函数依赖集F，求F+。XYZXYZXZXYZYZXYZXYXYZZXYZYXYZXXYZφXYZXYZXZYZXZXZXZXYXZZXZYXZXXZφXZXYZXYYZXYXZXYXYXYZXYYXYXXYφXYφφZZφZYZYZZYZYYZφYZYZYZYYYφYXYZXYZXXZXXYXZXYXXXφXZ}YY,{XFFD的分类：1、对于FD：，如果，则称为“平凡的FD”2、对于FD：，如果，则称为“非平凡的FD”3、对于FD：，如果则为“完全非平凡的FD”YXXYYXXYYXφXYArmstrong的推论：1、合并规则：2、分解规则：3、伪传递规则：YZZ可以得到XXY,由XZXY,YZ可以得到X由XZZ则得到XWYWY,由XYZ(A3)得证XZY(A2)XYZX又XY(A2)XYX合并规则：分解规则：Z同理：XY(A3)XYZXZ同理：YZY(A1)YZYZY伪传递规则：ZWXZWY又WYWXYX*用函数依赖定义键超键：能唯一标识元组的属性集称为关系模式的超键。候选键：如果一个属性集能唯一标识元组，且不含有多余的属性，那么这个属性集成为候选键。定义：如果关系模式R的属性集为A1,A2,…An，F是R上成立的一个FD集，X是A1,A2,…An的一个子集，如果X－A1,A2,…An在F+中，那么称X是R的一个超键。如果X－A1,A2,…An在F+中，且对于X的任何一个真子集X1，X1－A1,A2,…An在都不在F+中，则称X是R的一个候选键。属性集的闭包定义：设F是属性集U上的FD集，X是U的子集，那么属性集X的闭包X+，它是一个从F集使用FD推导规则推出的所有满足X－A的属性集A的集合：中}A在FX|{属性集AX定理：X－Y能用FD推理规则推出的充分必要条件是证明：(充分性)根据，设Y=A1,A2,…,An。由属性集闭包定义可知：X－Ai在F+中。再根据合并规则，X－A1,A2,…,An即X－Y。(必要性)由X－Y，根据分解规则，X－Ai，根据属性集闭包定义可得，所以，即XYXYXAiXA,...,A,An21XY*用属性集的闭包来定义候选键定义：如果关系模式R的属性集为U，F是R上成立的一个FD集，X是U的一个子集，如果X的属性集的闭包X+=U,则称X为R的一个超键，如果对于X的任何一个真子集Y，有Y+≠U。则X为R的一个候选键。算法：求属性集X关于FD集F的闭包X+输入：属性集U，U上的FD集F，X是U的子集输出：X关于F的闭包X＋方法：Result:=X;repeatforF中的每个FDY－ZdoifthenResult:=ResultUZ;until(result没有改变)；Result即为所求的X+ResultY例：属性集U为ABCD，FD集为,求A+,AD+A+(1)Result=A(2)Result=AUB=AB(3)Result=ABUC=ABCB}DC,BB,{AAD+=ABCD例题：AG}CEB,ACDBD,CGD,BCC,BEA,CEG,DC,{ABF求BD+1)result=BD,AB不含于result，result=BD2)result=BD，D包含于result,result=BDUEG=BDEG3)result=BDEG，C不含于result,result=BDEG4)result=BDEG，BE包含于result,result=BDEGUC=BCDEG5)result=BCDEG,BC包含于result,result=BCDEGUD=BCDEG6)result=BCDEG,CG包含于result,result=BCDEGUBD=BCDEG7)result=BCDEG,ACD不含于result,result=BCDEG8)result=BCDEG,CE含于result,result=BCDEGUAG=ABCDEG*快速求解候选键的充分条件对于给定的关系模式R=(A1,A2,…,An)和函数依赖集F，可将其属性分为四类：1、仅仅出现在F的函数依赖左部的属性L类；2、仅仅出现在F的函数依赖右部的属性R类；3、在F的函数依赖的左右两边都没有出现的属性N类；4、在F的函数依赖的左右两边都出现的属性LR类；定理：对于给定关系模式R及其函数依赖集F(不包含平凡FD)1)X是L类属性，则X必为R的任何一个候选键的成员。2)X是R类属性，则X不包含在任何候选键中。3)X是R的N类属性，则X也必为R的任何一个候选键的成员。4)X是R的LR类属性，则X可能是也可能不是候选键的成员。1)反证法：设W为R的任一候选键，X不是W的成员。由于X仅仅出现在F的函数依赖左部，所以R中没有其它属性能够函数决定X，这样W+中就不可能包含X，这样就与W是R的候选键相矛盾。所以X必然是候选键W的成员。（X为L类的情况）2)反证法：设W是R的任一候选键，X不是W的成员。由于X没有出现在F中，那么R中没有其它属性能够函数决定X。这样W+中就不可能包含X，这与W是R的候选键相矛盾。所以X必然是候选键W的成员。（X是N类的情况）例：设有关系模式R(A,B,C,D)，其函数依赖集F如下，求R的候选键。D}ACDB,CDB,AD,BB,{D传统步骤：1、分别求A/B/C/D/AB