ch.4数据依赖与关系模式规范化

第二部分设计篇Ch.4数据依赖与关系模式规范Ch.5数据库设计Ch.4数据依赖与关系模式规范化1.问题的提出2.数据依赖3.关系模式分解4.关系模式规范化一个具体的例子:SCT(S#，C#，Grade，Teacher，Dept)SCT至少在两个方面存在着比较严重的问题：(1)、数据冗余:Teacher和Dept属性上存在着大量的重复取值，不仅消耗了更多的存储空间，而且还容易引起数据的不一致。(2)、更新异常:例如“CS－01”课程的任课教师为刘朝，因某种原因此课改由张明华担任任课教师，更新时如果不注意就可能仅将一部分选修了“CS－01”的元组更新了，从而造成了“CS－01”课程有两名任课教师的情况，这时就出现了修改时的异常。1.问题的提出S#C#GradeTeacherDept关系模式SCT属性间依赖关系计算机计算机计算机计算机计算机…刘朝张莹刘朝林琳张莹…8986689273…CS－01CS－03CS－01CS－02CS－03…0205501902055019020550370205506602055066…我们认为关系SCT不是一个“好”的关系，原因是将S#、C#、Grade、Teacher、Dept等属性放在一个关系模式中是不合适的，那么，怎么样对这个关系加以改进呢？如果将其分为两个关系SC(S#，C#，Grade)和CT(C#，Teacher，Dept)，这样一来关系中就不会存在数据的冗余了。然而观察关系CT(C#，Teacher，Dept)可以发现，该关系上的更新异常是仍然存在的。将关系CT(C#，Teacher，Dept)继续分解，将其拆分成C(C#，Teacher)和T(Teacher，Dept)。经过这两次调整之后，关系SCT(S#，C#，Grade，Teacher，Dept)被分解成了三个关系SC(S#，C#，Grade)、C(C#，Teacher)和T(Teacher，Dept)，此时的这三个关系都已经比较合理，分解也就到此为止了。我们很好的解决了关系SCT存在的问题，但是实际当中可能存在数据冗余和更新异常等问题的关系并不仅仅只有SCT一个，如何从关系数据理论的层面上来解决关系模式的分解及规范化这一类问题，将是本章后面各节的主要内容。数据依赖是指关系模式的属性间存在的一些制约关系，常见的数据依赖包括两种类型，即函数依赖(FunctionalDependency，FD)和多值依赖(MultivaluedDependency，MD)。数据依赖是一个语义问题，是根据该关系模式及其属性所表达的具体含义而定的。数据依赖是我们评价一个关系的重要依据，根据关系模式上的数据依赖，我们可以判断这个关系是否是合理的。2.数据依赖（1）、函数依赖定义4-1：设R为关系模式，r是R上的任意一个关系实例，X，Y是R的两个属性子集，若对于r上的任意两个元组t1，t2∈r都有如果t1[X]＝t2[X]，则必有t1[Y]=t2[Y]，则称在R上X函数决定Y或者Y函数依赖于X，记为X→Y，X称为决定子(Determinant)。定义4-2：设R为关系模式，X、Y是R的不同属性集，如果X→Y成立，且不存在X中的子集使得X’→Y也成立，则称Y完全函数依赖于X，记为X(f)→Y，否则称Y部分依赖于X，记为X(p)→Y。定义4-3：设X、Y、Z是R上的不同属性集合，如果有X→Y，Y→Z成立且Y→X，则称Z传递函数依赖于X。Armstrong公理系统，该公理系统中与函数依赖有关的规则主要有以下三条:A1（自反率）：如果Y≦X≦U，则X→Y成立；A2（增广率）：如果X→Y成立，且Z≦U，则XZ→YZ成立；A3（传递率）：如果X→Y，Y→Z成立，则X→Z成立。引理4-1：Armstrong公理是正确的。定义4-4：设F是函数依赖集合，X→Y是一个函数依赖，如果F在某个R上成立时必然有X→Y也成立，则称F逻辑蕴涵X→Y，记为F∣＝X→Y。定义4-5：由函数依赖集合F所逻辑蕴涵的全部函数依赖所构成的集合称之为F的闭包，记作F＋，F＋＝{X→Y|F∣＝X→Y}。定义4-6：属性集X关于R(U，F)上的函数依赖集合F的闭包XF定义为XF＝{A|A∈U，X→A可由Armstrong公理推出}。引理4-2：X→Y可由Armstrong公理推出的充分必要条件是Y≦X＋F。定理4-1：Armstrong公理系统是有效而且完备的。算法4-1：计算X＋F输入：U，X，F且X≦U输出：X＋F步骤：(1)令X(0)＝X，i:＝0；(2)计算Z＝{A|(v)(w)(V→W∈F∧vX(i)∧A∈w)}；(3)X(i＋1):＝X(i)∪Z；(4)判断X(i＋1)是否与X(i)相等或X(i＋1)等于属性全集U；(5)如果X(i＋1)≠X(i)且X(i＋1)≠U，则i:＝i＋1，转至(2)；(6)如果X(i＋1)＝X(i)或X(i＋1)＝U，则X(i＋1)即为X＋F，输出X(i＋1)，计算结束。定义4-7：设F、G是两个函数依赖集合，如果F＋＝G＋，则称F等价于G，或者F与G互相覆盖。引理4-3：F＋＝G＋的充分必要条件是F≦G＋且G≦F＋。定义4-8：若F满足下列条件，(1)F中所有函数依赖的右部均为单属性；(2)F中不存在这样的函数依赖X→A及ZX，使得F＋＝(F－{X→A}∪{Z→A})＋；(3)F中不存在这样的函数依赖X→A：使F＋＝(F－{X→A})＋，则称F为最小函数依赖集或最小覆盖。定理4-2：任一函数依赖集合必等价于某一最小函数依赖集合Fmin。（2）多值依赖SchoolDeanDept每名领导均可对各系进行管理电信学院何海潮计算机系电信学院何海潮电子系电信学院何海潮通信工程系电信学院李萌计算机系电信学院李萌电子系电信学院李萌通信工程系电信学院王国栋计算机系电信学院王国栋电子系电信学院王国栋通信工程系外国语学院苏勤英语系外国语学院苏勤日语系外国语学院姚远英语系外国语学院姚远日语系这个关系的元组具有这样一个特点，即对于School属性上的每一个取值，如“电信学院”，πDean(σSchool＝’电信学院’(Man))与πDept(σSchool＝’电信学院’(Man))集合中任意两个元素的组合一定在关系Man中出现。定义4-9：设R为关系模式，X、Y、Z是R的属性子集，且Z＝U―X―Y，如果对于R的任何实例r都有：如果r中存在两个元组s，t使得s[X]＝t[X]，则R中必然存在两个元组u，v使得：u[X]＝v[X]＝s[X]＝t[X]u[Y]＝t[Y]，u[Z]＝s[Z]v[Y]＝s[Y]，v[Z]＝t[Z]即交换元组s、t在Y属性集上的取值后所得新元组仍然在r中出现，则称在R上Y多值依赖于X，记为X→→Y。Armstrong公理系统也在仅与函数依赖有关的A1～A3基础上进行了扩充，增加了以下五条与多值依赖有关的规则，当然，A4～A8也是完备的。A4（互补率）：如果X→→Y，则X→→(U―X―Y)；A5（增广率）：如果X→→Y，且V≦W，则WX→→VY；A6（传递率）：如果X→→Y，Y→→Z，则X→→(Z－Y)；A7如果X→Y，则X→→Y；A8如果X→→Y，Z≦Y，且对某一W当Y∩W＝时有W→Z，则X→Z成立；对于不太恰当的关系模式，通常的处理办法是将其分解为若干小的子关系模式，当然这样的分解并不是随意进行的，分解时需要保证无损连接和保持函数依赖两个特性.(1)无损连接分解(2)保持函数依赖分解(1)无损连接分解定义4-10：关系模式R(U，F)的分解是一个关系模式的集合＝{R1(U1，F1)，…，Rk(Uk，Fk)}，其中U＝，且对于任意的1≤i，j≤k有Ui∩Uj≠，Fi是F在Ui上的投影。定义4-11：函数依赖集合F在Ui上的投影定义为πUi(F)＝{X→Y|X→Y∈F＋∧XY≦Ui}。3.关系模式分解引理4-4：设ρ＝{R1，R2，…，Rk}是R的一个分解，r是满足R的一个关系，令ri＝πUi(r)，1≤i≤k，则有(1)r≦mρ(r)；(2)设s=mρ(r)，则πUi(s)＝ri；(3)mρmρ(r)=mρ(r)其中mρ是投影连接算子，mρ(r)＝︱×︳ri。定义4-12：设ρ＝{R1，R2，…，Rk}是R的一个分解，r是满足R的任一个关系，令ri＝πUi(r)，1≤i≤k，如果该分解ρ满足条件r＝r1︱×︳r2︱×︳…︱×︳rk，则称分解ρ是无损连接分解。算法4-2：判别无损连接的模式分解输入：关系模式R(U，F)，U＝{A1，…，An}，F是最小函数依赖集，R的一个分解ρ＝{R1，…，Rm}；输出：YES/NO步骤：(1)根据R及ρ构造一个m×n的符号表T，符号表每行对应一个子关系模式，每列对应R上的一个属性，符号表取值规则为：T[i，j]＝ajAj∈RibijAj¢Ri(2)根据F对T进行变换，逐个扫描F中的函数依赖Xi→Ai，根据Xi→Ai对T进行变换，如果T中存在不满足该函数依赖的行（即在Xi列上的取值相同，而在Ai列上的取值不同），则修改这些行在Ai属性列上的取值，具体修改方法为：如果这些行中存在某行在Ai列上的取值为a，则将其它行在Ai列上的取值也改为相同的a，否则改为i、j最小的bij；(3)扫描一遍后检验T是否发生变化，如果T中已有全’a’行或T较之于上一遍扫描结果未发生变化，则扫描终止，如T有变化且未出现全’a’行，则返回(2)；(4)算法终止时，若T中有全’a’行，则输出YES，否则输出NO。定理4-3：关系模式R的一个分解ρ＝{R1(U1)，R2(U2)}无损连接的充分必要条件是(U1∩U2)→(U1－U2)∈F＋或者(U1∩U2)→(U2－U1)∈F＋。(2)保持函数依赖分解定义4-13：设ρ＝{R1，R2，…，Rk}是R(U，F)的一个分解，如果F＋＝()+，则称分解ρ保持函数依赖。无损连接和保持函数依赖是模式分解时的两个重要性质，如果一个分解既是无损连接的，同时又保持函数依赖，那么这样的分解将是一个非常理想的分解，既保证了关系的等价，又保证了函数依赖的等价。(1)范式范式(NormalForm，NF)就是满足了一定限制条件的关系模式，这个概念首先由关系数据模型的奠基人E.F.Codd提出，后来又有Boyce，Fagin等学者对其进行了扩充，目前常用的范式包括1NF，2NF，3NF，BCNF，4NF等.范式所要求的限制条件通常都会与关系模式上的数据依赖和候选键有关，因此在介绍范式的概念前，我们需要给出一个计算关系模式上所有候选键的算法。4.关系模式规范化算法4-3：计算关系模式上的全部候选键输入：关系模式R(U，F)，其中F是最小覆盖输出：R上的所有候选键步骤：(1)首先将R的全部属性分为四类，分别是C1：不在任何函数依赖中出现的属性；C2：仅在函数依赖决定子中出现的属性；C3：仅在函数依赖右部出现的属性；C4：在函数依赖左部右部均有出现的属性。任何候选键中必然会包括C1、C2中的属性。(2)若(C1∪C2)＋＝U或者C4＝，则C1∪C2即为惟一的候选键；否则，逐一将C4中的属性加入C1∪C2并计算其闭包，若其闭包为U，则C1∪C2与该属性构成关系上的一个候选键，重复该过程直至找出所有的候选键。定义4-14：如果R的每个属性均是原子属性，且元组在每个属性上的取值也是不可再分的，则称R满足1NF，可以表示为R∈1NF。定义4-15：如果关系模式R中的所有非主属性都完全函数依赖于所有CK，则称R满足2NF，表示为R∈2NF。定义4-16：如果关系模式R中的非主属性既不部分函数依赖也不传递函数依赖于R上的所有候选键，则称R满足3NF，表示为R∈3NF。定义4-17：若对于R上的任何非平凡函数依赖X→Y都有X必包含R的某个候选键，则称R满足BCNF，表示为R∈BCNF。定义4-18：如果对于R中的非平凡多值依赖X→→Y，X必包含R的某个候选键，则称R满足4NF，表示为R∈4NF。由于满足上述各种范式的要求条件是逐渐增强的，所以可以得到如下的范式间包含关系：4NFBCNF3NF2NF1NF，满足更高级别范式的关系模式一定满足低级