资源简介

(共33张PPT)
关系数据库规范化理论
第4章
目录
01
关系规范化
的引入
02
函数依赖
03
函数依赖的
公理系统
04
关系模式的
规范化
05
多值依赖
与4NF
06
关系模式分解
及规范化步骤
本章主要内容
通过第2、3章的学习，学生可以完成数据库关系模型的设计及实现。每种关系模型对应一种关系模式，关系模式的好坏直接决定数据的完整性、准确性、一致性和操作性。然而，是不是所有满足关系模型的关系模式设计都是“最好”的设计？不同的关系模式设计会出现什么样的问题？有没有什么理论标准来评价或者优化该关系模式，使其成为“更好”的关系模式设计？
本章重点内容是学习如何针对具体的应用项目，从概念模型设计出发，通过不断优化，实现一个“较好”的数据库关系模式设计。其内容包括关系模式设计存在的常见问题，关系模式中属性间依赖关系及函数依赖的公理系统理论，最小函数依赖集及其求解算法，范式及其转换步骤和多属性之间的依赖关系。
函数依赖的公理系统
第4章
03
4.3.1 函数依赖集的完备性
1. 问题的引入
首先看一个例子，在关系模式R中，已知函数依赖X→{A,B};根据函数依赖的定义，可推出未知函数依赖X→{A}和X→{B}；在关系模式R，已知非平凡函数依赖集F{X→Y,Y→Z}，根据传递函数依赖的定义，可推出新的未知函数依赖X→Z。在关系模式R中，X→{A}、X→{B}和X→Z并不是直接在给定的函数依赖F中，而是依据一定的推理规则和已知条件推导出来的。
将这种由已知的函数依赖集合F，推导出新的函数依赖的问题一般化。解决该问题需要有一套推理规则理论，即函数依赖的公理系统。
4.3.1 函数依赖集的完备性
2．函数依赖集F的逻辑蕴含
定义：设有关系模式R(U,F)，X和Y是属性集合U的两个子集，若对于R中任何一个满足函数依赖集F的关系r，函数依赖X→Y都成立，则称F逻辑蕴含X→Y，或称X→Y可以由F推出。记为F|=X→Y
【例4.5】关系模式R=(A,B,C)，函数依赖集F={A→B,B→C}，证明：F逻辑蕴含A→C。
4.3.1 函数依赖集的完备性
3. 函数依赖集的完备性
闭包的定义：设关系模式R(U,F)，F是函数依赖集，被F逻辑蕴含的函数依赖的全体构成的集合，称为函数依赖集F的闭包（Closure），记为
由以上定义可知，已知函数依赖集F求新函数依赖，可以归结为求F的闭包。
4.3.2 函数依赖的推理规则
在关系模式R中，为了从已知的函数依赖集F中推导出其闭包，1974年，阿姆斯特朗（W. W. Armstrong）在论文中提出了一套推理规则，即著名的“Armstrong公理系统”，其为函数依赖集的推导提供了一个有效且完备的理论基础。
4.3.2 函数依赖的推理规则
1．Armstrong公理及其正确性
在Armstrong公理系统中，有3条基本公理：自反律（Reflexivity）、增广律（Augmentation）及传递律（Transitivity）。经研究发现，任何函数依赖关系都可由此三条基本公理推出。
A1自反律
如果YXU，则X→Y在R上成立。
证明：因YX，若r中存在两个元组在X上的值相同，那么Y的值也必然相同，其中平凡函数依赖就可以依据自反律推出。
例如：在教学关系模式TC中，可知(SNo,CN)→SNo和(SNo,CN)→CN。
4.3.2 函数依赖的推理规则
A2增广律
如果X→Y在R上成立，且ZU，则XZ→YZ在R上成立。
证明：用反证法。
假设r中存在两个元组u1和u2并违反XZ→YZ，即u1[XZ]=u2[XZ]，但u1[YZ]≠u2[YZ]。
由u1[YZ]≠u2[YZ]可知，u1[Y]≠u2[Y]或者u1[Z]≠u2[Z]。
若u1[Y]≠u2[Y]，则与已知X→Y相矛盾；若u1[Z]≠u2[Z]，则与假设的u1[XZ]=u2[XZ]相矛盾。
因此假设不成立，从而得出增广律是正确的。
例如：教学关系模式TC中，已知SNo→Sex，则(SNo,SN)→(SN,Sex)也成立。
4.3.2 函数依赖的推理规则
A3传递律
如果X→Y和Y→Z在R上成立，则X→Z在R上也成立。
证明：用反证法。
假设r中存在两个元组u1和u2违反X→Z，即u1[X]=u2[X]，但u1[Z]≠u2[Z]。
根据上述假设，u1[Y]=u2[Y]，但u1[Z]≠u2[Z]。
若u1[Y]=u2[Y]，则与已知Y→Z相矛盾；若u1[Y]≠u2[Y]，则与已知X→Y相矛盾。
因此，假设不成立，传递律是正确的。
例如：教学关系模式TC中，已知SNo→DNo，DNo→DN，则SNo→DN。
4.3.2 函数依赖的推理规则
根据以上3条基本定理的证明，可以得出如下定理。
定理4.1 Armstrong公理的推理规则是正确的。即：若X→Y是从F中用Armstrong公理推导出的，则X→Y被F逻辑蕴含，存在于中。
4.3.2 函数依赖的推理规则
2．Armstrong公理推论及其正确性
根据Armstrong基本公理A1、A2和A3可以导出如下4条推理规则。
A4合并律（Union Rule）
若X→Y，X→Z在R上成立，则X→YZ在R上也成立。
证明：已知X→Y，根据增广律，两边用X扩充，得到X→XY。
又已知X→Z，根据增广律，两边用Y扩充，得到XY→YZ。
由X→XY和XY→YZ，根据传递律可知，X→YZ。
例如：教学关系模式TC中，已知SNo→(Sex,Age)，SNo→DN，则SNo→(Sex,Age,DN)。
4.3.2 函数依赖的推理规则
A5分解律（Decomposition Rule）
若X→Y，ZY在R上成立，则X→Z在R上也成立。
证明：已知ZY，根据自反律，得到Y→Z，又已知X→Y，根据传递律，可以得到X→Z。
例如：教学关系模式TC中，已知SNo→(Sex,Age)，Sex、Age是(Sex,Age)的子集，则SNo→Sex，SNo→Age。
A4合并律和A5分解律是互逆的过程，由此可得如下定理。
定理4.2 若A1,A2,…,An是关系模式R的属性集，则X→A1A2…An的充分必要条件是X→Ai(i=1,2,…,n)成立。
必要性证明：当X→A1A2…An成立时，根据分解律，X→Ai(i=1,2,…,n)成立。
充分性证明：X→Ai(i=1,2,…,n)成立时，根据合并律，X→A1A2…An成立。
例如：在教学关系模式TC中，SNo→(SN,Sex,Age)(SNo→SN,SNo→Sex,SNo→Age)。
4.3.2 函数依赖的推理规则
A6伪传递律（Pseudo-Transivity Rule）
若X→Y，WY→Z在R上成立，则WX→Z在R上也成立。
证明：已知X→Y，根据增广律，两边用W扩充，得到XW→YW。由XW→YW和WY→Z，根据传递律，得到WX→Z。
例如：在教学关系模式TC中，已知CNo→CN，(SNo,CN)→Score，则(SNo,CNo)→Score。
A7复合律（Composition Rule）
若X→Y，W→Z在R上成立，则XW→YZ在R上也成立。
证明：已知X→Y，根据增广律，两边用W扩充，得到XW→YW。又已知W→Z，根据增广律，两边用Y扩充，得到YW→YZ。对XW→YW和YW→YZ，根据传递律，得到XW→YZ。
例如：在教学关系模式TC中，已知SNo→(SN,Age)，DNo→DN，则(SNo,DNo)→(SN,Age,DN)。
4.3.2 函数依赖的推理规则
3．Armstrong公理系统的完备性
4.3.2 函数依赖的推理规则
【例4.6】设有关系模式R(U,F)，其中U＝{X,Y,Z}，F＝{X→Y,Y→Z}，求函数依赖集F的闭包F+。
4.3.2 函数依赖的推理规则
4.3.3 属性集闭包
1．属性集闭包的概念
4.3.3 属性集闭包
2．求属性集闭包的算法
4.3.3 属性集闭包
【例4.7】设有关系模式R(U,F)，其中U＝{A,B,C}，F＝{A→B,B→C}，求A+，B+，C+。
解：根据定义，A应该属于A+（AA+），根据函数依赖A→B和属性集闭包算法可知，BA+；又因为B→C，则CA+，因此属性集A的闭包A+为{A,B,C}。
同理，B+为{B,C}，C+为{C}。
属性集闭包的算法具有以下作用。
（1）判断属性集X是否为关系模式R的码，通过计算X的闭包X+，查看X是否包含了R中的全部属性。若X包含了R的全部属性，则属性集X是R的一个码；否则，属性集X不是码。
（2）检验YX+是否成立，可以验证函数依赖X→Y是否成立（即某个函数依赖X→Y是否在F+中）。
（3）一种计算函数依赖集F的闭包F+的方法：对任意的属性集X，可以计算其闭包X+，对任意的YX+，输出一个函数依赖X→Y。
4.3.4 最小函数依赖集Fmin
1．函数依赖集的覆盖与等价
定义4.8 设F和G是关系模式R上的两个函数依赖集，如果所有为F所蕴含的函数依赖都为G所蕴含，即F+是G+的子集：F+G+，则称G是F的覆盖。
即：当G是F的覆盖时，只要实现了G中的函数依赖，就自动实现了F中的函数依赖。
定义4.9 如果G是F的函数覆盖，同时F又是G的函数覆盖，即F+＝G+，则称F和G是相互等价的函数依赖集。
即：当F和G等价时，只要实现了其中一个的函数依赖，就自动实现了另一个的函数依赖。
4.3.4 最小函数依赖集Fmin
2．最小函数依赖集Fmin的定义
定义4.10 对于任意的关系模式R，其函数依赖集为F，若满足以下条件，则称函数依赖集Fmin为F的最小函数依赖集。
4.3.4 最小函数依赖集Fmin
【例4.8】设有如下的函数依赖集F1、F2，判断它们是否为最小函数依赖集。
1）F1={A→BC,BD→C,D→C}
2）F2={AB→C,A→C,C→D,A→D}
解：1）在F1中，因存在函数依赖A→BC，其右边不是单属性，且函数依赖BD→C，D→C中存在部分函数依赖，因此，F1不是最小函数依赖集。
2）在F2中，因为由函数依赖A→C，C→D，可以推导出A→D，所以A→D为冗余函数依赖，因此，F2不是最小函数依赖集。
4.3.4 最小函数依赖集Fmin
3．最小函数依赖集的算法
算法4.2（最小函数依赖集的求解算法）:设关系模式R(U,F)，求函数依赖F的最小函数依赖集Fmin，其具体算法步骤如下。
4.3.4 最小函数依赖集Fmin
3．最小函数依赖集的算法
算法4.2（最小函数依赖集的求解算法）:设关系模式R(U,F)，求函数依赖F的最小函数依赖集Fmin，其具体算法步骤如下。
4.3.4 最小函数依赖集Fmin
4.3.4 最小函数依赖集Fmin
【例4.9】已知关系模式R(U,F)，其中属性集U={A,B,C,D,E,G}，函数依赖集F={AB→C,D→EG,C→A,BE→C,BC→D,CG→BD,ACD→B,CE→AG}，求F的最小函数依赖集Fmin。
解：根据最小函数依赖集Fmin的求解算法，求解过程如下。
4.3.4 最小函数依赖集Fmin
4.3.4 最小函数依赖集Fmin
4.3.4 最小函数依赖集Fmin
4.3.4 最小函数依赖集Fmin
【例4.10】设教学关系模式TC(U,F)，其中属性集U={SNo,SN,Age,DN,CNo,CN,Score}，
函数依赖集F={SNo→(SN,Age,DN),(SNo,CN)→Score,CNo→CN}，求F的最小函数依赖集Fmin。
4.3.4 最小函数依赖集Fmin

展开更多......

收起↑