关系数据理论-Read.pptVIP

6.3 Armstrong公理系统 定义：逻辑蕴涵 对于满足一组函数依赖F的关系模式RU, F，其任何一个关系r，若函数依赖X?Y都成立，则称F逻辑蕴含X ? Y Armstrong公理系统是函数依赖的一个有效而完备的公理系统 可用于从一组函数依赖F求得蕴含(导出)的函数依赖 可用于求得关系模式的码 Armstrong公理系统 Armstrong公理系统 A1自反律： A2增广律： A3传递律： Armstrong公理系统的推理规则 合并规则: 伪传递规则: 分解规则: 引理6.1 (由合并规则和分解规则可得) Armstrong公理系统 定义：闭包 在关系模式RU, F中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记为F+ Armstrong公理系统是有效的、完备的 Armstrong公理系统的有效性 由F出发根据Armstrong公理导出的每一个函数依赖一定在F+中 Armstrong公理系统的完备性 F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理导出 定义 设F为属性集U上的一组函数依赖，X?U， X+F＝{A?X ?A能由Armstrong公理导出}, X+F称为属性集X关于函数依赖F的闭包 引理2：设F为属性集U上的一组函数依赖，X,Y?U，X ? Y能根据Armstrong公理导出的充分必要条件是Y ? X+F 算法：求属性集X关于函数依赖集F的闭包X+F 例2 练习 假设关系模式为R(A,B,C,D), F={A?B,B ? C,B ? D}，求蕴含于给定函数依赖的所有非平凡函数依赖。 求解方法：求所有属性组合的闭包，从中找出新的非平凡依赖。如： 定义 如果G+=F+，就说函数依赖集F覆盖G,或F与G等价 引理3： 定义 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，或称最小依赖集 性质：函数依赖集F的最小函数依赖集不一定唯一，它与求解的次序有关 定理：每一个函数依赖集F均等价于一个最小依赖集Fm 算法：求函数依赖F的最小依赖集F’ 例子 1）考查A?B，去掉它，计算A+=A?C，不包含B，不能去掉 2）考查 B ? A，去掉它，计算B＋＝B ? C ? A，包含A，可去掉它 3）考查 B ? C，去掉它，计算B＋＝B，不包含C，不能去掉 4）考查A ? C，去掉它，计算A＋＝A ?B ? C，包含C，可去掉它 5）考查 C ? A，去掉它，计算C＋＝C，不包含A，不能去掉 其它例子 6.4 模式的分解 分解的目的 解决冗余和异常，提高范式等级 分解的概念 用原关系模式的若干个投影构成新的关系模式，即 关系模式分解应满足的特性 无损连接性(Lossless join) 保持函数依赖性(Preserve dependency) 相互独立性 分解后的关系模式中，当修改某一个关系数据时，不会影响其他关系 例子分析 设S-C-M（学号，班级，班主任） F={学号?班级，班级?班主任，学号?班主任 算法：检验一个分解是否具有无损连接性 例子：判断无损连接性 简易方法：只画关注数据 例子 R(A,B,C), F={A?B, C ? B} 分解1={(A,B) {A?B}, (A,C)} 分解2={(A,B) {A?B}, (B,C) {C?B}} 分析两种分解的无损连接性？ 分解1只具有无损连接性, 分解2不具有无损连接性 算法：检验一个分解是否具有保持函数依赖性 例子 R(A,B,C), F={A?B, C ? B} 分解1={(A,B) {A?B}, (A,C) } 分解2={(A,B) {A?B}), (B,C) {C ? B}} 分析两种分解的依赖保持性？ 分解1：只有A?B，显然，分解1不具有依赖保持性 分解2：保留了所有函数依赖，具有依赖保持性 简单练习：判定无损连接性和函数依赖性 设S-C-M（S学号，C班级，M班主任） F={S学号?C班级，C班级?M班主任，S学号?M班主任} 几个命题 一个无损连接的分解不一定具有依赖保持性，反之亦然 若要求模式分解保持函数依赖，则模式分离总能达到3NF，但不一定能达到BCNF 若要求分解既保持函数依赖，又具有无损连接性，则模式分离可以达到3NF，但不一定能达到BCNF 若要求分解具有无损连接性，则模式分离一定可以达到4NF 求解关系模式的候选码 属性分类 L类：只出现在函数依赖的左边的属性 R类：只出现在函数依赖的右边的属性 N类：在函数依赖的两边均未出现的属性 LR类：出现在函数依赖的两边的属性 函数依赖图FDG 用有向图表示的函数依赖，如 快速求解候选码的充分条件 对于给定的关系模式R及其函数依赖集F 如果X是L或N类属性，则X必为R的任一候选码的成员 如果X是R类属性，则X必不在任何候选