第4-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），确定关系的码，或者推导出其它的函数依赖，为此，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公理系统是有效的、完备的。即1.由F出发根据推理规则推导出的函数依赖一定为F所逻辑蕴含。2.F所蕴含的每一个函数依赖必定可以由F出发推导出来。根据Armstrong公理系统可以得到下面的推理规则：（1）合并规则：由XY及XZ，可有XYZ。例如：由：学号姓名，学号性别，可有：学号（姓名，性别）（2）伪传递规则：由XY及YWZ，可有XWZ。（3）分解规则：由XY及Z⊆Y，可有XZ。例如：由：学号（姓名，性别）可有：学号姓名和学号性别一.问题：对于关系模式：学生（学号，姓名，系名，系主任，学号姓名,学号系名,系名系主任）可有多种分解方案。下面是其中三种。分解方案1：R1（学号，姓名，系主任）R2（系名，系主任）分解方案2：R1（学号，姓名，系主任）R2（学号，系名）分解方案3：R1（学号，姓名，系名）R2（系名，系主任）上面三种方案均满足第三范式要求，但哪一种比较好呢？2模式分解二.关系模式的等价标准将一个关系模式分解为若干个关系模式后，应保证分解产生的模式与原来的模式等价。常用的标准是：标准1：“无损连接性”标准2：“保持函数依赖”两个标准相互独立。一般要求分解方案要同时满足两个标准。2模式分解三.标准1：“无损连接性”设关系模式R（U，F）分解为R1（U1，F1），R2（U2，F2），若对于R的任何一个可能的r，都有r=r1*r2,即r在R1、R2上的投影的自然连接等于r,则称R的这个分解具有“无损连接性”其充分必要条件是：(U1∩U2U1－U2）∊F＋或(U1∩U2U2－U1）∊F＋2模式分解例1：考察分解方案1：R1（学号，姓名，系主任）R2（系名，系主任）因为：U1∩U2＝(系主任）U1－U2=(学号，姓名)U2－U1=（系名）但是：(系主任)(学号，姓名)∉F＋(系主任）（系名）∉F＋因此，该分解方案不具有“无损连接性”问题：实际上无法正确连接。因为根据系主任无法确定系名，因而，无法确定学生所在系。2模式分解例2：考察分解方案2：R1（学号，姓名，系主任）R2（学号，系名）因为：U1∩U2＝(学号）U2－U1=(系名)U1－U2=（姓名，系主任）而：(学号）(系名)∊F＋因此，该方案具有“无损连接性”例3：考察分解方案3：R1（学号，姓名，系名）R2（系名，系主任）因为：U1∩U2＝(系名）U2－U1=(系主任)U1－U2=（学号，姓名）而：(系名）(系主任)∊F＋因此，该方案具有“无损连接性”四.标准2：“保持函数依赖”关系模式R（U，F）分解为:R1（U1，F1），R2（U2，F2），若:F＋＝(F1∪F2)＋,即F所逻辑蕴含的函数依赖一定也可由分解得到的各个关系模式中的函数依赖所逻辑蕴含，则：称R的这个分解具有“保持函数依赖”。2模式分解例1：考察分解方案1：R1（学号，姓名，系主任）R2（系名，系主任）F＝（学号姓名,学号系名,系名系主任）F1＝（学号姓名,学号系主任）F2＝（系名系主任）但：（学号系名）根据(F1∪F2)推导不出来。故：该分解方案不“保持函数依赖”。问题：学生转系后，要由人工先确定新系的系主任后，才能修改数据库。麻烦！容易错！2模式分解例2：考察分解方案2：R1（学号，姓名，系主任）R2（学号，系名）F＝（学号姓名,学号系名,系名系主任）F1＝（学号姓名,学号系主任）F2＝（学号系名）但：（系名系主任）根据(F1∪F2)推导不出来。故：该分解方案不“保持函数依赖”。问题：学生转系后，要修改两个表，容易造成数据的不一致性。2模式分解例3：考察分解方案3：R1（学号，姓名，系名）R2（系名，系主任）F＝（学号姓名,学号系名,系名系主任）F1＝（学号姓名,学号系名）F2＝（系名系主任）因为：F与(F1∪F2)相同所以：F＋＝(F1∪F2)＋故：该分解方案“保持函数依赖”。2模式分解五：总结学生（学号，姓名，系名，系主任，学号姓名,学号系名,系名系主任）可有多种分解方案。下面是其中三种。分解方案1：R1（学号，姓名，系主任）R2（系名，系主任）既不保持“无损连接性”，又不“保持函数依赖”性分解方案2：R1（学号，姓名，系主任）R2（学号，系名）保持“无损连接性”，但不“保持函数依赖”性分解方案3：R1（学号，姓名，系名）R2（系名，系主任）既保持“无损连接性”，又“保持函数依赖”性2模式分解