第2篇 设计与应用开发篇
第6章 关系数据理论
复习笔记
一、问题的提出
关系要符合一个最基本的条件:每一个分量必须是不可分的数据项。满足了这个条件的关系模式就属于第一范式(1NF)。
01数据依赖
数据依赖是一个关系内部属性与属性之间的一种约束关系。这种约束关系是通过属性间值是否相等体现出来的数据间的相关联系。它是现实世界属性间相互联系的抽象,是数据内在的性质,是语义的体现。许多种类型的数据依赖中,最重要的是函数依赖(Functional Dependency,FD)和多值依赖(Multivalued Dependency,MVD)。
02关系模式存在的问题
(1)数据冗余太大;
(2)更新异常;
(3)插入异常;
(4)删除异常。
一个“好”的模式应当不会发生插入异常、删除异常、更新异常,数据冗余应尽可能少。
二、规范化
01函数依赖
(1)定义
设R(U)是属性集U上的关系模式,X,Y是U的子集。若对于R(U)的任意一个可能的关系r,r中不可能存在两个元组在X上的属性值相等,而在Y上的属性值不等,则称X函数确定Y或Y函数依赖于X,记作X→Y。
(2)完全依赖、部分依赖和传递依赖
①完全依赖
在R(U)中,如果X→Y,并且对于X的任何一个真子集X',都有X'↛Y,则称Y对X完全函数依赖,记作:
②部分依赖
若X→Y,但Y不完全函数依赖于X,则称Y对X部分函数依赖,记作:
③传递依赖
在R(U)中,如果
则称Z对X传递函数依赖。记为:
加上条件Y↛X,是因为如果Y→X,则X←→Y,实际上是,是直接函数依赖而不是传递函数依赖。
02码
(1)候选码
设K为R<U,F>中的属性或属性组合,若,则K为R的候选码(candidate key)。
(2)主码
若候选码多于一个,则选定其中的一个为主码(primary key)。包含在任何一个候选码中的属性称为主属性(prime attribute);不包含在任何候选码中的属性称为非主属性(nonprime attribute)或非码属性(non key attribute)。
(3)外码
关系模式R中属性或属性组X并非R的码,但X是另一个关系模式的码,则称X是R的外部码(foreign key),也称外码。
03范式
关系数据库中的关系是要满足一定要求的,满足不同程度要求的为不同范式。满足最低要求的叫第一范式,简称1NF;在第一范式中满足进一步要求的为第二范式,其余以此类推。范式是指符合某一种级别的关系模式的集合,R 为第几范式可以写成 R∈xNF。各种范式之间的关系是:5NF⊂4NF⊂BCNF⊂3NF⊂2NF⊂1NF,如图6-1所示。
图6-1 各种范式之间的天系
一个低一级范式的关系模式通过模式分解(schema decomposition)可以转换为若干个高一级范式的关系模式的集合,这种过程就叫规范化(normalization)。
042NF
2NF的定义:
若R∈1NF,且每一个非主属性完全函数依赖于任何一个候选码,则R∈2NF。
一个关系模式R不属于2NF,就会严生以下几个问题:
(1)插入异常;
(2)删除异常;
(3)修改复杂。
053NF
定义:关系模式R<U,F>中若不存在这样的码x,属性组y及非主属性z(z∈y),使得x→y,y→z成立,y↛x,则称R<U,F>∈3NF。
若R∈3NF,则每一个非主属性既不部分依赖于码也不传递依赖于码。
06BCNF
(1)定义
关系模式R<U,F>∈1NF,若X→Y且Y⊈X时X必含有码,则R<U,F>∈BCNF。
即关系模式R<U,F>中,若每一个决定因素都包含码,则R<U,F>∈BCNF。
由BCNF的定义可以得到结论,一个满足BCNF的关系模式有:
①所有非主属性对每一个码都是完全函数依赖。
②所有的主属性对每一个不包含它的码,也是完全函数依赖。
③没有任何属性完全函数依赖于非码的任何一组属性。
07多值依赖
(1)定义
设R(U)是属性集U上的一个关系模式。X,Y,Z是U的子集,并且Z=U-X-Y。关系模式R(U)中多值依赖X→→Y成立,当且仅当对R(U)的任一关系r,给定的一对(x,z)值,有一组r的值,这组值仅仅决定于x值而与z值无关。
(2)多值依赖的另一个等价的形式化的定义是
在R(U)的任一关系r中,如果存在元组t、s使得t[X]=s[X],那么就必然存在元组w、v∈r(w、v可以与s、t相同),使得w[X]=v[X]=t[X],而w[Y]=t[Y],w[Z]=s[Z],v[Z]=t[Z](即交换s、t元组的Y值所得的两个新元组必在r中),则Y多值依赖于X,记为X→→Y这里,X、Y是U的子集,Z=U-X-Y。
(3)性质
①对称性。
②传递性。
③函数依赖可以看作是多值依赖的特殊情况。
④若X→→Y,X→→Z,则X→→YZ。
⑤若X→→Y,X→→Z则X→Y∩Z。
⑥菪X→→Y,X→→Z,则X→→Y-Z,X→→Z-Y。
(4)多值依赖和函数依赖的区别
①多值依赖的有效性与属性集的范围有关。若X→→Y在U上成立,则在W(XY⊆W⊆U)上一定成立;反之则不然,即X→→Y在W(W⊂U)上成立,在U上并不一定成立。
②若函数依赖X→Y在R(U)上成立,则对于任何Y'⊂Y均有X→Y',成立。而多值依赖X→→Y若在R(U)上成立,却不能断言对于任何Y'⊂Y有X→→Y'成立。
084NF
(1)定义
关系模式R<U,F>∈1NF,如果对于R的每个非平凡多值依赖X→→Y(Y⊈X),X都含有码,则称 R<U,F>∈4NF。
(2)4NF与BCNF
4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。如果一个关系模式是4NF,则必为BCNF。一个关系模式如果已达到了BCNF但不是4NF,这样的关系模式仍然具有不好的性质。可以用投影分解的方法消去非平凡且非函数依赖的多值依赖。
(3)函数依赖和多值依赖
函数依赖和多值依赖是两种最重要的数据依赖。如果只考虑函数依赖,则属于 BCNF 的关系模式规范化程度已经是最高的了。如果考虑多值依赖,则属于4NF的关系模式规范化程度是最高的。
三、数据依赖的公理系统01Armstrong 公理系统
(1)定义
对于满足一组函数依赖F的关系模式R<U,F>,其任何一个关系r,若函数依赖X→Y,都成立(即r中任意两元组t、s,若t[X]=s[X],则t[Y]=s[Y]),则称F逻辑蕴涵X→Y.
(2)推理规则
①自反律
若Y⊆X⊆U,则X→Y为F所蕴涵。
②增广律
若X→Y为F所蕴涵,且Z⊆U,则XZ→YZ为F所蕴涵。
③传递律
若X→Y及Y→Z为F所蕴涵,则X→Z为F所蕴涵。
(3)重要定义
①在关系模式R<U,F>中为F所逻辑蕴涵的函数依赖的全体叫作F的闭包(closure),记为F+。人们把自反律、传递律和增广律称为Armstrong公理系统。
②设F为属性集U上的一组函数依赖,X、Y⊆U,XF+={A}X→A能由F根据Armstrong公理导出},XF+称为属性集X关于函数依赖集F的闭包。
③如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集,亦称为最小依赖集或最小覆盖(minimal cover)。
a.F中任一函数依赖的右部仅含有一个属性;
b.F中不存在这样的函数依赖X→A,使得F与F-{X→A}等价;
c.F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X→A}∪{Z→A}与F等价。
(4)引理
①X→A1A2…Ak成立的充分必要条件是X→Ai;成立(i=1,2,…,k)。
②设F为属性集U上的一组函数依赖,X、Y⊆U,X→Y能由F根据Armstrong 公理导出的充分必要条件是Y⊆ XF+。
③F+=G+的充分必要条件是F+⊆G+和G⊆F+。
(5)有效性和完备性
Armstrong公理系统是有效的、完备的。
①有效性
有效性指的是由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中。
②完备性
完备性指的是F+中的每一个函数依赖,必定可以由F出发根据Armstrong公理推导出来。
四、模式的分解
关系模式R<U,F>的一个分解是指:ρ={R1<U1,F1>,R2<U2,F2>,…,Rn<Un,Fn>}
01模式分解的3个定义
对于一个模式的分解是多种多样的,但是分解后产生的模式应与原模式等价。
对“等价”的概念有三种不同的定义:
(1)分解具有“无损连接性”;
(2)分解要“保持函数依赖”;
(3)分解既要“保持函数依赖”,又要具有“无损连接性”。
按照不同的分解准则,模式所能达到分离程度各不相同,各种范式就是对分离程度的测度。
02分解的无损连接性和保持函数依赖性
03模式分解的算法
关于模式分解的几个重要事实是:
(1)若要求分解保持函数依赖,那么模式分离总可以达到3NF,但不一定能达到BCNF。
(2)若要求分解既保持函数依赖,又具有无损连接性,可以达到3NF,但不一定能达到BCNF。
(3)若要求分解具有无损连接性,那一定可达到4NF。