第4章关系数据及其规范化理论

第2页四川农业大学潘勇浩2016问题的引入一个学籍E-R模型•学生可能重名，但只有一个学号；•系不能重名，只有一名系主任，但系主任可能重名；•每门课有一个唯一的课名，不同课的学分可能相同；•每个学生所学的每一门课程都有一个成绩。课程课名学分学生学号姓名选修成绩mn属于n系系名系主任1另有语义约定:第3页四川农业大学潘勇浩2016方案1：把学籍E-R模型设计成一个关系模式学号姓名系名系主任课名学分成绩9801张明IS刘成C语言3859801张明IS刘成数据库3809801张明IS刘成数据结构3769801张明IS刘成高数5829802赵龙CS王浩高数3729802赵龙CS王浩C语言3689803陈然MA魏征C语言3849803陈然MA魏征数据库3869803陈然MA魏征高数5749804钟伟IS刘成高数575┆┆┆┆┆┆┆SCD(学号,姓名,系名,系主任,课名,学分,成绩)说明：带下划线的属性集构成主码。这个方案是“好”的方案吗？问题的引入第4页四川农业大学潘勇浩2016SCD的问题1：数据冗余太大多次出现同一个学生的姓名、所在系和系主任；多次出现同一课程的学分。学号姓名系名系主任课名学分成绩9801张明IS刘成C语言3859801张明IS刘成数据库3809801张明IS刘成数据结构3769801张明IS刘成高数5829802赵龙CS王浩高数3729802赵龙CS王浩C语言3689803陈然MA魏征C语言3849803陈然MA魏征数据库3869803陈然MA魏征高数5749804钟伟IS刘成高数575┆┆┆┆┆┆┆问题的引入第5页四川农业大学潘勇浩2016SCD的问题2：存在插入异常无法插入没有选课的学生；无法插入还无学生选修的新课；无法插入尚无学生的新系。问题的引入学号姓名系名系主任课名学分成绩9801张明IS刘成C语言3859801张明IS刘成数据库3809801张明IS刘成数据结构3769801张明IS刘成高数5829802赵龙CS王浩高数3729802赵龙CS王浩C语言3689803陈然MA魏征C语言3849803陈然MA魏征数据库3869803陈然MA魏征高数5749804钟伟IS刘成高数575┆┆┆┆┆┆┆第6页四川农业大学潘勇浩2016SCD的问题3：存在删除异常如果删除了某一系的所有学生，则该系被删除；如果删除了所有选同一门课的学生，则该课程被删除。问题的引入学号姓名系名系主任课名学分成绩9801张明IS刘成C语言3859801张明IS刘成数据库3809801张明IS刘成数据结构3769801张明IS刘成高数5829802赵龙CS王浩高数3729802赵龙CS王浩C语言3689803陈然MA魏征C语言3849803陈然MA魏征数据库3869803陈然MA魏征高数5749804钟伟IS刘成高数575┆┆┆┆┆┆┆第7页四川农业大学潘勇浩2016SCD的问题4：更新复杂某一系换了系主任，则必须修改所有该系学生的系主任数据，否则就会出现同一系有两个以上的系主任。问题的引入学号姓名系名系主任课名学分成绩9801张明IS刘成C语言3859801张明IS刘成数据库3809801张明IS刘成数据结构3769801张明IS刘成高数5829802赵龙CS王浩高数3729802赵龙CS王浩C语言3689803陈然MA魏征C语言3849803陈然MA魏征数据库3869803陈然MA魏征高数5749804钟伟IS刘成高数575┆┆┆┆┆┆┆第8页四川农业大学潘勇浩2016可见：方案1不是一个“好”的方案！SCD(学号,姓名,系名,系主任,课名,学分,成绩)原因：每一个关系模式中的属性之间的相互依赖关系过于复杂！学号课名系名系主任学分成绩姓名问题的引入第9页四川农业大学潘勇浩2016方案2：把学籍E-R模型设计成4个关系模式学号姓名系名9801张明IS9802赵龙CS9803陈然MA9804钟伟IS┆┆┆学号课名成绩9801C语言859801数据库809801数据结构769801高数829802高数729802C语言689803C语言849803数据库869803高数749804高数75┆┆┆系名系主任IS刘成CS王浩MA魏征┆┆课名学分C语言3数据库3数据结构3高数5┆┆S(学号,姓名,系名)D(系名,系主任)C(课名,学分)SC(学号,课名,成绩)SSCDC问题的引入第10页四川农业大学潘勇浩2016方案2的评价学号姓名系名9801张明IS9802赵龙CS9803陈然MA9804钟伟IS┆┆┆学号课名成绩9801C语言859801数据库809801数据结构769801高数829802高数729802C语言689803C语言849803数据库869803高数749804高数75┆┆┆系名系主任IS刘成CS王浩MA魏征┆┆课名学分C语言3数据库3数据结构3高数5┆┆SSCDC•数据冗余最小•没有插入异常•没有删除异常•更新简单问题的引入第11页四川农业大学潘勇浩2016可见：方案2比方案1“好”！原因：每一个关系模式中的属性之间的相互依赖关系比较简单！学号课名系名系主任成绩S(学号,姓名,系名)学号系名姓名SC(学号,课名,成绩)D(系名,系主任)C(课名,学分)课名学分问题的引入第12页四川农业大学潘勇浩2016结论：什么是一个“好”的关系模式？要能正确而完整地体现客观现实；无过度的数据冗余；无插入异常；无删除异常；更新不复杂！对一个不“好”的关系模式该怎么办？依据关系模式的规范化理论，将它分解成符合某种规范化标准（范式）的“好”的关系模式集！影响关系模式“好坏”的主要因素是什么？属性间的数据依赖！它也是关系模式规范化理论的最基本的概念。问题的引入第13页四川农业大学潘勇浩2016函数依赖函数依赖的定义设有关系模式R(U)，X和Y是U的子集。若对R(U)的任一具体关系r中的任意两个元组u和v，只要u[X]=v[X]就有u[Y]=v[Y]，则称X函数决定Y或Y函数依赖于X，记作X→Y。SnoSnameSsexSageSdep98001张明男29CS98002李华女30MA98003王军男28IS98004孙六女27IS98005赵龙女18CS98006李华女22MA98007钟伟男19CSX→Y意为元组的X值一经确定则它的Y值也随之确定。或者说，不可能存在X上的属性值相等，而在Y上的属性值不等的两个元组。例如Sno→Sname，Sno→(Sname,Ssex,Sage,Sdep)第14页四川农业大学潘勇浩2016函数依赖的定义若X→Y，则称X为该函数依赖的决定因子。若X→Y，且Y→X，则记为X←→Y(即互相依赖)。若Y不函数依赖于X，则记为X→Y。若X→Y,但YX,则称X→Y是非平凡的函数依赖。若X→Y,但YX,则称X→Y是平凡的函数依赖。学号→姓名，(学号,课名)→成绩是非平凡的学号→学号，(学号,课名)→学号是平凡的注意：平凡的函数依赖是必然成立的，所以一般没有特别指明时均是指非平凡的函数依赖。函数依赖第15页四川农业大学潘勇浩2016函数依赖的定义学号姓名性别年龄系别98001张三男20CS98002李四女19IS98003王五男21IS98004赵六女20MA此时姓名→年龄函数依赖是一个语义范畴的概念，并且必须以关系模式（包括所有可能的关系）为准，而不能只考虑到一个关系的状态！学号姓名性别年龄系别98001张三男20CS98002李四女19IS98003王五男21IS┆┆┆┆┆能肯定姓名→年龄吗？若约定不能重名呢？函数依赖第16页四川农业大学潘勇浩2016函数依赖的定义设R(U)是一个关系模式，X和Y都是U的子集，且存在X→Y。若对于X的任何一个真子集X'，都有X'→Y，则称Y完全函数依赖于X，记作XY；若对于X的某一个真子集X'，有X'→Y，则称Y部分函数依赖于X，记作XY。fp学号课名系名系主任学分成绩姓名(学号,课名)成绩(学号,课名)学分fp函数依赖第17页四川农业大学潘勇浩2016函数依赖的定义学号系主任t设R(U)是一个关系模式，X、Y、Z都是U的子集，如果X→Y,Y→Z，并且YX，ZY，Y→X，则称Z传递函数依赖于X，记作XZ。t学号课名系名系主任学分成绩姓名函数依赖第18页四川农业大学潘勇浩2016函数依赖函数依赖的逻辑蕴涵函数依赖涉及这样一类问题：已知关系模式R(U,F)，其中属性集U={A,B,C}，函数依赖集F={A→B，B→C}，能推出A→C成立吗?对于关系模式R(U,F)，XU，YU，且(X→Y)F，若函数依赖X→Y成立，则称R的函数依赖集F逻辑蕴涵X→Y，记为FX→Y。被函数依赖集F逻辑蕴涵的所有函数依赖所构成的集合，称为F的闭包(closure)，记作F+。即：F+={X→Y|FX→Y}。第19页四川农业大学潘勇浩2016Armstrong公理系统设有关系模式R(U,F)，X、Y、Z、W均是U的子集：自反律：若YX，则有X→Y；增广律:若X→Y，则有XZ→YZ；传递律:若X→Y，Y→Z，则有X→Z；合并律:若X→Y，X→Z，则有X→YZ；伪传递律：若X→Y，YW→Z,则有XW→Z；分解律：若X→Y，ZY，则有X→Z；推论：性质：Armstrong公理系统是有效的，完备的。函数依赖的公理系统第20页四川农业大学潘勇浩2016Armstrong公理系统设有关系模式R(U,F)，其中U={A，B，C，D,E,G},F={AB→C,C→A,BC→D,ACD→B,D→EG,BE→C，CG→BD,CE→AG},证明FBD→AC。由D→EG可得D→E(分解)，进一步得BD→BE(增广)；由BE→C，C→A得出BE→A(传递)，BE→AC(合并);由前面推导出的BD→BE和BE→AC得出BD→AC(传递)所以BD→AC被F所蕴涵，即FBD→AC函数依赖的公理系统第21页四川农业大学潘勇浩2016Armstrong公理系统已知R(U={ABC},F={A→B,B→C}),求F+。F+={A→φ，AB→φ，AC→φ，ABC→φ，B→φ，C→φ，A→A，AB→A，AC→A，ABC→A，B→B，C→C，A→B，AB→B，AC→B，ABC→B，B→C，A→C，AB→C，AC→C，ABC→C，B→BC，A→AB，AB→AB，AC→AB，ABC→AB，BC→Φ，A→AC，AB→AC，AC→AC，ABC→AC，BC→B，A→BC，AB→BC，AC→BC，ABC→BC，BC→C，A→ABC，AB→ABC，AC→ABC，ABC→A，BC→BC}函数依赖的公理系统第22页四川农业大学潘勇浩2016Armstrong公理系统设有关系模式R(U,F)，其中U={A,B,C,E,H,P,G},F={AC→PE,PG→A,B→CE,A→P,GA→B,GC→A,PAB→G,AE→GB,ABCP→H},证明BG→HE属于F+。即证明FBG→HE①由B→CE知B→C，B→E(分解)，进一步由BG→B(自反)可得BG→C和BG→E(传递)②由①知BG→GC(增广),又GC→A所以BG→A(传递),再根据A→P有BG→P(传递)③由①②结论得出BG→ABCP(合并)④已知ABCP→H，由③知BG→H(传递)，再结合①中的BG→E得出BG→HE函数依赖的公理系统第23页四川农业大学潘勇浩2016属性集闭包对于关系模式R(U,F)，XU，A是U中的单个属性，称={A|AU，X→A能由F根据Armstrong公理导出}为属性集X关于F的闭包，通常简记为X+。已知R({ABC},{A→B,B→C})根据F能得出A→A(自反)，A→B(已知)，A→C(传递)所以A+={A，B，C}同理B+={B，C}C+={C}XF+函数依赖的公理系统第24页四川农业大学潘勇浩2016属性集闭包下面给出一种求属性集闭包的算法:输入：属性集U、函数依赖集F和U的一个子集X。输出：X关于F的闭包X+。计算方法和计算步骤：⑴设置初始值：令X0＝φ，X1＝X；⑵如果X0X1，令X0＝X1，否则转⑷；⑶构