第六章 关系数据库理论

6.1问题的提出例如：Student(Sno，Sdept，Mname，Cname，Grade)F={SnoSdept，SdeptMname，(Sno,Cname)Grade}存在问题：⑴数据冗余太大⑵插入异常⑶删除异常⑷更新异常分解成三个关系模式：S(Sno，Sdept，SnoSdept)；SG(Sno，Cname，Grade，(Sno,Cname)Grade)；D(Sdept，Mname，SdeptMname)；6.2规范化数据依赖：关系中属性值之间的这种相互依赖又相互制约的联系，称为数据依赖。包括：函数依赖、多值依赖。一、函数依赖定义1：设R(U)是属性集U上的关系模式。X，Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数决定Y或Y函数依赖于X，记作X→Y。说明：1、函数依赖是语义范畴的概念2、函数依赖关系是反映属性之间的一般规律根据函数依赖的定义，可找出下面规律：1、在一个关系模式中，如属性X，Y有1：1联系，则存在函数依赖X→Y、Y→X，可记作XY2、X、Y是1：m联系，则存在Y→X，但X\→Y3、X、Y是n:m联系，则X、Y之间不存在任何函数依赖X→Y，但YX则称X→Y是平凡的函数依赖。否则，称非平凡的函数依赖。定义2：在R（U）中，如果X→Y，并且对于X的任何一个真子集X′，都有X′→Y，则称Y对X部分函数依赖，记作X→pY，否则，称Y完全函数依赖于X，记作X→fY。定义3：在R（U）中，如果X→Y，（YX），Y\→X，Y→Z，则称Z对X传递函数依赖。定义4：设K为RU，F中的属性或属性组合，若Kf→U则K为R的候选码。若候选码多于一个，则选定其中的一个为主码（PrimaryKey）。包含在任何一个候选码中的属性，叫做主属性。不包含在任何码中的属性称为非主属性或非码属性。整个属性组是码，称为全码。定义5：关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码（ForeignKey），也称外码。二、码三、范式范式：是符合某一种级别的关系模式的集合。关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式。1NF，2NF，3NF，BCNF，4NF，5NF定义：关系模式R（U）中所有属性都不可再分的，则称R是第一范式，记作R1NF。例如：SLC（SNO，SDEPT，SLOC，CNO，GRADE）四、2NF定义6：若R1NF，且每一个非主属性完全函数依赖于码，则R2NF。SNOCNOGSDEPTSLOC五、3NF定义7：若R2NF，且R中任一非主属性都不传递函数依赖于码，则R3NF。SNOCNOGSDEPTSLOCSNOSLSC上例SL分解为：SD（SNO，SDEPT）DL（SDEPT，SLOC）由于第三范式有效地消除了非主属性对码的部分和传递依赖，因而消除了一大类操作异常问题。因此，3NF在数据库设计中得到了广泛应用。六、BCNF例：关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示教师，J表示课程。每一教师只教一门课。每门课有若干教师，某一学生选定某门课，就对应一个固定的教师。由语义可得到如下的函数依赖：（S，J）→T；（S，T）→J；T→J关系有两个候选键，是（S，J）和（S，T）S、T、J都是主属性，不存在非主属性，更不会有非主属性对键的传递依赖、部分依赖了，因此，STJ关系满足第三范式。但仍然存在问题：定义8：RBCNF，当且仅当每个决定因素都是码（候选键）。上例分解为：ST（S，T）、TJ（T，J）七、多值依赖例：学校中某一门课程由多个教员讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。如下表：课程C教员T参考书B物理李勇普通物理学物理李勇光学原理物理李勇物理习题集物理王军普通物理学物理王军光学原理物理王军物理习题集数学李勇数学分析数学李勇微分方程数学李勇高等代数数学张平数学分析数学张平微分方程数学张平高等代数┇┇┇定义9：关系模式R（U），X，Y，Z是U的子集，并且Z=U-X-Y。关系模式R(U)中多值依赖XY成立，当且仅当对R（U）的任一关系r，给定的一对（x，z）值，有一组Y的值，这组值仅仅决定于x值而与z值无关。若XY，而Z=即Z为空，则称XY为平凡的多值依赖。多值依赖性质：⑴对称性。若XY，则XZ，其中Z=U－Ｘ－Ｙ。⑵传递性。若XY，ＹＺ，则XＺ－Y。⑶函数依赖可看作是多值依赖的特殊情况。若XY，则XY。⑷若XY，XＺ，则XYＺ。⑸若XY，XＺ，则XYＺ。⑹若XY，XＺ，则XY－Ｚ，XＺ－Y。八、4NF定义10：关系模式RU，F1NF，如果对于R的每个非平凡多值依赖XY（YX），X都含有码，则称RU，F4NF。九、规范化小结1NF↓消除非主属性对码的部分函数依赖2NF↓消除非主属性对码的传递函数依赖3NF↓消除主属性对码的部分和传递函数依赖BCNF↓消除非平凡且非函数依赖的多值依赖4NF6.3数据依赖的公理系统定义11：对于满足一组函数依赖F的关系模式RU,F，其任何一个关系r，若函数依赖X→Y都成立，则称F逻辑蕴含X→Y。Armstrong公理系统：设U为属性集总体，F是U上的一组函数依赖，于是有关系模式RU,F。对RU,F来说有以下的推理规则：A1自反律：若YXU，则XY为F所蕴含。A2增广律：若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。A3传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含。推论：•合并规则：由XY，XZ，有XYZ。•伪传递规则：由XY，WYZ，有XWZ。•分解规则：由XY及ZY，有XZ。根据合并规则和分解规则，得到一重要事实：引理1：XA1A2┅Ak成立的充分必要条件是XAi成立（i=1,2,┅,k）。定义12：在关系模式RU,F中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记为F+。定义13：设F为属性集U上的一组函数依赖，XU，XF+={A|XA能由F根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F的闭包。引理2：设F为属性集U上的一组函数依赖，X，YU，XY能由F根据Armstrong公理导出的充分必要条件是YXF+。算法6.1：求属性集X（XU）关于U上的函数依赖集F的闭包XF+。步骤：⑴令X(0)=X，i=0⑵求B，这里B={A|(V)(W)(VWF∧VX(i)∧AW)};⑶X(i+1)=BX(i)⑷判断X(i+1)=X(i)吗？⑸若相等或X(i+1)=U，则X(i+1)就是XF+，算法终止。⑹若否，则i=i+1，返回第⑵步。例1已知关系模式RU,F，其中U={A，B，C，D，E}；F={ABC，BD，CE，ECB，ACB}。求（AB）F+。定义14：如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。引理3：F+=G+的充分必要条件是FG+，和GF+。定义15：如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。⑴F中任一函数依赖的右部仅含有一个属性。⑵F中不存在这样的函数依赖XA，使得F与F－{XA}等价。⑶F中不存在这样的函数依赖XA，X有真子集Z使得F－{XA}{ZA}与F等价。例：F={AB，BA，BC，AC，CA}求Fm。Fm1={AB，BC，CA}Fm2={AB，BA，AC，CA}6.4模式的分解分解具有“无损连接性”分解要“保持函数依赖”分解既要“保持函数依赖”，又要具有“无损连接性”。定义16：关系模式RU,F的一个分解是指ρ＝{R1U1，F1，R2U2，F2，…，RnUn,Fn}其中U=Ui，并且没有UiUj，1≤ｉ，j≤n，Fi是F在Ui上的投影。定义17：函数依赖集合{XY|XYF+∧XYUi}的一个覆盖Fi叫做F在属性Ui上的投影。一、模式分解的三个定义例：已知关系模式RU,F，其中U={SNO,SDEPT,MN},F={SNOSDEPT,SDEPTMN}。分解：ρ1＝{R1SNO，，R2SDEPT，，R3MN，}ρ2＝{R1{SNO,SDEPT},{SNOSDEPT}，R2{SNO,MN},{SNOMN}}ρ3＝{R1{SNO,SDEPT}，{SNOSDEPT}，R2{SDEPT,MN}，{SDEPTMN}}二、分解的无损连接性和保持函数依赖性定义18:ρ＝{R1U1，F1，…，RkUk,Fk}是RU,F的一个分解，若RU,F的任何一个关系r均有r=mρ(r)成立，则称分解ρ具有无损连接性。简称ρ为无损分解。算法6.2：判别一个分解的无损连接性。ρ＝{R1U1，F1，…，RkUk,Fk}是RU,F的一个分解，U={A1,…,An}，F＝{FD1,FD2,…,FDρ}，F是一极小依赖集,记FDi为XiA1i。⑴建立一张n列k行的表。每一列对应一个属性，每一行对应分解中的一个关系模式。若属性Aj属于Ui，则在j列i行交叉处填上aj，否则填上bij；⑵对每一个FDi做下列操作：找到Xi所对应的列中具有相同符号的那些行。考察这些行中li列的元素，若其中有ali，则全部改为ali；否则全部改为bmli；m是这些行的行号最小值。⑶比较扫描前后，表有无变化。如有变化，则返回第⑵步，否则算法终止。例：已知RU,F，U＝{A,B,C,D,E}，F={ABC，CD，DE}，R的一个分解为R1(A,B,C)，R2(C,D)，R3(D,E)。⑴首先构造初始表，如图ABCDEa1a2a3b14b15b21b22a3a4b25b31b32b33a4a5⑵对ABC，因各元组的第1、2列没有相同的分量，所以表不改变。由CD可以把b14改为a4，再由DE可使b15，b25全改为a5。ABCDEa1a2a3a4a5b21b22a3a4a5b31b32b33a4a5定理：RU,F的一个分解ρ＝{R1U1，F1，R2U2,F2}具有无损连接性的充分必要条件是：U1∩U2U1－U2F+或U1∩U2U2－U1F+。⑴若要求分解保持函数依赖，那么模式分离总可以达到3NF，但不一定能达到BCNF;⑵若要求分解既保持函数依赖，又具有无损连接性，可以达到3NF，但不一定能达到BCNF;⑶若要求分解具有无损连接性，那一定可达到4NF;当关系模式R分解为两个关系模式R1，R2时有下面的判定准则。定义19：若F+＝（∪Fi）＋，则RU,F的分解ρ＝{R1U1，F1，…，RkUk,Fk}保持函数依赖。三、模式分解的算法关于模式分解的几个重要事实是：算法6.3转换为3NF的保持函数依赖的分解⑴对RU,F中的函数依赖集F进行“极小化处理”，仍记为F。⑵找出不在F中出现的属性，把这样的属性构成一个关系模式。把这些属性从U中去掉，剩余的属性仍记为U。⑶若有XAF，且XA=U，则ρ＝{R}，算法终止。⑷否则，对F按具有相同左部的原则分组（假定分为k组）,每一组函数依赖Fi´所涉及的全部属性形成一个属性集Ui。若UiUj(i≠j)就去掉Ui。算法6.4转换为3NF既有无损连接性又保持函数依赖的分解⑴设X是RU,F的码。RU,F已由算法5.3分解为ρ＝{R1U1，F1，R2U2，F2，…，RkUk,Fk}，令＝ρ∪{RxU,Fx}。⑵若有某个Ui，XUi,将RxU,Fx从中去掉。把这些属性从U中去掉，剩余的属性仍记为U。⑶就是所求的分解。算法6.5转换为BCNF的无损连接的分解⑴令ρ＝{RU，F}⑵检查ρ中各关系模式是否均属