第3章 关系数据库设计理论

第3章关系数据库设计理论DesignTheoryforRelationalDatabases关系数据库设计理论3.1函数依赖3.2函数依赖的规则3.3关系数据库模式设计3.4分解的优劣3.5第三范式3.6多值依赖3.7MVD的发现算法3.1函数依赖3.1.1函数依赖的定义3.1.2关系的键3.1.3超键3.1.1函数依赖的定义关系R上的函数依赖是指

如果R的两个元组在属性A1，A2，…，An上一致(即它们对应于这些属性的分量值都相等)，那么它们必定在其他属性B1，B2，…，Bm上也一致。函数依赖的形式为A1，A2，…，An->B1，B2，…，Bm,并称为A1，A2，…，An函数决定B1，B2，…，Bm3.1.1函数依赖的定义tuAB如果t和u在此一致则它们必定在此也一致3.1.1函数依赖的定义A1A2…An→B1A1A2…An→B2…A1A2…An→BmA1A2…An→B1B2…Bm3.1.1函数依赖的定义Movies1

(title,year,length,filmtype,studioName,starName)titleyear→lengthfilmTypestudioName?

titleyear→starName?

titleyearlengthfilmTypestudioNamestarNameStarWarsStarWarsStarWarsMightyDucksWayne’sWorldWayne’sWorld…1977197719771991199219921241241241049595colorcolorcolorcolorcolorcolorFoxFoxFoxDisneyParamountParamountCarrieFisherMarkHamillHarrisonFordEmilioEstevezDanaCarveyMikeMeyersMovies13.1.2关系的键如果下列条件满足，就认为一个或多个属性集{A1，A2，…，An}是关系R的键：1.这些属性函数决定关系的所有其他属性。也可以说，关系R不可能存在两个不同的元组，它们具有相同的A1，A2，…，An的值。3.1.2关系的键2.在{A1，A2，…，An}的真子集中，没有一个能函数决定R的所有其他属性。也就是说，键必须是最小的。3.1.2关系的键当键只包括一个单独的属性A时，称A（而不是{A}）是键。3.1.2关系的键Movies1(title,year,length,filmtype,studioName,starName){title,year}?{title,year,starName}?3.1.3超键超键：一个包含键的属性集。每个键都是超键，但是有些超键不是键。每个超键都满足键的第一个条件：它函数决定了关系中所有其他属性。但超键不需要满足第二个条件：最小化。3.1.3超键例如：Keysaresuperkeys.{title,year,starName}Somesuperkeysarenotkeys.

{title,year,length,starName}3.2函数依赖规则对于FD集合S和T而言，若关系实例集合满足S与其满足T的情况完全一样，就认为S和T等价。若满足T中所有FD的每个关系实例也满足S中的所有FD，则认为S是从T中推断而来。3.2函数依赖规则分解/结合规则平凡函数依赖传递规则Armstrong’saxiom规则分解/结合规则A1A2…An→B1B2…Bm等价于A1A2…An→B1A1A2…An→B2…A1A2…An→Bm分解/结合规则这种等价的两种使用方法：分解规则：用一个FD的集合A1A2…An→Bi(i=1,2,…m)

替换FDA1A2…An→B1B2…Bm。

组合规则：用一个FDA1A2…An→B1B2…Bm替换FD集合A1A2…An→Bi(i=1,2,…m)

。平凡函数依赖如果关系上的一个约束对所有关系实例都成立，且与其他约束无关，则称其为平凡的。平凡FD是这样的一类FD：A1A2…An→B1B2…Bm，其中{B1,B2,…,Bm}{A1,A2,…,An}。平凡FD右边是左边的子集。平凡函数依赖例如：titleyear→titletitleyear→yearlengthtitleyear→length平凡函数依赖FDA1A2…An→B1B2…Bm等价于A1A2…An→C1C2…Ck其中C是集合B中而不是集合A中的属性。这种规则被称为平凡依赖规则。ABCtu如果t和u在A上一致则它们一定也在B上一致因此它们必定在C上一致传递规则传递规则联结了两个FD若关系R中FDA1A2…An→B1B2…Bm和B1B2…Bm→C1C2…Ck都成立，那么FDA1A2…An→C1C2…Ck在R中也成立。如果C中有属性属于A，则可根据平凡依赖规则把它们从右边消除。传递规则MovieStudio(title,year,length,fileType,studioName,studioAddr)title,year→studioNamestudioName→studioAddrtitle,year→studioAddrArmstrong’saxiom规则Armstrong’saxioms:Reflexivity

自反律If{B1,B2,…,Bm}{A1,A2,…,An},thenA1A2…An→B1B2…Bm.(trivial)Armstrong’saxiom规则Augmentation

增长律IfA1A2…An→B1B2…Bm,thenA1A2…AnC1C2…C→B1B2…BmC1C2…CkforanysetofattributesC1,C2,…,Ck.Armstrong’saxiom规则Transitivity

传递律IfA1A2…An→B1B2…BmandB1B2…Bm→C1C2…Ck,thenA1A2…An→C1C2…Ck.3.3关系数据库模式设计引起冗余的原因：实例在多个元组中重复。titleyearlengthfilmTypestudioNamestarNameStarWarsStarWarsStarWarsMightyDucksWayne’sWorldWayne’sWorld1977197719771991199219921241241241049595colorcolorcolorcolorcolorcolorFoxFoxFoxDisneyParamountParamountCarrieFisherMarkHamillHarrisonFordEmilioEstevezDanaCarveyMikeMeyers3.3关系数据库模式设计如何解决冗余？1.首先深入细致地研究不好的模式设计存在的问题。2.然后，引入“分解”的思想，把一个关系模式（若干属性的集合）分解为两个较小的模式。3.3关系数据库模式设计3.接着，引入“Boyce-Codd范式”，即“BCNF”，这是在关系模式上消除上述问题的条件。4.当解释怎样通过分解关系模式来确保BCNF条件时，把上面的几点结合起来。3.3关系数据库模式设计5.稍微放松BCNF的要求，引入“第三范式”，即“3NF”。6.引入“1NF”和“2NF”。3.3.1异常冗余：信息没有必要地在多个元组中重复。更新异常：可能修改了某个元组的信息，但没有改变其他元组中的相同信息。删除异常：如果一个值集变成空集，就可能带来丢失信息的副作用。titleyearlengthfilmTypestudioNamestarNameStarWarsStarWarsStarWarsMightyDucksWayne’sWorldWayne’sWorld1977197719771991199219921241241241049595ColorColorColorColorColorColorFoxFoxFoxDisneyParamountParamountCarrieFisherMarkHamillHarrisonFordEmilioEstevezDanaCarveyMikeMeyers3.3.2分解关系给定一个关系R(A1,A2,…,An)，把它分解为关系S(B1,B2,…,Bm)和T(C1,C2,…,Ck)，并且满足：1.{A1,A2,…,An}={B1,B2,…,Bm}∪{C1,C2,…,Ck}2.S=πB1,B2,…,Bm(R)3.T=πC1,C2,…,Ck(R)分解关系

Movies(title,year,length,filmType,studioName,starName)intotworelations:

Movie1(title,year,length,filmType,studioName)

titleyearlengthfilmTypestudioNameStarWarsMightyDucksWayne’sWorld19771991199212410495ColorColorColorFoxDisneyParamountMovie2(title,year,starName)titleyearstarNameStarWarsStarWarsStarWarsMightyDucksWayne’sWorldWayne’sWorld197719771977199119921992CarrieFisherMarkHamillHarrisonFordEmilioEstevezDanaCarveyMikeMeyers3.3.3Boyce-Codd范式分解的目的就是将一个关系用多个不存在异常的关系替换。也就是说，在一个简单的条件下保证前面讨论的异常不存在，这个条件称为Boyce-Codd范式，简称为BCNF。3.3.3Boyce-Codd范式关系R属于BCNF当且仅当：如果R中非平凡FDA1A2…An→B1B2…Bm成立，则{A1,A2,…,An}是关系R的超键。注意：1.非平凡是指B1B2…Bm不是A1A2…An的子集。2.每个非平凡FD的左边必须是超键，（必须包含键）3.5第三范式稍微放松BCNF的要求，以允许那些在分解为BCNF关系时不能保持函数依赖的特殊关系模式。这个条件称为第三范式。3.5第三范式关系R属于第三范式(3NF)，如果它满足：只要A1A2…A