数据库课程 ppt课件

4 闭包的计算
〔算法〕：求属性集X关于函数依赖集F的属性闭包X
。
F
输入：有限的属性集合U,它上面的函数依赖集合F，和U的 一个子集X.
输出：X关于F的闭包
X
。
F
方法：
1、置初始X(0) =X,i=0;
2、对F中的每一个函数依赖Y Z,若Y X(i),置 X(i+1)=X(i)Z 即，将可以被X(i)决定的属性加入到X(i+1)中
3NF 2NF
反证：若R3NF， Leabharlann BaiduR2NF，则按2NF定义，一定 有非主属性部分依赖于码，
设（XZ 为 RX的′）码，，使则得存X在′X的Z。真子集X′，以及非主属性Z 于X′)是 ，在使R得中X存在X码′，X，X′属Z性，组XX′′，X以成及立非，主这属与性RZ3（NZF
矛盾。 所以R2NF。
4NF BCNF
练习:
(4) 如果下表为R的数据,存在什么错误? C# H R S G C1 周一 101 张 80 C1 周二 203 张 80 C1 周一 101 李 86 C2 周三 204 王 78 C2 周四 301 王 78 C2 周三 204 张 74
遗漏： （C1 周二 203 李 86） （C2 周四 301 张 74）
第六章 关系数据库的模式设计
思考：
A B B A R∈4NF？
任何一个二目关系模式R（A，B）一定 属于BCNF吗？一定属于4NF吗？
关系模式R（A，B，C），ABC一定 成立吗？
一个全是主属性的关系模式一定可以达 到第几范式？
一个全键的关系模式一定可以达到第几 范式？
解释——范式之间的关系(Ⅰ)
3、如果X(i+1)= X(i),置i=i+1,并转2;否则转4
4、输出X(i),即为
X
F
4 闭包的计算
举例：R (A, B, ACB},计算
C, D, E), F =
( AB)F 。
{ABC,
BD,
CE,
CEB,
解：由算法：
第一次：
1) X(0) =AB;
2) 搜索F中的每一个函数依赖，得AB C与B D因为 AB,B X(0),置 X(1)=ABCD=ABCD
练习:
设有关系模式R(A，B，C，D)，其函数依 赖集为F={A→B，B→A，AC→D，BC→D， AD →C，BD→C，A→→CD，B→→CD}
请回答如下问题： (1)指出R的所有候选键； (2)R属于第4范式吗，为什么?
1) R的候选键为: AC, 或BC, 或AD, 或BD 2) R不属于4NF
解释——范式之间的关系(Ⅱ)
BCNF 3NF
反证：若RBCNF， 但R3NF，则按3NF定义，一 定有非主属性对码的传递依赖，于是存在：
R的码X ，属性组Y，以及非主属性Z（Z Y），使
得XY， Y Z，YX成立 。 由YZ，按BCNF定义，Y含有码，于是YX成立， 这与YX矛盾。 所以R3NF。
4）输出X(2)=X+=ABCDE
X(i)最多到UR终止
4 闭包的计算
例：对关系R（A,B,C,D,E,F）,给定函数依赖 AB→C,BC→AD,D→B,CF→B,求 {A，B}+
{AB} += AB {AB} +=ABC //AB→C {AB} +=ABCD //BC→AD {AB} +=ABCD //D→B
4 闭包的计算
求整个关系的FD集，即求F+将是一个繁杂的过程 例：求关系R(A,B,C)的F+: F+包含 {A} +、{B} +、{C} + {AB} +、{AC} +、{BC} + {ABC} +
判定XY是否在F＋中，只要判断XY能否用
推样理就规把则 计从算FF导＋的出问，题即简判化断为Y计X F算 的是否X成问F 立题。。这
3 函数依赖的闭包
定义
在关系模式R中，为F所逻辑蕴涵的函数依赖 的全体构成的集合称作F的闭包，记作F+。
F+ ＝｛X Y| F =XY}
例：F={XY，YZ}，则{XZ} F+。
闭包的计算是一个复杂的工作，F不大， F+却可能很大。
4 属性集的闭包
定义：
设F是属性集合U上的一个函数依赖集，X U, 则称用Armstrong推理规则推出的函数依赖X A中所有A的集合，称为属性集X关于F的闭包， 记为X+,显然： X X+
6.2.9 规范化的步骤
▪规范化的基本思想：
▪ 逐步消除数据依赖中不合适的部分 ▪ “一事一地”模式设计原则： 一个关系只说明一个概念、一件事物或事物 间的一种联系，这是规范化的目标
规范化的基本步骤
1NF
消去非主属性对键的部分函数依赖
2NF
消去非主属性对键的传递函数依赖
3NF
消去主属性对键的传递函数依赖
3) X(1)= X(0)，继续下一轮
第二次：
2) X(1)= ABCD，找到C E,与AC B,置X(2)=ABCD E B=ABCDE
3) X(2)= X(1)，继续下一轮
第三次：
2) 由于X(2)= ABCDE,找到ECB,置X(3)=ABCDE B=ABCDE
3) X(3)= X(2)，转4
BCNF
消去非平凡且非函数依赖的多值依赖
4NF
6.3 数据依赖的公理系统
逻辑蕴涵 推理规则 闭包
函数依赖的闭包 属性集的闭包 函数依赖集的覆盖与等价 最小函数依赖集
1 函数依赖的逻辑蕴涵
定义 设F是关系模式R的一个函数依赖集， X,Y是R的属性子集，如果从F中的函数 依赖能够推出XY,则称F逻辑蕴涵 XY,记为 F =XY
4 闭包的计算
目标
通过给定的函数依赖，找出所有的函 数依赖
方法
利用FD的规则(传递、合并、分解)， 推导出函数依赖的集合，即闭包 (closure)
4 闭包的计算
闭包
F的闭包是指F逻辑蕴涵的所有函数依 赖的集合，记作F+
闭包的意义
检验给定的函数依赖是否蕴涵于某个 函数依赖集S
从给定的函数依赖，可以推导出蕴涵 的函数依赖
2 函数依赖的推理规则
Armstrong公理
X，Y，Z是属性集， 自反律。若Y X， 则X Y。 增广律。若X Y ，则XZ YZ。 传递律。若X Y， Y Z，则X Z 。 合并律。若X Y，X Z，则X YZ。 分解律。若X YZ ，则X Y，X Z 。 伪传递律。若X Y，WY Z，则XW Z 。