数据库-第四章(无多值依赖).ppt

数据库系统原理教程 Database Systems,第四章 关系数据库设计理论,4.1 数据依赖 4.2 范式 4.3 关系模式的规范化,数据库的概念模型可以转换为关系模型，但是这样得到的关系模型，或用其他方法得到的关系模型，经常会存在一系列更新异常问题。利用关系数据库的规范化理论，通过规范化使得到的关系模式符合一定的范式，可以不同程度地解决更新异常问题，从而得到一组更优的关系模式。,4.1 数据依赖,4.1.1 关系模式中的数据依赖,关系模式对关系的刻划,R(U , D , DOM , F),说明： R关系名 U组成该关系的属性名集合,DU中属性所来自的域 DOM属性向域的映像集合 F属性间数据的依赖关系集合,描述关系的元组语义，限定组成关系的各个元组必须满足的完整性约束条件,属性取值范围的限定 属性值间相互关联数据依赖,外延关系、表或当前值；插入、删除和修改；外延与 时间有关，随时间推移在不断变化 内涵对数据的定义以及数据完整性约束的定义。,数据的定义：对关系、属性、域的定义和说明；,数据完整性约束定义： 静态约束：涉及数据之间联系（数据依赖）、主 建和值域的设计； 动态约束：定义各种操作（插入、删除、修改） 对关系值的影响。内涵称为关系模式。,对一个现实问题，它有一个属性集 U，其中，每个属性Ai对应一个值域，不同属性可以有相同的值域。现实问题的所有属性组成的关系模式记为R(U)。关系r是关系模式R(U)的当前值，是元组的集合。 实际应用中，往往R(U)和r不是恰当的形式，而必须用一个关系模式的集合 R1 R2 Rk代替R(U)，其中每个Ri的属性是U的子集。,有时用Ri表示其属性集，有R1 R2 Rk=U； 称为数据库模式 对数据库的每一个关系模式Ri赋予一个当前值，就得到数据库实例。 本章讨论如何把关系模式分解成规范的、较优的数据库模式。,关系是关系模式在某一时刻的状态或内容 关系模式静态的、稳定的 关系动态的必须满足关系模式中数据依赖关系F中指定的完整性约束条件,R(U , F),关系模式简化为三元组,当且仅当U上的一个关系r满足F时，r称为关系模式R(U , F)的一个关系,关系模式的冗余和异常问题,数据管理中，数据冗余一直是影响系统性能的大问题。 数据冗余：同一个数据在系统中多次重复出现。 文件系统中，文件之间没有联系，引起一个数据在多个文件中出现； 数据库系统设计的不好仍然出现数据冗余、异常、不一致等问题。,设有一个关系模式R(Sno,Cno,Cname,Tname)，分别表示学号、课程号、课程名称和任课教师姓名。,例,数据冗余：一门课程有多个学生选修，则课程名称和教 师名称多次重复出现 更新异常：C4课的任课教师修改要修改3个元组，易产 生不一致 插入异常：安排新课程（C8,DELPHI,CHEN）,无学生 选修时，则表中属性Sno上出现空值 删除异常：删除S8学生选课元组，则将课程名和教师名 一起删除,解决办法：分解R(Sno,Cno,Cname,Tname)， R1(Sno,Cno)， R2(Cno,Cname,Tname)，,上述分解是否是最佳分解？ 什么样的关系模式分解是最优的？ 标准是什么？ 如何实现？,4.1.2 数据依赖对关系模式的影响,数据依赖 函数依赖（functional dependency） 多值依赖（multialueddependenc） 数据依赖针对关系模式，而不是特定的实例,数据依赖是通过一个关系中属性间值的相对与否体现出来的数据间的相互关系，是现实世界属性间联系的抽象，是数据内在的性质，是语义的体现。,数据库技术中，把数据之间存在的联系称为“数据依赖”。函数依赖是基本的一种依赖，是关键码概念的推广。,数据库中，属性值之间会发生联系。如每个学生只有一个姓名，没门课程有一个任课教师，每个学生选修一门课程只有一个成绩等等。这类联系称为函数依赖。,定义4.1：设R（U）是属性集U上的关系模式。X，Y是 U的子集。若对于R（U）的任意一个可能的关系r， r中不可能存在两个元组t和s，它们在X上的属性值相等，而在Y上的属性值不等，也即，对这任意两个元组t和s，都有若tX=sX则tY=sY，则称X函数确定Y或Y函数依赖于X ，记作XY。,4.1.3 有关概念,1.函数依赖（FD）,这里tX表示元组t在属性集X上的值，其余类同。,FD是对关系模式R的一切可能的关系r定义的。对于当前关系r的任意两个元组，如果X值相同，要求Y值也相同，即有一个X值就有一个Y值与之对应，或者说Y值由X值决定。这种依赖称为函数依赖。,R(Sno,Sname,Cno,Grade,Cname,Tname,Tage)，分别表示学号、姓名、课程号、成绩、课程名称、任课教师姓名和年龄。,例,设有一个关系模式,规定：每个学号只能有一个学生姓名，每个课程号只能决定一门课程，则写出如下FD: SnoSname、 CnoCname 每个学生每学一门课程，有一个成绩，则FD: (Sno,Cno) Grade 其它FD： Cno（Cname、Tname,Tage)、 TnameTage,例：,R（ Sno , Sdept , Mname , Cname , Grade ）,一个系有若干学生，但一个学生只属于一个系 一个系只有一名主任 一个学生可以选修多门课程，每门课程可以有多名学生选修 每个学生所学每门课程都有一个成绩,F=SnoSdept , SdeptMname ,（Sno Cname）Grade ,数据冗余太大 更新异常 插入异常 删除异常,R(ABCD)，在关系R中，属性值间有这样的联系：A值与B值有一对多联系，即每个A值有多个B值与之联系，而每个B值只有一个A值与之联系；C值与D值是一对一联系，即每个C值只有一个D值与之联系，每个D值只有一个C值与之联系。试写出相应的函数依赖。,例,设有一个关系模式,BA D C、CD,超码：在关系R中，能惟一标识元组的属性或属性集。 超码的概念不足以帮助我们达到目的，因为超码中可能包含一些无关紧要的属性。如果K是一个超码，那么K的任意超集也是超码。 若超码 K 的任意真子集都不能成为超码，这种最小超码称为候选码。,回忆超码的概念：,设R（U）是属性集 U 上的关系模式。X是 U 的子集。若 XU 在 R 上成立，那么称 X 是 R 的一个超码。若 XU 在 R 上成立，但对于X的任一真子集X1都有X1U不成立，那么称X是 R 的一个候选码。,函数依赖（FD）和关键码的联系,R(Sno,Sname,Cno,Grade,Cname,Tname,Tage),例,规定：每个学生每学一门课程，只有一个成绩，每个学号只能有一个学生姓名，每个课程号有一个课程名，每门课只有一个任课教师 则写出如下FD: (Sno,Cno) Grade SnoSname、 CnoCname Cno（Tname,Tage),(Sno,Cno),Sno,Cno,Sname,Tname,函数依赖是用命题形式定义的，所以函数依赖之间存在着逻辑蕴涵的关系。 若 AB 和 B C在R 上成立，那么AC 在 R 上成立吗？ 这样的问题就是FD之间的逻辑蕴涵问题。,FD的逻辑蕴含,Armstrong 公理,设F是在关系模式R(U)上成立的函数依赖集， X，Y是 U的子集。如果从F推导出XY也在R(U)上成立，那么称F逻辑蕴涵XY，记做 F| XY。 函数依赖集F的闭包（closure）是F所逻辑蕴涵的所有的函数依赖的集合，记为F+，即 F+XY|F|= XY,假设A、B、C和D是关系模式R的四个属性组，Armstrong公理包括如下三条推理规则： 自反律（reflexivity）：若AB，则AB。 例如，A:（sex, birthdate) ； B: （sex) 则： （sex, birthdate） （sex）,证明： 自反律（reflexivity）：若AB，则AB。 不可能在一个关系中两个元组在A上相等，而在A的某个子集B上不相等。,增广律（augmentation）：若AB在R上成立，则对任意的属性组C且CU，ACBC在R上成立。 例如： empID empName (empID, sex) (empName, sex) (empID, sex, birthdate) (empName, sex, birthdate) ,证明： 增广律（augmentation）：若AB在R上成立，则对任意的属性组C且CU，ACBC在R上成立。 假设：R的某个关系 r中存在两个元组t和s违反ACBC即tAC=sAC则tBCsBC； 从tBCsBC中可知tBsB或tCsC。如果tCsC则与假设的tAC=sAC矛盾；如果tBsB则与已知的AB矛盾； 所以，假设不成立，从而推出命题成立。,传递律（transitivity）：若AB和BC在R上成立，则AC在R上成立。 例如： empID branchID，branchID branchName 则empID branchName,证明： 传递律（transitivity）：若AB和BC在R上成立，则AC在R上成立。 假设：R的某个关系 r中存在两个元组t和s违反AC即tA=sA则tCsC； 如果：tBsB则与已知的BC矛盾；如果tBsB则与已知的AB矛盾； 所以，假设不成立，从而推出命题成立。,合并律（union）：若AB和AC成立，则A BC成立。 例如： empID empName, empID sex 则： empID empName, sex,引申的另外三条规则：,伪传递律（pseudo transitivity）：若AB和BDC成立，则AD C成立 证明：由增广律，因为 AB，故ADBD成立，由于BDC，由传递律， ADC必成立。,例如，关系模式TCourse(SNo,CNo, TNo, score)中各属性分别代表学号、课程编号、教师号以及成绩，假设每个教师只教一门课。则存在函数依赖： TNo CNo, (CNo, SNo) score, 由伪传递规则可得： (TNo, SNo) score,分解律（decomposition）：若A BC成立，则AB和AC成立。 例如： empID empName, sex 则：empID empName, empID sex,几点说明：,函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。 语义范畴概念 数据库设计者可以对现实世界作强制的规定,2.平凡函数依赖与非平凡函数依赖,3.完全函数依赖与部分函数依赖,4.传递函数依赖,5.码,主属性：包含在任何一个候选码中的属性。 非主（码）属性：不包含在任何一个码中的属性。 全码（All-key）：整个属性组是码。 定义4.6：关系模式 R 中的属性或属性组 X 并非 R 的码，但 X 是另一个关系模式的码，则称X是R的外码（FK）。,设F是关系模式R(ABC) 的FD集， F=A BC , BC , AB , ABC，求Fmin,例,1、先把F中的FD写成右边是单属性形式： F=A B , A C ，BC , AB , ABC F= A C ，BC , AB , ABC 2、 A C冗余去掉 F= BC , AB , ABC ABC可以从BC 推出，因此删除，最后得到： Fmin= BC , AB ,4.2 范式,什么是好的数据库设计 体现客观世界的信息 无过度的冗余 无插入异常 无更新复杂 无删除异常,更新复杂!,删除异常!,异常的原因 数据依赖的约束 解决方法 数据库设计的规范化分解,模式分解问题 无损分解 保持函数依赖的分解,模式分解问题,设有关系模式R（U），R1，R2,，Rk都是R的子集（关系模式看成属性的集合），UR1Rk。关系模式R1，R2,，Rk的集合用表示。 R1，R2,，Rk。用代替R的过程称为关系模式的分解。这里称为R的一个分解， 也称为数据库模式。,将关系模式R分解成的目的是为了消除数据冗余和消除操作异常现象，那么分解后和r是否表示同一个数据库呢？ 如果它们表示的内容不同，那么分解就没有意义了。,（1）分解后和r是否等价，是否表示同一个数据库用“无损分解”特性表示； （2）在模式R上有一个FD集F，在的每一个模式Ri上有一个FD集Fi，那么F1，Fk与F是否等价，用“保持依赖”特性表示。,从如下角度考虑分解分解：,无损分解,例：设关系模式R(A,B,C),分解成AB,AC,关系模式R上的一个关系r，r1，r2是r在AB和AC上的投影。显然 r1 r2r 可以看到，r投影、联接以后仍然能恢复成r，即未丢失信息，这样的分解叫“无损分解”。,无损分解,例：设关系模式R(A,B,C),分解成AB,AC,关系模式R上的一个关系r，r1，r2是r在AB和AC上的投影。显然 r1 r2r 可以看到，r投影、联接以后比原来r的元组还多，丢失原来的信息，这样的分解叫“损失分解”。,无损分解,分解与函数依赖有关。,如果对于R是一个关系模式，F是R上的一个FD集。R分解成数据库模式 R1,，Rk，如果对R中满足F的每一个关系r，都有 r =R1(r) R2(r) Rk(r) 那么称分解相对于F是“无损分解”，损失称为“损失分解”。 Ri（r）表示关系r在模式Ri属性上的投影。,保持函数依赖的分解,设F是属性集U上的FD集Z是U的子集，F在Z上投影用Z（F）表示，定义为： Z（F）XY|XYF，XY Z 设 R1,，Rk是R的一个分解，F是R上的FD集，如果有 ，那么称分解保持函数依赖集F。,范式(Normal Forms) 规范化 一个关系满足某个范式所规定的一系列条件时,它就属于该范式 可以用规范化要求来设计数据库 也可以用来验证设计结果的合理性，用其指导优化过程 1NF2NF3NFBCNF4NF,第一范式(1NF) 当且仅当一个关系R中，每一个元组的每一个属性 只含有一个值时，该关系属于第一范式。 要求属性是原子的,一个关系的每一行的每个分量，即行和列的交叉处的取值必须是原子的，而不是多个独立的取值或多个值复合而成的一个取值，满足此条件的关系模式R属于1NF，记为R1NF。,满足1NF的关系称为规范化的关系，否则称为非规范化的关系。关系数据库研究的关系都是规范化的关系。 1NF是关系模式应具备的最起码的条件。 例如： 关系模式R（name,address,phone)，如果一个人有多个电话号码，那么在关系中就要出现多个元组，去存储这些电话号码。,插入异常 删除异常 数据冗余太大 修改复杂,满足1NF，但是存在下述问题：,第二范式(2NF) 对于关系R，若R1NF，且每一个非主属性完全 函数依赖于码，则R2NF。 不能部分依赖于码 sc(sno,sname,cno,grade) sno,cnograde snosname,完全依赖,非完全依赖,分解成2NF模式集的方法： 设关系模式R(WXYZ), 主码是WX，R上还存在FD XZ，则存在部分函数依赖（WX Z） 此时应把R分解成两个关系模式： R1（XZ），主码X； R2（WXY），主码WX，外码X 利用主码和外码可以连接R1和R2重新得到R 如果R1和R2还不是2NF，则重复上述过程，一直到数据库模式中每一个关系模式都是2NF。,例如：SC( Sno , Cno , Grade ) SL( Sno , Sdept , Sloc ),插入异常 删除异常 数据冗余太大 修改复杂,例：设关系模式 R(sno,cno,grade,tname,taddr) sno,cno为候选码 R上FD： （sno，cno）（tname，taddr） cno（tname，taddr） 存在局部函数依赖，非2NF, 分解成2NF,R1（cno，tname，taddr） R2(sno,cno,grade),插入异常 删除异常 数据冗余太大 修改复杂,SD( Sno , Sdept ) DL( Sdept , Sloc ),DL中可以插入无在校生的系信息 某系学生全部毕业，只删除SD中相应元组，DL中该系信息仍存在 系住处信息只在DL中存储一次 调整某系学生住处时，只修改DL中相应属性Sloc,第三范式(3NF) 对于关系R，若R2NF，且每个非主属性都不传 递依赖于码，则R3NF。 主属性可以传递依赖于码,定义4.8：关系模式R中，若不存在这样的码X，属性组 Y及非主属性Z（ Z Y）使得X Y， Y Z， Y X成立，则称R 3NF。,STJ ( S , T , J ) 某学生选定某门课，则确定了一个固定的教师,/学生，课程，教师,TJ /每位教师只上一门课 (S,J)T (S,T)T /每门课有若干位教师,插入异常 删除异常 数据冗余太大 修改复杂,分解成3NF模式集的方法： 设关系模式R(WXY), 主码是W，R上还存在FD XY，则存在传递函数依赖（W Y） 此时应把R分解成两个关系模式： R1（XY），主码X； R2（WX），主码W，外码X 利用主码和外码可以连接R1和R2重新得到R 如果R1和R2还不是3NF，则重复上述过程，一直到数据库模式中每一个关系模式都是3NF。,部分函数依赖和传递函数依赖是模式产生冗余和异常的两个重要原因。由于3NF模式中不存在非主属性对候选键的局部依赖和传递依赖，因此消除了很大一部分存储异常，具有较好的性能。 1NF、2NF，由于它们性能上的弱点，一般不宜作为数据库的模式，通常要变换成3NF或者更高级的范式，这种变换过程叫“关系的规范化处理”。,ST ( S , T ) , TJ ( T , J ),ST中可以存储尚未选修课程的学生，TJ中可以存储所有开课，但尚未有学生选课的教师 选修某课的学生全部毕业了，只删除ST关系中的相应元组，不会影响TJ关系中相应教师开设某门课程信息 每个教师开设课程信息只在TJ中存储一次 某教师开设的某门课程改名，只修改TJ中一个元组即可,例：设关系模式 R1(cno,tname,taddr) R上FD： tname taddr cnotname 存在传递函数依赖，非3NF, 分解成3NF,R11（cno，tname） R12(tname，taddr),插入异常 删除异常 数据冗余太大 修改复杂,Boyce/Codd范式(BCNF) 对于关系R，若R1NF，且所有非平凡的函数依赖， 其决定因素是候选码，则RBCNF。,定义4.9：关系模式R 1NF，若X Y且Y X时X必含有码， 则R BCNF。,性质： 所有非主属性都完全函数依赖于每个候选码 所有主属性都完全函数依赖于每个不包含它的候选码 没有任何属性完全函数依赖于非码的任何一组属性,Student( Sno , Sname , Ssex , Sage , Sdept ) Course (Cno , Cname , Cpno , Ccredit ) SC (Sno , Cno , Grade ),SJP( S , J , P ) ( S , J)P 每个学生每门课有一定名次 ( J , P)S 每门课，每个名次只有一个学生,分解成BCNF模式的方法： 设关系模式R的分解(初始R)，如果中有一个关系模式Ri相对于Ri（F）不是BCNF，根据定义1可知，Ri中存在一个非平凡FD XY，有X不包含超码。此时，把Ri分解成XY和RiY两个模式。重复上述过程，一直到中每一个模式都是BCNF。 上述方法能保正把R无损分解成，但不一定能保持FD。,定义1： 设F是关系模式R的FD集，如果对F中每个非平凡的FD XY，都有X是R的超码，则R是BCNF的模式。,例：设关系模式 R(Bno,Bname,Author)，属性表示书号和名、作者； 规定：每个书号只有一个书名，但不同书号可以有相同书名；每本书可以有多个作者合写，但每个作者参与编著的书名应该互不相同。 R上FD： （Author，Bname） Bno BnoBname 候选码： （Author，Bname）或（ Bno， Author） 所有属性都是主属性，R为3NF,由R上FD： （Author，Bname） Bno BnoBname 可知Bname传递依赖于候选码（Author，Bname）,R不是BCNF。 比如：一本书由多个作者编著，书名与书