数据库原理与应用第5章解析.ppt

模式分解的定义(续) 例: 对于关系模式RU,F, 其中U={SNO,SDEPT,MN}, F={SNO→SDEPT, SDEPT→MN} 已知R∈2NF, 该关系模式存在插入异常、删除异常、数据冗余度大和修改复杂的问题. 因此需要分解该关系模式, 使成为更高范式的关系模式. 分解方法可以有很多种. R的一个关系r SNO SDEPT MN S1 S2 S3 S4 D1 D1 D2 D3 张五 张五 李四 王一 模式分解的定义(续) R的一个分解 ?1={R1SNO,?,R2SDEPT, ?,R3MN, ?} 将r分解成R在SNO上的投影, 在SDEPT上的投影, 在MN上的投影 r1={S1,S2,S3,S4}, r2={D1,D2,D3}, r3={张五,李四,王一} 对于分解后的数据库, 无法回答“S1在哪个系学习” R的另一种分解 ?2={R1{SNO,SDEPT},{SNO →SDEPT}, R2{SNO,MN}, {SNO → MN}} 模式分解的定义(续) 分解?2具有无损连接性----r分解后可以通过自然连接恢复 但分解?2不具有依赖保持性----函数依赖SDEPT→MN在R1和R2中都不成立 R的第三种分解 ?3={R1{SNO,SDEPT},{SNO →SDEPT}, R2{SDEPT,MN}, {SDEPT → MN}} 分解?3既具有无损连接性, 又具有依赖保持性 无损连接分解 无损连接分解: 定义5.19 设关系模式RU, F，如果把它分解为两个或多个子模式R1和R2，相应一个R关系中的数据就要被分解成R1、R2两个或多个子表。假如将这些子表自然连接，即进行R1 R2操作，得到的结果与原来关系中的数据一致，信息并没有丢失，则称该分解具有无损连接性，否则如果R≠ R1 R2，则称该分解不具有无损连接性。 并非每个分解都是无损连接分解 直接使用定义判定分解的无损连接性是不现实的 结论: 需要一个简单的方法, 判定分解的无损连接性 无损连接分解(续) 算法5.5 判定分解的无损连接性 输入: 关系模式RU, F的的一个分解? = {R1U1, F1, R2U2, F2, …, RkUk, Fk} 输出: ? 是否为无损连接分解的判定 方法: 建立一个 k 行n列的表, 表的每一行对应一个关系模式, 每一列对应一个属性. 如果Aj属于Ui, 则第i行第j列处填上aj, 否则填上bij. 重复如下过程, 直到表不发生变化或一行成为a1a2… an: 无损连接分解(续) 对于每个X?Y?F, 如果存在两行或多行在X上相同, 则按如下规则使得这些行在Y上的符号相同: 对于每个Aj?Y, 如果这些行存在ai, 则将这些行的第j列均改为aj, 否则将它们均改为bij, 其中i是这些行的最小行号. 如果存在一行为a1a2… an, 则?是无损连接分解, 否则不是. 无损连接分解(续) 例 RU, F, U={A, B, C, D, E}, F={AB ?C, C ?D, D ?E} R的一个分解: R1(A, B, C), R2(C, D), R3(D, E) 判定该分解的无损连接性. 构造初始化表如下: A B C D E a1 b21 b31 a2 b22 b32 a3 a3 b33 b14 a4 a4 b15 b25 a5 R1 R2 R3 无损连接分解(续) AB ?C不改变表 C ?D: 1, 2行对应于C的列相同, 改变第1行第D列为a4 D ?E: 三行的D列均相同, 改变1, 2行的E列为a5 结果表如下: 第一行为a1a2a3a4a5, 算法终止, 该分解为无损连接分解 A B C D E a1 b21 b31 a2 b22 b32 a3 a3 b33 a4 a4 a4 a5 a5 a5 R1 R2 R3 分解是否具有无损连接性是相对于F来说的，F不同，同样的分解，无损连接性可能不一样。 A B C D AB a1 a2 b13 b14 BC b21 a2 a3 b24 CD b31 b32 a3 a4 例：设关系模式R(ABCD)，R分解成?={AB,BC,CD}。如果R上成立的函数依赖集F1={B→A, C→D}，那么相对于F1是否为无损分解？如果R上成立的函数依赖集F2={A→B,C→D}呢？ A B C D AB a1 a2 b13 b14 BC a1 a2 a3 a4 CD b31 b32 a3 a4 A B C D AB a1 a2 b13 b14 BC