第7章关系数据库理论

第6章 数据库建立与管理

文章目录

• 系列文章目录
• 前言
• 一、基本概念
• • 函数依赖
• 二、范式
• • 1.常见范式定义
  • 2.判定关系属于哪个范式
  • 3.最小化函数依赖集
• 三、模式分解
• • 0.简单分解方法
  • 1.准则
  • 2.保持函数依赖的3NF的分解
  • 3.既有无损连接性又保持函数依赖的3NF分解
  • 4.BCNF的无损连接的分解
• 总结

判断关系属于哪个范式、关系模式的分解

函数依赖

依赖：一个属性的值可以决定另一个属性的值

• 非平凡的函数依赖：X→Y，但Y不包含于X
• 平凡的函数依赖：X→Y，X包含Y
• 完全函数依赖：X→Y，且X的真子集均不能推出Y（必须完整的X才能推出Y）
• 传递函数依赖：X→Y，Y→Z且X不包含Y，Y不能推出X，Z对X传递函数依赖

1.常见范式定义

1NF/第一范式
定义：所有属性均不可分解
2NF/第二范式
定义：关系属于第一范式，且所有非主属性完全依赖于码
3NF
定义：所有的非主属性完全依赖于码，且不传递依赖于码
每一列数据都与主键直接相关，不能间接相关
BCNF
定义：非主属性对码都是完全函数依赖；主属性对不包含它的码是完全函数依赖；没有属性完全依赖于非码属性
消除传递依赖

2.判定关系属于哪个范式

从BCNF开始，找是否存在不满足的条件，依次降低范式等级

• 找候选码
• 是否存在非主属性部分依赖于码(码的真子集就能推出它)——存在则不满足2NF
• 是否存在非主属性传递依赖于码——存在则不满足3NF，为2NF
• 以上均满足，找主属性是否有传递依赖于码、是否有部分依赖于码——存在则非BCNF

3.最小化函数依赖集

1. 拆右边为多个元素的 ⽐如A->BC 拆为 A->B 和A->C
2. 对每个依赖：除去当前依赖,求它左边的元素的闭包,若依赖右边的元素包含于左边元素的闭包，则去掉该依赖
3. 左边最小化(通过遮住左边某个元素来看其余左边元素能不能推出该元素)
   例：对依赖BCD→A，BCD 遮住B看CD能否推出B，能就去掉B

例：已知关系 R, U{A,B,C,D,E,F,G} F={BCD->A,BC->E,A->F,F->G,C->D,A->G} 求F的最小依赖集

• 右边均为单元素
• 去除冗余依赖：
  对BCD→A：
  除去依赖BCD→A，BCD能推出E、D，故BCD闭包为BCDE，不包含A，保留该依赖
  同理BC→E：BC闭包为BCDAFG，不包含E，保留
  A→F：A的闭包为AG，不包含F，保留
  F→G：F闭包为F，不包含G，保留
  C→D：C闭包为C，不包含D，保留
  A→G：A的闭包为AG，包含G，除去
• 去除左边冗余
  BCD→A：去除B，CD不能推出B，保留B
  去除C，BD不能推出C，保留C
  去除D，BC能推出D，去除D，改为BC→A
  BC→E：去除B，C不能推出B，保留B
  去除C，B不能推出C，保留C

所以F的最小依赖集为{BC→A,BC→E,A→F,F→G,C→D}

0.简单分解方法

分解成3NF的快速准则：
有一个函数依赖就单独组成一个关系

分解成BCNF的快速分解规则：
将函数依赖集中左边不含码的函数依赖单独组成一个关系，包含码的组成一关系

1.准则

• 保持函数依赖
• 无损连接性：分解前后连接结果相同

2.保持函数依赖的3NF的分解

1. 求出最小函数依赖集Fmin
2. 把不再函数依赖集F内的元素找出，单独分一类并从U中除去
3. 把Fmin中每一个左边元素相同的依赖元素分成一类。A→B,A→C=={ABC}；没有一样的，就把A→D改成{AD}

例：已知R(ABCDEGH) ,F={A→D,E→D,D→B,BC→D,DC→A} ,求保持函数依赖的3NF的分解

1. 最小函数依赖集{A→D,E→D,D→B,BC→D,DC→A}
2. GH不在F内，单独一类{GH}
3. Fmin中：没有左边相同的，故{AD},{ED},{DB},{BCD},{DCA}

故满足条件的分解为ρ={GH,AD,ED,DB,BCD,DCA}

3.既有无损连接性又保持函数依赖的3NF分解

先进行保持函数依赖的3NF分解，得到ρ={U1,U2,U3,…}
找出关系的码。若任意一个候选码没被ρ中的任何一个Ui包含，则任意一个候选码分为一类，否则不变。

例：已知R(ABCDEGH) ,F={A→D,E→D,D→B,BC→D,DC→A} ,求既有无损连接性又保持函数依赖的3NF的分解

1. 保持函数依赖的3NF分解：ρ={GH,AD,ED,DB,BCD,DCA}
2. 关系的码：{CE}，没有被ρ中元素包含，单独一类

故分解结果为τ={ CE,GH,AD,ED,DB,BCD,DCA}

4.BCNF的无损连接的分解

要求满足无损连接性：

1. 将U中所有元素加入集合ρ
2. 检查关系模式中各关系是否均属于BCNF，若是，则计算终止
3. 若某个Ri不属于BCNF，找一个服从BCNF的关系Rj作为S1，其余关系所包含属性元素集合作为S2，将R拆成S1、S2两部分。判断S2是否属于BCNF，是则停止，否则同样方法拆分S2