《第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 模式分解,