数据库笔记(四)关系模式的规范化

发布于 / 笔迹 / 12 条评论

这次不想像以前那样详细讲解知识点了,重点讲解函数依赖五种范式,以及多值依赖与第四范式间关系。文中可能存在错别字,理论上不影响阅读。

函数依赖

引言

关系模式中的不同属性之间通常存在一定的依赖关系,而最基本的依赖关系是函数依赖。所谓函数依赖是指关系模式中不同属性间的一种约束关系,即一个属性或一组属性的值可以决定该关系中其他属性的值

例如,一个学生的学号可以决定一个学生的姓名,即学号属性决定了姓名属性的值,一个学生的学号和他所选课程的课程号可以决定他这门课程的成绩,即学号属性和课程号属性决定了学生该门课程的成绩属性值。

关系模式中不同属性间的函数依赖是否存在完全取决于数据的语义

例如,在职工信息表中,如果一个职工只允许有一个电话号码,那么,一旦职工号确定了,该职工的电话号码也就确定了,即职工号和电话号码之间存在函数依赖:职工号→电话号码。但是,如果一个职工允许有多个电话号码,则职工号与电话号码之间就不存在这种依赖关系了,即职工号\→电话号码。【在这用\→表示不函数依赖,下同】因此,确定不同属性间的函数依赖,既不能根据数据的当前值来归纳,也不能凭“想当然”,要根据数据的语义来决定

为了方便讨论,对一些符号进行约束:

  • R 表示一个关系模式;
  • U={A1,A2…An}是R中所有属性的集合;
  • FD是R中的一个函数依赖,而F是R中所有函数依赖的集合;
  • r是R所取的一个当前值。

函数依赖的定义

假设R是一个关系模式,U是R中的所有属性的集合,X、Y⊆U。对于R中的任意两个元组t1,t2∈r,若t1[X]=t2[X],有t1[Y]=t2[Y],则称X函数决定Y或Y函数依赖于X,记作X→Y,X又称为决定子。

这里ti[X]表示元组ti在属性集X上的值。函数依赖是对关系R的一切可能当前值r进行定义的。对于当前值r的任意两个元组,如果X值相同,则一定要求Y值也相同,即有一个X值就有一个Y值与之对应,或者说Y的值由X决定。这种依赖称为函数依赖F。

确定关系R的一个函数依赖是否成立,需要弄清数据的语义,而语义是现实世界的反映,不是主观的臆断。

  • 示例关系r如表所示
A B C D
a1 b1 c1 d1
a1 b2 c1 d2
a2 b2 c2 d2
a2 b2 c2 d3
a3 b3 c2 d4

从表中可以看出函数依赖A→C是满足的,但是,函数依赖C→A是不满足的,因为c2在A上有两个不同的值a2和a3。

由上可知,函数依赖主要表现为对属性值的约束。

平凡函数依赖

若Y⊆X,显然X→Y成立,这种函数依赖称为平凡函数依赖。

每个关系中都会存在平凡函数依赖,例如X→X在所有包含属性X的关系中都是满足的。平凡函数依赖必然成立,平常所指的函数依赖都指非平凡函数依赖。

完全函数依赖与部分函数依赖

假设R是一个关系模式,U是R中所有属性的集合。X、Y⊆U。如果X→Y,并且对于X的任何一个真子集Z,都不存在Z→Y,则称Y对X完全函数依赖,记作X-f->Y。否则,称Y对X部分函数依赖,记作X-p->Y

举例说明,在关系R(学号(S#),课程号(C#),成绩(G),任课教师姓名(TN),教师所在系名(D))中存在以下函数依赖的集合:
F = {{S#,C#}→G,C#→TN, TN→D}
其中{S#, C#}是主键,而主键能够函数决定关系中所有主属性,故有{S#, C#}→TN,又每门课程(非每种课程)只有一位任课教师,故有C#→TN。既然C#→TN{S#, C#}→TN同时成立,而C#是{S#, C#}的一个真子集,则{S#, C#}-p->TN,另外,{S#, C#}→G,而{S#, C#}的任何一个真子集都不能函数决定G,则{S#, C#}-f->G

传递函数依赖

假设R是一个关系模式,U是R中所有属性的集合。X、Y、Z⊆U。如果X→YY\→XY→Z,则称Z对X传递函数依赖。记X-t->Y

举例,有一个含有A、B、C属性的关系R满足函数依赖: {A→B,B→C},根据传递律,可得到:A→C。(注意: 如果关系中只给出A→B,而没有给出B\→A时,一般默认B\→A成立)。

说明

  • 函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件,而是指R的所有关系均要满足的约束条件。
  • 函数依赖是语义范畴的概念,只能根据数据的语义来确定函数依赖。例如“姓名→年龄”这个函数依赖只有在不允许同名人的条件下成立。

  • 候选键:设R(U)是属性集U上的关系模式,K⊆U,如果K-f->U,则K为R的候选键(即K能决定R中其他任意属性)。如果候选键多于一个,则选定其中的一个候选键作为识别元组的主键。
  • 主属性:包含在任意一个候选键中的属性。
  • 非主属性:不包含在任意候选键中的属性。

候选键包含了关系模式的所有属性称为全键


范式

关系模式的范式主要有第一范式(1NF)、第二范式(2NF)、第三范式(3NF)、BCNF等四种,更复杂的有第四范式(3NF)和第五范式(5NF)。

第一范式(1NF)

如果关系模式的所有属性都是不可再分的数据项,则称该关系属于第一范式,记作R∈1NF

  • 满足第一范式关系中的属性不能是集合属性。
  • 第一范式是所有关系模式必须满足的约束条件。
  • 所有关系至少属于第一范式。

下面举例说明。

  • 课程计划(非第一范式)

  • 课程计划(第一范式)
课程名称 讲课时数 实验时数
数据结构 64 24
数据库原理 48 12

实例讲解

假设某企业设计了一个关系模式W,用来对各车间职工完成生产定额的情况进行考核,同时也提供职工个人信息、工种定额信息以及各车间主任信息。该模式由以下属性构成:
W(日期,工号,姓名,工种,超额,定额,车间主任)
每个员工在不同的日期有不同的生产定额完成情况,如表。

  • 各车间职工完成生产定额情况表
日期 工号 姓名 工种 定额 超额 车间 车间主任
05.1 101 江灵 车工 80 22% 工具 赵昊
05.1 102 北辰 车工 80 17% 金工 谢皓
05.1 103 钟航 钳工 75 14% 工具 赵昊
05.1 104 欧阳 打杂 70 24% 金工 谢皓
05.2 101 江灵 车工 80 15% 工具 赵昊
05.2 102 北辰 车工 80 25% 金工 谢皓
05.2 103 钟航 钳工 75 16% 工具 赵昊
05.2 104 欧阳 打杂 70 26% 金工 谢皓

该模式有唯一的候选键{日期,工号},主属性是日期工号,其他为非主属性。根据数据的语义,可以给出关系W上满足的函数依赖集F:
F={{日期,工号}→超额工号→姓名工号→车间工号→工种工种→定额车间→车间主任工号→车间主任}
关系W中的每一个属性都是原子项,故W中存在第一范式。但是W模式存在以下问题:
① 数据冗余大
② 更新异常
③ 插入异常
④ 删除异常
出现上述问题的原因在于模式中存在着各种数据依赖关系。比如:{日期,工号}→超额工号→姓名,这样就出现了部分函数依赖{日期,工号}→姓名,再比如工号→车间车间→车间主任,这样就出现了传递函数依赖。 部分函数依赖以及传递函数依赖的存在使得关系W中存在大量的数据冗余等问题,要想解决这些问题就必须想办法消除关系中存在的部分函数依赖和传递函数依赖。我们往下看。

第二范式(2NF)

若关系R∈1NF,且它的每一非主属性都完全依赖于候选键(不存在部分函数依赖),则称R属于第二范式,记为R∈2NF
简单点说就是在1NF上消除非主属性与候选键间的部分函数依赖。

对上面讨论的关系W进行分解,分解为W1和W2两个关系,以消除部分依赖于候选键的部分,使之满足2NF,即W→W1+W2W1∈2NFW2∈2NF

分解后关系中的值如W1、W2表所示。W1的候选键为工号,主属性为工号,其他为非主属性;W2的候选键为{日期,工号},主属性是日期工号,非主属性为超额。

  • W1(W1∈2NF)
工号 姓名 工种 定额 车间 车间主任
101 江灵 车工 80 工具 赵昊
102 北辰 车工 80 金工 谢皓
103 钟航 钳工 75 工具 赵昊
104 欧阳 打杂 70 金工 谢皓
  • W2(W2∈2NF)
日期 工号 超额
05.1 101 22%
05.1 102 17%
05.1 103 14%
05.1 104 24%
05.2 101 15%
05.2 102 25%
05.2 103 16%
05.2 104 26%

分解后,原函数依赖集F在W1和W2上的投影分别为:

  • F1={工号→姓名工号→工种工号→定额工号→车间工号→车间主任工种→定额车间→车间主任},因为工号→工种工种→定额,故工号→定额存在传递函数依赖,同理可知,工号→车间主任也存在传递函数依赖
  • F2={{日期,工号}→超额},F2为完全函数依赖

由于W1中仍存在传递函数依赖引起的数据冗余等问题,所以需要继续对关系模式W1进行分解,以消除其中的传递函数依赖我们接着往下看。

第三范式(3NF)

若关系R∈2NF,且它的每一非主属性都不传递依赖于候选键,则称R属于第三范式,记为R∈3NF
简单点说就是在2NF上消除非主属性与候选键的传递函数依赖。

对上面讨论的关系W1进一步分解,分解为W11+W12+W13。其中W11的候选键为工种,非主属性是定额;其中W12的候选键为车间,非主属性是车间主任;其中W13的候选键为工号,非主属性是姓名、工种、车间。

  • W11(W11∈3NF)
工种 定额
车工 80
车工 80
钳工 75
打杂 70
  • W12(W12∈3NF)
车间 车间主任
工具 赵昊
金工 谢皓
工具 赵昊
金工 谢皓
  • W13(W13∈3NF)
工号 姓名 工种 车间
101 江灵 车工 工具
102 北辰 车工 金工
103 钟航 钳工 工具
104 欧阳 打杂 金工

分解后,原函数依赖集F在W11、W12和W13上的投影分别为:

  • F11={工种→定额}
  • F12={车间→车间主任}
  • F13={工号→姓名工号→工种工号→车间}

此时,W11、W12和W13已不存在部分函数依赖和传递函数依赖,所以都属于第三范式。

第三范式基本消除了数据冗余以及数据冗余带来的一些操作异常问题,一般都能取得较满意的结果。但是在某些情况下,3NF仍然会出现问题。原因是没有对主属性和候选键之间的关系给出任何限制(我们上面讨论的都是非主属性和候选键之间的依赖关系),于是出现主属性部分依赖或传递依赖于候选键的情况,也会使关系性能变坏。解决主属性对候选键的部分函数依赖的办法仍采用关系分解,故出现了BCNF我们继续往下看。

BCNF

如果R∈3NF,且不存在主属性候选键之间的传递或部分函数依赖。则称R属于BC范式,记R∈BCNF
即在一个关系模式的所有非平凡函数依赖中,R的每一个决定子都是候选关键字(决定子概念见上文函数依赖定义部分,即X→Y中的X)。

举例说明,假定一个学生学习多门课程,一个教师只能教授一门课程,但同一门课程可以由好几个教室担任。如表SCT所示。

  • SCT表
学生 课程 教师
江灵 数字逻辑 宁倩
钟航 数字逻辑 宁倩
北辰 数字逻辑 阳彬
北辰 数据结构 迅哥
岳麓 离散数学 傅桓
胡士 数据库原理 安毅

从表中可以看出,候选键为{学生,教师}{学生,课程},因此,该关系的所有属性都是主属性,即SCT表中不存在非主属性,SCT属于3NF。

当选择{学生,教师}作为候选键时,SCT的函数依赖集F={{学生,教师}→课程教师→课程},故SCT上存在主属性对候选键的部分函数依赖,因此SCT不属于BCNF。

如果将SCT表分解为{学生,教师}{学生,课程},则没有任何属性对候选键的部分函数依赖和传递函数依赖,故{学生,教师}∈BCNF{学生,课程}∈BCNF

3NF与BCNF的关系:

  • 如果关系模式R∈BCNF,则必定有R∈3NF。
  • 如果R∈3NF,且R只有一个候选键,则必定有R∈BCNF。

多值依赖与第四范式

这个不知道该怎么讲,先不说定义,用通俗的语言讲一下,再举个例子吧。

首先说一下多值依赖(在这都指非平凡的多值依赖),一个关系,至少存在三个属性(A、B、C),才能存在多值依赖。对于每一个A值,有一组确定的B值和C值,并且这组B的值独立于这组C的值。

举个例子,建立课程、教师和教材之间的关系模型,我们规定,每门课程有对应的一组教师每门课程也有对应的一组教材一门课程使用的教材和教师没有关系。这样我们首先肯定有三个实体表,分别表示课程,教师和教材。现在我们要建立这三个对象的关系,于是我们建立的关系表,定义如下:{Course,Teacher,Book}这三列作为联合主键(即超键)。

Course Teacher Book
英语 Bill 人教版英语
英语 Bill 美版英语
英语 Jay 美版英语
高数 Mary 人教版高数
高数 Dave 美版高数

这个表只有一个主键,没有非键属性,所以肯定满足BC范式,但是却存在多值依赖导致的异常。假如我们下学期想采用一本新的英版高数教材,但是还没确定具体哪个老师来教,那么我们就无法在这个表中维护Course高数和Book英版高数教材的的关系。解决办法是我们把这个多值依赖的表拆解成2个表,分别建立关系。

拆分后的表如下:

Course Teacher
英语 Bill
英语 Jay
高数 Mary
高数 Dave
Course Book
英语 人教版英语
英语 美版英语
高数 人教版高数
高数 美版高数

第四范式的定义很简单:已经是BC范式,并且不包含多值依赖关系。当然,如果最开始一门课程使用的教材和教师有关系,那么原始最初的关系模式就满足第四范式。

除了第四范式外,我们还有更高级的第五范式和域键范式(DKNF),第五范式处理的是无损连接问题,这个范式基本没有实际意义,因为无损连接很少出现,而且难以察觉。而域键范式试图定义一个终极范式,该范式考虑所有的依赖和约束类型,但是实用价值也是最小的,只存在理论研究中。

补充

多值依赖的定义:设R(U)是一个属性集合U上的一个关系模式,X, Y, 和Z是U的子集,并且Z=U-X-Y,多值依赖X→→Y成立当且仅当对R的任一个关系r,r在(X,Z)上的每个值对应一组Y的值,这组值仅仅决定于X值而与Z值无关。若X→→Y,而Z为空集,则称X→→Y为平凡的多值依赖。否则,称X→→Y为非平凡的多值依赖。

可以看出,如果把上面的一组改为一个,那么多值依赖就变成了函数依赖。当然一个值组成的组也是组,所以说,函数依赖是多值依赖的特殊情况。

对于R中的每个非平凡多值依赖X→→Y(Y不属于X),X都含有候选码,则R属于4NF。

分析:对于每一个非平凡多值依赖X→→Y,X若含有候选码,也就是X->Y,所以4NF所允许的非平凡多值依赖是函数依赖。

问题详述:老师,请问"任何二元关系都属于4NF”这种说法对吗?我看数据库系统概论学习指导与习题解答上面说这句话是对的,但是丁康宝,施伯乐他们编的书上面说这句话是错的,上面解释到”有R(AB)但r=rA×rB不一定成立”.请问这句话到底对不?谢谢!
解答:这句话是正确的, 对于任何二元关系而言,不存在非平凡的多值依赖,因此,一定属于4NF.


我是从网上博客学习第四范式与多值依赖的,找了很多资料,但是感觉都差不多,还是没弄太懂,上面说的通俗易懂,来自于:博客园深蓝居,同时,推荐阅读CSDN博客smstong所写的多值依赖与4NF,以及维基百科第四范式

To be continued.
2018-01-13 星期六
The end.
2018-01-16 星期二

转载原创文章请注明,转载自: 太傅 » 数据库笔记(四)关系模式的规范化
  1. CongTsang

    懒得一批,还不可抗拒!!!我等了这么久都没有范式!!

    1. TaiFu_S
      @CongTsang

      你不睡觉的吗😪

      1. CongTsang
        @TaiFu_S

        程序员睡什么觉啊~

        1. TaiFu_S
          @CongTsang

          那你每天睡那么早🌚

  2. 安脚拉

    安脚拉脑残粉在此!!!!

    1. TaiFu_S
      @安脚拉

      哇!欢迎啊!

  3. 安脚拉

    啦啦啦啦🙈🙈🙈🙈🙈😮😮😮😮😮

    1. TaiFu_S
      @安脚拉

      范式学会了嘛

  4. 安脚拉

    我又忘了怎么把范式的部分依赖和传递依赖给消除掉了!!!

    1. TaiFu_S
      @安脚拉

      那就再看一遍好了!

  5. 一只在头大的复习喵

    还是很迷茫。

    1. TaiFu_S
      @一只在头大的复习喵

      有哪个地方不懂呢?