《第4-1章 关系数据理论-公理与模式分解(选讲)》由会员分享，可在线阅读，更多相关《第4-1章 关系数据理论-公理与模式分解(选讲)（15页珍藏版）》请在金锄头文库上搜索。
1、,第4-1章 数据依赖的公理系统与模式分解理论,1. 函数依赖的逻辑蕴含 对于关系模式R（U，F），若对任何一个 r ，函数依赖 X Y都成立，则称F逻辑蕴含X Y。 （即根据F中的函数依赖可以推导出X Y） 例如，对于下面关系模式： 学生 ( 学号, 姓名, 系名, 系主任, 课名, 成绩，学号姓名, 学号系名, 系名系主任, (学号,课名) 成绩 ) 函数依赖：学号系主任 就蕴含其中。 在关系模式R（U，F）中，为F所逻辑蕴含的函数依赖的全体称作F的闭包，记作F。,1 数据依赖的公理系统,2. Armstrong公理系统 为了根据R（U，F），确定关系的码，或者推导出其它的函数依赖，为此，
2、Armstrong给出了一组推理规则，称作Armstrong公理系统。 推理规则如下： （1）自反律 若Y X U，则X Y为F所蕴含。 自反律的应用只依赖与U，而与F无关 由自反律得到的函数依赖，均是平凡的函数依赖。 例如：(学号，姓名） 姓名,1 数据依赖的公理系统,（2） 增广律 若X Y为F所逻辑蕴含，Z U，则XZ YZ 例如：因为：学号 姓名 所以：( 学号，课号） ( 姓名，课号） （3） 传递律 若 X Y 及 Y Z 为F所逻辑蕴含，则X Z为F 所逻辑蕴含。 例：因为：学号系名, 系名系主任， 则： 学号系主任。,1 数据依赖的公理系统,Armstrong公理系统是有效的、
3、完备的。即 1. 由F出发根据推理规则推导出的函数依赖一定为F所逻辑蕴含。 2. F所蕴含的每一个函数依赖必定可以由F出发推导出来。 根据Armstrong公理系统可以得到下面的推理规则： （1）合并规则：由X Y 及 X Z ，可有X Y Z。 例如： 由： 学号姓名，学号性别， 可有： 学号（姓名，性别） （2）伪传递规则：由X Y 及 YW Z ，可有XW Z。 （3）分解规则：由X Y 及 Z Y，可有X Z。 例如： 由： 学号（姓名，性别） 可有： 学号姓名 和 学号性别,一. 问题：对于关系模式： 学生（学号，姓名，系名，系主任，学号姓名, 学号系名, 系名系主任） 可有多种分解
4、方案。下面是其中三种。 分解方案1：R1（学号，姓名，系主任） R2（系名，系主任） 分解方案2：R1（学号，姓名，系主任） R2（学号，系名） 分解方案3： R1（学号，姓名，系名） R2（系名，系主任） 上面三种方案均满足第三范式要求，但哪一种比较好呢？,2 模式分解,二. 关系模式的等价标准 将一个关系模式分解为若干个关系模式后，应保证分解产生的模式与原来的模式等价。常用的标准是： 标准1： “无损连接性” 标准2：“保持函数依赖” 两个标准相互独立。一般要求分解方案要同时满足两个标准。,2 模式分解,三. 标准1： “无损连接性” 设关系模式R（U，F）分解为R1（U1，F1），R2（
5、U2，F2），若对于R的任何一个可能的r，都有r=r1*r2, 即r在R1、R2上的投影的自然连接等于r, 则称R的这个分解具有“无损连接性” 其充分必要条件是： ( U1 U2 U1U2 ） F 或 ( U1 U2 U2U1 ） F,2 模式分解,例1：考察分解方案1： R1（学号，姓名，系主任） R2（系名，系主任） 因为： U1 U2 (系主任） U1U2 =(学号，姓名) U2U1 =（系名） 但是：(系主任) (学号，姓名) F (系主任） （系名） F 因此，该分解方案不具有“无损连接性” 问题：实际上无法正确连接。因为根据系主任无法确定系名， 因而，无法确定学生所在系。,2 模式
6、分解,例2：考察分解方案2： R1（学号，姓名，系主任） R2（学号，系名） 因为：U1 U2 (学号） U2U1 =(系名) U1U2 =（姓名，系主任） 而：(学号） (系名) F 因此，该方案具有“无损连接性” 例3：考察分解方案3： R1（学号，姓名，系名） R2（系名，系主任） 因为：U1 U2 (系名） U2U1 =(系主任) U1U2 =（学号，姓名） 而：(系名） (系主任) F 因此，该方案具有“无损连接性”,四. 标准2：“保持函数依赖” 关系模式 R（U，F）分解为: R1（U1，F1），R2（U2，F2）， 若: F( F1F2) , 即F所逻辑蕴含的函数依赖一定也可由
7、分解得到的各个关系模式中的函数依赖所逻辑蕴含， 则：称R的这个分解具有“保持函数依赖”。,2 模式分解,例1：考察分解方案1： R1（学号，姓名，系主任） R2（系名，系主任） F（学号姓名, 学号系名, 系名系主任） F1（学号姓名, 学号系主任） F2（系名系主任） 但：（学号系名）根据 ( F1F2) 推导不出来。 故：该分解方案不“保持函数依赖”。 问题：学生转系后，要由人工先确定新系的系主任后，才能修改数据库。麻烦！容易错！,2 模式分解,例2：考察分解方案2： R1（学号，姓名，系主任） R2（学号，系名） F（学号姓名, 学号系名, 系名系主任） F1（学号姓名, 学号系主任）
8、F2（学号系名） 但：（系名系主任）根据 ( F1F2) 推导不出来。 故：该分解方案不“保持函数依赖”。 问题：学生转系后，要修改两个表，容易造成数据的不一致性。,2 模式分解,例3：考察分解方案3： R1（学号，姓名，系名） R2（系名，系主任） F（学号姓名, 学号系名, 系名系主任） F1（学号姓名, 学号系名） F2（系名系主任） 因为： F 与( F1F2) 相同 所以： F( F1F2) 故：该分解方案“保持函数依赖”。,2 模式分解,五：总结 学生（学号，姓名，系名，系主任，学号姓名, 学号系名, 系名系主任） 可有多种分解方案。下面是其中三种。 分解方案1：R1（学号，姓名，系主任） R2（系名，系主任） 既不保持“无损连接性”，又不 “保持函数依赖”性 分解方案2：R1（学号，姓名，系主任） R2（学号，系名） 保持“无损连接性”，但不 “保持函数依赖”性 分解方案3： R1（学号，姓名，系名） R2（系名，系主任） 既保持“无损连接性”，又 “保持函数依赖”性,2 模式分解,
