函数依赖与范式

发表于 更新于 分类于

规范化

函数依赖

函数依赖定义

设R(U)是一个属性集U上的关系模式 , X和Y是U的子集 .
若对于R(U)的任意一个可能的关系r :
r中不可能存在两个元组在X上的属性值相等 , 而在Y上的属性值不等.

则称 : “X函数确定Y” 或 “Y函数依赖于X” , 记作 X->Y
X则称为这个函数依赖的决定属性组, 也称为决定因素

若Y不函数依赖于X, 则记作 : X -/> Y

例子1

如下的一张表

Sno Sname Ssex …
s1 张三 男 …
s2 李四 女 …

其中两个元组违背了Sno->Sname的依赖, 因此这张表不正确

关于函数依赖

  • 函数依赖是语义范畴的概念, 只能 根据语义来确定函数依赖
  • 数据库设计者可以对现实世界作 强制规定 , 以满足函数依赖
  • 函数依赖是指 关系模式R在任何时刻的盥洗室里均要满足的约束条件

平凡函数依赖 与 非平凡函数依赖

在关系模式R(U)中:
若X->Y, Y不是X的一部分, 则X->Y是 非平凡的函数依赖
若X->Y, Y是X的一部分, 则X->Y是 平凡的函数依赖

例如

SC(Sno, Cno, Grade) 中 :
(Sno, Cno)->Grade 是 非平凡函数依赖
(Sno, Cno)->Sno 是 平凡函数依赖

对于任何一个关系模式, 平凡函数依赖是必然陈立的. 因此讨论的总是非平凡的函数依赖

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

在关系模式R(U)中:
如果X->Y , 且任何一个X真子集X’都有X’-/>Y, 则称 Y完全函数依赖于X , 记作 X -F> Y
如果X->Y , 只要有一个X真子集X’满足X’->Y, 则称 Y部分函数依赖于X , 记作 X -P> Y

例如

STUDENT(Sno, Sdapt, Mname, Cno, Grade) 中 :
(Sno, Cno) -F> Grade 是 完全函数依赖
(Sno, Cno) -P> Sdept 是 部分函数依赖 (因为Sno->Sdept)

传递函数依赖

在关系模式R(U)中:
如果X->Y , X不包含Y , Y-/>X , Y->Z , 则称 Z对X传递函数依赖 , 记作 X -传递> Z
注意 : 若Y->, 即X<–>Y, 则 Z直接依赖于X

例如

STUDENT(Sno, Sdapt, Mname, Cno, Grade) 中 :
Sno->Sdept , Sdept->Mname , Sno -传递> Mname

码(键)

K为R<U,F>中的属性或属性组合 : 若K-F>U , 则K称为R的一个 候选码

  • 如果U部分函数依赖于K , 即 K-P>U , 则称K为 超码
  • 候选码是最小的超码 , 即K的任意一个真子集都不是候选码
  • 若R有多个候选码 , 则选定其中一个作为 主码
  • 若整个属性组是一个码 , 则称为 全码
  • 若属性组X并非R的码 , 但它是另一个关系模式的码 , 则称 X 是 R 的 外码

例如

S(_Sno_ , Sdept , Sage) 中
Sno->(Sno,Sdept,Sage) , Sno 是码 可以选择Sno为主码
(Sno,Sdept) , (Sno,Sage) , (Sno,Sdept,Sage) 都是超码
SC(_Sno_,_Cno_,Grade)中(Sno,Cno)是码 可以选择(Sno,Cno)为主码

主属性与非主属性

  • 包含在任何一个候选码中的属性 , 称为 主属性
  • 不包含在任何码中的属性称为 非主属性 或 非码属性

范式 与 第一范式(1NF)

范式是符合某一级别的关系模式的集合 , 关系满足不同程度要求的为不同的范式

范式的种类

  • 第一范式 (1NF)
  • 第二范式 (2NF)
  • 第三范式 (3NF)
  • BC范式 (BCNF)
  • 第四范式 (4NF)
  • 第五范式 (5NF)

各种范式之间是由低到高包含的关系 : 1NF 包含 2NF , 2NF 包含 3NF…
即 : 满足了高等级范式 自然也就满足了 低等级范式

规范化

一个低一级范式的关系模式 , 通过模式分解可以转换为若干个高一级范式的关系模式的集合.
这个过程叫做 规范化

第一范式(1NF)

如果一个关系模式R的所有属性都是不可分的基本数据项 , 则R∈1NF

第一范式是对关系模式最起码的要求, 不满足第一范式的数据库模式不能称为关系数据库模式
即关系数据库模式不能 : 表中有表

例如 : 一个字段在一个基本表中出现多次, 则不符合1NF

例子3-1

SLC(Sno,Cno,Sdept,Sloc,Grade) 关系模式中:(Sloc为住)依赖图如下:
范式-1NF例子依赖图.png
其中 : SLC满足1NF , 码为(Sno,Cno) , 主属性为Sno,Cno , 非主属性为Grade,Daept,Sloc
这里非主属性Sdept和Sloc部分函数依赖与码(Sno,Cno)

这其中存在问题 :

  1. 插入异常 : 若某学生已入住但未选课 , 则无法插入其数据 , 因为Cno是主属性
  2. 删除异常 : 若某学生只选了3号课程 , 但他又退选了3号课程 , 则删除其选修课程号时将删除他的整条记录
  3. 更新复杂 : 若某学生转系 , 则要修改其的Sdept与Sloc , 但若他选了K门课 , 则要在K条记录中操作
  4. 数据冗余 : 若某学生选修了8门课程 , 则他的Sdept与Sloc的值被重复存储了8次

分析原因 : 是因为非主属性Sdept和Sloc部分函数依赖与码(Sno,Cno)
解决办法 : 投影分解法 , 将SLC分解为两个关系模式 , 消除这些部分函数依赖

第二范式(2NF)

若关系模式R∈1NF , 且 每个非主属性都完全函数依赖与R的码 , 则 R∈2NF

例子3-1中的SLC∈1NF但SLC/∈2NF

例3-2 : 将例3-1的SLC表改造至满足2NF

将 SLC(Sno,Cno,Sdept,Sloc,Grade) 拆分为如下两个关系模式 :
SC(Sno,Cno,Grade) 与 SL(Sno,Sdept,Sloc) 函数依赖图如下:
范式-2NF例子依赖图.png
SC的码(Sno,Cno) , SL的码Sno
所有非主属性对码都是完全依赖了 , SC和SL都满足2NF
之前存在的四个问题得到了 一定程度 的解决

但这其中仍然存在问题 :

  1. 插入异常 : SL中若暂时没有在校学生 , 则无法在中将院系和住处等信息存入数据库
  2. 删除异常 : SL中若某个系学生全毕业了 , 则删除这些学生信息同时也删除了院系和住等信息
  3. 更新复杂 : SL中当调整一个系的住处时 , 需要调整该系所有N个学生的N个元组
  4. 数据冗余 : SL中每个系的学生都住在一个地方 , 但关于系的住处的信息却重复出现

分析原因 ： 在SL中 ：Sno->Sdept , Sdept->Sloc , Sno-传>Sloc . 即存在 非主属性传递函数依赖于码
解决方法 : 投影分解法 , 把SL分解为两个关系模式 , 消除传递函数依赖

第三范式(3NF)

关系模式R<U,F>∈1NF , 若R中不存在这样的码X , 属性组Y 及 为主属性Z (Y不包含Z) :
使得X->Y , Y->Z , Y-/>X 成立, 则称为R<U,F>属于3NF
(即不存在 非主属性对码的部分函数依赖 , 也不存在 非主属性对码的传递函数依赖 )

例3-2中的SC∈3NF , 但SL/∈3NF

例3-3 : 将例3-2中的表改造至满足3NF

SC(Sno,Cno,Grade) 不变 . 将 SL(Sno,Sdept,Sloc) 拆分为两个关系模式 :
SD(Sno,Sdept) 和 DL(Sdept,Sloc) 函数依赖图如下 :
范式-3NF例子函数依赖图.png
所有非主属性都不存在传递依赖于码 , 所有关系模式都符合3NF .
(本身源自2NF , 也没有非主属性对码的部分依赖)
之前的问题得到了一定的解决

BC范式(BCNF)

设关系模式R<U,F>∈1NF , 如果R的每个函数依赖X->Y , 且 X不包含Y 时 , X必须含有码 , 那么R属于BCNF
(在R<U,F>中 , 若每个决定因素都包含码 , 则R∈BCNF . )
即不存在 任何属性 对码有 部分函数依赖 和 传递函数依赖

BCNF的性质 :

  1. 所有非主属性对每一个码都是完全函数依赖的
  2. 所有主属性对每一个不包含它的码也是完全函数依赖的
  3. 没有任何属性完全函数依赖于非码的任何一组属性

例子3-4

关系模式 STJ(S,T,J) 中 : S是学生 , T是教师 , J是课程 . 语义如下:

  • 每一个教师只教一门课 T->J
  • 每一门课有若干个教师教 , 但学生选定课后 , 就确定了一个固定教师 (S,J)->T
  • 某个学生选修某个教师的课程就确定了所选课的名称 (S,T)->J

函数依赖图如下 :
范式-例子3-4函数依赖图.png

  • 候选码 : (S,J) 和 (S,T)
  • S T J 都是主属性 => 不存在非主属性对码的部分函数依赖与传递函数依赖 => STJ∈3NF

该例子存在问题 :

  1. 插入异常 : 若某教师开了某门课 , 但还没有学生选这个课 , 则有关信息无法插入
  2. 删除异常 : 若选修某门的学生都毕业了 , 在删除这些学生相关元组同时也删除了课程信息
  3. 修改复杂 : 某个课程改名了 , 则选修了该课程的学生元组都要更新记录
  4. 数据冗余 : 虽然每个教师只教一门课 , 但每个选修该教师的该课程的学生元组都记录了教师信息

分析原因 : 主属性J部分依赖于码(S,T) , 因为 T->J
解决方法 : 采用投影分解法 , 将STJ分解为两个关系模式 , 消除主属性对码的部分函数依赖

改进例3-4

将 STJ(S,T,J) 分解为两个关系模式 : SJ(S,J) 和 TJ(T,J)
SJ的码是(S,J) TJ的码是T , 依赖图为 :
范式-BCNF改进依赖图.png
至此没有任何属性对码有 部分函数依赖 和 传递函数依赖

BC模式解决了上述的问题

如果一个关系数据库内的 所有关系模式都属于BCNF , 则 :
在函数依赖范畴内 , 它已经实现了模式的彻底分解 , 达到了最高的规范化程度 .

关系模式规范化的基本步骤

范式 定义
1NF 所有属性都是不可分的基本数据项 ( 不可表中有表 )
2NF 所有非主属性都完全依赖于码 ( 消除非主属性对码的部分依赖 )
3NF 所有非主属性都只完全依赖于码 ( 消除非主属性对码的传递依赖 )
BCNF 所有属性都只完全依赖于码 ( 消除主属性对码的传递依赖 )
关系模式规范化的基本步骤.png