第6章关系数据理论

第6章关系数据理论6.1问题的提出6.2规范化6.3数据依赖的公理系统*6.4模式的分解(要求)6.5小结问题的提出关系数据库逻辑设计针对具体问题，如何构造一个适合于它的数据模式数据库逻辑设计的工具──关系数据库的规范化理论关系模式的形式化定义关系模式由五部分组成，即它是一个五元组：

R(U,D,DOM,F)R：关系名U：组成该关系的属性名集合D：属性组U中属性所来自的域DOM：属性向域的映象集合F：属性间数据的依赖关系集合关系模式的简化表示关系模式R（U,D,DOM,F）简化为一个三元组：

R（U,F）当且仅当U上的一个关系r满足F时，r称为关系模式R（U,F）的一个关系数据依赖定义属性值间的相互关连,是数据库模式设计的关键一个关系内部属性与属性之间的约束关系现实世界属性间相互联系的抽象数据内在的性质语义的体现数据依赖的类型函数依赖（FunctionalDependency，简记为FD）多值依赖（MultivaluedDependency，简记为MVD）其他数据依赖对关系模式的影响[例1]建立一个描述学校教务的数据库： 学生的学号（Sno）、所在系（Sdept） 系主任姓名（Mname）、课程名（Cname） 成绩（Grade）单一的关系模式：Student<U、F>U＝｛Sno,Sdept,Mname,Cname,Grade｝关系模式Student<U,F>中存在的问题1.数据冗余太大2.更新异常（UpdateAnomalies）3.插入异常（InsertionAnomalies）4.删除异常（DeletionAnomalies）U＝｛Sno,Sdept,Mname,Cname,Grade｝结论：Student关系模式不是一个好的模式。“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少不好原因：由存在于模式中的某些数据依赖引起解决方法：通过分解关系模式来消除其中不合适的数据依赖规范化基本概念

1,函数依赖

定义:设R(U)是属性集U上的关系模式X,Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等,而在Y上的属性值不等,则称X函数确定Y或Y函数依赖于X，记作X→Y。

{R<U,F>X→YR中属性（组）X的每一个值，R

中的Y只有一个值与之对应}2、非平凡函数依赖

（X→Y；Y￠X）

X→Y，Y不包含于X，X→Y非平凡的函数依赖3、决定因素

X→Y，X为决定因素

4、完全函数依赖

X→Y：X→Y，X’为X的任一真子集

X’/Y5、部分函数依赖

X→Y：X→YX’为X的任一真子集存在X’Y例如SCI（SNO，CNO，G，CRE）（SNO，CNO）→G（SNO，CNO）→CRE又CNO→CRE

6、传递函数依赖

X→Y，Y不包含于X，Y→X，Y→Z则称Z对X传递函数依赖

7、码侯选码：K为R<U，F>的属性或属性组合，若K完全函数确定U(强调不存在K的真子集能函数确定U)，K为R的候选码。若候选码多于一个，则选定其中的一个为主码主属性：包含在任何一个候选码中的属性非主属性：不包含在任何侯选码中的属性全码：整个属性组是码外码：范式

第一范式：1NF要求：关系模式R<U,F>中每个分量必须是不可分的数据项。满足1NF则满足了关系模式中的基本要求。例：SC1（SNO，CNO，G，CRE）SC1∈1NF

例：SC1（SNO，CNO，G，CRE）SC1∈1NF

分析步骤：1）写出关系模式的函数依赖集FD(或画函数依赖图)(SNO,CNO)→G,(SNO，CNO)→CRE,CNO→CRE2）确定关系模式的候选码：(SNO，CNO)3）分析存在的问题：

冗余，插入异常，删除异常，更新复杂4）找出存在问题的原因：

存在非主属性CRE部分函数依赖于码（SNO,CNO）5）问题的解决：

分解关系模式SC1为两个关系模式：

SC11<（SNO，CNO，G），(SNO，CNO)→G>SC12<（CNO，CRE）,CNO→CRE

>由此，消除了非主属性对码的部分函数依赖,所有非主属性对码是完全函数依赖．第二范式：2NF要求：R∈1NF且每一个非主属性完全函数依赖于码,

则R∈2NF例：S-L-C（SNO，SD，SL，CNO，G）

FD：（SNO，CNO）→GSNO→SD,SD不属于SNOSDSNO,SD→SLSL传递依赖SNOGSNOCNOSDSL

∵码（SNO，CNO）主属性SNO，CNO

非主属性SD，SL，G∴存在非主属性部分依赖于码并非每个非主属性完全函数依赖于码∴S-L-C∈2NF问题：冗余，插入异常，删除异常，更新复杂解决：模式分解分解S-L-C为:SC和SL2个关系模式

SC<（SNO，CNO，G）,（SNO，CNO）→G>∈2NF

SL<（SNO，SD，SL）,SNO→SD,SD→SL>∈2NF每个非主属性完全函数依赖于码,不存在非主属性对码的部分函数依赖.R∈2NFSL仍然存在问题：冗余,存储异常,更新复杂

显然是存在非主属性对码的传递函数依赖

第三范式：3NF要求：如果关系模式R<U,F>中的所有非主属性对任何码（侯选码）都不存在传递依赖，则关系R是第三范式.R∈3NF可以证明：若R∈3NF则每一个非主属性即不部分依赖于码也不传递依赖于码∴R∈3NF必然R∈2NFS-L-C（SNO，SD，SL，CNO，G）分解为如3个关系模式:SC<（SNO,CNO,G）,（SNO，CNO）→G>SD<（SNO，SD）,SNO→SD>DL<（SD，DL）,SD→SL

>SC,SD,SL均属于第三范式如图给出的关系R为第几范式?是否存在操作异常?若存在，则将其分解为高一级范式。分解完成的高级范式中是否可以避免分解前关系中存在的操作异常?(确定R<U,F>)工程号材料号数量开工日期完工日期价格

P1I1498059902250P1I2698059902300P1I31598059902180P2I1698119912250P2I41898119912350

完工日期

工程号开工日期数量

材料号价格R1(工程号,材料号,数量)R2(材料号,价格)R3(工程号,开工日期,完工日期)例:R(SNO,SNA,CNO,G,CNA,TNA,TAGE)(学号,姓名,课程号,成绩,课程名称,教师姓名,教师年龄)

一名教师可以讲授多门课程,一门课程仅由一位教师讲授,其它语意略分析R并将其转换为高级范式FD:SNOSNA;(SNO,CNO)G;CNOCAN;CNOTNA;TNATAGER1(SNO,SNA),R2(SNO,CNO,G)R3(CNO,CAN,TNA,TAGE)例：设有关系模式,

仓库保管WPE（W＃，P＃，E＃，QNT）仓库号，器件号，职工号，数量函数依赖：（W#，P#）QNT

（E#，P#）QNT

（W#，P#）E#E#W#W#问题：关系模式WPE（W＃，P＃，E＃，QNT）达到？NFE#P#QNT分析：关系模式WPE有两个侯选码（W#，P#）、（E#，P#）主属性：W#，P#，E#非主属性：QNT∴WPE∈3NF存在问题(设确定（E#，P#）为主码)某新职工分配来仓库，处于学习阶段，但没有独立承但任务，即有E＃但无P＃，缺少码的组成部分，无法插入到该关系——插入异常原因：主属性W＃对另一个侯选码（E#，P#）的部分函数依赖解决方法：分解关系模式WPE为保管EP（E＃，P＃，QNT）码（E＃，P＃）工作EW（E＃，W＃）码E＃*分解后的关系可以通过自然连接恢复原关系*分解后将失去某些函数依赖：（P#，W#）E#

（P#，W#）QNT意味着失去某些语义，从而不符合语义的数据可以被数据库接受。(如果原关系模式确定(P#，W#)为主码上述函数依赖可以保证)对应上述丢失的函数依赖，失去语义要求：*每个仓库一种器件由专人负责，新关系模式接受如下情况（P1W1）E1

（P1W1）E2*某仓库的某种器件有其数量所以：分解后的关系模式降低了部分的完整性约束。实际工程应综合考虑整体代价。

BC范式：BCNF要求：R〈U，F〉∈1NF，若X→Y且Y￠X时,X必含有码，则R〈U，F〉∈BCNF。意味着：R〈U，F〉中，若每个决定因素都包含码，则R〈U，F〉∈BCNF上例中存在E#W#E#中没有包含码∴WPE∈BCNF可以证明：R∈BCNF则R∈3NFR∈3NF，仍可能存在的问题，原因在于主属性对码的部分依赖和传递依赖。例：判断以下关系模式是否∈BCNF1、SJP（S，J，P）学生,课程,名次(唯一)

2、STJ（S，T，J）学生,教师,课程(一名教师仅讲授一门课程)例：判断以下关系模式是否∈BCNF1、SJP（S，J，P）学生,课程,名次(唯一)FD:(S,J)P(J,P)S2、STJ（S，T，J）学生,教师,课程(一名教师仅讲授一门课程)FD:(S,J)T(S,T)JTJ小结：1NF（每个分量必须不可分）消除非属性对码的部分函数依赖2NF（每个非属性完全函数依赖于码）消除非属性对码的传递函数依赖3NF(所有非属性对任何码都不存在传递函数依赖）消除主属性对码的部分和传递函数依赖BCNF（每个决定因素都包含码）

多值依赖定义6.9设R(U)是属性集U上的一个关系模式。X，Y，Z是的U的子集,并且Z=U-X-Y。关系模式R(U)中多值依赖X→→Y成立，当且仅当对R(U)的任一关系r,给定的一对(x，z)值有一组Y的值，这组值仅仅决定于x值而与z值无关。若X→→Y，Z为空，则称X→→Y为平凡的多值依赖。例如:Teaching(课程,教师,参考书)普通物理学光学原理物理习题集普通物理学光学原理物理习题集数学分析微分方程高等代数数学分析微分方程高等代数…李勇李勇李勇王军王军王军李勇李勇李勇张平张平张平

…物理物理物理物理物理物理数学数学数学数学数学数学…

参考书B教员T课程CTeaching∈BCNFTeaching具有唯一候选码(C，T，B)，即全码Teaching

4NF

定义:关系模式R〈U,F〉∈lNF,如果对于R的每个非平凡多值依赖X→→Y(YX)，

X都含有码,则称R〈U,F〉∈4NF。

4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖存在。因为根据定义，对于每一个非平凡的多值依赖X→→Y，

X都含有候选码，于是就有X→Y，所以4NF所允许的非平凡的多值依赖实际上是函数依赖。关系模式WSC（W，S，C）

W表示仓库，S表示保管员，C表示商品假设每个仓库有若干个保管员，有若干种商品每个保管员保管所在的仓库的所有商品每种商品被所有保管员保管

WSCW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S3C4W2S3C5W2S4C4W2S4C5W→→S且W→→C用下图表示这种对应

第四范式：4NFR<U,F>∈1NF,如果对于R的每个非平凡多值依赖X→→Y（Y￠X），X都含有码，则R〈U，F〉∈4NF例中:教员T多值依赖,课程C:C→→T是非平凡多值依赖,但C不含有码,所以Teaching,WSC都不属于4NF解决:模式分解消除非平凡且非函数依赖的多值依赖.(R1(C,T),R2(C,B))

应为平凡的多值依赖或函数依赖,既为4NF即：要么是平凡的多值依赖，要么是函数依赖。本例分解属于前者。小结：1NF（每个分量必须不可分）消除非属性对码的部分函数依赖2NF（每个非属性完全函数依赖于码）消除非属性对码的传递函数依赖3NF(所有非属性对任何码都不存在传递函数依赖）消除主属性对码的部分和传递函数依赖BCNF（每个决定因素都包含码）消除非平凡且非函数依赖的多值依赖4NF(平凡的多值依赖或函数依赖)

对于各种范式之间的联系有

5NF

4NFBCNF

3NF

2NF

lNF成立。

一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合,这种过程就叫规范化。理论上高级范式规范程度高,关系模式好.实际工程中要结合具体情况进行分析,确定数据库中的关系模式,例如P22例中R3保持在2NF更好

数据依赖的公理系统

定义6.11对于满足一组函数依赖F的关系模式R〈U,F〉,其任何一个关系r,若函数依赖X→Y都成立(即r中任意两元组t,s,若t[X]=s[X],则t[Y]=s[Y]),则称F逻辑蕴含X→Y。

Armstrong公理系统

对R〈U,F〉来说有以下的推理规则：Al.自反律(Reflexivity):若YXU,则X→Y为F所蕴含。A2.增广律(Augmentation):若X→Y为F所蕴含,且ZU,则XZ→YZ为F所蕴含A3.传递律(Transitivity):若X→Y及Y→Z为F所蕴含,则X→Z为F所蕴含。根据Armstrong公理系统

的A1，A2，A3这三条推理规则进一步可以得到下面三条推理规则：

合并规则：由X→Y，X→Z，有X→YZ。（A2，A3）

伪传递规则：由X→Y，WY→Z，有XW→Z。（A2，A3）

分解规则：由X→Y及ZY，有X→Z。（A1，A3）根据合并规则和分解规则，可得引理6.1

引理6.l

X→A1A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）定义6.l2在关系模式R<U，F>中为F所逻辑蕴含的函数依赖的全体叫作F的闭包，记为F+。

F={XY,YZ},F+计算是NP完全问题，

F+={Xφ,Yφ,Zφ,XYφ,XZφ,YZφ,XYZφ,XX,YY,ZZ,XYX,XZX,YZY,XYZX,XY,YZ,XYY,XZY,YZZ,XYZY,XZ,YYZ,XYZ,XZZ,YZYZ,XYZZ,XXY,XYXY,XZXY,XYZXY,XXZ,XYYZ,XZXZ,XYZYZXYZ,XYXZ,XZXY,XYZXZ,XZYZ,XYXYZ,XZXYZ,XYZXYZ}F={XA1,……,XAn}的闭包F+计算是一个NP完全问题

定义6.l2在关系模式R<U，F>中为F所逻辑蕴含的函数依赖的全体叫作F的闭包，记为F+。定义6.13设F为属性集U上的一组函数依赖，X

U，XF+={A|X→A能由F根据Armstrong公理导出}，

XF+称为属性集X关于函数依赖集F的闭包(左部为X的全体右部的集合,或出发点为X的全体右部的集合)引理6.2

设F为属性集U上的一组函数依赖，X，Y

U，X→Y能由F根据Armstrong公理导出的充分必要条件是Y

XF+用途将判定X→Y是否能由F根据Armstrong公理导出的问题，就转化为求出XF+

，判定Y是否为XF+的子集的问题算法6.1

求属性集X（X

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

输入：X，F 输出：XF+步骤：1）令X（0）=X，i=02）求B，这里B={A|(

V)(

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

W)}(左部为X（i）子集的那些右部并入XF+)3）X（i+1）=B∪X（i）

4）判断X（i+1）=X

（i）吗?5）若相等或X（i）=U,则X（i）就是XF+,算法终止。6）若否，则i=i+l，返回第（2）步。[例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。

(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。A,B之间无函数依赖关系,所以AB为一个候选码.例:求（AC）F+

Armstrong公理有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来

定义6.14如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。引理6.3F+=G+

的充分必要条件是

F

G+，和G

F+

定义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等价。[例]关系模式R<U，F>，其中：

U={Sno，Sdept，Mname，Cno，Grade}，

F={Sno→Sdept，Sdept→Mname，(Sno，Cno)→Grade}

设F’={Sno→Sdept，Sno→Mname，Sdept→Mname，(Sno，Cno)→Grade，

(Sno，Sdept)→Sdept}F是最小覆盖，而F’不是。因为：F’

-{Sno→Mname}与F’等价

F’

-{(Sno，Sdept)→Sdept}也与F’等价

定理6.3每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集。证明:构造性证明，找出F的一个最小依赖集。

(1)逐一检查F中各函数依赖FDi：X→Y，若Y=A1A2

…Ak，

k>2，则用{X→Aj

|j=1，2，…，k}来取代X→Y。(2)逐一检查F中各函数依赖FDi：X→A，令G=F-{X→A}，若AXG+，则从F中去掉此函数依赖。(3)逐一取出F中各函数依赖FDi：X→A，设X=B1B2…Bm，逐一考查Bi

（i=l，2，…，m），若A（X-Bi

）F+，则以X-Bi

取代X。例1：R<U,F>

U={A,B,C,D}F={A→B,B→A,B→C,A→C,C→A}

求Fm例2:R<U,F>U={A,B,C,D}F={A

→

C,C→

A,B→

AC,D→

AC,BD→

A}求Fm答见word把低一级的关系模式分解为若干个高一级的关系模式的方法不是唯一的只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义关系模式分解的标准三种模式分解等价的定义：⒈分解具有无损连接性⒉分解要保持函数依赖⒊分解既要保持函数依赖，又要具有无损连接性定义6.16关系模式R<U,F>的一个分解：ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}U=∪Ui，且不存在Ui

Uj，Fi为F在Ui上的投影定义6.17函数依赖集合{X→Y|X→Y

F+∧XY

Ui}的一个覆盖Fi叫作F在属性Ui上的投影i=1n关系模式R<U,F>的一个分解ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}

若R与R1、R2、…、Rn自然连接的结果相等，则称关系模式R的这个分解ρ具有无损连接性（Losslessjoin）具有无损连接性的分解保证不丢失信息无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题例：S-L（Sno，Sdept，Sloc）

F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}S-L∈2NF分解方法可以有多种：1.S-L分解为三个关系模式：SN(Sno) SD(Sdept) SO(Sloc)2.SL分解为下面二个关系模式：NL(Sno,Sloc) DL(Sdept,Sloc)3.将SL分解为下面二个关系模式：

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

第3种分解方法具有无损连接性S-L（Sno，Sdept，Sloc）

F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}S-L∈2NF模式分解：ND<(Sno,Sdept),Sno→Sdept>NL<(Sno,Sloc),Sno→Sloc>

问题:这种分解方法没有保持原关系中的函数依赖S-L中的函数依赖Sdept→Sloc没有投影到关系模式ND、NL上这样，现实中Sdept确定，办公地点Sloc确定的语义丢失，即：函数依赖Sdept→Sloc没有保持。

设关系模式R<U,F>被分解为若干个关系模式R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>（其中U=U1∪U2∪…∪Un，且不存在UiUj，Fi为F在Ui上的投影），若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的（Preservedependency）4.将SL分解为下面二个关系模式：

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

这种分解方法就保持了函数依赖第1种分解方法既不具有无损连接性，也未保持函数依赖，它不是原关系模式的一个等价分解第2种分解方法不保持函数依赖，不具有无损连接性第3种分解方法具有无损连接性，但未持函数依赖第4种分解方法既具有无损连接性，又保持了函数依赖三种模式分解的等价定义⒈分解具有无损连接性⒉分解要保持函数依赖⒊分解既要保持函数依赖，又要具有无损连接性如果一个分解具有无损连接性，则它能够保证不丢失信息。如果一个分解保持函数依赖，

则它可以减轻或解决各种异常情况。分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。以下分别讨论模式分解的无损连接和保持函数依赖[1]如果R只分解为两个关系模式定理6.5对于R<U,F>的一个分解{<R1<U1,F1>,R2<U2,F2>}，如果：

U1∩U2→U1-U2∈F+U1∩U2→U2-U1∈F+则该分解具有无损连接性例WPE(W#,P#,E#,QNT)分解为:EP(E#,P#,QNT)EW(E#,W#)此分解是否具有无损连接性?答:因为E#→W#∈F+

所以,此分解是否具有无损连接性[2]R分解为多个(>2个)关系模式算法6.2判别一个分解的无损连接性;定理6.4p190例5例:R(A,B,C,D,E)F:{A→D,E→D,D→B,BC→D,DC→A}分解为:R1(A,B)R2(A,E)R3(C,E)R4(B,C,D)R5(A,C)判断其无损连接性(是)ABCDER1(A,B)a1a2b13b14b15R2(A,E)a1b22b23b24a5R3(C,E)b31b32a3b34a5R4(B,C,D)b41a2a3a4b45R5(A,C)a1b52a3b54b55A→D,E→D,D→B,BC→D,DC→AABCDER1(A,B)a1a2b13b14b15R2(A,E)a1b22b23b14a5R3(C,E)b31b32a3b34a5R4(B,C,D)b41a2a3a4b45R5(A,C)a1b52a3b14b55R1(A,B);R2(A,E);R3(C,E);R4(B,C,D);R5(A,C)ABCDER1(A,B)a1a2b13b14b15R2(A,E)a1b22b23b14a5R3(C,E)b31b32a3b14a5R4(B,C,D)b41a2a3a4b45R5(A,C)a1b52a3b14b55ABCDER1(A,B)a1a2b13b14b15R2(A,E)a1a2b23b14a5R3(C,E)b31a2a3b14a5R4(B,C,D)b41a2a3a4b45R5(A,C)a1a2a3b14b55A→D,E→D,D→B,BC→D,DC→A

ABCDER1(A,B)a1a2b13b14b15R2(A,E)a1a2b23b14a5R3(C,E)b31a2a3a4a5R4(B,C,D)b41a2a3a4b45R5(A,C)a1a2a3a4b55ABCDER1(A,B)a1a2b13b14b15R2(A,E)a1a2b23b14a5R3(C,E)a1a2a3a4a5R4(B,C,D)a1a2a3a4b45R5(A,C)a1a2a3a4b55A→D,E→D,D→B,BC→D,DC→A例:R(A,B,C,D,E)F:{A→C,B→D,C→D,DE→C,CE→A}分解ρ={AD,AB,BE,CDE,AE}是否为R的无损连接分解?是定义6.16关系模式R<U,F>的一个分解：ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}U=∪Ui，且不存在Ui

Uj，Fi为F在Ui上的投影定义6.17函数依赖集合{X→Y|X→Y

F+∧XY

Ui}的一个覆盖Fi叫作F在属性Ui上的投影i=1n定义6.19若F+=

,则R<U,F>的分解ρ={<R1<U1,F1>,…,Rk<Uk,Fk>}保持函数依赖引理6.3F+=G+的充分必要条件FG+,和GF+

要判定FG+,只需逐一对F中的函数依赖,X→Y

考察Y是否属于XG++

定义6.19,引理6.3判别R的分解是否保持函数依赖R<U,F>U={A,B,C,D}F＝{A→B,B→C,C→D,D→A}判断关系模式R的分解ρ={AB,BC,CD}是否具有保持依赖性解:ΠAB(F)={A→B,B→A}(定义6.１７)

ΠBC(F)={B→C,C→B}ΠCD(F)={C→D,D→C}ΠAB(F)∪ΠBC(F)∪ΠCD(F)=G={A→B,B→A,B→C,C→B,C→D,D→C}又DG+=ABCD,D→A也被保持(定义6.19,引理6.3)

所以,该分解具有依赖保持性

求所有的候选码给定一个关系模式R<U，F>

U={A1，A2，…An}F中的函数依赖关系可以将属性分为如下四类：

L：仅出现在函数依赖集F左部的属性

R：仅出现在函数依赖集F右部的属性

LR：在函数依赖集F左右部都出现的属性

NLR：在函数依赖集F左右部都未出现的属性

问题:?有可能是候选码的属性

?肯定不是候选码的属性算法：1)把R的所有属性分为L、R、NLR和LR四类

并令X代表L、NLR类,Y代表LR类。2)求XF+

(简记为X+),如果X+包含了R的全部属性,则X为R的唯一候选码,转(5);否则,转(3)。3)在Y中取一个属性A,求(XA)+,如果它包含了R的全部属性,则转(4);否则,调换一个属性反复进行这一过程,直到试完所有Y中的属性。4)如果已经找到所有的候选码,则转(5);否则在Y中依次取两个、三个……求它们的属性闭包,直到其闭包包含R的所有属性。5)停止,输出结果。有如下结论：ZWYXF={W→Y,Y→W,X→W,X→Y,Z→Y,Z→W,XZ→W

}L类:{Z,X}又:(ZX)F+={X,Z,Y,W}所以:ZX是唯一候选码极小函数依赖集:F’={W→Y,Y→W,X→Y,Z→W

}SDIBOQIBOQSD已知分解,判别无损连接性和保持函数依赖的依据:算法6.2判别一个分解的无损连接性(定理6.4)定理6.5R分解为R1,R2具有无损连接性的充要条件定义6.19,引理6.3判别R的分解是否保持函数依赖未知分解.将低级关系模式分解为满足相应范式要求的关系模式:算法6.3（合成法）转换为3NF的保持函数依赖的分解。算法6.4转换为3NF既有无损连接性又保持函数依赖的分解算法6.5转换为BCNF的无损连接分解（分解法）R<U,F>U={A,B,C,D}F={A→C,C→A,B→AC,D→AC,BD→A}对关系模式R进行范式分析:1)求最小函数依赖集：Fm={A→C,C→A,B→C,D→C}2)候选码:(BD)3)R属于1NF4)转换为高级范式,例如3NF如何进行?R<U,F>U={A,B,C,D}F={A→C,C→A,B→AC,D→AC,BD→A}对关系模式R进行范式分析:求得：Fm={A→C,C→A,B→C,D→C}唯一候选码：

（BD）转换为3NF保持函数依赖的分解为:

ρ={AC,BC,DC}(算法6.3)转换为3NF既无损链接又保持函数依赖的分解为：ρ={AC,BC,DC,BD}(算法6.4)例１:R(A,B,C,D,E)F＝{A→Ｄ,Ｅ→D,Ｄ→Ｂ,ＢＣ→Ｄ,CＤ→

A}１）求Ｒ的侯选码２）将Ｒ分解为３ＮＦ且保持函数依赖

１）Ｒ的侯选码CE因为：仅在左部出现的属性(ＣＥ)+=ABCDE２）ρ={ＤＥ，ＢＣＤ，ＡＣＤ}因为:Fm={A→Ｄ,Ｅ→D,D→Ｂ,ＢＣ→D,CD→A}将R分解为3NF:

ρ={AD,DE,BD,BCD,ACD}除去包含关系,化简为:ρ={DE,BCD,ACD}

例２：R(Ｆ，Ｇ，Ｈ，Ｉ，Ｊ)F={Ｆ→Ｉ,Ｊ→Ｉ,Ｉ→Ｇ,ＧＨ→Ｉ,ＩＨ→Ｆ}

１）求Ｒ的侯选码２）判断ρ={FG,FJ,JH,IGH,FH}是否为无损分解．３）将Ｒ分解为３ＮＦ，具有无损连接并保持函数依赖

１）Ｒ的侯选码JH

因为：仅在左部出现的属性(JH)+=FGIJH２）由判断表ρ具有无损分解

3）Fm={Ｆ→Ｉ,Ｊ→Ｉ,Ｉ→Ｇ,ＧＨ→Ｉ,ＩＨ→Ｆ}则满足3NF具有保持依赖的分解为

ρ={JI,IGH,IHF}

经判断ρ不具有无损连接性令ρ=ρ∪{JH}

ρ={JI,IGH,IHF,JH}即为所求.例３：R(Ａ，Ｂ，Ｃ，Ｄ，Ｅ)F＝{Ａ→Ｃ,Ｃ→Ｄ,Ｂ→Ｃ,ＤＥ→Ｃ,ＣＥ→Ａ}１）求Ｒ的侯选码２）判断ρ={AD,AB,BC,CDE,AE}是否为无损分解．３）将Ｒ分解为BCNF，具有无损连接性．１）Ｒ的侯选码BE

因为：仅在左部出现的属性(BE)+=ABCDE２）由判断表ρ不具有无损分解F＝{Ａ→Ｃ,Ｃ→Ｄ,Ｂ→Ｃ,ＤＥ→Ｃ,ＣＥ→Ａ}

3）R不属于BCNF(并非决定因素都包含码)首先考虑A→C,A非码,将U分解为:U1={AC},F1={Ａ→Ｃ},R1是BCNF；U2={ABDE}，由F可推出F2

必包括：B→D

因为BE为码，所以R2不是BCNF(并非决定因素都包含码)对于R2,考虑B→D,B非码,将U2进一步分解为

{BD},{ABE}均属于BCNF

所以ρ={AC,BD,ABE}即为所求

设关系模式R(ABCD),在R上有五个相应的FD集及分解。①F={B→C,D→A},ρ={BC,AD}②F={AB→C,C→A,C→D},ρ={ACD,BC}③