数据库系统基础教程(第3章).ppt

1,第3章关系数据模型,2,本章介绍的内容,关系数据模型是什么？以二维表的形式排列数据的模型称之为关系数据模型。如何将E/R模型转变为关系数据模型？如何使关系模型满足一定规范形式(范式)?,3,3.1关系模型的基本概念,4,关系模型的基本概念,关系模型是以集合论中的关系来表示数据以及数据之间的联系的。关系relation是什么？由若干列和行组成的一个二维表，称为一个关系，即一个表table。表示数据结构和数据集合的一种简单方式。一个关系有一个名称。,5,属性,属性attribute是什么？一个关系中某一列的名称，描述一列数据的含义。如Movies中的length。一个属性有一个名称。一个关系中的多个属性不能重名。,6,模式,关系模式relationalschema是什么？一个关系的名称及其一组属性的集合，称为一个“关系模式”。表示为：关系名(属性1、属性2、属性n)例如：movies(title,year,length,filmtype)一个数据库包含一个或几个关系模式。一个关系数据库中所包含的关系模式的全体，称为一个“关系数据库模式”，或“数据库模式”。一个关系模式中的各属性排列有次序吗？没有。但为方便起见，一个关系通常设有一个“缺省次序”。,7,元组,一个元组tuple是什么？某个关系中除了属性标题之外的一行数据。一个关系中可能没有元组。一个元组(行)在每个属性(列)上有一个交叉，即一个分量(component)。如何表示一个元组？按照关系模式，用逗号分割每个分量。例如：(StarWars,1977,124,color)注意：不表示属性名称，按照关系模式的属性次序表示各分量。,8,元组,元组和对象之间有何对应关系？一个关系可粗略对应一个类。一个元组可粗略对应一个对象。一个元组的一个分量对应一个对象在某属性上的一个值。元组和对象之间有何区别？对象具有自身固有的标识(OID)；无需人为定义键。一个关系中的元组在关系中不能出现多次；而类中的一组对象的属性值可以相同。,9,域,域domain是什么概念？一个域是一种基本数据类型，如integer,char(n),datetime等。一个关系中每个属性都属于某个域，即某种基本数据类型。关系模型要求每个元组的每个分量必须具有原子性。原子性atomic是什么含义？没有内部结构，不能再分解的基本数据类型。,10,关系的等价表示法,一个关系为什么有多种等价表示？改变关系中属性的排列次序，即改变列次序，不改变关系的含义。注意，各分量对应各列。改变关系中元组的排列次序，即改变行次序，不改变关系的含义。,11,关系的实例,一个关系的模式和元组之间有何关系？关系模式相对静态；而关系中的元组是动态变化的。元组的增、删、改必须按关系模式进行。关系的实例是什么？一个关系的一组元组即为该关系的一个实例。关系的实例随时间变化，“当前实例”指的是在当前时刻，某关系中的元组。,12,3.2从E/R图到关系设计,13,实体集到关系的转换,建立与实体集相同名称的关系，且具有与实体集相同属性集。,Stars-in,Movies,Stars,Studios,title,length,year,filmType,name,address,name,address,Owns,14,实体集到关系的转换,Movies(title,year,length,filmtype)Stars(name,address)Studio(name,address),15,E/R图二元联系到关系的转换,根据二元联系的多重性分别处理：1.E1到E2的多对多联系R：R表示为一个关系，其属性是E1和E2的键属性，加上自身属性。例如：Movies和Stars之间的StarsIn(title,year,starName)例如：学生与课程间的选修关系：选修(学号，课号，成绩),16,E/R图二元联系到关系的转换,2.E1到E2的多对1联系R：R可表示为一个关系，但不是必须表示为关系。例如：Movies到Studios之间的Owns(title,year,studioName)在E1关系中增加E2的键属性，E2作为被参照关系。例如：Movies(title,year,length,filmType,studioName)例如：系与职工间的从属关系。职工(职工号，姓名，系号),17,E/R图二元联系到关系的转换,3.E1到E2的1对1联系R：R可表示为一个关系，但通常不表示为关系。而采用两种方法：在E1关系中增加E2关系的键，E2作为被参照关系。在E2关系中增加E1关系的键，E1作为被参照关系。1对1联系可能被合并为一个关系。例如：系与职工间的领导关系。可表示为：系(系号，系名，系主任职工号)或：职工(职工号，姓名，系号，领导系号),18,E/R图中的多元联系转换为关系,先将多元联系转换为二元联系，再按上述的方法转换为关系。,19,处理弱实体集,弱实体集E表示为一个关系，包含自身属性和F关系的键属性。关系R不再表示为一个关系。例如：职工与职工简历职工(职工号,姓名,性别,出生日期,)职工简历(职工号,时间,单位,任职)例如:Contracts(starName,studioName,titlt,year,salary,date),F,20,3.3子类结构到关系的转换,21,子类结构转换为关系的条件,有一个根实体集。有一个可唯一确定层次中每个实体集的键。包含属于这个层次中某些子树的实体集的分量，只要这个子树包含根。,22,子类结构转换为关系的策略,遵照E/R观点。为任一个在层次中的实体集创建一个关系，它包含根的键属性和实体集自身属性。把实体集看作属于单个类的对象。为每个包含根的子树创建一个关系，这个关系模式包括子树中所有实体集的所有属性。使用空值(NULLvalue)。创建一个包含层次中所有实体集属性的关系。每个实体由一个元组表示，对于实体不具有的属性，则设该元组的相应分量为空。,23,E/R方式转换,为每个实体集建立关系。,Movies,Cartoons,isa,Murder-Mysteries,isa,weapon,Voices,toStars,length,title,year,filmType,24,E/R方式转换,Movies(title,year,length,filmtype)MurderMysteries(title,year,weapon)Cartoons(title,year)Voices(title,year,starName),25,面向对象的方法,枚举层次中所有可能的子树。为每一个子树构造一个可以描述该子树中实体的关系。这个关系模式含有子树中所有实体集的所有属性。Movies(title,year,length,filmtype)MoviesC(title,year,length,filmtype)MoviesMM(title,year,length,filmtype,weapon)MoviesCMM(title,year,length,filmtype,weapon),26,使用空值组合关系,允许空值(NULL)作为元组值，就可以对一个实体集层次只创建一个关系。这个关系包含了层次中所有实体集的所有属性。Movies(title,year,length,filmtype,weapon),27,各种方法比较,由于涉及几个关系的查询代价高昂，所以人们宁愿在一个关系中寻找查询需要的所有属性。如果倾向于用尽量少的关系，可使用“空值”的方法，因它只有一个关系。如果倾向于减少空间和避免重复的信息。“面向对象”的方法对每个实体集只使用一个元组，且这个元组只含有对实体有意义的属性的分量，所以这种方法占用的空间最少。,28,3.4函数依赖,29,函数依赖的定义,所谓函数依赖就是用形式化方法研究一个关系中各属性之间的语义关系。定义若关系R的任意两个元组在属性A1、A2、An上一致(即有相同分量值)，则这两个元组在属性B上也一致，则称属性A1A2An函数决定B，或称B函数依赖于A1A2An。记为A1A2AnB,30,函数依赖的定义,31,例子,例如：学号姓名学号性别考虑：姓名性别？关系：学生(学号,姓名，性别)中为何学号姓名成立？如果两个元组具有相同学号，则两个元组指同一个学生，故具有相同姓名和性别。在一个关系中，不存在（键值）完全相同的元组。如果不存在两个元组具有相同学号，即每个元组各表示一个学生，则学号姓名成立。,32,推论,推论1：当且仅当A1A2AnB1A1A2AnB2A1A2AnBm则A1A2AnB1B2Bm推论2：AA,33,举例,关系Movies(title,year,length,filmType,studioName,starName)中，存在哪些函数依赖？titleyearlengthfilmTypestudioName考虑：titleyearstarName?,思考题：分析学生（学号，课号，成绩，系号，宿舍区）中的函数依赖。,34,怎样分析一个具体关系中的函数依赖,根据属性之间的语义关系分析函数依赖。应考虑所有可能的属性组合。尽可能使函数依赖式的左面最小化，而右面最大化。注意：函数依赖是针对关系模式，而不是针对特定实例，故只从关系实例不能确切断定函数依赖。,35,判断函数依赖的三种情形,如果任意两元组在属性A上一致，在B上也一致，则有AB成立。如果任意两元组在属性A上一致，在B上不一致，则AB不成立。如果任意两元组在属性A上不可能一致，则不管在B上是否一致，有AB成立。,36,函数依赖的定义,部分函数依赖：若XY，且存在X的真子集X，XY，则称Y对X部分函数依赖。完全函数依赖：若XY，且Y对X不是部分函数依赖，则称Y对X是完全函数依赖。传递函数依赖：若XY，YZ，且YX，则称Z对X是传递函数依赖。,37,关系的键,定义：对于关系R，若属性集合A1,A2,An满足下列条件，则该属性集合是R的一个键key:1A1,A2,An函数决定R中所有其他属性。(超键)2A1,A2,An的任何真子集都不能函数决定R中所有其他属性。(最小化),38,函数依赖定义的键与E/R模型的键定义一致性,函数依赖所定义的键与E/R模型所定义的键完全一致。函数依赖的定义是形式化的定义，而E/R模型键的定义是一种非形式化的语义说明。,39,例子,Movies关系的键是什么？title,year是键吗？为何title,year,starName是关系StarIn(title,year,starName)键？若有关系R(A,B,C)，已知AB在R上成立，则R的键是什么？,40,候选键与主键的关系,一个关系中的所有的键，都称之为候选键。一个关系可能有多个键，但只选择其中之一作为主键。,41,超键,定义包含键的属性集就称为超键(superkey)，它是“键的超集”的简写。每个键都是超键吗？是。关系模式StarIn(title,year,starName)的属性集title,year,starName是超键吗？一个关系的属性全集是超键吗？是。每个超键都是键吗？不是。,42,从E/R图中发掘键,一个关系模式中键的表示：每个关系只描述主键。下划线表示。E/R模型实体集的关系的键的确定来自实体集的关系的键码就是相应实体集的键属性。如Movies(title,year,length,filmType),43,从E/R图中发掘键,来自E/R模型二元联系的关系R的键的确定根据多重性分三种情况：多对多：相联系的两个实体集的键属性共同构成R的键。多对1：E1E2,E1的键属性作为R的键。通常该关系可合并到E1关系中。1对1：任意一端实体集的键都可作为R的键，但通常该关系可合并到E1或E2关系中。,44,例子,StarsIn(title,year,starName)Owns(title,year,studioName)，但我们通常关系Owns的属性studioName合并到movies关系中：Movies(title,year,length,filmType,studioName)再如销售业务系统的例子。(见第1章最后给出的综合应用题),45,3.5函数依赖规则,46,函数依赖规则,什么是函数依赖规则？在一个给定关系上，已知一组函数依赖作为前提条件。根据一组函数依赖规则，推断另一些函数依赖。为何需要它？这种计算和验证可有效减少冗余，得到良好的关系设计。,47,例子,已知R(A,B,C)，及AB，BC，可证AC。证明：设(a,b1,c1)和(a,b2,c2)是R的元组由AB可知b1=b2记作b又由BC可知c1=c2从而AC,48,有哪些重要的函数依赖规则,分解合并(Splitting/combining)规则平凡依赖(TrivialDependance)规则传递(Transitivy)规则Armstrong公理,49,两个函数依赖集合之间有何关系,设T是关系R上的函数依赖集，若对R的所有实例，函数依赖XY都成立，则称T“逻辑蕴含”XY。(XY可由T推导出来)设S是关系R上的另一函数依赖集，若对R的所有实例，S中的所有函数依赖均成立，则称函数依赖集S“蕴含于”函数依赖集T。(S可由T推导出来)若函数依赖集S“蕴含于”T，同时T“蕴含于”S，则函数依赖集S“等价于”函数依赖集T。,50,蕴含和等价关系有何用处,可用等价的更简单的函数依赖集代替复杂的函数依赖集。可在一个函数依赖集S中增加蕴含其中的其它函数依赖。可判断一个函数依赖是否蕴含于已知的函数依赖集。,51,分解/合并规则(Splitting/CombiningRule),A1A2AnB1B2Bm等价于A1A2AnB1A1A2AnB2A1A2AnBm,52,分解/合并规则(Splitting/CombiningRule),例如：关系Movies中，titleyearlengthfilmTypestudioName等价于：titleyearlengthtitleyearfilmTypetitleyearstudioName注意：函数依赖的左面不能分解合并。例如：学号课号成绩,53,平凡依赖(TrivialDependance),对于函数依赖A1A2AnB，若B是A中的某一个属性，则该函数依赖是“平凡的”。平凡依赖是恒真式。,54,平凡依赖的一般定义,对于函数依赖A1A2AnB1B2Bm若B是A的子集，则该依赖是“平凡的”；若B中至少有一个属性不在A中，则该依赖是“非平凡的”；若B中没有一个属性在A中，则该依赖是“完全非平凡的”。例如：titleyearyearlength是非平凡的；titleyearlength是完全非平凡的。,55,平凡依赖规则,如果函数依赖式右边的属性中有一些出现在左面，那么可以将右边重复出现的属性删除。即：函数依赖A1A2AnB1B2Bm等价于A1A2AnC1C2Ck，其中：C是B中不在A中出现的属性。,56,平凡依赖规则,如果t和u在属性A上一致则它们必然在B上一致，所以在C上也一致。,A,C,B,u,t,57,计算属性的闭包,已知S是关系R上的函数依赖集，则属性集A1,A2,An可函数决定的最大属性集合是什么？这个集合被称做什么?如何计算这个集合？这种计算有何用途？,58,属性的闭包,设S是关系R上的函数依赖集，A=A1,A2,An是R上的属性集，属性A在函数依赖集S下的闭包(closure)是这样一个属性集B，使对关系R的所有实例，函数依赖：A1A2AnB均成立。即A1A2AnB“蕴含于”函数依赖集S。属性集A1,A2,An的闭包表示为A1,A2,An+。A1,A2,An包含于A1,A2,An+若A1A2AnX，则XB,59,如何计算属性的闭包,给定函数依赖集S和属性集A=A1,A2,An，如何计算A+？1将X初始化为A1,A2,An，闭包最小集合。2遍历S中的每个函数依赖，对于每个依赖式：B1B2BmC如果B1、B2、Bm都在X中，而C不在X中，则把C加入X中。3重复第2步，直到遍历完S中所有函数依赖，而没有新属性能加入到X中。4最终属性集X即为属性集A在函数依赖集S下的闭包A+。,60,例子,设有关系R(A,B,C,D,E,F)与函数依赖集S：ABC，BCAD，DE，CFB求：A,B+解：X(1)=A,B,由ABC，得：X(2)=A,B,C,由BCAD，得：X(3)=A,B,C,D,由DE，得：X(4)=A,B,C,D,E=A,B+,61,属性闭包计算的用途,假设关系R上已有一个依赖集S，另有一个函数依赖A1A2AnB，该依赖是否蕴含于S？判断方法：计算A1,A2,An+。若B在A1,A2,An+中，则函数依赖A1A2AnB蕴含于S中。若B不在A1,A2,An+中，则函数依赖A1A2AnB不蕴含于S中。,62,属性闭包计算的用途,一般性结论：若关系R有函数依赖集S，当且仅当所有B1B2Bm都在A1,A2,An+中，则A1A2AnB1B2Bm蕴含于S中。思考题：上例关系R中，ABD和DA是否蕴含于函数依赖集S中？,63,为什么闭包算法给出正确的函数依赖,用归纳法证明基础最基础的情况是没有进行任何计算。于是D必定是A1,A2,An中一员，则A1A2AnD是平凡函数依赖。因此，R满足A1A2AnD。归纳假设当使用函数依赖B1B2BmD时已把D加入到X。则由归纳法假设可知R满足A1A2AnBi(i=1,m)。换言之，R的任何两个元组在A1,A2,An上的取值相等时，它们在B1,B2,Bm上的取值也相等。由于R满足B1B2BmD，还可以得出这两个元组在D上取值也相等。因此，R满足A1A2AnD。,64,为什么闭包算法可找到所有得函数依赖,实际上我们要证明至少有一个满足S中所有函数依赖集合，但不满足A1A2AnB的关系实例存在。构造实例：,65,属性的闭包与键之间关系,对于一个关系R，当且仅当A1,A2,An是R的超键时，A1,A2,An+是R的所有属性的集合。,66,例子,已知关系模式R(A,B,C,D)有函数依赖ABC,CD,DA(a)求蕴含于给定函数依赖的所有完全非平凡函数依赖。(b)求R的所有键。(c)求R的所有超键(不包括键)。,67,例子,解：(a)根据所有属性集合的闭包，计算所有可能的函数依赖。A+=AB+=BC+=C,D,ACADD+=D,AA,B+=A,B,C,DABCDA,C+=A,C,DACDA,D+=A,D,68,例子,B,C+=B,C,D,ABCADB,D+=B,D,A,CBDACC,D+=C,D,ACDAA,B,C+=A,B,C,DABCDA,B,D+=A,B,D,CABDCA,C,D+=A,C,DB,C,D+=B,C,D,ABCDA,69,例子,(b)所有的键：A,B,B,C,B,D(c)所有的超键(不包括键)：A,B,C,A,B,D,B,C,D,A,B,C,D,70,传递规则,把两个函数依赖级联起来。具体来说：若A1A2AnB1B2Bm和B1B2BmC1C2Ck成立，则A1A2AnC1C2Ck成立(蕴含于前两个依赖中)。传递规则的证明计算A1,A2,An的闭包，应包含B1B2Bm，再包含C1C2Ck。,71,例子,关系MovieStudio(title,year,legth,filmType,studioName,studioAddr)title,yearstudioNamestudioNamestudioAddr则title,yearstudioAddr,72,函数依赖的闭包,对于给定的关系模式R和函数依赖集F，所有能由F导出的函数依赖的全体称作F的闭包，记作F+。通常我们更需要选择一个依赖集来表示所有依赖。对于一个关系，任何一个能导出所有依赖的依赖集，称为该关系的一个“基”base。对于同一个关系，可能有多个“基”。如果一个基的任何真子集都不能导出该关系的所有依赖集，则称该基为“最小”基。对于同一个关系，可能有多个“最小”基。,73,例子,已知关系R(A,B,C)及函数依赖集F:AB,AC,BA,BC,CA,CB最小基有：AB,BA,BC,CBAB,BC,CA等,74,最小函数依赖集,定义设F是属性集U上的函数依赖集，如果Fmin是F的一个最小依赖集，那么Fmin应满足下列四个条件：Fmin+=F+；每个函数依赖的右边都是单属性；Fmin中没有冗余的函数依赖(即在F中不存在这样的函数依赖XY，使得F与F-|XY|等价)；每个函数依赖的左边没有冗余的属性(即F中不存在这样的函数依赖XY，X有真子集W使得F-|XY|WY|与F等价)；,75,求最小函数依赖集算法,根据分解规则，可得到一个与F等价的函数依赖集G，G中每个函数依赖的右边均为单属性。在G中的每个函数依赖中消除左边冗余的属性。在G中消除冗余的函数依赖。,76,例子,关系模式R(A,B,C,D,E,G)有函数依赖BGC,BDE,DGC,DAGCB,AGB,BD求此模型的最小函数依赖集。求出关系模式的候选键。解Fmin=BE,DGC,AGB,BD所有的键：A,G,77,函数依赖的投影,什么是投影？设R是一个含有函数依赖集合的关系，取关系R中部分指定的属性集，称之为“投影”。设有关系模式R(U)及函数依赖集F，若将R分解为S(U1)及T(U2)，则S上存在那些函数依赖？从函数依赖集推断而来。只包含S的属性。,78,函数依赖投影的算法,算法：对于S的属性集U中的每个属性子集X，计算X+，于是对于满足下列条件的每个属性B，函数XB在S中成立：B是S的一个属性，B属于X+，而且B不属于X。,79,例子,已知关系R(A,B,C,D)及函数依赖集F:AB,BC,CD假设关系R投影到S(A,C,D)。A+=A,B,C,DC+=C,D从而可得到关系S的函数依赖F:AC,CD,80,Armstrong公理,1自反律(Reflexivity)。若B1,B2,BmA1,A2,An，则A1A2AnB1B2Bm。(平凡)2增长律(Augmentation)。若A1A2AnB1B2Bm，则对于任意属性集C1,C2,Ck，有A1A2AnC1C2CkB1B2BmC1C2Ck3传递律(Transitivity)。若A1A2AnB1B2Bm和B1B2BmC1C2Ck成立，则A1A2AnC1C2Ck。,81,3.6关系数据库模式设计,82,关系模式设计中为何出现冗余,关系模式设计中可能出现各种冗余，即同一事实在多个元组中重复。造成冗余的原因通常是将同一个对象的单值和多值特征混合在同一个关系中。,83,异常,“异常”指什么？异常anomaly，即不符合规范，在操作数据库时，影响数据一致性。关系设计中主要有哪些异常？冗余。同一信息在多个元组中不必要的重复。浪费空间，增加更新操作的复杂度，影响数据一致性。修改异常。当修改了某个元组中的信息，而重复的信息可能未修改而破坏一致性。插入数据时，某些有用信息暂时无法插入。删除异常。当删除某个元组时，可能删除其它信息；若需删除某个对象时，必须删除多个元组而不是一个元组。否则，破坏数据一致性。,84,如何解决冗余问题,按如下步骤解决冗余问题：分析关系模式设计缺陷可能导致的问题。引入“关系分解”，把一个关系模式(属性集)分解为更小的模式。介绍“Boyce-Codd范式”(Boyce-CoddNormalForm,即BCNF)，给出关系模式所应满足的条件。如何通过分解关系模式保证满足BCNF。放宽BCNF条件，引入“3NF”。简单介绍1NF和2NF。,85,关系分解,什么是关系分解？给定一个关系RA1,A2,An，将R分解为两个关系SB1,B2,Bm和TC1,C2,Ck，使得1A1,A2,An=B1,B2,BmC1,C2,Ck2S中的元组是R的所有元组在B1,B2,Bm上的投影；T中的元组是R的所有元组在C1,C2,Ck上的投影。为何要进行关系分解？为了避免异常，用几个关系代替原有的关系，且保持数据一致性。,86,例子,将关系模式Movies(title,year,length,filmtype,studioname,starname)分解为:Movies1(title,year,length,filmtype,studioname)Movies2(title,year,starname),87,例子,88,例子,将关系模式学生(学号,课号,成绩,系号,系主任)分解。,89,例子,学生(学号,系号,系主任),选修(学号,课号,成绩),分解后的关系无异常。这些关系可连接(join)得到原有的关系元组，且不改变原有语义。,90,问题,对于一个给定的关系模式，如何判断是否存在异常？如何进行关系模式的分解？,91,什么是范式(NormalForm),关系模式所满足的不同程度的要求(规范形式)称之为范式。若关系模式R的每个分量均是不可再分的数据项，则R满足第一范式，又记作：R1NF。在第一范式的基础上，逐步加强条件，分别有2NF,3NF,BCNF,4NF,5NF。一个较低级别的关系模式，可通过分解的方式，转换成若干个较高级别的关系模式，这种过程叫做关系规范化。,92,BC范式(BCNF,Boyce-CoddNormalForm),为何引入BC范式？BC范式是常用判断条件，满足该条件就能避免函数依赖引起的异常。BC范式如何定义？关系模式R满足BC范式，当且仅当若非平凡函数依赖A1A2AnB1B2Bm在关系R中成立，则A1,A2,An是R的超键。,93,关系R满足BC范式的两种情形,关系R中不存在非平凡函数依赖。(只有平凡函数依赖)每个非平凡函数依赖的左面包含某个键(即左面是超键)。,94,关系R违背BC范式的唯一情形,关系R中至少存在一个非平凡函数依赖，其左面不是超键。,95,例子,学生(学号,课号,成绩,系号,系主任)是否满足BC范式？键：学号,课号非平凡函数依赖：学号系号,系主任成立而左面不是超键。分解后的选修(学号,课号,成绩)和学生(学号,系号,系主任)是否满足BC范式？,96,判断BC范式的方法,找出所有的Key。检查所有非平凡函数依赖。左面是否超键？,97,仅有两个属性的关系必是BC范式,R(A,B)可分四种情况讨论：1没有非平凡函数依赖。2AB成立，而BA不成立。A是唯一键，函数依赖式左面是键。3BA成立，而AB不成立。B是唯一键，函数依赖式左面是键。4AB成立，且BA成立，关系R有两个键：A和B，每个函数依赖式左面是键。注意：一个关系可能有多个键，而BC范式要求依赖式左面包含某个键，而不是所有键。,98,分解为BC范式,分解关系有何条件？把一个关系模式分解成一个由若干个关系模式构成的集合，且这些关系模式应满足如下条件：1每个关系模式都满足BCNF。2分解后的元组能如实反映原有关系中的数据，即能从分解后的关系中准确重构原有关系。思考题：能否将所有关系分解为单目关系？,99,分解策略：消除违背BCNF的函数依赖,1找一个违背BCNF的非平凡函数依赖A1A2AnB1B2Bm。2把关系R分解成两个关系：R1(A1,A2,An,B1,B2,Bm)。R2(A1,A2,An,所有其它属性)，若不满足BC范式，则再分解。,100,例子,R(学号,课号,成绩,系号,系主任)不满足BCNF。1非平凡函数依赖：学号系号,系主任成立2R分解为：R1(学号,系号,系主任)R2(学号,课号,成绩)分解消除了部分属性对键的部分依赖。3非平凡函数依赖：系号系主任成立4R1继续分解为：R11(系号,系主任)R12(学号,系号)分解消除了部分属性对键的传递依赖。,101,从分解中恢复信息,t,u,x,w,v,投影,连接,连接,投影,102,分解若非基于函数依赖，则可能无法恢复成原关系,设R为：,分解为：R1(A,B),R2(B,C),连接R1,R2:,103,存在某些关系尽管不符合BCNF，但不能再分解,关系Booking(movie,theater,city)表示电影的预定。其中一个元组(m,t,c)表示预定在城市c的影院t放映影片m。条件：一座城市有多个影院；每个影院对应唯一的城市。每个影院可放映多部影片；每部影片可在多个影院放映。同一个城市的两个影院不会预定同一部影片。故有函数依赖：theatercitymoviecitytheater有两个键:movie,city和movie,theater非平凡函数依赖：theatercity违背BCNF。,104,存在某些关系尽管不符合BCNF，但不能再分解,能分解为theater,city和theater,movie而保持原有函数依赖吗？假设这两个关系的元组如下：,把两个关系连接起来，恢复为原有关系。,函数依赖moviecitytheater不成立，违背原有的语义。关系Booking(movie,theater,city)如果为了满足BC范式而分解的话，就不能保持原有的函数依赖。,105,第三范式,定义关系模式R满足3NF，当且仅当若非平凡函数依赖A1A2AnB在关系R中成立，则A1,A2,An是R的超键，或者B是某个键的组成部份（键属性）。根据定义，关系Booking(movie,theater,city)满足3NF。,106,分解为第三范式的算法,对于关系模式R和R上的函数依赖集F，先求出F的最小依赖集，然后再把最小依赖集中那些左部相同的函数依赖用合并规则合并起来；对最小依赖集中的每个函数依赖XY去构成一个模式XY；在构成的模式集中，如果每个模式都不包含R的候选键，那么把候选键作为一个模式放入模式集中。这样得到的模式集是关系模式R的一个分解，并且这个分解既是无损分解，又能保持函数依赖。,107,第三范式结论,一个关系模式总可以分解为满足3NF的模式，且所有的函数依赖都可得到保持。,108,第一范式和第二范式,第一范式(1NF)的条件是什么？每个元组的每个分量都是原子的(atomic)。第二范式(2NF)的条件是什么？在1NF的基础上，要求每个非键属性依赖于键的整体(直接或间接)，而不是键的部分属性，即不允许有非平凡函数依赖的右面是非键属性，而左面是某个键的真子集。,109,满足2NF的几种情形,不存在非平凡函数依赖。存在非平凡函数依赖，且其右面是某个键的组成部分(键属性)。存在非平凡函数依赖，且其右面是非键属性，则其左面要么是超键，要么包含非键属性。,110,例子,1学生(学号,课号,成绩,系号,宿舍区)满足的最高范式是什么？仅满足1NF。为何不满足2NF？2Movies(title,year,length,filmType,studioName,starName)满足的最高范式是什么？仅满足1NF。为何不满足2NF？3MovieStudio(title,year,length,filmType,studioName,studioAddr)满足的最高范式是什么？仅满足2NF。为何不满足3NF？,111,范式等级,满足范式条件：BCNF3NF2NF1NF给定一个关系，函数依赖决定它是否满足BCNF/3NF/2NF范式。问题：关系分解是逐步提高范式等级的吗？,112,例子,关系模式R(A,B,C,D)有函数依赖ABC,CD,DA找出所有违背BCNF的函数依赖。必要时，分解为几个满足BCNF的关系找出所有违背3NF的函数依赖。解：所有的键：A,B,B,C,B,D违背BCNF的函数依赖：CAD,DA分解：R1(A,C,D),R2(B,C)R11(A,D),R12(C,D)函数依赖ABC不保持R满足3NF,113,例子,关系模式R(A,B,C,D,E,G)有函数依赖BGC,BDE,DGC,DAGCB,AGB,BD求此模型的最小函数依赖集。求出关系模式的候选键。此关系模型最高属于哪级范式。将此模型按照模式分解的要求分解为3NF。解Fmin=BE,DGC,AGB,BD所有的键：A,G2NFR1:A,B,GF1=AGBR2:C,D,GF2=DGCR3:B,D,EF3=BDE,114,3.7多值依赖,115,多值依赖,多值依赖是如何产生的？反映两个属性或属性集互相独立的特征；属性独立性可能导致严重冗余；这种特征不能用函数依赖表示。与函数依赖有什么关系？多值依赖是函数依赖的一般化；函数依赖是多值依赖的特例；每个函数依赖都隐含一个相应的多值依赖。,116,本节要解决的问题和方法是什么,属性独立性引发的冗余如何定义多值依赖多值依赖有何规则第四范式是什么如何分解关系使之满足4NF总结关系模式的范式。,117,属性的独立性及其带来的冗余,如果一个关系中包含了两个多值属性或联系，会导致明显的冗余，但却可能符合BCNF。如：关系Star(name,street,city,title,year)表示影星的多个住址及其主演的多部影片。,6个元组表示1位影星的2个住址和3部影片。元组数目n住址m影片冗余是明显的。但不存在非平凡函数依赖(全属性集作为键)，故满足BCNF。这是多值依赖引起的冗余，故不能靠函数依赖解决冗余问题。,118,属性独立性是什么,同一个关系中的两个不交叉的属性集相互没有关联，都表示多值特征，造成两者属性值自由组合。导致严重冗余。,119,多值依赖的定义,定义：若关系R(A,B,Z)中的元组在属性A上取某一特定值，则其在属性B上的值（集）与R中不属于A和B的其它属性Z无关，这种条件即为多值依赖。记作：AB,120,多值依赖的说明,1当A上的值确定后，B上的值集亦随之确定。(多值)2对于每一个(a,z)，均有相同的B集。(与Z无关)从而：在关系R(A,B,Z)中，若存在两个元组t和u在属性A上取值一致，则必可找到一个元组v，满足：1v与t、u在A上取值一致；2v与t在B上取值一致，且3v与u在Z上取值一致。则多值依赖AB成立。,121,多值依赖的说明,注：若t和u相互交换，则存在第四个元组w，与u在B上一致，与t在Z上一致。注：若v与u重合为一个元组，则特化为函数依赖。所以函数依赖是多值依赖的一种特例。,A,B,Z,t,v,u,122,例子,故：有多值依赖namestreetcity成立同时nametitleyear成立,t,w,v,u,A,B,Z,123,判断多值依赖的几种情形(不完全),若限定在属性A上的取值，则B上的取值与其它属性值可自由组合，那么AB成立。若限定在属性A上的取值，则B上取值不能与其它属性值自由组合，那么AB不成立。若AB，则AB成立。若A和B并集构成R属性全集(没有其它属性)，则AB成立。,124,例子,以下关系中系班级是否成立？,125,多值依赖规则,平凡依赖规则若多值依赖AB在关系R上成立，则AC成立，其中C是B属性加上A的一个或几个属性；同时AD成立，其中D是B属性中不属于A的属性。传递规则若多值依赖AB和BC在关系R上成立，则AC也成立。注意：多值依赖没有分解合并规则。例如：namestreetcity成