关系模式的分解-无损连接与保持函数依赖.docx

关系模式的分解关系模式的分解-无损连接与保持函数依赖无损连接与保持函数依赖2012.11.02 分解是具有无损连接性的；● 分解是保持函数依赖的；● 分解既要具有无损连接又要保持函数依赖两种将一个关系模式 R(U,F)分解为若干个关系模式 R1(U1,F1),R2(U2,F2)…Rn(Un,Fn)（其中 U＝U1 U2 … Un，R1 为 F 在 U1 上的投影），这意味着相应的将存储在一个二维表 r 中的数据分散到若干个二维表 r1,r2,…,rn 中（其中 r1 是 r 在属性组 U1 上的投影）我们当然希望这样的分解不丢失信息，也就是说，希望能够通过对关系 r1,r2…rn 的自然连接运算重新得到关系 r 中的所有信息事实上，将关系 r 投影为 r1,r2,…,rn 时并不会丢失信息，关键是对 r1,r2,…,rn 作自然连接可能会产生一些原来 r 中没有的元组，从而无法区别那些元组是 r 中原来有的，即数据库中应该存在的数据，在这个意义上丢失了信息例如：设关系模式 S(SNO,CLASSNO,DEPTNO)在某一时刻的关系 r 如下表 5-14表 5-14SNOCLASSNODEPTNOS1C1D1S2C2D2S3C2D2S4C3D1若按分解方案一将关系模式 S 分解为：S11(SNO,DEPTNO)和S12(CLASSNO,DEPTNO)，则将 r 投影到 S11 和 S12 的属性上，得到关系 r11 如表 5-15，r12 如表 5-16。

表 5-15SNODEPTNOS1D1S2D2S3D2S4D1表 5-16 CLASSNODEPTNOC1D1C2D2C3D1对分解后的两个关系作自然连接 r11*r12，得到 r'如表 5-17 如下：表 5-17SNOCLASSNODEPTNOS1C1D1S1C3D1S2C2D2S3C2D2S4C1D1S4C3D1r'中的元组 S1C3D1 和 S4C1D1 都不是原来 r 中的元组就是说，我们无法知道原来 r 中到底有哪些元组，这是我们不希望的定义定义 1：设关系模式 R(U,F)分解为关系模式 R1(U1,F1)，R2(U2,F2)，…，Rn(Un,Fn)，若对于 R的任何一个可能的关系 r，都有 r=r1*r2…*rn，即 r 在 R1,R2,…,Rn 上的投影的自然连接等于 r，则称关系模式 R 的这个分解是具有无损连接性的分解 1 不具有无损连接性，这是一个不好的分解方案在将一个关系模式分解为三个或者更多个关系模式的情况下，要判别分解是否具有无损连接性需要比较复杂的算法然而若将一个关系模式分解为两个关系模式，则很容易判别分解是否具有无损连接性 关系模式 R(U,F)分解为关系模式 R1(U1,F1),R2(U2,F2)是具有无损连接性的分解的充分必要条件是（U1∩U2→U1-U2）∈F+，或者（U2∩U1→U2-U1）∈F+。

让我们再考察第二种分解方案，将关系模式 S 分解为：S21(SNO,CLASSNO)，S22(SNO,DEPTNO)由于 U1∩U2＝SNO，U1-U2=CLASSNO，显然 U1 U2→U1-U2，所以分解 2 具有无损连接性然而分解 2 也不是一个很好的分解方案，将前面例子的关系 r 投影到 S21,S22 的属性上，得到关系 r21如表 5-18 和 r22 如表 5-19：表 5-18SNOCLASSNOS1C1S2C2S3C2S4C3表 5-19 SNODEPTNOS1D1S2D2S3D2S4D1在这种分解中，假设学生 S3 从 C2 班转到 C3 班，于是我们需要在 r21 中将元组 S3C2 修改为S3C3，同时在 r22 中将元组 S3D2 修改为 S3D1如果这两个修改没有同时完成，数据库中就会存在不一致信息这是因为分解得到的两个关系模式不是互相独立造成的F 中的函数依赖CLASSNO→DEPTNO 既没有投影到关系模式 R22 中，而是跨在两个关系模式上函数依赖是数据库中的完整性约束条件在 r 中，若两个元组的 X 值相等，则 Y 值也必须相等现在 r 的一个元组中的 X 值和 Y 值跨在两个不同的关系中，为维护数据库的一致性，在一个关系中修改 X 值时就需要相应的在另外一个关系中修改 Y 值，这当然是很麻烦而且是容易出错的，于是我们要求模式分解保持函数依赖这条等价标准。

定义定义 2：设关系模式 R(U,F)分解为关系模式 R1(U1,F1)，R2(U2,F2)，…，Rn(Un,Fn)，若F=(F1F2…Fn) ，即 F 所逻辑蕴含的函数依赖一定也由分解得到的各个关系式中的函数依赖所逻辑蕴含，则称关系模式 R 的这个分解是保持函数依赖的分解方案二不是保持函数依赖的，因为分解得到的关系模式中只有函数依赖 SNO→CLASSNO，丢失了函数依赖 CLASSNO→DEPTNO不是一个好的分解分解方案三是保持函数依赖的2．关于模式分解的几个事实 （1） 分解具有无损连接性和分解保持函数依赖是两个互相独立的标准具有无损连接性的分解不一定保持函数依赖，例如分解方案二；保持函数依赖的分解不一定具有无损连接性例如，有学号 SNO，班级号 CLASSNO，课程号 COURSENO，学分 CREDIT，构成关系模式：SC(SNO，CLASSNO，COURSENO，CREDIT)，其属性集合上的函数依赖集为：F={SNO→CLASSNO, COURSENO→CREDIT}，分解为两个关系模式：SC1(SNO,CLASSNO)，SC2(COURSENO,CREDIT)，这个分解是保持函数依赖的，但是不具有无损连接性。

因此，关系模式的一个分解可能是保持函数依赖的，可能是具有无损连接性的，也可能是既具有无损连接性又保持函数依赖的2） 若要求分解具有无损连接性，那么模式分解一定可以达到 4NF3） 若要求分界保持函数依赖，那么模式分解可以达到 3NF，但不一定能达到 BCNF4） 若要求分解既具有无损连接性，又保持函数依赖，则模式分解可以达到 3NF，但不一定能达到BCNF。