数据库数电课件第6章2database_第1页
数据库数电课件第6章2database_第2页
数据库数电课件第6章2database_第3页
数据库数电课件第6章2database_第4页
数据库数电课件第6章2database_第5页
已阅读5页,还剩52页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

AnIntroductiontoDatabaseSystem

上课了。。。请肃静数据库,,,,AnIntroductiontoDatabaseSystem6.3数据依赖的公理系统逻辑蕴含 定义6.11对于满足一组函数依赖

F的关系模式R<U,F>,其任何一个关系r,若函数依赖X→Y都成立,则称

F逻辑蕴含X→YAnIntroductiontoDatabaseSystem1.函数依赖闭包定义6.13设F为属性集U上的一组函数依赖,X

U,

XF+={A|X→A能由F导出},XF+称为属性集X关于函数依赖集F的闭包AnIntroductiontoDatabaseSystem求闭包的算法算法6.l求属性集X(X

U)关于U上的函数依赖集F的闭包XF+

输入:X,F输出:XF+步骤:(1)令X(0)=X,i=0(2)求B,这里B={A|(

V)(

W)(V→WF∧VX(i)∧A

W)};(3)X(i+1)=B∪X(i)

AnIntroductiontoDatabaseSystem算法6.l(4)判断X(i+1)=X

(i)吗?(5)若相等或X(i)=U,则X(i)就是XF+,

算法终止。(6)若否,则i=i+l,返回第(2)步。对于算法6.l,令ai=|X(i)|,{ai

}形成一个步长大于1的严格递增的序列,序列的上界是|U|,因此该算法最多|U|-|X|次循环就会终止。AnIntroductiontoDatabaseSystem函数依赖闭包[例1]已知关系模式R<U,F>,其中U={A,B,C,D,E};F={AB→C,B→D,C→E,EC→B,AC→B}。求(AB)F+

。解设X(0)=AB;(1)计算X(1):逐一的扫描F集合中各个函数依赖,找左部为A,B或AB的函数依赖。得到两个:

AB→C,B→D。于是X(1)=AB∪CD=ABCD。AnIntroductiontoDatabaseSystem函数依赖闭包(2)因为X(0)≠X(1),所以再找出左部为ABCD子集的那些函数依赖,又得到AB→C,B→D,C→E,AC→B,于是X(2)=X(1)∪BCDE=ABCDE。(3)因为X(2)=U,算法终止所以(AB)F+=ABCDE。AnIntroductiontoDatabaseSystem2.最小依赖集

定义6.15如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。

(1)F中任一函数依赖的右部仅含有一个属性。

(2)F中不存在这样的函数依赖X→A,使得F与 F-{X→A}等价。没有多余的函数依赖

(3)F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X→A}∪{Z→A}与F等价。去掉左部多余的属性AnIntroductiontoDatabaseSystem最小依赖集[例2]对于6.l节中的关系模式S<U,F>,其中:

U={SNO,SDEPT,MN,CNAME,G},

F={SNO→SDEPT,SDEPT→MN,(SNO,CNAME)→G}

设F’={SNO→SDEPT,SNO→MN,

SDEPT→MN,(SNO,CNAME)→G,

(SNO,SDEPT)→SDEPT}F是最小覆盖,而F’不是。因为:F’-{SNO→MN}与F’等价

F’-{(SNO,SDEPT)→SDEPT}也与F’等价

F’-{(SNO,SDEPT)→SDEPT}∪{SNO→SDEPT}也与F’等价AnIntroductiontoDatabaseSystem7.极小化过程定理6.3每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集证:构造性证明,依据定义分三步对F进行“极小化处理”,找出F的一个最小依赖集。(1)逐一检查F中各函数依赖FDi:X→Y,若Y=A1A2

…Ak,k>2,则用{X→Aj

|j=1,2,…,k}来取代X→Y。

AnIntroductiontoDatabaseSystem极小化过程(2)逐一取出F中各函数依赖FDi:X→A,设X=B1B2…Bm,逐一考查Bi

(i=l,2,…,m),若A(X-Bi

)F+,则以X-Bi

取代X。

AnIntroductiontoDatabaseSystem极小化过程(3)逐一检查F中各函数依赖FDi:X→A,令G=F-{X→A},若AXG+,则从F中去掉此函数依赖。

AnIntroductiontoDatabaseSystem极小化过程例:设有关系模式R<U,F>,其中U={EFGH}F={E→G,G→E,F→EGH→EG,FH→E}求F的最小依赖集。将F中右侧属性单一化F1={E→G,G→E,F→E,F→G,H→E,H→G,FH→E}去掉左侧多余的属性,对于FH→E,去掉F,H+=GE,E∈H+,所以F可以去掉F2={E→G,G→E,F→E,F→G,H→E,H→G}AnIntroductiontoDatabaseSystem极小化过程F2={E→G,G→E,F→E,F→G,H→E,H→G}去掉多余的函数依赖E→G,G→E二个没有E+和G+F→E,F+=GE,E∈GE,可去掉F→G,没有F+,注意F→E已删除了H→E,H+=GE,E∈GE,可去掉H→G,没有H+,注意H→E已删除了注:结果不唯一,F→E,F→G可去掉任何一个,H→E,H→G也可去掉任何一个。AnIntroductiontoDatabaseSystem极小化过程[例3]F={A→B,B→A,B→C,

A→C,C→A}Fm1、Fm2都是F的最小依赖集:

Fm1={A→B,B→C,C→A}

Fm2={A→B,B→A,A→C,C→A}F的最小依赖集Fm不一定是唯一的它与对各函数依赖FDi

及X→A中X各属性的处置顺序有关AnIntroductiontoDatabaseSystem极小化过程若改造后的F与原来的F相同,说明F本身就是一个最小依赖集AnIntroductiontoDatabaseSystem6.4模式分解有时候为了控制由于冗余带来的问题以及插入和删除等问题要求关系模式满足一定的范型,可以通过模式分解来达到,这一过程称之为规范化(Normalization)有时候考虑到查询的效率,需要将满足较高范型的关系模式进行合并,这一过程称之为DenormalizationAnIntroductiontoDatabaseSystem

模式的分解把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的只有能够保证分解后的关系模式与原关系模式等价,分解方法才有意义AnIntroductiontoDatabaseSystem关系模式分解的标准三种模式分解的等价定义⒈分解具有无损连接性⒉分解要保持函数依赖⒊分解既要保持函数依赖,又要具有无损连接性AnIntroductiontoDatabaseSystem模式的分解(续)例:SL(Sno,Sdept,Sloc)

F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}SL∈2NF存在插入异常、删除异常、冗余度大和修改复杂等问题分解方法可以有多种AnIntroductiontoDatabaseSystem模式的分解(续)SL──────────────────Sno Sdept Sloc──────────────────95001CSA95002ISB95003MAC95004ISB95005 PH B──────────────────AnIntroductiontoDatabaseSystem模式的分解(续)1.SL分解为下面三个关系模式:

SN(Sno)SD(Sdept)SO(Sloc)AnIntroductiontoDatabaseSystem分解后的关系为:

SN──────SD──────SO──────SnoSdeptSloc

──────────────────95001CSA95002ISB95003MAC95004PH─────95005────────────AnIntroductiontoDatabaseSystem模式的分解(续)

分解后的数据库丢失了许多信息例如无法查询95001学生所在系或所在宿舍。如果分解后的关系可以通过自然连接恢复为原来的关系,那么这种分解就没有丢失信息AnIntroductiontoDatabaseSystem模式的分解(续)2.SL分解为下面二个关系模式:

NL(Sno,Sloc)DL(Sdept,Sloc)分解后的关系为:

NL────────────DL────────────SnoSlocSdeptSloc

────────────────────────95001A CSA95002B ISB95003C MAC95004B PHB95005B──────────────────────AnIntroductiontoDatabaseSystem模式的分解(续)NLDL─────────────SnoSlocSdept─────────────95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPHAnIntroductiontoDatabaseSystem模式的分解(续) NLDL比原来的SL关系多了3个元组

无法知道95002、95004、95005

究竟是哪个系的学生

元组增加了,信息丢失了AnIntroductiontoDatabaseSystem第三种分解方法3.将SL分解为下面二个关系模式:

ND(Sno,Sdept)NL(Sno,Sloc)

分解后的关系为:

AnIntroductiontoDatabaseSystem模式的分解(续)ND────────────NL──────────SnoSdeptSnoSloc

──────────────────────95001CS95001A95002IS95002B95003MA95003C95004IS95004B95005PH95005B

───────────────────────AnIntroductiontoDatabaseSystem模式的分解(续)NDNL──────────────SnoSdeptSloc──────────────

95001CSA95002ISB95003MAC95004CSA95005PHB──────────────与SL关系一样,因此没有丢失信息AnIntroductiontoDatabaseSystem具有无损连接性的模式分解关系模式R<U,F>的一个分解ρ={R1<U1,F1>,R2<U2,F2>,…,Rn<Un,Fn>}若R与R1、R2、…、Rn自然连接的结果相等,则称关系模式R的这个分解ρ具有无损连接性(Losslessjoin)具有无损连接性的分解保证不丢失信息无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题AnIntroductiontoDatabaseSystem模式的分解(续)

第三种分解方法具有无损连接性

问题:

这种分解方法没有保持原关系中的函数依赖

SL中的函数依赖Sdept→Sloc

没有投影到关系模式ND、NL上

AnIntroductiontoDatabaseSystem保持函数依赖的模式分解设关系模式R<U,F>被分解为若干个关系模式R1<U1,F1>,R2<U2,F2>,…,Rn<Un,Fn>(其中U=U1∪U2∪…∪Un,且不存在UiUj,Fi为F在Ui上的投影),若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含,则称关系模式R的这个分解是保持函数依赖的(Preservedependency)。AnIntroductiontoDatabaseSystem第四种分解方法

将SL分解为下面二个关系模式:

ND(Sno,Sdept)DL(Sdept,Sloc)

这种分解方法就保持了函数依赖。AnIntroductiontoDatabaseSystem模式的分解(续)如果一个分解具有无损连接性,则它能够保证不丢失信息。如果一个分解保持了函数依赖,则它可以减轻或解决各种异常情况。分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样,保持函数依赖的分解也不一定具有无损连接性。AnIntroductiontoDatabaseSystem模式的分解(续)第一种分解方法既不具有无损连接性,也未保持函数依赖,它不是原关系模式的一个等价分解第二种分解方法保持了函数依赖,但不具有无损连接性第三种分解方法具有无损连接性,但未持函数依赖第四种分解方法既具有无损连接性,又保持了函数依赖AnIntroductiontoDatabaseSystem分解算法算法6.2判别一个分解的无损连接性算法6.3(合成法)转换为3NF的保持函数依赖的分解。算法6.4转换为3NF既有无损连接性又保持函数依赖的分解AnIntroductiontoDatabaseSystem分解算法若要求分解保持函数依赖,那么模式分解一定能够达到3NF,但不一定能够达到BCNF。若要求分解既具有无损连接性,又保持函数依赖,则模式分解一定能够达到3NF,但不一定能够达到BCNF。AnIntroductiontoDatabaseSystem算法6.3(合成法)转换为3NF的保持函数依赖的分解对R(U,F)中的函数依赖集F进行极小化找出不在F中出现的属性,把这样的属性构成一个关系模式,把这些属性从U中去掉,剩余的属性仍记为U若有X→A∈F,且XA=U,则ρ={R}否则对F按具有相同左部的原则分组,每一组函数依赖Fi’所涉及全部属性形成一个属性集Ui,若Ui

Uj(i≠J)就去掉UiAnIntroductiontoDatabaseSystem算法6.3例:设有关系模式R<U,F>,其中U={CTHSRG},F={CS→G,C→T,TH→R,HR→C,HS→R},将其保持依赖性分解为3NF。Fmin=F没有不在F中出现的属性没有哪个依赖X→A∈F,且XA=U没有相同的左部,所以每个依赖自成一组R1=CSG,R2=CT,R3=THR,R4=HRC,R5=HSRρ={CSG,CT,THR,HRC,HSR}AnIntroductiontoDatabaseSystem算法6.3例:设有关系模式R(ABCDE),R的依赖集F={A→D,E→D,D→B,BC→D,CD→A},将R分解为3NFAnIntroductiontoDatabaseSystem算法6.3例:设有关系模式R(ABCDE),R的依赖集F={A→D,E→D,D→B,BC→D,CD→A},将R分解为3NFFmin=F没有不在F中出现的属性没有哪个依赖X→A∈F,且XA=U没有相同的左部,所以每个依赖自成一组AD,DE,BD,BCD,ACD,因ADACDBDBCD,所以ρ={DE,BCD,ACD}AnIntroductiontoDatabaseSystem算法6.4

转换为3NF既有无损连接性又保持函数依赖的分解。根据算法6.3求出保持依赖性分解ρ={R1,R2……Rk}设X是R的码,若X某个Ri,则τ=ρ,否则τ=ρ

∪{X}τ就是所求的分解

AnIntroductiontoDatabaseSystem算法6.4(续)例:设有关系模式R(EGHIJ),R的函数依赖集为F={E→I,J→I,I→G,GH→I,IH→E},求R的候选码,将R分解为3NF,并具有无损连接性和依赖保持性。解:去掉在函数依赖集右侧出现的,剩下JH(JH)+=EGHIJ,所以候选码只有JH求出最小依赖集Fm=F没有不在F中出现的属性没有哪个依赖X→A∈F,且XA=U没有相同的左部,所以每个依赖自成一组ρ={EI,JI,IG,GHI,IHE}τ=ρ

∪{JH}τ={EI,JI,IG,GHI,IHE,JH}订单号DDH姓名XM地址DZ书号SH书名SM单价DJ数量SL98010张三

沈阳102001020510201高数线代概率8.007.509.0012012012098011李四

大连220201020530502数据库线代汇编8.507.506.0080804098204王五北京0530230502制图汇编5.806.008090例:设某新华书店,订书单汇总表如下:规范到3NF,要求分解即具有无损性连接,又要保持函数依赖。解:R(DDH,XM,DZ,SH,SM,DJ,SL)(1)求最小函数依赖集F={DDH→XM,DDH→DZ,SH→SM,SH→DJ,(DDH,SH)→SL}(2)找R中不在F中出现的属性——没有;(3)找每一个函数依赖中的属性集是否与R中属性集相同即不存在若X→A,则X∪A=U(4)按左部相同的原则分组

R1(DDH,XM,DZ)

R2(SH,SM,DJ)

R3(DDH,SH,SL)达到了把R分解成3NF,且保持函数依赖。继续做无损性连接分解。由于关系模式R中的关键字是(DDH,SH)而R3中的属性集包含此关键字所以R1,R2,R3即为所求。即:关系模式R模式分解为R1,R2,R3,规范化到了3NF,并且保持了函数依赖和无损性连接。AnIntroductiontoDatabaseSystem学校兴趣小组表如下规范到3NF,要求分解即具有无损性连接,又要保持函数依赖。学号姓名兴趣小组时间地点05001赵一计算机周一563-10105001赵一舞蹈周二783-10205002钱二计算机周一563-101AnIntroductiontoDatabaseSystem综合例:设有如下所示的关系R它为第几范式,为什么?是否存在删除异常,如存在,什么情况下发生将它分解为高一级的范式,分解后的关系如何解决分解前的删除异常。AnIntroductiontoDatabaseSystem综合它为2NF,因为R的候选码为课程名,而课程名→教师名,教师名→课程名不成立,教师名→教师地址,所以课程名T

教师地址,存在非主属性对码的传递函数依赖,所以它不是3NF,又因为不存在非主属性对码的部分依赖,所以它是2NF。存在删除异常,当删除某门课程时会删除教师的信息将它分解为R1(课程名,教师名)R2(教师名,教师地址),当删除课程时,仅对R1操作AnIntroductiontoDatabaseSystem例:设有关系模式R(运动员编号、比赛项目、成绩、比赛类别、比赛主管)存储运动员比赛成绩及比赛类别、主管等信息。如果规定:每个运动员每参加一个比赛项目,只有一个成绩;每个比赛项目只属于一个比赛类别;每个比赛类别只有一个比赛主管。试回答下列问题:根据上述规定,写出关系模式R的基本函数依赖找出R的候选码找出函数依赖来说明R不是2NF的理由,并把R分解成2NF模式集。进而分解成3NF模式集。AnIntroductiontoDatabaseSystem基本的FD有三个:(运动员编号,比赛项目)→成绩比赛项目→比赛类别比赛类别→比赛主管R的关键码为:(运动员编号,比赛项目)R中有二个这样的FD

(运动员编号,比赛项目)→(比赛类别,比赛主管)比赛项目→(比赛类别,比赛主管)可见前一个是局部依赖,所以R不是2NF。AnIntroductiontoDatabaseSystemR分解为R1(比赛项目,比赛类别,比赛主管)

R2(运动员编号,比赛项目,成绩)

R1和R2都是2NFR2是3NF,在R1中比赛项目→比赛类别,比赛类别→比赛主管,因此比赛项目

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论