今日笔者在复习数据库部分时复习到这个知识点,网络上资源感觉不太适合我所以干脆自己总结出一份笔记。
模式分解:
函数依赖定义:
设有关系模式R(U),X和Y是属性集U的子集,函数依赖是形状为X→Y的一个命题,只要r是R的当前关系,对r中任意两个元组t和s,都有t[X]=s[X]蕴涵t[Y]=s[Y],那么称FD X→Y在关系模式R (U)中成立。 X→Y读作“X函数决定Y”,或者“Y函数依赖于X”。
模式分解:
设有关系模式R(U),R1 (U 1),…,Rk (U k) 是R的一组子集,且U1∪U2∪…∪Uk=U。关系模式R1,…,Rk的集合用ρ表示,ρ={R1,…,Rk}。用ρ代替R的过程称为关系模式的分解。
问题:我们发现在分解之后再重新进行连接是会发生一些函数依赖出现了消失等等的行为,这样的分解之后会将原有的信息进行了丢失等行为是我们所不喜欢的所以我们希望可以得到无损的分解。
无损分解:
设R是一个关系模式,F是R上的一个FD集。R分解成数据库模式ρ={R1,…,Rk }, ri=πRi(r)(1≤i≤k)。如果对R中满足F的每一个关系r,都有
r =πR1(r)⋈πR2 (r) ⋈ … ⋈πRk (r) 那么称分解ρ相对于F是“无损联接分解”(lossless join decomposition),简称为“无损分解”,否则称为“损失分解”(lossy decomposition)。
既然有了无损分解的定义那么我们需要怎么判断一个分解是不是无损分解呢,在这里我们有两种判断的方式分别适用于不同的情况。
无损分解的情况一:交决定差这个是我给它起的名字比较生动形象。这个只是适用于分解为两个函数依赖的情况。具体的定理如下: 设ρ={ R1,R2 }是关系模式R的一个分解,F是R上成立的FD集,那么分解ρ相对于F是无损分解的充分必要条件是(R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)。只要是关系模式分解后的两个关系模式的交可以决定他们的差那么这个分解我们可以认为是无损分解这个名字是不是很生动形象。这个就很简单了就不举例子了。
无损分解情况二:算法这个是比较复杂的但是可以解决基本上所有的问题。
具体算法如下:一共有三个步骤
(1)构造一张k行n列的表格,每列对应一个属性Aj(1≤j≤n),每行对应一个模式Ri(1≤i≤k)。如果Aj在Ri中,那么在表格的第i行第j列处填上符号aj,否则填上bij。
(2)把表格看成模式R的一个关系,反复检查F中每个FD在表格中是否成立,若不成立,则修改表格中的值。修改方法如下:对于F中一个FD X→Y,如果表格中有两行在X值上相等,在Y值上不相等,那么把这两行在Y值上也改成相等的值。如果Y值中有一个是aj,那么另一个也改成aj;如果没有aj,那么用其中一个bij替换另一个值(尽量把下标ij改成较小的数)。一直到表格不能修改为止。(这个过程称为chase过程)
(3)若修改的最后一张表格中有一行是全a,即a1a2…an,那么称ρ相对于F是无损分解,否则称损失分解。
可能算法的描述看着会很麻烦不是太通俗易懂这里举个例子:
设关系模式R(ABCD),R分解成ρ={AB,BC,CD}。如果R上成立的函数依赖集F1={B→A,C→D},那么ρ相对于F1是否为无损分解?如果R上成立的函数依赖集F2={A→B,C→D}呢?
有这个例子是不是就会看的更明白了呢,首先我们需要构建这样的一个表格然后根据函数依赖去填写这个表格//----接着我们就去寻找对于F中一个FD X→Y,如果表格中有两行在X值上相等,在Y值上不相等,那么把这两行在Y值上也改成相等的值。如果Y值中有一个是aj,那么另一个也改成aj;如果没有aj,那么用其中一个bij替换另一个值(尽量把下标ij改成较小的数)。一直到表格不能修改为止。-----//如果不好理解可以这么看B→A两者在B上有两行是相等的都是a2但是他们在A那一列上市不相同的所以我们进行修改就行。这个是最关键的一步。做完这个之后我们只需要去寻找有没有一行完全是a如果是的话那么这个分解就是无损分解。
所有的分解是不是无损分解都是建立在函数依赖的情况下所以有的分解在这个函数依赖下可能不是无损分解但是在有的情况下他就是无损分解。
注意有的会满足无损分解但是不满足保持函数依赖的分解这是两个不同的情况,要注意。
例子:
例:设关系模式R(NO,GRADE,SALARY)的属性分别表示职工的工号、工资级别和工资数目。规定每个职工只有一个级别,并且一个工资级别只有一个工资数目,那么R上的FD有 NO → GRADE和 GRADE → SALARY。 如果ρ={R1, R2}, R1 ={NO , GRADE}, R2 ={NO , SALARY},可以验证这个分解是无损分解,但不保持函数依赖GRADE → SALARY。
关系范式的分解:
关于关系模式范式的一些知识点和定义我在之前的博客中有提到过可以去看我之前的博客这里就不在赘述了。关系模式的范式_用编程写诗的博客-CSDN博客_关系模式r范式
这里就直接讲述如何进行范式的分解吧,我们常常需要将1范式转换成2范式 2范式转换成3范式来保证数据库的规范化。那么我们是要如何进行转换呢
首先先举个例子:
关系模式R(S#,C#,SCORE,T#,TITLE) 是第几范式?
R上的FD: (S#,C#)→SCORE,C#→(T#,TITLE)。R的候选键:(S#,C#) 。
主属性: S#,C# 非主属性: SCORE,T#,TITLE
因为 (S#,C#)→(T#,TITLE)是局部依赖,R不是2NF模式, R是1NF模式。
把R分解成R1(C#, T#,TITLE)和R2(S#,C#,SCORE)后,R1和R2都是2NF模式。
那么我们是怎样将1范式通过分解得到2范式的呢。我们是如何知道只要这样转换就能得到2范式呢。
分解成2NF模式集的算法:
设关系模式R(U),主键是W,R上还存在FD X→Z,其中Z是非主属性, XW,那么W→Z就是一个局部依赖。 此时应把R分解成两个模式
R1(XZ),主键是X;
R2(Y),其中Y=U-Z,主键仍是W,外键是X(REFERENCES R1)。
利用外键和主键的联接可以从R1和R2重新得到R。
如果R1和R2还不是2NF,则重复上述过程,一直到数据库模式中每一个关系模式都是2NF为止。
在上述例子中我们可以看到由于存在C#→(T#,TITLE)这样的X→Z所以直接把他俩放到一起得到了R1然后R2就是U-Z。这样分解的一个过程就可以得到将1范式转换成2范式了。
那么我们知道了如何分解2范式了我们该如何去分解成3范式呢还是那个例子:
在上述例子中,R2(S#,C#,SCORE)是2NF模式,而且也已是3NF模式。但R1(C#,T#,TITLE)是2NF模式,不是3NF模式。
R1上的FD:C#→T#和T#→TITLE。候选键:C# 主属性:C#,非主属性: T#,TITLE 因为R1中C#→TITLE就是一个传递依赖,R1不是3NF模式。
把R1分解成R11(C#,T#)和R12(T#,TITLE),R11和R12都是3NF模式
分解成3NF模式集的算法:
设关系模式R(U),主键是W,R上还存在FD X→Z。并且Z是非主属性,Z不属于X,X不是候选键,这样W→Z就是一个传递依赖。此时应把R分解成两个模式:
R1(XZ),主键是X;
R2(Y),其中Y=U-Z,主键仍是W,外键是X(REFERENCES R1)。
利用外键和主键相匹配机制,R1和R2通过联接可以重新得到R。
如果R1和R2还不是3NF,则重复上述过程,一直到数据库模式中每一个关系模式都是3NF为止。
T#→TITLE是形似X→Z的形式所以我们可以直接得到R12然后我们将Z也就是TITLE删去得到R11也就是(C#,T#)。这样得到的两者皆是3范式。