第五章 关系数据理论.docx
- 文档编号:18386353
- 上传时间:2023-08-16
- 格式:DOCX
- 页数:15
- 大小:23.02KB
第五章 关系数据理论.docx
《第五章 关系数据理论.docx》由会员分享,可在线阅读,更多相关《第五章 关系数据理论.docx(15页珍藏版)》请在冰点文库上搜索。
第五章关系数据理论
第五章关系数据理论
5.1问题的提出
关系模式的五元组表示:
R(U,D,dom,F)
R:
关系名,符号化的元组语义;
U:
一组属性;
D:
属性组U中属性所来自的域;
dom:
属性到域的映射;
F:
属性组U上的一组数据依赖F。
D,dom对模式设计关系不大,故一般的关系模式表示为:
R〈U,F〉
例描述一个学生关系,学号(SNO),系名(SDEPT),系负责人(MN),课程(CNAME),成绩(G)。
S(U,F)
U={SNO,SDEPT,MN,CNAME,G}
F={SNO→SNAME,SDEPT→MN,(SNO,CNAME)→G}
或S(SNO,SDEPT,MN,CNAME,G,
SNO→SNAME,SDEPT→MN,(SNO,CNAME)→G)
F由现实世界的已知事实得到:
*一个系的有若干学生,但一个学生只属于一个系;
*一个系只有一名(正职)负责人;
*一个学生可以选修多门课程,每门课程有若干学生选修;
*每个学生学习每一门课程有一个成绩。
函数依赖图为:
SNOCNAMEG
SDEPTMN
*每个学生学习每一门课程有一个成绩
模式存在三个问题:
(1)插入异常:
系刚成立无学生无系及无负责人
(2)删除异常:
某系学生全部毕业系及其负责人信息丢失
(3)冗余大:
负责人更换每一元组都必须修改
模式分解为以下的模式不会发生插入异常、删除异常,且数据冗余较少。
S(SNO,SDEPT,SNO→SDEPT);
SG(SNO,CNAME,G,(SNO,CNAME)→G);
DEPT(SDEPT,MN,SDEPT→MN);
5.2规范化
5.2.1函数依赖
定义5.1设R(U)是属性集U上的关系模式。
X,Y是U的子集。
若对于R(U)的任意一个可能的关系r,r中不可能存在两个元组在X上的属性值相等,而在Y上的属性值不等,则称X函数确定Y或Y函数依赖于X,记作X→Y。
例SNO→SNAME,
SDEPT→MN,
(SNO,CNAME)→G
术语和记号:
·X→Y,但Y不属于X则称X→Y是非平凡的函数依赖。
(一般不特别声明,表示为非平凡的函数依赖)
·X→Y,但YX则称X→Y是平凡的函数依赖。
·若X→Y,则X叫做决定因素。
·若X→Y,Y→X,则记作X←→Y。
·若Y不函数依赖于X,则记作X→Y。
定义5.2在R(U)中,如果X→Y,并且对于X的任何一个真子集X′,都有X′→Y,则称Y对X完全函数依赖,记作:
XFY。
赖,记作:
XPY。
例(SNO,SDEPT)PMN
SNOFMN
定义5.3在R(u)中,如果X→Y,(YX),Y→X,Y→Z,则称Z对X传递函数依赖。
加上条件Y→X,是因为如果Y→X,则Y←→X,
实际上是X直接Z,是直接函数依赖而不是传递函数依赖。
5.2.2码
定义5.4设K为R〈U,F〉中的属性或属性组合,若KFU则K为R的侯选码。
若侯选码多于一个,则选定其中的一个为主码。
主属性:
包含在任何一个侯选码中的属性;
非主属性:
不包含在任何一个侯选码中的属性;
全码:
整个属性组是码。
例S(SNO,SDEPT,SAGE)中SNO是码;
SC(SNO,CNO,G)中属性组合(SNO,CNO)是码。
R(P,W,A)[演奏者、作品、听众]码为(P,W,A),即全码。
5.2.42NF
1NF:
满足基本关系条件的二维表。
定义5.6若R∈1NF,且每个非主属性完全函数依赖于码,则R∈2NF。
例不是2NF的例子
关系模式S-L-C(SNO,SDEPT,SLOC,CNO,G)
其中SLOC为学生的住处,并且每个系的学生住在同一个地方。
码为(SNO,CNO)
函数依赖有:
(SNO,CNO)FG
SNO→SDEPT,(SNO,CNO)PSDEPT
SNO→SLOC,(SNO,CNO)PSLOC,
SNO→SLOC(因为每个系的学生只住一个地方),如图所示
SNOSDEPT
G
CNOSLOC
虚线表示部分函数依赖。
非主属性SDEPT,SLOC并不完全函数依赖于码。
故S-L-C(SNO,SDEPT,SLOC,CNO,G)不符合2NF定义,即S-L-C∈2NF。
一个关系模式不属于2NF,会产生以下问题:
1.插入异常若插入一个学生SNO=S7,SDEPT=PHY,SLOC=BLD2,但该生还未选课,即无CNO,元组插不进S-L-C中。
(部分码值为空,学生固有信息不能插入)。
2.删除异常如果某个学生(S4)只选一门课(C3),现不选了,删除C3(主属性),则删除了整个元组,S4的其他信息也被删除了。
3.修改复杂某个选修了k门课的学生,从数学系(MA)转到计算机系(CS),必须无遗漏地修改k个元组中全部SDEPT,SLOC信息。
(本来只需修改此学生元组中的SDEPT分量)
主要原因:
SDEPT,SLOC对码不是完全函数依赖。
解决方法:
分解为两个关系模式
SC(SNO,CNO,G)
S-L(SNO,SDET,SLOC)
SNOSDEPT
GSNO
CNOSLOC
满足2NF(非主属性对码都是完全函数依赖)
5.2.53NF
定义5.7关系模式R〈U,F〉中若不存在这样的码X,属性组Y及非主属性Z(ZY)使得X→Y,(Y→X)Y→Z成立,则称R〈U,F〉∈3NF。
可以证明,若R∈3NF,则每一个非主属性既不部分依赖于码也不传递依赖于码。
例SC没有传递依赖,S-L中,由SNO→SDEPT,(SDEPT→SNO),SDEPT→SLOC,可得SNO传递SLOC,故SC∈3NF,而S-L∈3NF。
一个关系不是3NF,会数据异常(插入、删除、修改)。
解决办法将S-L分解为:
S-D(SNO,SDEPT)
D-L(SDEPT,SLOC)
不存在传递函数依赖。
5.2.6BCNF(扩充的第三范式)
定义5.8关系模式R〈U,F〉∈1NF,若X→Y且YX时X必含有码,则R〈U,F〉∈BCNF。
即关系模式R〈U,F〉中,若每一个决定因素都包含码,则R〈U,F〉∈BCNF。
推论:
一个满足BCNF的关系模式有:
·所有非主属性对每一个码都是完全函数依赖。
·所有的主属性对每一个不包含它的码,也是完全函数依赖。
·没有任何属性完全函数依赖于非码的任何一组属性。
·R∈BCNF则R∈3NF(因为排除了任何属性对码的传递依赖与部分依赖)
5.2.7多值依赖
例1学校中某一门课程由多名教员讲授,他们使用相同的一套参考书,每个教员可以讲授多门课程,每种参考书可以供多门课程使用。
可以用一个非规范化的关系来表示教员T,课程C和参考书B之间的关系
表5.1
课程C教员T参考书B
物理李勇普通物理学
王军光学原理
物理习题集
数学李勇数学分析
张平微分方程
高等代数
计算数学张平数学分析
周峰
规范化的二维表为:
表5.2Teaching
课程C教员T参考书B
物理李勇普通物理学
物理李勇光学原理
物理李勇物理习题集
物理王军普通物理学
物理王军光学原理
物理王军物理习题集
数学李勇数学分析
数学李勇微分方程
数学李勇高等代数
数学张平数学分析
数学张平微分方程
数学张平高等代数
关系模型TEACHING(C,T,B)的码是(C,T,B),即全码,故TEACHING∈BCNF。
但某一课程(如物理)增加一名讲课教员(如周英)时,必须插入多个(三个)元组:
(物理,周英,普通物理学);(物理,周英,光学原理);(物理,周英,物理习题集)。
同样,某一门课(如数学)要去掉一本参考书(如微分方程),必须删除多个(两个)元组:
(数学,张平,数学分析);(数学,李勇,数学分析)。
即TEACHING∈BCNF,但存在着数据异常。
原因:
存在多值依赖
定义5.9设R(U)是属性集U上的一个关系模式。
X,Y,Z是U的子集,并且Z=U-X-Y。
关系模式R(U)中多值依赖X→→Y成立,当且仅当对R(U)的任一关系r,给定的一对(x,z)值,有一组Y的值,这组值仅仅决定x值而与z值无关。
例如关系模式TEACHING中,C→→T。
多值依赖的形式化定义:
在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],v[Z]=s[Z],v[Y]=t[Y],w[Z]=s[Z],(即交换s,t元组的Y值所得的两个新元组必在r中),则Y多值依赖于X,记为X→→Y,(X,Y是U的子集,Z=U-X-Y)
若X→→Y,而Z=Φ(空),则称X→→Y为平凡的多值依赖。
例2关系模式WSC(W,S,C)中,W表示仓库,S表示管理员,C表示商品。
假设每个仓库有若干个保管员,有若干种商品。
每个保管员保管所在仓库的所有商品,每种商品被所有保管员保管。
列出关系如下:
WSC
W1S1C1
W1S1C2
W1S1C3
W1S2C1
W1S2C2
W1S2C3
W2S3C4
W2S3C5
W2S4C4
W2S4C5
按照语义对于W的每个值Wi,S有一个完整的集合与之对应而不论C取何值。
故W→→S。
由于C与S的完全对称性。
必然有W→→C成立。
Si1Si2…Sin{S}wi
Wi
Ci1Ci2…Cin{C}wi
多值依赖具有以下性质:
(1)对称性:
若X→→Y,则Y→→X,其中Z=U-X-Y。
(2)传递性若X→→Y,Y→→Z,则X→→Z-Y。
(3)函数依赖可以看作多值依赖的特殊情况。
即X→Y,则X→→Y。
(4)若X→→Y,X→→Z,则X→→YZ。
(5)若X→→Y,X→→Z,则X→→Y∩Z。
(6)若X→→Y,X→→Z,则若X→→Y-Z,X→→Z-Y。
多值依赖与函数依赖的区别:
(1)若X→→Y在U上成立则W(XYWU)上一定成立;反之则不然,即X→→Y在W(WU)上成立,在U上并不一定成立。
因为多值依赖的定义中不仅涉及属性组X和Y,而且涉及U中其余属性Z。
但是在关系模式R(U)中函数依赖X→Y的有效性仅决定于X,Y这两个属性集的值。
只要在R(U)的任何一个关系r中,元组在X和Y上的值满足函数依赖定义(5.1),则函数依赖X→Y在任何属性集W(XYWU)上成立。
(2)若函数依赖X→Y在R(U)上成立,则对于任何Y′Y均有
X→Y′成立。
而多值依赖X→→Y若在R(U)上成立,却不能断言任何Y′Y有X→→Y′成立。
5.2.84NF
定义5.10关系模式R〈U,F〉∈1NF,如果对于R的每个非平凡多值依赖X→→Y(YX),都含有码,则称R〈U,F〉∈4NF。
4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。
因为根据定义,对于每个非平凡的多值依赖X→→Y,X都含有侯选码,于是就有X→Y,所以4NF所允许的非平凡的多值依赖实际上是函数依赖。
如果一个关系模式是4NF,则必为BCNF。
例关系模式WSC中,W→→S,W→→C,为非平凡的多值依赖。
码为(W,S,C),W不是码,故WSC∈4NF。
一个关系模式如果达到了BCNF但不是4NF,仍存在不好的性质。
例WSC∈4NF,但是WSC∈BCNF数据冗余度较大。
解决方法:
投影分解为WS(W,S),WC(W,C)。
WS∈4NF,WC∈4NF
(虽然存在W→→S,但为平凡的多值依赖)
5.2.9规范化小结
规范化的基本思想是逐步消除数据依赖中不适合的部分。
1NF
↓消除非主属性对码的部分函数依赖
2NF
↓消除非主属性对码的传递函数依赖
3NF
↓消除主属性对码的部分和传递函数依赖
BCNF
↓消除非平凡且非函数依赖的多值依赖
4NF
5.3数据依赖的公理系统(Armstrong公理系统)
定义5.11对于满足一组函数依赖F的关系模式R〈U,F〉,其任何一个关系r,若函数依赖X→Y都成立(即r中任意两元组t,s,若t[X]=s[X],则t[Y]=s[Y]),则称F逻辑蕴涵X→Y。
Armstrong公理系统设U为属性集总体,F是U上的一组函数依赖,于是有关系模式R〈U,F〉。
对R〈U,F〉来说有以下的推理规则:
·A1自反律:
若YXU,则X→Y为F所蕴涵。
·A2增广律:
若X→Y为F所蕴含,且ZU,则XZ→YZ为F所蕴含。
·A3传递律:
若X→Y及Y→Z为F所蕴含,,则X→Z为F所蕴含。
由A1,A2,A3可得到以下推理规则:
定理5.1Armstrong推理规则是正确的。
·合并规则:
由X→Y,X→Z,有X→YZ。
·伪传递规则:
由X→Y,WY→Z,有XW→Z。
·分解规则:
由X→Y及ZU,WY→Z,有XW→Z。
引理5.1X→A1A2…Ak成立的充分必要条件是X→Ai成立(i=1,2,…,k)。
定义5.12在关系模式R〈U,F〉中为F所逻辑蕴含的函数依赖的全体叫做F的闭包,记为F+。
定义5.13设F为属性集U上的一组函数依赖,XU,XF+={A|X→A能由F根据Armstrong公理导出},XF+称为属性集X关于函数依赖集F的闭包。
由引理5.1容易得出:
引理5.2设F为属性集U上的一组函数依赖,X,YU,X→Y能由F根据Armstrong公理导出的充分必要条件是YXF+。
于是,判定Y是否能由F根据Armstrong公理导出的问题,就转化为求出XF+,判定Y是否为XF+的子集的问题。
此问题由算法5.1解决。
算法5.1求属性集X(YU)关于U上的函数依赖集F的闭包XF+。
输入:
X,F
输出:
XF+
步骤:
(1)令X(0)=X,i=0
(2)求B,这里B={A|(V)(W)(V→W∈F∧VX∧A∈W)}
(3)X(i+1)=B∪X(i)
(4)判断X(i+1)=X(i)吗?
(5)若相等或X(i+1)=U,则X(i+1)=就是XF+,算法终止。
(6)若否,则i=i+1,返回第
(2)步。
例1已知关系模式R〈U,F〉,
其中U={A,B,C,D,E};F={AB→C,B→D,C→E,EC→B,AC→B}。
求(AB)F+。
解由算法5.1,设X(0)=AB;
计算X
(1);逐一扫描F集合中各个函数依赖,找左部为A,B或AB的函数依赖。
得到两个:
AB→C,B→D。
于是X
(1)=AB∪CD=ABCD。
因为X(0)≠X
(1),所以再找出左部ABCD子集的那些函数依赖,又得到C→E,AC→B,于是X
(2)=X
(1)∪BE=ABCDE。
因为X
(2)已等于全部属性集合,所以(AB)F+=ABCDE。
对于算法5.1,令ai=|X(i)|,{ai}形成一个步长大于1的严格递增的序列,序列的上界是|U|,因此该算法最多|U|-|X|次循环就会终止。
定理5.2Armstrong公理系统是有效的、完备的。
定义5.14如果G+=F+,就说函数依赖集F覆盖G(F是G的覆盖,或G是F的覆盖),或F与G等价。
引理5.3F+=G+的充分必要条件是FG+,和G=F+。
定义5.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等价。
例2考察关系模式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}
根据定义5.15可以验证F是最小覆盖,而F′不是。
因为F′-{SNO→MN}与F′等价,F′-{(SNO,SDEPT)→SDEPT}与F′等价。
定理5.3每一个函数依赖集F均等价于一个极小函数依赖集Fm。
此Fm称为F的最小依赖集。
F的最小依赖集Fm不一定是唯一的,它与对各函数依赖FDi及X→A中X个属性的处置顺序有关。
例3F={AB,BA,BC,AC,CA}
Fm1={A→B,B→C,C→A}
Fm2={A→B,B→A,A→C,C→A}
5.4模式的分解
定义5.16关系模式R〈U,F〉的一个分解是指ρ={R1〈U1,F1〉,R2〈U2,F2〉,…Rn〈Un,Fn〉}
n
其中U=∪Ui,并且没有UiUi,1≤i,j≤n,Fi是F在Ui上的投影。
i=1
所谓“Fi是F在Ui上的投影”的确切定义是:
定义5.17函数依赖集合{X→Y|X|Y∈F+∧XYUi}的一个覆盖Fi叫做F在属性Ui上的投影。
5.4.1模式分解的三个定义
·分解具有“无损连接性”。
·分解要“保持函数依赖”。
·分解既要“保持函数依赖”,又要具有“无损连接性”。
一个关系分解为多个关系,相应地原来存储在一张二维表内的数据就要分散存储到多张二维表中,要使这个分解有意义,起码的要求是后者不能丢失前者的信息。
例4已知关系模式R〈U,F〉,其中U={SNO,SDEPT,MN},F={SNO→SDEPT,SDEPT→MN}。
R〈U,F〉的元组语义是学生SNO正在SDEPT系学习,其系主任是MN。
并且一个学生(SNO)只在一个系学习,一个系只有一名系主任。
R的一个关系见表。
由于R中存在传递函数依赖SNO→MN,会发生更新异常。
于是进行如下的分解:
ρ1={R1〈SNO,Φ〉,R2〈SDEPT,Φ〉,R3〈MN,Φ〉}
分解后诸Ri的关系ri是R在Ui上的投影,即ri=R[Ui]
r1={S1,S2,S3,S4},r2={D1,D2,D3,},r3={张五,李四,王一}。
SNOSDEPTMN
S1D1张五
S1D1张五
S1D2李四
S1D3王一
显然分解后的数据库丢失了原有的信息(例S1在哪个系学习)。
无损连接性:
分解后的数据库能够恢到原来的情况,不丢失信息。
Ri向R的恢复是通过自然连接来实现的。
R的另一种分解:
ρ2={R1〈{SNO,SDEPT},{SNO→SDEPT}〉,R2〈{SNO,MN},{SNO→MN}〉}
此分解具有“无损连接性”,但丢失了函数依赖SDEPT→MN,所以
不能“保持函数依赖”。
将R分解为:
ρ3={R1〈{SNO,SDEPT},{SNO→SDEPT}〉,R2〈{SDEPT,MN},{SDEPT→MN}〉}
可以证明分解ρ3既“保持函数依赖”,又具有“无损连接性”。
解决了更新异常,又没有丢失原数据库的信息。
关于模式分解的几个重要事实:
(1)若要求分解保持函数依赖,那么模式分离总可以达到3NF,但不一定能达到BCNF;
(2)若要求分解既保持函数依赖,又具有无损连接性,可以达到3NF,但不一定能达到BCNF;
若要求分解具有无损连接性,一定能达到4NF。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五章 关系数据理论 第五 关系 数据 理论