第9讲关系模式的分解与范式.ppt

4.3 关系模式的分解* 4.3.1 模式分解问题 定义4.11 设有关系模式R(U)，R=R1∪R2∪…∪Rk，ρ={R1，R2，…，Rk}。这里ρ称为R的一个分解，也称为数据库模式。 4.3.2 无损连接分解 定义4.12 设有R，F是R上的函数依赖集，ρ={R1，R2，…，Rk}。如果对R中满足F的每一个关系r，有: r =ΠR1(r)∞ΠR2(r)∞…∞ΠRk(r), 那么就称分解ρ相对于F是“无损连接分解” ；否则称为“损失分解”。 4.3.3 无损分解的测试算法 （1）构造一个k行n列的表格Rρ，表中每一列对应一个属性Aj（1≤j≤n），每一行对应一个模式Ri（1≤i≤k）。如果Aj在Ri中，则在表中的第i行第j列处填上符号aj，否则填上bij。 （2）把表格看成模式R的一个关系，根据F中的每个函数依赖，在表中寻找X分量上相等的行，分别对Y分量上的每一列做修改： 如果列中有一个是aj，那么这一列上（X相同的行）的元素都改成aj； 如果列中没有aj，那么这一列上（X相同的行）的元素都改成bij（下标ij取i最小的那个）。 对F中所有的函数依赖，反复地执行上述的修改操作，一直到表格不能再修改为止（这个过程称为“追踪” 过程）。 （3）若修改到最后，表中有一行全为a，即a1a2…an，那么称ρ相对于F是无损连接分解。 [例4-11] 设有关系模式R(A，B，C，D)，R分解成ρ={AB，BC，CD}，如果R上成立的函数依赖集F={B→A，C→D}，那么ρ相对于F是否为无损连接分解？ 定理4.7 设ρ={R1，R2}是关系模式R的一个分解，F是R上成立的函数依赖集，那么分解ρ相对于F是无损分解的充分必要条件是： (R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1) 当模式R分解成两个模式R1和R2时，若两个模式的公共属性（?除外）能够函数决定R1（或R2）中的其他属性，这样的分解具有无损连接性。 4.3.4 保持函数依赖的分解 定义4.13 设有关系模式R(U)，F是R(U)上的函数依赖集，Z是属性集U上的一个子集，ρ={R1，R2，…，Rk}是R的一个分解。 F在Z上的一个投影用ΠZ(F)表示：ΠZ(F)={X→Y | X→Y∈F +∧XY Z}； F在Ri上的一个投影用ΠRi(F)表示： =ΠR1(r)∪ΠR2(r)∪…∪ΠRk(r)； 如果有F +=( )+，则称ρ是保持函数依赖集F的分解。 4.4 关系模式的范式 各种范式之间的关系 4.4.1 第一范式 定义4.14 如果关系模式R所有的属性均为简单属性，即每个属性都是不可再分的，则称R属于第一范式，简称1NF，记作R∈1NF。 1NF是关系模式应具备的最起码的条件。 第一范式可能具有大量的数据冗余，具有插入异常、删除异常和更新异常等弊端。 如关系模式SCD属于1NF，它既存在完全函数依赖，又存在部分函数依赖和传递函数依赖 。 克服这些弊端的方法是用投影运算将关系分解，去掉过于复杂的函数依赖关系，向更高一级的范式进行转换。 4.4.2 第二范式 第二范式的定义 如果关系模式R∈1NF，且每个非主属性都完全函数依赖于R的主关系键，则称R属于第二范式，简称2NF，记作R∈2NF 。 如：关系模式TCS（T，C，S） 关系键 （T，C，S） ；主属性 T、C、S 不存在非主属性对主关系键的部分函数依赖，因此属于2NF。 2NF规范化 2NF规范化是指把1NF关系模式通过投影分解，转换成2NF关系模式的集合。 [例4-15] 将SCD(SNo，SN，Age，Dept，MN，CNo，Score)规范为2NF。 2NF的缺点 4.4.3 第三范式 第三范式的定义 如果关系模式R∈2NF，且每个非主属性都不传递函数依赖于R的主关系键，则称R属于第三范式，简称3NF，记作R∈3NF。 如：SC(SNo，CNo，Score) 函数依赖为(SNo，CNo)→Score，非主属性Score不传递函数依赖于主关系键（SNo，CNo），因此，SC∈3NF。 又如：SD(SNo，SN，Age，Dept，MN) SNo→Dep和Dept→MN SNo → MN 非主属性MN与主关系键SNo间存在着传递函数依赖，所以SD 3NF。 3NF规范化 算法4.6 把一个关系模式分解为3NF，使它具有保持函数依赖性。 （1）如果Fmin中有一函数依赖X→A，且XA=R，则输出ρ={R}