第六章 关系数据理论(NF)
关系模式由五部分组成,是一个五元组:
R(U,D,DOM,F)
D(属性U取值所来自的域),DOM(属性到域的映射)与模式设计关系不大,用三元组表示关系R<U,F>
第六章主要讲的就是范式(NF)!!!
1NF→2NF→3NF→BCNF→4NF
范式随这个顺序,逐渐更加规范化。
第一范式——1NF
关系,即二维表,每个分量都是不可分开的数据项。
即 严格的多行多列的二维表,不存在表中有表。
函数依赖
数据依赖:
- 函数依赖
- 多值依赖(在4NF之前穿插)
Y=f(X) ,记作 X→Y 称为Y函数依赖于X,X函数决定Y。
【引例】Student关系中,每个学生有唯一的学号,每个学生只属于一个系别。
则
Sname=f(Sno) ,Sno函数决定Sname,记为Sno→Sname
Sdept=f(Sno) ,Sno函数决定Sdept,记为Sno→Sdept
【定义】
设R(U)是一个属性集U上的关系模式,X和Y是U的子集。
若 对于R(U)的任意一个可能的关系r,r中不可能存在:
两个元组在X上的属性值相等,而在Y上的属性值不等,
则 称 X函数确定Y,或Y函数依赖于X,记作X→Y。
其中X称为决定因素,即左边的属性(组)为决定因素
【简化理解】
在关系R中,也就是在这个表中,取定X时,其对应的Y一定为一个确定值,也就是X与Y是一对一或者多对一(在下面传递函数依赖的例子中)的关系;一对多,多对多,都不满足函数确定的关系。
叫做函数依赖,也就是函数映射(一对一或多对一)的关系。
【栗子】Student(Sno,Sname,Ssex,Sage,Sdept),假设不允许重名。该关系中的函数依赖有:
- Sno→Sdept,Sno→Ssex,Sno→Sage
每个学生的学号确定,系别,性别,当前年龄确定 - Sno←→Sname
每个学生的学号确定,姓名确定;不重名,姓名确定,学号确定 - Sname→Ssex,Sname→Sage,Sname→Sdept
学生姓名确定,性别确定,年龄确定,系别确定(不重名)
性别如果确定,假定是女,不能确定任何其他属性。其他属性分析类似。
【分类】
1.平凡函数依赖 非平凡的函数依赖
平凡函数依赖即 自己可以确定自己的子集,没有什么意义。
2.完整函数依赖 部分函数依赖
任何真子集不能函数确定的为完全的,即少一个都不能确定。部分的函数依赖,顾名思义,就是部分的属性就可以确定。
SC表中(Sno,Cno)→Grade就是完全函数依赖,因为Sno和Cno任何一个都不能确定Grade。
3.传递函数依赖
要注意Y→X不成立的条件!!!
【例】Std(Sno,Sdept,Mname)中,有:
Sno→Sdept,Sdept→Mname,并且Sdept→Sno不成立,所以有Sno→Mname,Mname传递函数依赖于Sno。
(这里的函数依赖就是多对一的情况,是指多个Sno对应相同的一个Mname的值,Sno确定为一个特定值时,Mname只有一个值)
码
- 候选码 —— 可以唯一确定一个元组
- 超码 —— 某个真子集为候选码;候选码为最小的超码
- 主码 —— 认为选定的一个候选码
- 全码 —— 整个属性组是码 All-key
- 外码 —— 关系R中不是码的属性,是另一关系的码
- 主属性与非主属性 —— 所有候选码的属性为主属性,其他为非主属性
找候选码:从单个开始找,若找到单个为候选码,将所有单个属性组试完后,不必找两个的;若单个都不能作为码,则找两个的,就要把两个的所有组合情况都试验一遍,以此类推。
范式和规范化
1.范式:符合某一级别的关系模式的集合
各级范式,约束性,规范性逐渐增强。
2.规范化:一个低一级的范式,通过模式分解可以转换为若干个高一级范式的关系模式的集合的过程。“拆”
2NF
不存在部分函数依赖!!!
步骤:①找函数依赖关系→②找候选码→③找非主属性→④看是否完全依赖
【例6.4】S-L-C(Sno,Sdept,Sloc,Cno,Grade),Sloc为学生住址,同一系的学生住在同一个地方。
①函数依赖:
Sno→Sdept,Sdept→Sloc,Sno→Sloc(传递)(Sno,Cno)→Grade(完全)
(Sno,Cno)→Sdept(部分)
(Sno,Cno)→Sloc(部分)
②候选码 —— 可以确定其他所有属性
(Sno,Cno)
③非主属性
Sdept,Sloc,Grade
④是否完全依赖
(Sno,Cno)→Grade(完全)
(Sno,Cno)→Sdept(部分)
(Sno,Cno)→Sloc(部分)
否,不是2NF
【模式分解——拆】
SC(Sno,Cno,Grade)
S-L(Sno,Sdept,Sloc)
将有问题的部分函数依赖拆出来,同时保证不丢关系
3NF
不存在传递函数依赖!!!
【例】在上述S-L-C分解成为第二范式后中的SC表没有传递函数依赖,为3NF,S-L表中:
Sno→Sloc(传递),不满足
【拆】
S-L拆为:
S-D(Sno,Sdept)
D-L(Sdept,Sloc)
只有两个属性值,都为3NF
BCNF
扩展的第三范式。
在满足3NF后,才能满足BCNF。
决定因素必含有码!!!
步骤:(首先保证没有部分函数依赖和传递函数依赖关系)①找函数依赖关系→②找候选码→③决定因素是否包含码
【例子】关系模式 STJ(S,T,J)中,S表示学生,T表示教师,J表示课程。每一教师只教一门课。每门课有若干教师,某一学生选定某门课,就对应一个固定教师。
①函数依赖:
T→J,(S,J)→T,(S,T)→J
②候选码:
(S,J),(S,T)
③非主属性:无
所以没有部分函数依赖和传递函数依赖(这两者都涉及到非主属性)
④决定因素为T,(S,J),(S,T)。其中T不包含任何码,所以该关系模式不属于BCNF。
多值依赖X→→Y
每个X值对应一组Y值,这组值与Z值无关。这里注意X+Y+Z=U
当Z为空的时候,为平凡的多值依赖
Z不为空,为非平凡多值依赖
这里比较难理解,放PPT上的一个图,就容易多了。
就像这个图中的,不是规范化的表,但是可以很好的理解多值依赖。
课程C→→T,对于每个C值,都有对应的一组T值,而且这组T值与B值无关。
再找多值依赖的时候,可以先将关系化为上述图片的格式,比较容易看出来。
4NF
是4NF的前提是要是BCNF。
候选码的求解理论和算法
闭包:一个属性直接或间接推导出来的属性的集合。
属性分类:
- L类:只出现在函数依赖左边的属性
- R类:只出现在函数依赖右边的属性
- LR类:出现在函数依赖两边的属性
- N类:没有出现在函数依赖的属性
定理及推论:(为了方便记忆,自己总结的)
1.候选码必包含L类属性,必不包含R类属性。
2.N类属性必包含在任一个候选码中。
3.若X为L类属性或L∪N的属性集,X的闭包包含U,则X为唯一候选码。
注:当存在X←→Y的时候,可以替换,即若XZ为码,则YZ也为码。
【例子】U=(A,B,C,D,E,F),F={A→BC,BC→A,BCD→EF,E→C}
(1)L=(D),R=(F),LR=(A,B,C,E),N=空;
(2)L∪N=(D),D的闭包只有D
(3)候选码不会有F,逐个配对
AD闭包=ABCDEF=U
BD闭包=BD
CD闭包=CD
DE闭包=CDE
AD为候选码,因为A←→BC,所以DBC也为候选码,需要开始找三个属性组的。三个不会包含A,因为那样是超码,一定包含D。
DBE闭包=CDBEAF=U
DCE闭包=DCE
所以候选码为DA,DBC,DBE。
总结:
习题
附加题
【心得】这章主要是范式,概念比较多,有些符号比较难打,就将PPT上的定义截屏了,记住几个范式的注重点就好。在后面的做题中,感觉多值依赖和4NF比较难理解,做题的时候也有些模糊,多个候选码的情况下进行模式分解也有些糊。刚开始在老师讲解候选码的另一个求解方法之前做题,自己求解的候选就很没有底气,后面讲的这个闭包和属性分类的方法理解了之后,做题真的很有效,感觉求解出来的候选码很正确。另外在证明题中,也是感觉证明的很牵强。有时候判别第三范式的传递也会有些迷惑。
帅琦Q: 你好,为什么推到递推公式时,分母中ui+1-ui=1?
蓝海岛中月: 9.(1)感觉这么写会好点 SELECT PNO,SUM(QTY) FROM SAN_JIAN GROUP BY PNO;
ckssss44: 很好的资源
Ginkgo biloba L: 这里是不是假定u2-u1=1了
处眠: 请问这个如何理解包含B个块的文件排序代价 = (2B)+(2B*log2 B)