第六章 关系数据理论-new

第六章关系数据理论问题的提出规范化数据依赖的公理系统关系模式的分解本章主要内容本章讨论的核心问题如何判断一个关系模式是否存在问题如何构造一个好的数据库模式6.1问题的提出一个关系模式应当是一个五元组。R(U,D,DOM,F)这里：(1)关系名R，它是符号化的元组语义；(2)一组属性U;(3)属性组U中属性所来自的域D;(4)属性到域的映射DOM;(5)属性组U上的一组数据依赖F。由于(3),(4)对模式设计关系不大，因此在本章中把关系模式看作是一个三元组：R<U,F>6.1问题的提出数据依赖是一个关系内部属性与属性之间的一种约束关系。这种约束关系是通过属性间值的相等与否体现出来的数据间相关联系。它是现实世界属性间相互联系的抽象，是数据内在的性质，是语义的体现。例子:描述学校教务的数据库，该数据库涉及的对象包括学生的学号(Sno)、所在系(Sdept)、系主任名(Mname)、课程号(Cno)和成绩(Grade)。假设用一个单一的关系模式Student来表示，则该关系模式的属性集合为U={Sno,Sdept,Mname,Cno,Grade}其中:一个系有若干学生,但一个学生只属于一个系一个系只有一名(正职)负责人一个学生可以选修多门课程,每门课可有若干学生选修每个学生学习每一门课程有一个成绩于是得到属性组U上的一组函数依赖FF={Sno→Sdept,Sdept→Mname,(Sno,Cno)→Grade}6.1问题的提出6.1问题的提出某一时刻关系模式Student的一个实例，即数据表。S1CS李洪C190S2CS李洪C1 90S3CS李洪C190S4CS李洪C190S5MA张力C190S5MA张力C190存在的问题冗余太大：每一个系的系主任姓名重复出现，重复次数与该系所有学生的所有课程成绩出现次数相同，这将浪费大量存储空间。删除异常:删除某系学生的选课将删除系信息插入异常:系刚成立,无学生，就无法把这个系及其系主任的信息存入数据库。更新异常：某系更换系主任后，必须修改与该系学生有关的每一个元组。6.1问题的提出结论:关系模式Student(Sno,Sdept,Mname,Cno,Grade)不是好的关系模式,好的关系模式不会发生插入异常、删除异常并且冗余尽可能少。 为什么会发生这些问题？这是因为这个模式中的函数依赖存在某些不好的性质。假如把这个单一的模式改造一下，分成3个关系模式：S(Sno,Sdept,Sno→Sdept)SC(Sno,Cno,Grade,(Sno,Cno)→Grade)DEPT(Sdept,Mname,Sdept→Mname)这3个模式都不会发生插入异常、删除异常的毛病，数据的冗余也得到了控制。一个模式的数据依赖会有哪些不好的性质，如何改造一个不好的模式，这就是下一节规范化理论讨论的内容。6.2规范化根据属性间依赖情况来判定关系是否具有某些不合适的性质。通常按属性间依赖情况来区分关系规范化的程度分为第一范式、第二范式、第三范式和第四范式等。6.2规范化定义6.1函数依赖:设R<U>是属性集U上的关系模式,X,Y是U的子集,若对于R<U>的任意一个可能的关系r,r中不可能存在两个元组在X上的属性值相等,而在Y上的属性值不等,则称“X函数确定Y”或“Y函数依赖于X”,记作XY。函数依赖和别的数据依赖一样是语义范畴的概念。函数依赖不是指关系模式R的某个或某些关系满足的约束条件，而是指R的一切关系均要满足的约束条件。

6.2规范化一些记号和术语:若XY,但YX则称X→Y是非平凡的函数依赖。若XY,但ＹＸ则称Ｘ→Ｙ是平凡的函数依赖。对于任一关系模式，平凡函数依赖都是必然成立的，它不反应新的语义。若不特别声明，总是讨论非平凡的函数依赖。若X→Y，则X称为这个函数依赖的决定属性组，也称为决定因素。若X→Y，Y→X，则记作X←→Y。若Y不函数依赖于X，则记作XY6.2规范化定义6.2完全函数依赖:在R<U>中,如果XY,并且对于X的任何真子集X’

,都有X’Y,则称Y对X完全函数依赖,记作XY部分函数依赖:如果XY,但Y不完全函数依赖于X,则称Y对X部分函数依赖,记作XY定义6.3函数传递依赖:在R<U>中,如果XY,(YX),

YX,YZ,则称Z对X传递函数依赖。记为X→Z。fp传递6.2规范化6.2.2码定义6.4候选码:设K为R<U,F>中的属性或属性组,若KU,则K为R的候选码。若候选码多于一个，则选定其中的一个为主码。包含在任何一个候选码中的属性，称为主属性。不包含在任何码中的属性称为非主属性或非码属性。最简单的情况，单个属性是码。最极端的情况，整个属性组是码，称为全码。定义6.5关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码，也称外码。f6.2规范化6.2.3范式关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式。满足最低要求的叫第一范式，简称1NF。在第一范式中满足进一步要求的为第二范式，其余依次类推。范式就是符合某一种级别的关系模式的集合，则R为第几范式就可以写成R∈xNF。对于各种范式之间的联系有1NF2NF3NFBCNF4NF5NF一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫规范化。一范式(1NF)：如果一个关系中的所有属性值均是原子的，则称该关系满足1NF。关系模型中的关系必须满足1NF6.2规范化定义6.6二范式(2NF):若R1NF,且每一个非主属性完全函数依赖于码,则称R2NF例子:关系模式S-L-G(S#,SD,SL,C#,G),其中一个系的学生只住一个地方SL,码为(S#,C#),函数依赖有:(S#,C#)G因为S#SD,所以(S#,C#)SD因为S#SL,所以(S#,C#)SLS-L-G2NF

fpp6.2规范化问题:关系模式S-L-G(S#,SD,SL,C#,G)不属于2NF,将出现插入异常:如果学生95001没选课,不能插入删除异常:如果一个学生只选修了一门课,如删除这门课，会导致数据库中没有该学生的其他信息，如S#,SD,SL。修改复杂:学生转系,不仅修改所在系,还修改住处6.2规范化规范化:解决办法是用投影分解所以关系模式S-L-C被分解为S-C(S#,C#,G)S-L(S#,SD,SL)定义6.7三范式(3NF):关系模式R<U,F>中若不存在这样的码X,属性组Y以及非主属性组Z(ZY),使得XY，YZ和YX成立，则称R<U,F>3NF 如果关系模式R<U,F>2NF，且每一个非主属性不传递依赖于任一候选关键字，则称R<U,F>3NF可以证明如果R<U,F>3NF,则每一个非主属性既不部分依赖于码,也不传递依赖于码6.2规范化例子:关系模式S-L(S#,SD,SL)中有S#SD,SDS#,SDSL则S#SL所以S-L3NF问题:关系模式S-L不属于3NF,将出现插入异常:一个系刚成立,无学生删除异常:某个系的学生全毕业了修改复杂:学生转系,不仅修改SD,也要修改SL规范化:解决方法是投影分解,将S-L分解为不好:S-D(S#,SD)好:S-D(S#,SD)S-L(S#,SL)D-L(SD,SL)传递?6.2规范化关系模式S-L-G(S#,SD,SL,C#,G)分解为S-G(S#,C#,G)S-D(S#,SD)

D-L(SD,SL)BCNF(BoyceCoddNormalForm):关系模式R<U,F>1NF,若XY且YX时,X必含有码,则RBCNF6.2规范化讨论RBCNF,则R3NF若R3NF,则R未必属于BCNF例如:关系模式STJ(S,T,J),其中每位教师只教授一门课,每门课由若干教师担任,某一学生S选定一门课J,就对应一位固定的教师T,因此对应函数依赖可表示TJ

(S,J)T(S,T)J,候选码为(S,J)和(S,T)结论:STJ3NF,但STJBCNF6.3数据依赖的公理系统数据依赖的公理系统是模式分解算法的理论基础Armstrong公理系统:函数依赖的一个有效而完备的公理系统定义6.11逻辑蕴含:对于满足一组函数依赖F的关系模式R<U,F>,其中任何一个关系r,若函数依赖XY都成立(即r中任意两元组t,s，若t[X]=s[X],则t[Y]=s[Y]),则称F逻辑蕴含XY一套推理规则(Armstrong公理系统):可以求得给定关系模式的码,可以从一组函数依赖求得蕴含的函数依赖，例如已知函数依赖集F，要问X→Y是否为F所蕴含。6.3数据依赖的公理系统Armstrong公理系统:设U为属性集总体,F是U上的一组函数依赖,于是有关系模式R<U,F>,对R<U,F>来说有以下的推理规则：A1自反律:若YXU,则XY为F所蕴含A2增广律:若XY为F所蕴含,且ZU,则XZYZ为F所蕴含A3传递律:若XY及YZ为F所蕴含,则XZ为F所蕴含定理6.1Amstrong推理规则是正确的。6.3数据依赖的公理系统证明1:设YXU对R<U,F>的任一关系r中的任意两个元组t,s若t[X]=s[X],由YX可得t[Y]=s[Y]所以XY成立证明2:设XY为F所蕴含,且ZU对R<U,F>的任一关系r中的任意两个元组t,s若t[XZ]=s[XZ],则有t[X]=s[X]和t[Z]=s[Z]又XY成立,则有t[Y]=s[Y]所以t[YZ]=s[YZ],所以XZYZ为F所蕴含6.3数据依赖的公理系统证明3:设XY及YZ为F所蕴含对R<U,F>的任一关系r中的任意两个元组t,s若t[X]=s[X],由XY可得t[Y]=s[Y]又YZ成立,则有t[Z]=s[Z]所以XZ为F所蕴含根据上述推理规则得到另外的推理规则1合并规则:若XY，XZ,则有XYZ2伪传递规则:若XY，WYZ,则有XWZ3分解规则:若XY及ZY,则有XZ6.3数据依赖的公理系统引理6.1:XA1A2...

Ak成立的充分必要条件是X

Ai成立(由合并规则和分解规则可以证明)定义6.12:F的闭包在关系模式R<U,F>中为F所逻辑蕴含的函数依赖的全体,记作F+Armstrong公理系统是有效的、完备的有效的:指由F出发,根据Armstrong公理导出的每个函数依赖一定在F+中完备的:指F+中的每个函数依赖必定可由F出发,根据Armstrong公理推导出来6.3数据依赖的公理系统证明完备性，要解决如何判定一个函数依赖是否属于由F根据Armstrong公理推导出来的函数依赖的集合。理论上是可以求得F+的,如果有F+,判断XY是否属于F+是非常容易的,但实际上由F求F+有时几乎是不可能做到的,例如从F={XA1,XA2,…,XAn}出发至少可以推导出2n个不同的函数依赖。为此引入了下面的概念：定义6.13:设F为属性集U上的一组函数依赖,XU,XF+={A|XA能由F根据Armstrong公理导出},XF+称为属性集X关于函数依赖集F的闭包引理6.2:设F为属性集U上的一组函数依赖,X,YU,XY能由F根据Armstrong公理导出的充分必要条件是YXF+6.3数据依赖的公理系统判断XY是否能由F根据Armstrong公里推导出来的问题,转化为求XF+,判断Y是否为XF+的子集问题。这个问题由算法6.1解决。算法6.1求XF+算法(输入X,F,输出XF+)(1)令X(0)=X,i=0(2)求B,B={A|(v)(w)(vwFvX(i)Aw)}(3)X(i+1)=BX(i)(4)判断X(i+1)=X(i)?(5)若相等或X(i)=U,XF+=X(i),结束(6)若不等,i=i+1,返回(2)找到左部为X子集的函数依赖6.3数据依赖的公理系统例子:已知关系模式R<U,F>,U={A,B,C,D,E},F={ABC,BD,CE,ECB,ACB}求(AB)F+(1)X(0)=AB,i=0(2)求B,B={CD}(3)X(1)=BX(0)={ABCD}(4)因为X(1)X(0),所以再找出左部为ABCD子集的那些函数依赖(5)B={CDBE}(6)X(2)=BX(1)={ABCDE}(AB)F+={ABCDE}找到左部为X子集的函数依赖6.3数据依赖的公理系统定理6.2Amstrong公理系统是有效的、完备的。Amstrong公理的完备性及有效性说明了“导出”与“蕴含”是两个完全等价的概念。于是F+也可以说成是由F出发借助Armstrong公理导出的函数依赖的集合。从蕴含(或导出)的概念出发，又引出了两个函数依赖等价和最小依赖集的概念。6.3数据依赖的公理系统定义6.14

如果G+=F+,就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。引理6.3:F+=G+的充分必要条件是FG+和GF+证:必要性F+=G+F+G+G+F+

所以F

G+G

F+充分性F

G+则F+(G+)+,但(G+)+=G+故F+G+同理可证G+F+

所以F+=G+6.3数据依赖的公理系统定义6.15:如果函数依赖集F满足下列条件,则称F为一个极小的函数依赖集,也称最小覆盖(1)F中的每个函数依赖的右部为单属性(2)F中不存在这样的函数依赖XA,使得F-{XA}与F等价

(3)F中不存在这样的函数依赖XA,使得F-{XA}{ZA}与F等价(ZX)6.3数据依赖的公理系统定理6.3:每个函数依赖集F均等价于一个极小的函数依赖集Fm,Fm称为F的最小覆盖证明:只要能构造一个满足定义6.15中3个条件的覆盖Fm,定理得证(1)逐一检查F中的函数依赖XY,如Y=A1A2...An,则用{XAi|i=1,2...,K}取代XY(2)逐一检查XAi令G=F-{XAi},若AiXG+则从F中去掉该函数依赖,对所有的XAi检查并处理后的覆盖G’,G’满足定义6.15中的(1)(2)6.3数据依赖的公理系统(3)检查G‘中每个函数依赖XA,设X=B1B2...Bm,对Bi逐一做下列检查和处理G’与G’-{XA}{(X-Bi)A}是否等价如等价,则以X-Bi取代X,如不等价,则X不变所有的Bi检查完后,令最后的X为Z并以G’-{XA}{(ZA)代替G’G’中每个XA做如此检查后,求得函数依赖集G’’显然G’’满足定义5中的3项,故令G’’为Fm,即Fm是可构造的6.3数据依赖的公理系统求候选关键字的经验方法若属性A仅出现在所有函数依赖的右部，则它一定不包含在任何候选关键字中；若属性A仅出现在所有函数依赖的左部，则它一定包含在某个候选关键字中；若属性A既出现在函数依赖的右部，又出现在左部，则它可能包含在候选关键字中；若属性A既不出现在函数依赖的左部，又不出现在函数依赖的右部。在上述基础上求属性集闭包。6.3数据依赖的公理系统给定关系模式R,求候选码例子:对于R(ABCDE),F={AB,BCE,EDA}求出R的所有候选关键字如果K是关键字,则有KU,所以只要判断KF+=U且K’F+U(K’K)(CD)F+={CD}(CDE)F+={CDEAB}(CDA)F+={ABCDE}(CDB)F+={CDBEA}R的候选关键字为CDA，CDB，CDE。f6.4模式分解定义6.16关系模式R<U,F>的一个分解是指={R1<U1,F1>,R2<U2,F2>,…,Rn<Un,Fn>},其中

,并且没有UiUj,1i,jn,Fi是F在Ui上的投影。Fi是F在Ui上的投影的定义是：定义6.17函数依赖集合的一个覆盖Fi叫做F在属性Ui上的投影。6.4模式分解6.4.1模式分解的3个定义对于一个模式的分解是多种多样的，分解后产生的模式应与原模式等价。对“等价”的概念形成了三种不同的定义。分解具有“无损连接性”分解要“保持函数依赖”分解既要“保持函数依赖”，又要具有“无损连接性”6.4模式分解例子:已知R<U,F>,其中U={Sno,Sdept,Mname}F={SnoSdept,SdeptMname},R<U,F>的元组语义是学生Sno正在Sdept系学习，其系主任是Mname。并且一个学生(Sno)只在一个系学习，一个系只有一名系主任。R的一个关系如下表。S4毕业，则D3的系主任是王一的信息也丢掉了。一个系D5尚无在校学生，那么这个系的系主任是赵某的信息也无法输入。SnoSdept

Mname

S1D1张五S2D1张五S3D2李四S4D3王一6.4模式分解分解1={R1<S#,>,R2<SD,>,R3<MN,>}分解后Ri的关系ri是R的关系r在Ui上的投影r1={S1,S2,S3,S4}r2={D1,D2,D3}r3={张五,李四,王一}如果回答“S1在哪个系学习”也不可能了。6.4模式分解分解2={R1<{Sno,Sdpet},{SnoSdept}>,R2<{Sno,Mname},{SnoMname}>}SnoSdeptMnamer1={{S1,D1},{S2,D1},S1D1张五{S3,D2},{S4,,D3}}S2D1张五r2={{S1,张五},{S2,张五},S3D2李四{S3,李四},{S4,王一}}S4D3王一2对R的分解是可恢复的，但是前面提到的插入和删除异常仍然没有解决，原因就在于原来在R中存在的函数依赖SdeptMname，现在在R1和R2中都不再存在了。因此要求分解具有“保持函数依赖”的特性。6.4模式分解分解3={R1<{Sno,Sdept},{SnoSdept}>,R2<{Sno,Mname},{SdeptMname}>}SnoSdeptMnamer1={{S1,D1},{S2,D1},S1D1张五{S3,D2},{S4,,D3}}S2D1张五r2={{D1,张五},{S3,李四},S3D2李四{S4,王一}}S4D3王一通过自然连接,可以恢复r3既具有无损连接性，又保持函数依赖。它解决了更新异常，又没有丢失原数据库的信息，这是所希望的分解。6.4模式分解结论:对一个模式的分解是多种多样的分解具有“无损连接性”分解要保持函数依赖分解既要保持函数依赖又要具有无损连接性

定义3:设={R1,R2,…,Rn}是R的一个分解,r是R的任意一个值,如果满足条件r=r1r2,…,rn,其中ri=Ui(r),称分解具有无损连接性或简称无损分解6.4模式分解定义4:设={R1,R2,…,Rn}是R的一个分解,如果

逻辑蕴含F,称分解保持函数依赖

关系模式分解的两种准则

只满足无损分解:最基本的要求,发同样的查询得到查询结果相等即满足无损分解又满足保持函数依赖6.4模式分解算法6.2无损分解测试算法:检测一个分解是否无损分解输入:关系模式R(A1,A2,...,An)R上的函数依赖集FR上的分解={R1,R2,...,Rk}输出:是无损分解步骤:6.4模式分解(1)建立n列,k行的矩阵M属性的K个关系模式A1A2...Aj...AnR1R2Ri...M[i,j]Rk.........M[i,j]=aj若AiUi

bij若AiUi6.4模式分解(2)对F中的每个函数依赖XY反复进行下面的检查和处理,直到M无变化为止检查X中的属性所对应的列,找出X相等的那些行,如果找到X相等的两行(或多行),把相应的Y属性对应的符号改为一致,即如果其中之一为aj,则其他也改成aj,如果这两个符号为bij和blj,将它们统一成bij或blj(3)当M无变化时,如果M中有一行变成了a1,a2...,an,则是无损分解,否则不是6.4模式分解例子:关系模式R(ABCDE)={R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)}是R的一个分解,在R上有下列函数依赖F={AC,BC,CD,DEC,CEA},判别是否是无损分解解:(1)建M(2)对AC检查b13,b23,b53b13对BC检查b13,b33b13ABCDER1R2R3R4R56.4模式分解ABCDER1a1b12b13a4b15R2a1a2b23b24b25R3b31a2b33b34a5R4b41b42a3a4a5R5a1b52b53b54a5ABCDER1a1b12b13a4b15R2a1a2

b13b24b25R3b31a2b33b34a5R4b41b42a3a4a5R5a1b52b13b54a5={R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)}对AC检查对BC检查6.4模式分解对CD检查对DEC检查ABCDER1a1b12b13a4b15