null第4章 关系数据库理论 第4章 关系数据库理论 null4.1
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
化问题的提出
4.2 函数依赖
4.3 关系模式的分解*
4.4 关系模式的范式
4.5 关系模式的规范化 4.1 规范化问题的提出 4.1 规范化问题的提出 4.1.1 规范化理论的主要内容
关系数据库的规范化理论
函数依赖
范式(Normal Form)
模式设计 核心,是模式分解和设计的基础 模式分解的标准 4.1.2 不合理的关系模式存在的存储异常问题 4.1.2 不合理的关系模式存在的存储异常问题 教学管理数据库
SCD(SNo,SN,Age,Dept,MN,CNo,Score)
在此关系模式中填入一部分具体的数据
null该
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
出现的问题 数据冗余
插入异常
删除异常
更新异常 根本原因:属性间存
在着数据依赖关系 包罗万象 null一个好的关系模式应该具备以下四个条件:
(1)尽可能少的数据冗余;
(2)没有插入异常;
(3)没有删除异常;
(4)没有更新异常。 SCD (SNo,SN,Age,
Dept,MN,CNo,Score) S(SNo,SN,Age,Dept) SC(SNo,CNo,Score) D(Dept,MN) 关系模式分解:4.2 函数依赖 4.2 函数依赖 4.2.1 函数依赖的定义
定义4.1
SNo决定函数(SN,Age,Dept)
(SN,Age,Dept)函数依赖于SNo SCD (SNo,SN,Age,Dept,MN,CNo,Score) SNo一个学生SN,Age,Dept 惟一确定 惟一确定 4.2.2 函数依赖的逻辑蕴涵定义 4.2.2 函数依赖的逻辑蕴涵定义 定义4.2
设F是在关系模式R(U)上成立的函数依赖集合,X,Y是属性集U的子集,X→Y是一个函数依赖。如果从F中能够推导出X→Y,即如果对于R的每个满足F的关系r也满足X→Y,则称X→Y为F的逻辑蕴涵(或F逻辑蕴涵X→Y),记为F|=X→Y 。
定义4.3
设F是函数依赖集,被F逻辑蕴涵的函数依赖的全体构成的集合,称为函数依赖集F的闭包(Closure),记为F +。即:F +={ X→Y | F|=X→Y} 4.2.3函数依赖的推理规则 4.2.3函数依赖的推理规则 Armstrong公理
自反律:
如果YXU,则X→Y在R上成立如果YXU,则X→Y在R上成立
增广律 :
若X→Y在R上成立,且ZU,则XZ→YZ在R上也成立
传递律 :
若X→Y和Y→Z在R上成立,则X→Z在R上也成立 nullArmstrong公理推论
合并律(Union rule)
若X→Y和X→Z在R上成立,则X→YZ在R上也成立
伪传递律(Pseudotransitivity rule)
若X→Y和YW→Z在R上成立,则XW→Z在R上也成立
分解律(Decomposition rule)
若X→Y和ZY在R上成立,则X→Z在R上也成立
复合律(Composition)
若X→Y和W→Z在R上成立,则XW→YZ在R上也成立 4.2.4 完全函数依赖与部分函数依赖 4.2.4 完全函数依赖与部分函数依赖 设有关系模式R(U),U是属性全集,X和Y是U的子集:
如果X→Y,并且对于X的任何一个真子集X′,都有X′ Y,则称Y对X完全函数依赖,记作X → Y。
如果X→Y,并且对于X的某个真子集X′ ,有X’→Y,则称Y对X部分函数依赖,记作X → Y。
在关系模式SCD中,因为SNo Score,且CNo Score,所以有:(SNo,CNo) →Score。而SNo→Age,所以(SNo,CNo) →Age fpffp4.2.5 传递函数依赖 4.2.5 传递函数依赖 设有关系模式R(U),U是属性全集,X,Y,Z是U的子集
若X→Y,但Y X,而Y→Z(Y X,Z Y),则称Z对X传递函数依赖 ,记作:X → Z 。
如果Y→X,则X Y,这时称Z对X直接函数依赖,而不是传递函数依赖。 t函数依赖 完全函数依赖 部分函数依赖 传递函数依赖 4.2.6 属性集的闭包及其算法 4.2.6 属性集的闭包及其算法 X +={属性A|X→A在F +中}
定理4.3
X→Y能用函数依赖推理规则推出的充分必要条件是Y X +中
算法4.1
result=X
do
{
if F中有某个函数依赖Y→Z满足Y result
then result=result ∪ Z
}
while (result有所改变); 4.2.7 候选键的求解理论和算法 4.2.7 候选键的求解理论和算法 关键码的定义
如果X→U在R上成立(即X→U在F +中),那么称X是R的一个超键。
如果X→U在R上成立,但对X的任一真子集X′都有X′→U不成立(即X′→U不在F+中,或者X → U),那么称X是R上的一个候选键。
快速求解候选键的一个充分条件
对于给定的关系模式R(A1…,An)和函数依赖集F,可将其属性分为以下四类: fL类R类 N类 LR类 null定理4.4 对于给定的关系模式R及其函数依赖集F
(1)若X(X∈R)是L类属性,则X必为R的任一候选键的成员。
(2)若X(X∈R)是L类属性,且X +包含了R的全部属性,则X必为R的惟一候选键。
(3)若X(X∈R)是R类属性,则X不在任何候选键中。
(4)若X(X∈R)是N类属性,则X包含在R的任一候选键中。
(5)若X(X∈R)是R的N类和L类属性组成的属性集,且X +包含了R的全部属性,则X是R的惟一候选键。
null多属性函数依赖集候选键的求解算法
(1)属性分类(L、R、N和LR)
(2)若X +包含了R的全部属性,转(5);否则,转(3)。
(3)在Y中取一个属性A,求(XA) +,若它包含了R的全部属性,则转(4);否则,调换一属性反复进行这一过程,直到试完所有Y中的属性。
(4)如果已找出所有候选键,则转(5);否则在Y中依次取两个、三个、…,求它们的属性集的闭包,直到其闭包包含R的全部属性。
(5)停止,输出结果。令X代表L和N类,Y代表LR类4.2.8 函数依赖推理规则的完备性 4.2.8 函数依赖推理规则的完备性 定理4.5 函数依赖推理规则{A1,A2,A3}是完备的
(1)证明F中每个函数依赖V→W在r上成立。
(2)证明X→Y在关系r上不成立。
综合(1)和(2)可知,只要X→Y不能用推理规则推出,那么F就不逻辑蕴涵X→Y,也就是推理规则是完备的。
从函数依赖集F使用推理规则推出的函数依赖必定在F +中 F +中的函数依赖都能从F集使用推理规则集推出 正确性:完备性:4.2.9 函数依赖集的等价、覆盖和最小函数依赖集 4.2.9 函数依赖集的等价、覆盖和最小函数依赖集 等价定义4.8
关系模式R(U)的两个函数依赖集F和G,如果满足F += G + ,则称F和G是等价的函数依赖集。记作:F≡G。如果F和G等价,就说F覆盖G,或G覆盖F。
无关定义4.9
设F是属性集U上的函数依赖集,X→Y是F中的函数依赖。函数依赖中无关属性:
(1)如果A∈X,且F逻辑蕴涵(F-{X→Y}) ∪ {(X-A) →Y},则称属性A是X→Y左部的无关属性。
(2)如果A∈X,且(F-{X→Y}) ∪ {X→(Y-A)}逻辑蕴涵F,则称属性A是X→Y右部的无关属性。
(3)如果X→Y的左右两边的属性都是无关属性,则函数依赖X→Y称为无关函数依赖。 null定义4.10
设F是属性集U上的函数依赖集。如果Fmin是F的一个最小函数依赖集,那么Fmin应满足下列四个条件:
(1)Fmin+=F +;
(2)每个函数依赖的右边都是单属性;
(3)Fmin中没有冗余的函数依赖(即在Fmin中不存在这样的函数依赖X→Y,使得Fmin与Fmin-{X→Y}等价),即减少任何一个函数依赖都将与原来的F不等价;
(4)每个函数依赖的左边没有冗余的属性(即Fmin中不存在这样的函数依赖X→Y,X有真子集W使得Fmin-{X→Y} ∪ {W→Y}与Fmin等价),减少任何一个函数依赖左部的属性后,都将与原来的F不等价。null算法4.3 计算函数依赖集F的最小函数依赖集G
(1)对F中的任一函数依赖X→Y,如果Y=Y1,Y2,…,Yk(k≥2)多于一个属性,就用分解律,分解为X→Y1,X→Y2,…,X→Yk,替换X→Y,得到一个与F等价的函数依赖集G,G中每个函数依赖的右边均为单属性。
(2)去掉G中各函数依赖左部多余的属性。
(3)在G中消除冗余的函数依赖。4.3 关系模式的分解* 4.3 关系模式的分解* 4.3.1 模式分解问题
定义4.11
设有关系模式R(U),R=R1∪R2∪…∪Rk,ρ={R1,R2,…,Rk}。这里ρ称为R的一个分解,也称为数据库模式。泛关系模式泛关系数据库模式数据库实例 Rrρ={R1,R2,…,Rk} σ=
模式分解示意图 衡量关系模式的分解是否可取分解是否具有无损连接
分解是否保持了函数依赖4.3.2 无损连接分解 4.3.2 无损连接分解 定义4.12
设有R,F是R上的函数依赖集,ρ={R1,R2,…,Rk}。如果对R中满足F的每一个关系r,有r =ΠR1(r)∞ΠR2(r)∞…∞ΠRk(r),那么就称分解ρ相对于F是“无损连接分解” ;否则称为“损失分解”。
定理4.6 设ρ={R1,R2,…,Rk}是关系模式R的一个分解,r是R的任一关系,ri=ΠRi(r)(1≤i≤k),那么有下列性质:
(1)r mρ(r);
(2)若s=mρ(r),则ΠRi(s)=ri;
(3)mρ(mρ(r))=mρ(r),这个性质称为幂等性。4.3.3 无损分解的测试算法 4.3.3 无损分解的测试算法 (1)构造一个k行n列的
表格
关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载
Rρ,表中每一列对应一个属性Aj(1≤j≤n),每一行对应一个模式Ri(1≤i≤k)。如果Aj在Ri中,则在表中的第i行第j列处填上符号aj,否则填上bij。
(2)把表格看成模式R的一个关系,根据F中的每个函数依赖,在表中寻找X分量上相等的行,分别对Y分量上的每一列做修改:
如果列中有一个是aj,那么这一列上(X相同的行)的元素都改成aj;
如果列中没有aj,那么这一列上(X相同的行)的元素都改成bij(下标ij取i最小的那个)。
对F中所有的函数依赖,反复地执行上述的修改操作,一直到表格不能再修改为止(这个过程称为“追踪” 过程)。
(3)若修改到最后,表中有一行全为a,即a1a2…an,那么称ρ相对于F是无损连接分解。 null [例4-11] 设有关系模式R(A,B,C,D),R分解成ρ={AB,BC,CD},如果R上成立的函数依赖集F={B→A,C→D},那么ρ相对于F是否为无损连接分解? B→A a1C→D a4修改后的表格中的第二行为a1a2a3a4,
因此,ρ相对于F是无损连接分解 。null 定理4.7 设ρ={R1,R2}是关系模式R的一个分解,F是R上成立的函数依赖集,那么分解ρ相对于F是无损分解的充分必要条件是:
(R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)
当模式R分解成两个模式R1和R2时,若两个模式的公共属性(ø除外)能够函数决定R1(或R2)中的其他属性,这样的分解具有无损连接性。 4.3.4 保持函数依赖的分解 4.3.4 保持函数依赖的分解 定义4.13 设有关系模式R(U),F是R(U)上的函数依赖集,Z是属性集U上的一个子集,ρ={R1,R2,…,Rk}是R的一个分解。
F在Z上的一个投影用ΠZ(F)表示:ΠZ(F)={X→Y | X→Y∈F +∧XYZ};
F在Ri上的一个投影用ΠRi(F)表示:=ΠR1(r)∪ΠR2(r)∪…∪ΠRk(r);
如果有F +=( )+,则称ρ是保持函数依赖集F的分解。 一个无损连接分解不一定是保持函数依赖的一个保持函数依赖的分解也不一定是无损连接的4.4 关系模式的范式 4.4 关系模式的范式 各种范式之间的关系 4.4.1 第一范式 4.4.1 第一范式 定义4.14 如果关系模式R所有的属性均为简单属性,即每个属性都是不可再分的,则称R属于第一范式,简称1NF,记作R∈1NF。
1NF是关系模式应具备的最起码的条件。
第一范式可能具有大量的数据冗余,具有插入异常、删除异常和更新异常等弊端。
如关系模式SCD属于1NF,它既存在完全函数依赖,又存在部分函数依赖和传递函数依赖 。
克服这些弊端的方法是用投影运算将关系分解,去掉过于复杂的函数依赖关系,向更高一级的范式进行转换。 4.4.2 第二范式 4.4.2 第二范式 第二范式的定义
如果关系模式R∈1NF,且每个非主属性都完全函数依赖于R的主关系键,则称R属于第二范式,简称2NF,记作R∈2NF 。
如:关系模式TCS(T,C,S)
关系键 (T,C,S) ;主属性 T、C、S
不存在非主属性对主关系键的部分函数依赖,因此属于2NF。 从1NF关系中消除非主属性对主关系键的部分函数依赖,则可得到2NF如果R的关系键为单属性,或R的全体属性均为主属性,则R∈2NF null2NF规范化
2NF规范化是指把1NF关系模式通过投影分解,转换成2NF关系模式的集合。
[例4-15] 将SCD(SNo,SN,Age,Dept,MN,CNo,Score)规范为2NF。 学生
SD(SNo,SN,Age,Dept,MN )学生与课程联系
SC( SNo,CNo,Score)SCD非主属性对主键完全函数依赖。因此,SD∈2NF,SC∈2NF。 null2NF的缺点 数据冗余 插入异常 删除异常 更新异常 每个系名和系主任的名字存储的次数等于该系的学生人数 当一个新系没有招生时,有关该系的信息无法插入 某系学生全部毕业而没有招生时,删除全部学生的记录也
随之删除了该系的有关信息 更换系主任时,仍需改动较多的学生记录 4.4.3 第三范式 4.4.3 第三范式 第三范式的定义
如果关系模式R∈2NF,且每个非主属性都不传递函数依赖于R的主关系键,则称R属于第三范式,简称3NF,记作R∈3NF。
如:SC(SNo,CNo,Score)
函数依赖为(SNo,CNo)→Score,非主属性Score不传递函数依赖于主关系键(SNo,CNo),因此,SC∈3NF。
又如:SD(SNo,SN,Age,Dept,MN)
SNo→Dep和Dept→MN SNo → MN
非主属性MN与主关系键SNo间存在着传递函数依赖,所以SD 3NF。 主关系键 非主属性 t非主属性 主关系键 null3NF规范化
算法4.6 把一个关系模式分解为3NF,使它具有保持函数依赖性。
(1)如果Fmin中有一函数依赖X→A,且XA=R,则输出ρ={R},转(4)。
(2)如果R中某些属性与Fmin中所有依赖的左部和右部都无关,则将它们构成关系模式,从R中将它们分出去,单独构成一个模式。
(3)对于Fmin中的每一个函数依赖X→A,都单独构成一个关系子模式XA。若Fmin中有X→A1,X→A2,…,X→An,则可以用模式XA1A2…An取代n个模式XA1,XA2,…,XAn。
(4)停止分解,输出ρ。 null算法4.7 把一个关系模式分解为3NF,使它既具有无损连接性又具有保持函数依赖性。
(1)根据算法4.6求出保持函数依赖的分解:ρ={R1,R2,…,Rk}。
(2)判定ρ是否具有无损连接性,若是,转(4)。
(3)令ρ=ρ∪{X}={R1,R2,…,Rk,X},其中X是R的候选键。
(4)输出ρ。
[例4-17] 将SD(SNo,SN,Age,Dept,MN)规范到3NF。
(1)根据算法4.6求出保持函数依赖的分解:ρ={S(SNo,SN,Age,Dept),D(Dept,MN)}。null(2)判定ρ是否具有无损连接性
SD分解为ρ={S(SNo,SN,Age,Dept),D(Dept,MN)}时,S、D都属于3NF,且既具有无损连接性又具有保持函数依赖性。
3NF解决了2NF中存在的四个问题:Dept→MN a5a1a2a3a4a5 ,ρ相对于F是无损连接分解数据冗余降低了 不存在删除异常 不存在更新异常 不存在插入异常 4.4.4 BC范式 4.4.4 BC范式 BC范式的定义
如果关系模式R∈1NF,且所有的函数依赖X→Y(YX),决定因素X都包含了R的一个候选键,则称R属于BC范式,记作R∈BCNF。
BCNF具有如下性质 :
如果R∈BCNF,则R也是3NF 。
如果R∈3NF,则R不一定是BCNF 。
[例4-18] 设有关系模式SNC(SNo,SN,CNo,Score)
SNo SN。
存在着主属性对键的部分函数依赖:(SNo,CNo) SN,(SN,CNo) SNo,所以SNC不是BCNF。 无部分函数依赖和传递函数依赖,SNC∈3NF nullBCNF规范化
算法4.8 把一个关系模式分解为BCNF
(1)令ρ={R}。
(2)如果ρ中所有模式都是BCNF,则转(4)。
(3)如果ρ中有一个关系模式S不是BCNF,则S中必能找到一个函数依赖X→A且X不是S的候选键,且A不属于X,设S1=XA,S2=S-A,用分解{S1,S2}代替S,转(2)。
(4)分解结束,输出ρ。
[例4-19] 将SNC(SNo,SN,CNo,Score)规范到BCNF。
候选键:(SNo,CNo)和(SN,CNo)
函数依赖:
F={SNo→SN,SN→SNo,(SNo,CNo)→Score,(SN,CNo)→Score}null(1)令ρ={SNC(SNo,SN,CNo,Score)}。
(2)经过前面
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
可知,ρ中关系模式不属于BCNF。
(3)用分解{S1(SNo,SN),S2(SNo,CNo,Score)}代替SNC。
(4)分解结果为:S1(SNo,SN)描述学生实体;S2(SNo,CNo,Score)描述学生与课程的联系。
[例4-20] 设有关系模式TCS(T,C,S)
候选键 :(S,C)和(S,T)
函数依赖是 :F={(S,C)→T,(S,T)→C,T→C}
分解{TC(T,C),ST(S,T)}代替TCS
消除了函数依赖(S,T) C ,ST∈BCNF,TC∈BCNF 4.4.5 多值依赖与第四范式 4.4.5 多值依赖与第四范式 多值依赖的定义
假设学校中一门课程可由多名教师讲授,教学中他们使用相同的一套参考书。 关系CTB nullCTB转化成规范化的关系如下图所示:
C与T间的联系被称为多值依赖
多个T对应一个C
一个确定的C值,与其所对应的一组T值与B值无关 数据冗余大 插入异常 删除异常 null定义4.18 设有关系模式R(U),U是属性全集,X、Y、Z是属性集U的子集,且Z=U-X-Y
如果对于R的任一关系,对于X的一个确定值,存在Y的一组值与之对应,且Y的这组值仅仅决定于X的值而与Z值无关,此时称Y多值依赖于X,或X多值决定Y,记作X→→Y。
若X→→Y且Z=U-X-Y≠Φ,则称X→→Y是非平凡的多值依赖,否则称为平凡的多值依赖 。 null多值依赖公理及其推论
多值依赖公理
增广律:如果X→→Y,VWU,则WX→→VY。
传递律:如果X→→Y,Y→→Z,则X→→Z-Y。
补余律:如果X→→Y,则X→→U-X-Y 。
函数依赖公理与多值依赖混合公理
复制规则:从FD导出MVD,如果X→Y,则X→→Y。
接合规则:从MVD导出FD:如果X→→Y,ZY,且存在WU有W∩Y=ø,W→Z,则X→Z。
多值依赖推论
合并律:如果X→→Y,X→→Z,则X→→YZ。
伪传递律:如果X→→Y,WY→→Z,则XW→→(Z-W-Y)。
分解律:如果X→→Y,X→→Z,则X→→(Y∩Z),X→→(Y-Z),X→→(Z-Y) 。
混合伪传递律:如果X→→Y,XY→→Z,则X→→(Z-Y) 。null第四范式(4NF)定义
定义4.19 设有一关系模式R(U),U是其属性全集,X、Y是U的子集,D是R上的数据依赖集。如果对于任一多值依赖X→→Y,此多值依赖是平凡的,或者X包含了R的一个候选关键字,则称R是第四范式的关系模式,记为R∈4NF 。一个BCNF的关系模式不一定是4NF4NF的关系模式必定是BCNF的关系模式 4NF是BCNF的推广 null第四范式(4NF)的分解
(1)令ρ={R}。
(2)如果ρ中所有模式Ri都是4NF,则转(4)。
(3)如果ρ中有一个关系模式S不是4NF,则S中必能找到一个多值依赖X→→Y且X不包含S的候选键,Y-X≠ø,XY≠S,令Z=Y-X,设S1=XZ,S2=S-Z,用分解{S1,S2}代替S,由于S1∩S2=X,S1-S2=Z,所以有(S1∩S2)→→(S1-S2),分解具有无损连接性,转(2)。
(4)分解结束,输出ρ 。4.5 关系模式的规范化 4.5 关系模式的规范化 一个低一级范式的关系模式,通过模式分解转化为若干个高一级范式的关系模式的集合,这种分解过程叫作关系模式的规范化。
关系模式规范化的目的和原则
规范化的目的就是使结构合理,消除存储异常,使数据冗余尽量小,便于插入、删除和更新。
规范化的基本原则就是遵循“一事一地”的原则。 4.5.2 关系模式规范化的步骤4.5.2 关系模式规范化的步骤规范化过程 4.5.3 关系模式规范化的要求 4.5.3 关系模式规范化的要求 保证分解后的关系模式与原关系模式是等价的
等价的三种标准:
分解要具有无损连接性;
分解要具有函数依赖保持性;
分解既要具有无损连接性,又要具有函数依赖保持性。 保证不丢失信息 减轻或解决各种异常情况