[工学]数据库系统原理-第11章课件.ppt

1、1关系数据库的规范化设计是指面对一个现实问关系数据库的规范化设计是指面对一个现实问题题,如何选择一个比较好的关系模式集合，即应该构造如何选择一个比较好的关系模式集合，即应该构造几个关系模式，每个关系由哪些属性组成。几个关系模式，每个关系由哪些属性组成。规范化设计理论主要包括规范化设计理论主要包括三个方面三个方面的内容：的内容：数数据依赖据依赖、范式范式和和模式设计方法模式设计方法。其中数据依赖起着核。其中数据依赖起着核心的作用。数据依赖研究数据之间的联系，范式是关心的作用。数据依赖研究数据之间的联系，范式是关系模式的标准，模式设计方法是自动化设计的基础。系模式的标准，模式设计方法是自动化设计的

2、基础。规范化设计理论对关系数据库结构的设计起着重要的规范化设计理论对关系数据库结构的设计起着重要的作用。作用。第11章 关系数据规范化理论P2502v例例11-1 设有一个关系模式设有一个关系模式R（TNAME，ADDRESS，CNO，CNAME），其属性分别表示），其属性分别表示教师姓名、教师地址、任教课程的编号和课程名。教师姓名、教师地址、任教课程的编号和课程名。TNAMEADDRESSCNOCNAMEt1a1c1n1t1a1c2n2t1a1c3n3t2a2c4n4t2a2c5n2t3a3c6n4 在数据库设计中，如果一个关系模式设计得不在数据库设计中，如果一个关系模式设计得不好，就会出现

3、像文件系统一样的数据冗余、异常、好，就会出现像文件系统一样的数据冗余、异常、不一致等问题。不一致等问题。图11.13v该模式出现的问题有：该模式出现的问题有：(1)数据冗余数据冗余:如果一个教师教几门课程，那么这如果一个教师教几门课程，那么这个教师的地址就要重复几次存储。个教师的地址就要重复几次存储。(2)操作异常操作异常:由于数据的冗余，在对数据操作由于数据的冗余，在对数据操作时会引起各种异常：时会引起各种异常：修改异常。修改异常。例如教师例如教师t1教三门课程，在关系教三门课程，在关系中就会有三个元组。如果他的地址变了，这三个元中就会有三个元组。如果他的地址变了，这三个元组中的地址都要改变

4、。若有一个元组中的地址未更组中的地址都要改变。若有一个元组中的地址未更改，就会造成这个教师的地址不惟一，产生不一致改，就会造成这个教师的地址不惟一，产生不一致现象。现象。4v 插入异常。插入异常。如果一个教师刚调来，尚未分如果一个教师刚调来，尚未分派教学任务，那么要将教师的姓名和地址存储到关派教学任务，那么要将教师的姓名和地址存储到关系中去时，在属性系中去时，在属性CNO和和CNAME上就没有值（空上就没有值（空值）。在数据库技术中空值的语义是非常复杂的，值）。在数据库技术中空值的语义是非常复杂的，对带空值元组的检索和操作也十分麻烦。对带空值元组的检索和操作也十分麻烦。删除异常。删除异常。如果

5、在是上图如果在是上图11.1中要取消教师中要取消教师t3的教学任务，那么就要把这个教师的元组删去，的教学任务，那么就要把这个教师的元组删去，同时也把同时也把t3的地址信息从表中删去了。这是一种不的地址信息从表中删去了。这是一种不合适的现象。合适的现象。5TNAMEADDRESSTNAMECNOCNAMEt1a1t1c1n1t2a2t1c2n2t3a3t1c3n3 t2c4n4 t2c5n2 t3c6n4图11.2关系模式分解的实例（a）关系模式R1的实例（b）关系模式R2的实例 可以说，关系模式可以说，关系模式R不是一个好的模式。一个不是一个好的模式。一个“好好”的模式应的模式应当不会发生插入

6、异常、删除异常、更新异常，数据冗余应尽量少。当不会发生插入异常、删除异常、更新异常，数据冗余应尽量少。规范化原则规范化原则：“关系模式有操作异常或冗余问题，就分解关系模式有操作异常或冗余问题，就分解它它。”是否算最佳分解？是否算最佳分解？那末，什么样的关系那末，什么样的关系模式是最优的？标准模式是最优的？标准是什么？如何实现？是什么？如何实现？6如何构造合适的关系模式如何构造合适的关系模式?应构造几个关模式应构造几个关模式?每个关系模式由哪些属性组成每个关系模式由哪些属性组成?这就关系到数据库的逻辑设计问题这就关系到数据库的逻辑设计问题7vX函数决定函数决定Y，或，或Y函数依赖于函数依赖于X可

7、表示为：可表示为：vXY v如果有一个关系模式如果有一个关系模式R(A1，A2，,An),X和和Y为为A1，A2，,An的子集，那么对于关系的子集，那么对于关系R中的任意中的任意一个一个x值，都只有一个值，都只有一个y值与之对应，则称值与之对应，则称X函数决定函数决定Y，或，或Y函数依赖于函数依赖于X11.1.111.1.1函数依赖的基本函数依赖的基本概念概念11.111.1 函数依赖函数依赖 P248P2488函数依赖是属性间基本的一种依赖，它是关键码概念的推函数依赖是属性间基本的一种依赖，它是关键码概念的推广。广。定义定义1 设有关系模式设有关系模式R(U)，X和和Y是属性集是属性集U的子

8、集，若对的子集，若对于于R(U)的任意一个可能的关系的任意一个可能的关系r，r中不可能存在两个元组在中不可能存在两个元组在X上的属性值相等，而在上的属性值相等，而在Y上的属性值不等，则称上的属性值不等，则称X函数确定函数确定Y或或Y函数依赖函数依赖（Functional Dependency，简记为，简记为FD）于于X，记，记作作XY。FD是对关系模式是对关系模式R的一切可能的关系的一切可能的关系r定义的。对于定义的。对于r的任意的任意两个元组，如果两个元组，如果X值相同，则要求值相同，则要求Y值也相同，即对一个值也相同，即对一个X值有值有唯一个唯一个Y值与之对应。该定义类似于数学中的单值函数

9、定义。值与之对应。该定义类似于数学中的单值函数定义。9例例11-2：有一个关于学生选课、教师任课的关系模式：有一个关于学生选课、教师任课的关系模式：R（SNO，SNAME，CNO，GRADE，CNAME，TNAME，TAGE）属性分别表示学生学号、姓名、选修课程的课程号、成绩、属性分别表示学生学号、姓名、选修课程的课程号、成绩、课程名、任课教师姓名和年龄等意义。课程名、任课教师姓名和年龄等意义。如果规定，每个学号只能有一个学生姓名，每个课程号只如果规定，每个学号只能有一个学生姓名，每个课程号只能决定一门课程，那么可写成下列能决定一门课程，那么可写成下列FD形式：形式：SNOSNAME CNOC

10、NAME每个学生每学一门课程，有一个成绩，那么可写出下列每个学生每学一门课程，有一个成绩，那么可写出下列FD：（SNO，CNO）GRADE还可以写出其他一些还可以写出其他一些FD：CNOCNAME，TNAME，TAGE）TNAMETAGE注意注意：函数依赖不是指关系：函数依赖不是指关系R的某个或某些关系满足的约束条件，的某个或某些关系满足的约束条件，而是指而是指R的一切关系均要满足的约束条件。的一切关系均要满足的约束条件。10v对于函数依赖的定义对于函数依赖的定义注意注意以下三点：以下三点：函数依赖是一个基于关系模式（不是一个关系模式的特定函数依赖是一个基于关系模式（不是一个关系模式的特定实例

11、）的函数概念，即如果一个关系模式实例）的函数概念，即如果一个关系模式R中存在函数依赖中存在函数依赖XYY，则要求该模式的，则要求该模式的所有具体关系都满足所有具体关系都满足XYY。函数依赖不取决于属性构成关系的方式（即关系结构），函数依赖不取决于属性构成关系的方式（即关系结构），而是关系所表达的信息本身的语义特性，我们只能根据这种而是关系所表达的信息本身的语义特性，我们只能根据这种语义信息确定函数依赖，没有其他途径。语义信息确定函数依赖，没有其他途径。函数依赖是数据库设计者对于关系模式的一种断言或决策，函数依赖是数据库设计者对于关系模式的一种断言或决策，即在设计关系型数据库时不仅要设计关系结构

12、，而且要定义即在设计关系型数据库时不仅要设计关系结构，而且要定义数据依赖的条件，限制进入关系的所有元组都必须符合所定数据依赖的条件，限制进入关系的所有元组都必须符合所定义的条件，否则拒绝接受输入。义的条件，否则拒绝接受输入。11 11.1.2 11.1.2 一些术语和符号一些术语和符号 P249P249设有关系模式设有关系模式R（A1，A2，An）,X和和Y为（为（A1，A2，An）的子集，则有以下结论：）的子集，则有以下结论：（1）如果）如果XY，但，但Y不包含于不包含于X，则称，则称XY是是非平凡的非平凡的函数依赖。函数依赖。（2）如果）如果Y函数不依赖于函数不依赖于X，则记为，则记为X

13、Y。（3）如果）如果XY，则称，则称X为决定因子。为决定因子。（4）如果）如果XY，并且，则，并且，则Y X，记，记X Y（5）如果）如果XY，并且对于，并且对于X的任意一个真子集的任意一个真子集X都有都有 X Y，则称，则称Y完全函数依赖于完全函数依赖于X，记为，记为X f Y。如果。如果 X Y成立，则称成立，则称Y部分依赖于部分依赖于X，记为，记为X p Y12 (6)如果如果XY（非平凡的函数依赖，并且非平凡的函数依赖，并且Y X）、）、Y Z，则称则称Z传递函数依赖于传递函数依赖于X。例例11-3：P249例例11.1 11.21311.2 关系规范化关系规范化 P251 v设用设用

14、U表示关系模式表示关系模式R的属性全集，即的属性全集，即U=A1，A2，An，用，用F表示关系模式表示关系模式R上的函数依赖上的函数依赖集，则关系模式集，则关系模式R可表示为可表示为R（U，F）。）。v1、候选码、候选码v设设K为为R（U，F）中的属性，若）中的属性，若K f U，则，则K为为R的的候选码候选码（K为决定为决定R全部属性值的最小属性组）。全部属性值的最小属性组）。11.2.1 关系模式中的码关系模式中的码 14v主码主码:关系关系R(U,F)中可能有多个候选码中可能有多个候选码,则选其中一则选其中一个作为主码个作为主码v全码全码:候选码为整个属性组候选码为整个属性组v主属性主属

15、性:在在R(U,F)中中,包含在任一候选码中的属性包含在任一候选码中的属性v非主属性非主属性:在在R(U,F)中中,不包含在任一候选码中的属不包含在任一候选码中的属性性例例11-4:P251例例11.3和和11.415 2、外码、外码用于在关系表之间建立关联的属性（组）称为用于在关系表之间建立关联的属性（组）称为外码外码。16 关系模式的好与坏，用什么标准衡量？这个标准就关系模式的好与坏，用什么标准衡量？这个标准就模式的模式的范式范式（Normal Forms，简记为，简记为NF）。范式）。范式的种类与数据依赖有着直接的联系，基于的种类与数据依赖有着直接的联系，基于FD的范式的范式有有1NF、

16、2NF、3NF、BCNF等多种。等多种。在不提及在不提及FD时，关系中是不可能有冗余的问题，时，关系中是不可能有冗余的问题，但是当存在但是当存在FD时，关系中就有可能存在数据冗余问时，关系中就有可能存在数据冗余问题。题。1NF是关系模式的基础；是关系模式的基础；2NF已成为历史，一般不已成为历史，一般不再提及；在数据库设计中最常用的是再提及；在数据库设计中最常用的是3NF和和BCNF。11.2.2 范式范式 P251 17 v 对于各种范式之间的联系有：对于各种范式之间的联系有：NFNFNFBCNFNFNF123455NF4NF2NFBCNF3NF1NF范式越高、规范化的程度越高，关系模式就越

17、好。范式越高、规范化的程度越高，关系模式就越好。181、第一范式、第一范式 定义：定义：如果关系模式如果关系模式R的每个关系的每个关系r的属性值都是的属性值都是不可分的原子值，那么称不可分的原子值，那么称R是是第一范式（第一范式（first normal form，简记为，简记为1NF）的模式。的模式。满足满足1NF的关系称为的关系称为规范化的关系规范化的关系，否则称为非规，否则称为非规范化的关系。关系数据库研究的关系都是规范化的关系。范化的关系。关系数据库研究的关系都是规范化的关系。例如关系模式例如关系模式R（NAME，ADDRESS，PHONE），），如果一个人有两个电话号码（如果一个人有

18、两个电话号码（PHONE），那么在关系），那么在关系中至少要出现两个元组，以便存储这两个号码。中至少要出现两个元组，以便存储这两个号码。1NF是关系模式应具备的最起码的条件。是关系模式应具备的最起码的条件。非规范模式变为非规范模式变为1NF：(1)把不含单纯值的属性分解为多个原子值。把不含单纯值的属性分解为多个原子值。(2)把关系模式分解。把关系模式分解。192、第二范式、第二范式 定义定义 如果关系模式如果关系模式R R是是1NF1NF，且每个非主属性完，且每个非主属性完全函数依赖于候选键（主码），那么称全函数依赖于候选键（主码），那么称R R是是第二范式第二范式（2NF2NF）的模式。如果

19、数据库模式中每个关系模式都的模式。如果数据库模式中每个关系模式都是是2NF2NF，则称数据库模式为，则称数据库模式为2NF2NF的数据库模式的数据库模式。20例例11-5：设关系模式设关系模式R（SNO，CNO，GRADE，TNAME，TADDR）的属性分别表示学生学号、选修课程的编号、成绩、任）的属性分别表示学生学号、选修课程的编号、成绩、任课教师姓名和教师地址等意义。（课教师姓名和教师地址等意义。（SNO，CNO）是）是R的候选键。的候选键。R上有两个上有两个FD：（：（SNO，CNO）（TNAME，TADDR）和）和CNO（TNAME，TADDR），因此前一个），因此前一个FD是是局部依

20、赖局部依赖，R不不是是2NF模式。此时模式。此时R的关系就会出现冗余和异常现象。譬如某一门的关系就会出现冗余和异常现象。譬如某一门课程有课程有100个学生选修，那么在关系中就会存在个学生选修，那么在关系中就会存在100个元组，因而教个元组，因而教师的姓名和地址就会重复师的姓名和地址就会重复100次。次。如果把如果把R分解分解成成R1（CNO，TNAME，TADDR）和）和R2（SNO，CNO，GRADE）后，局部依赖（）后，局部依赖（SNO，CNO）（TNAME，TADDR）就消失了。）就消失了。R1和和R2都是都是2NF模式。模式。21 算法：算法：分解成分解成2NF模式集的算法模式集的算法

21、 设关系模式设关系模式R（U），主键是），主键是W，R上还存在上还存在FD XZ，并，并且且Z是非主属性和是非主属性和X W，那么，那么WZ就是一个局部依赖。此时就是一个局部依赖。此时应把应把R分解成两个模式分解成两个模式R1（XZ），主键是），主键是X；R2（Y），其），其中中Y=U-Z，主键仍是，主键仍是W，外键是，外键是X（REFERENCES R1）。）。利用外键和主键的联接可以从利用外键和主键的联接可以从R1和和R2重新得到重新得到R。如果如果R1和和R2还不是还不是2NF，则重复上述过程，一直到数据库，则重复上述过程，一直到数据库模式中每一个关系模式都是模式中每一个关系模式都是2N

22、F为止。为止。如如:在关系模式在关系模式R（SNO，CNO，GRADE，TNAME，TADDR）中，）中，W=SNO，CNO Z=TNAME，TADDR，X=CNO，Y=SNO，CNO，GRADE223、第三范式、第三范式 定义定义 如果如果XY，YA，且，且YX和和 AY，那么，那么称称XA是是传递依赖传递依赖（A传递依赖于传递依赖于X）。）。定义定义 如果关系模式如果关系模式R是是2NF，且每个非主属性都，且每个非主属性都不传递依赖于不传递依赖于R的主码，那么称的主码，那么称R是是第三范式（第三范式（3NF）的模式。如果数据库模式中每个关系模式都是的模式。如果数据库模式中每个关系模式都是3

23、NF，则称其为则称其为3NF的数据库模式的数据库模式。23 例例11-6：在上例中，在上例中，R2是是2NF模式，而且也已模式，而且也已是是3NF模式。但模式。但R1（CNO，TNAME，TADDR）是）是2NF模式，却不一定是模式，却不一定是3NF模式。如果模式。如果R1中存在函数中存在函数依赖依赖CNOTNAME和和TNAMETADDR，那么，那么CNOTADDR就是一个传递依赖，即就是一个传递依赖，即R1不是不是3NF模模式。此时式。此时R1的关系中也会出现冗余和异常操作。譬如的关系中也会出现冗余和异常操作。譬如一个教师开设五门课程，那么关系中就会出现五个元一个教师开设五门课程，那么关系

24、中就会出现五个元组，教师的地址就会重复五次。组，教师的地址就会重复五次。如果把如果把R2分解成分解成R21（TNAME，TADDR）和和R22（CNO，TNAME）后，）后，CNOTADDR就不会出现在就不会出现在R21和和R22中。这样中。这样R21和和R22都是都是3NF模式。模式。24 算法算法 分解成分解成3NF模式集的算法模式集的算法 设关系模式设关系模式R（U），主键是），主键是W，R上还存在上还存在FD XZ。并且。并且Z是非主属性，是非主属性，Z X，且，且X不是候选键，不是候选键，这样这样WZ就是一个传递依赖。此时应把就是一个传递依赖。此时应把R分解成两分解成两个模式：个模式

25、：R1（XZ），主键是），主键是X；R2（Y），其中），其中Y=U-Z，主键仍是，主键仍是W，外键是，外键是X（REFERENCES R1）。）。利用外键和主键相匹配机制，利用外键和主键相匹配机制，R1和和R2通过联接可以通过联接可以重新得到重新得到R。如果如果R1和和R2还不是还不是3NF，则重复上述过程，一直到，则重复上述过程，一直到数据库模式中每一个关系模式都是数据库模式中每一个关系模式都是3NF为止。为止。25违反违反3NF3NF的传递依赖的三种情况的传递依赖的三种情况 部分依赖部分依赖键是超键键是超键传递依赖传递依赖264、BCNF定义定义 如果关系模式如果关系模式R是是1NF，且每

26、个属性都不传，且每个属性都不传递依赖于递依赖于R的候选键，那么称的候选键，那么称R是是BCNF的模式的模式。如。如果数据库模式中每个关系模式都是果数据库模式中每个关系模式都是BCNF，则称为，则称为BCNF的数据库模式。的数据库模式。如果如果R是是BCNF模式，那么模式，那么R也是也是3NF模式。模式。设设F是关系模式是关系模式R的的FD集，如果对集，如果对F中每个非中每个非平凡的平凡的FD XY，都有，都有X是是R的超键，那么称的超键，那么称R是是BCNF的模式的模式。一个满足一个满足BCNF的关系模式有：的关系模式有：所有非主属性对每一个码都是完全函数依赖；所有非主属性对每一个码都是完全函

27、数依赖；所有的主属性对每一个不包含它的码所有的主属性对每一个不包含它的码,也是完全函数依赖；也是完全函数依赖；没有任何属性完全函数依赖于非码的任何一组属性。没有任何属性完全函数依赖于非码的任何一组属性。27 Boyce-Codd范式（范式（BCNF）是根据）是根据Ray Boyce（SQL的的创建者之一）以及创建者之一）以及Edgar Codd（关系数据库之父）的名字来（关系数据库之父）的名字来命名的。它是第二范式和第三范式的替代品，并且构建得更好，命名的。它是第二范式和第三范式的替代品，并且构建得更好，它包含了第二范式和第三范式的内在意义，但使用了一种更普它包含了第二范式和第三范式的内在意义

28、，但使用了一种更普通的方式进行重新表述。要注意的是，满足通的方式进行重新表述。要注意的是，满足BCNF时，不会提时，不会提到第二范式或第三范式。到第二范式或第三范式。BCNF覆盖了这两个范式覆盖了这两个范式 实体满足第一范式。实体满足第一范式。所有属性完全依赖于某个键。所有属性完全依赖于某个键。如果所有的判定都是一个键，则实体满足如果所有的判定都是一个键，则实体满足BCNF。让我们逐个看看后两条规则。让我们逐个看看后两条规则。28 例例11-7：关系模式关系模式S(SNO，SNAME，SDEPT，AGE)，假定假定SNAME也具有唯一性也具有唯一性，那么，那么S就有两个就有两个键，这两个键都由

29、单个属性组成，彼此不相交。其他键，这两个键都由单个属性组成，彼此不相交。其他属性不存在对键的传递依赖与部分依赖，所以属性不存在对键的传递依赖与部分依赖，所以S是是3NF。同时。同时S中除中除SNO，SNAME外没有其他决定因外没有其他决定因素，所以素，所以S也是也是BCNF。29 例例11-8：关系模式关系模式STJ(S，T，J)中，中，S表示学生，表示学生，T表示表示教师，教师，J表示课程。表示课程。每一教师只教一门课每一教师只教一门课。每门课有若干教师，。每门课有若干教师，某一学生选定某门课，就对应一个固定的教师。由语义可得到某一学生选定某门课，就对应一个固定的教师。由语义可得到如下的函数

30、依赖。如下的函数依赖。(S，J)T；(S，T)J；TJ。这里这里(S，J)、(S，T)都是候选键。都是候选键。STJ是是3NF，因为没有任何非主属性对键函数传递依赖或，因为没有任何非主属性对键函数传递依赖或部分函数依赖。但部分函数依赖。但STJ不是不是BCNF模式，是因为模式，是因为T是决定因素，是决定因素，而而T不包含键。不包含键。3NF和和BCNF是在函数依赖的条件下对模式分解所能达到是在函数依赖的条件下对模式分解所能达到的分离程度的测度。一个数据库中的关系模式如果都是的分离程度的测度。一个数据库中的关系模式如果都是BCNF，那么在函数依赖范畴内，它已经实现彻底的分离，已消除了插那么在函数

31、依赖范畴内，它已经实现彻底的分离，已消除了插入和删除异常。入和删除异常。30对于存在数据冗余、插入异常、删除异常问题对于存在数据冗余、插入异常、删除异常问题的关系模式，应采取将一个关系模式的关系模式，应采取将一个关系模式分解分解为多个关为多个关系模式的方法进行处理，但是这种分解过程必须是系模式的方法进行处理，但是这种分解过程必须是“可逆可逆”的，即模式分解的结果应该能重新映像到的，即模式分解的结果应该能重新映像到分解前的关系模式。分解前的关系模式。模式分解的模式分解的准则准则：（）模式分解必须具有（）模式分解必须具有无损连接性无损连接性。（）模式分解能够（）模式分解能够保持函数依赖保持函数依赖

32、11.关系模式分解的准则关系模式分解的准则 P254 31 定义定义 设设F是在关系模式是在关系模式R上成立的函数依赖的集合，上成立的函数依赖的集合，XY是一个函数依赖。如果对于是一个函数依赖。如果对于R的每个满足的每个满足F的关系的关系r也满也满足足XY，那么称，那么称F逻辑蕴涵逻辑蕴涵XY，记为，记为F XY。定义定义 设设F是函数依赖集，被是函数依赖集，被F逻辑蕴涵的函数依赖全体逻辑蕴涵的函数依赖全体构成的集合，称为函数依赖集构成的集合，称为函数依赖集F的的闭包闭包（closure），记为），记为F+。即即 F+=XY|记为记为 F XY。说明：说明：即使一个小的函数依赖集即使一个小的函

33、数依赖集F，其闭包，其闭包F+也是很大也是很大的，一般情况下总有的，一般情况下总有 。研究逻辑蕴涵的目的是利用推理的方法，从一组已知的函数依赖推导出另一研究逻辑蕴涵的目的是利用推理的方法，从一组已知的函数依赖推导出另一组函数依赖，从而找出所有函数依赖组函数依赖，从而找出所有函数依赖F+。FF32定义定义 F是关系模式是关系模式R(U)的一个函数依赖集，记为的一个函数依赖集，记为R(F，U)。如果若干。如果若干个关系模式的集合个关系模式的集合 =R1(U1,F1)，R2(U2,F2)，Rk(Uk,Fk)其中：其中：/*关系模式关系模式R的属性全集的属性全集U是分解后所有小关系模式的属性集是分解后

34、所有小关系模式的属性集Ui的并集的并集*/对于每个对于每个i，j(1i,jk)，有，有Ui Uj/*分解的小属性集间不会相互为子分解的小属性集间不会相互为子集集*/Fi=XY|XYF+XYUi /*Fi(i=1，2，k)是是F在在Ui上的上的投影投影*/则称则称是关系模式是关系模式R(F，U)的一个分解。的一个分解。定义实际上仅给出了模式分解必须满足的基本条件，有时也会出现将定义实际上仅给出了模式分解必须满足的基本条件，有时也会出现将原模式存储信息丢失的现象。原模式存储信息丢失的现象。1niiUU33无损分解无损分解例例11-8：设关系模式设关系模式R（ABC），分），分解成解成=AB=AB，

35、ACAC。见下页图见下页图34CrABCr1ABr2A111111112112未丢失信息的分解未丢失信息的分解（b）（c）（a）4C343 rABCr1ABr2AC r1r2AB1141114111231213111212（a）（b）（c）（d）丢失信息的分解丢失信息的分解 上上 图分解后的关系可以通过自然连接还原。而下图分解后的关系通过自图分解后的关系可以通过自然连接还原。而下图分解后的关系通过自然连接后不能还原。然连接后不能还原。称比称比r多出来的元组为多出来的元组为”噪音噪音”35 定义定义 设设R是一个关系模式，是一个关系模式，F是是R上的一个上的一个FD集。集。R分解成数据库模式分解

36、成数据库模式=R1，Rk。如果对。如果对R中满中满足足F的每一个关系的每一个关系r，都有，都有 r=R1（r）R2（r）Rk（r）那么称分解那么称分解相对于相对于F是是“无损联接分解无损联接分解”(lossless join decomposition),简称为简称为“无损分解无损分解”，否则称为，否则称为“损失分解损失分解”（lossy decomposition）。）。上例中给出了上例中给出了“无损分解无损分解”和和“损失分解损失分解”的例子。的例子。36v 例例11-9：设关系模式设关系模式R（ABC）分解成）分解成=AB，BC。（。（a）和）和（b）分别是模式）分别是模式AB和和BC上

37、的值上的值r1和和r2，（，（c）是）是r1 r2的值。显然的值。显然BC（r1 r2）r2。这里。这里r2中元组（中元组（b2c2）就是一个）就是一个悬挂元组悬挂元组，由于它，由于它的存在，使得的存在，使得r1和和r2不存在泛关系不存在泛关系r。r1ABr2BCABCa1b1a1b1c1bc1b12c2（a）关系r1（b）关系r2rr12（c）rr12 模式分解的目的就是为了消除冗余和操作异常现象，但有时会模式分解的目的就是为了消除冗余和操作异常现象，但有时会产生存储泛关系中无法存储的信息（悬挂元组）。产生存储泛关系中无法存储的信息（悬挂元组）。37 算法算法 无损分解的测试无损分解的测试

38、构造一张构造一张k行行n列的表格，列的表格，每列对应一个属性每列对应一个属性Aj（1jn），），每行对应一个模式每行对应一个模式Ri（1ik）。如果）。如果Aj在在Ri中，那么在表格的中，那么在表格的第第i行第行第j列处填上符号列处填上符号aj，否则填上，否则填上bij。把表格看成模式把表格看成模式R的一个关系，反复检查的一个关系，反复检查F中每个中每个FD在在表格中是否成立，若不成立，则修改表格中的值。修改方法如表格中是否成立，若不成立，则修改表格中的值。修改方法如下：下：对于对于F中一个中一个FD XY，如果表格中有两行在，如果表格中有两行在X值上相等，值上相等，在在Y值上不相等，那么把这

39、两行在值上不相等，那么把这两行在Y值上也改成相等的值。如值上也改成相等的值。如果果Y值中有一个是值中有一个是aj，那么另一个也改成，那么另一个也改成aj；如果没有；如果没有aj，那么，那么用其中一个用其中一个bij替换另一个值（尽量把下标替换另一个值（尽量把下标ij改成较小的数）。改成较小的数）。一直到表格不能修改为止。（这个过程称为一直到表格不能修改为止。（这个过程称为chase过程）过程）若修改的最后一张表格中有一行是全若修改的最后一张表格中有一行是全a，即，即a1a2an，那，那么称么称相对于相对于F是是无损分解无损分解，否则称损失分解。，否则称损失分解。38（F1F1）初始表格初始表格

40、（F1F1）修改后的表格修改后的表格 例例11-10：设关系设关系R(ABCD),R分解成分解成=AB=AB，BCBC，CDCD，如果，如果R R上成立上成立的函数依赖集的函数依赖集F1=BAF1=BA，CDCD，则，则对对F1F1是否为无损分解？如果是否为无损分解？如果F1F1换为换为F2=ABF2=AB，CDCD呢？呢？本行全是本行全是a,是无损连接是无损连接 ABCDABa1a2b13b14BCb21a2a3b24CDb31b32a3a4 ABCDABa1a2b13b14BCa1a2a3a4CDb31b32a3a4 ABCDABa1a2b13b14BCb21a2a3b24CDb31b32

41、a3a4 ABCDABa1a2b13b14BCb21a2a3a4CDb31b32a3a4无无a行行,是有损连接是有损连接（F2F2）初始表格初始表格（F2F2）修改后的表格修改后的表格 39对于分解为两个模式的情况，可根据下列定理分解：对于分解为两个模式的情况，可根据下列定理分解：定理定理 设设=R1，R2 是关系模式是关系模式R的一个分解，的一个分解，F是是R上成立的上成立的FD集，那么分解集，那么分解相对于相对于F是无损分解的是无损分解的充分必要条件充分必要条件是：是：（R1R2）（R1R2）或（）或（R1R2）（R2R1）。）。说明：该定理中的两个函数依赖不一定属于说明：该定理中的两个函

42、数依赖不一定属于F，只要属于，只要属于F+即可。即可。例例11-11：设有关系模式设有关系模式R（SNO，Sname,CNO,Grade,SNOSnameSname,(SNO,CNO)Grade,(SNO,CNO)Grade）的一个分解为：的一个分解为：=R=R1 1（SNOSNO，Sname,SNOSnameSname,SNOSname),),R R2 2(SNO,CNO,Grade,(SNO,CNO)Grade)(SNO,CNO,Grade,(SNO,CNO)Grade)因为因为R1R2=SNO,R1-R2=Sname,所以所以R1 R2RR1 1-R-R2 2,即即SNOSnameSna

43、me,它它属于属于F F，由定理可知，分解具有无损性连接。，由定理可知，分解具有无损性连接。如果两个关系模式间的公共属性集至少包含其中一个关系模式的主健，如果两个关系模式间的公共属性集至少包含其中一个关系模式的主健，则此分解是无损分解。则此分解是无损分解。40保持函数依赖分解保持函数依赖分解 保持函数依赖分解的意义：在作任何数据输入和保持函数依赖分解的意义：在作任何数据输入和修改时，只要每个关系模式本身的函数依赖约束可修改时，只要每个关系模式本身的函数依赖约束可满足，就可以确保整个数据库中数据的语义完整性满足，就可以确保整个数据库中数据的语义完整性不受破坏。不受破坏。41 定义定义 设设F F

44、是属性集是属性集U U上的上的FDFD集，集，Z Z是是U U的子集，的子集，F F在在Z Z上上的投影用的投影用Z Z（F F）表示，定义为）表示，定义为Z Z（F F）=XY|XY|XYFXYF+，且，且XYXY Z Z 定义定义 设设=R R1 1，R RK K 是是R R的一个分解，的一个分解，F F是是R R上上的的FDFD集，集，如果有如果有 R Ri i（F F）=F=F，那么称，那么称分解分解保持函数依赖保持函数依赖集集F F。定理定理 保持函数依赖分解的保持函数依赖分解的充要条件充要条件是是 FFkiRi)(142WNOWSWNOWGWNOWSWGW18级W12000W18级

45、2000W26级W21600W26级1600W36级W31400W36级1400 例例11-12:设关系模式设关系模式R（WNO，WS，WG）的属性）的属性分别表示职工的工号、工资级别和工资数目。如果规定每分别表示职工的工号、工资级别和工资数目。如果规定每个职工只有一个工资级别，并且一个工资级别只有一个工个职工只有一个工资级别，并且一个工资级别只有一个工资数目，那么资数目，那么R上的上的FD有有WNOWS和和WSWG。（c）rr12（a）关系r1（b）关系r2 R1R1上上FDFD是是F1=WNOWSF1=WNOWS，R2R2上的上的FDFD是是F2=WNOWGF2=WNOWG。但从这两。但从

46、这两个个FDFD推导不出在推导不出在R R上成立的上成立的FD WSWGFD WSWG，因此分解，因此分解把把WSWGWSWG丢失了，丢失了，即即不保持不保持F F。如果如果R R分解成分解成=R1=R1，R2R2，其中，其中R1=WNOR1=WNO，WSWS，R2=WNOR2=WNO，WGWG，可以验证这个分解是无损分解。，可以验证这个分解是无损分解。43一个无损连接不一定具有函数依赖保持性，一个无损连接不一定具有函数依赖保持性，反之一个具有函数依赖保持性的分解也不一定反之一个具有函数依赖保持性的分解也不一定是无损连接。是无损连接。例例11-13:设设R（ABCD），），F=ABB，CDCD

47、，=R=R1 1（AA，BB，ABAB），），R R2 2（CC，DD，CDCD）。因为因为 F=ABF=AB，CDCD F F1 1FF2 2=AB=AB，CDCD 所以所以 F F+=(F=(F1 1FF2 2)+即分解即分解具有依赖保持性，易验证具有依赖保持性，易验证不具有不具有无损性。无损性。44例例11-14:11-14:设设R(ABC)R(ABC)，F=ABF=AB，CBCB，=R=R1 1(A(A，BB，F F1 1)，R R2 2(A(A，CC，F F2 2)，其中，其中F F1 1=AB=AB，F F2 2=AC=AC。因为因为 R R1 1RR2 2=A=A，R R1 1-

48、R-R2 2=B=B，R R2 2-R-R1 1=C =C 所以所以 R R1 1RR2 2RR1 1-R-R2 2 因为因为 ABABF F，但，但F F+(F(F1 1FF2 2)+可见可见具有无损分解，但不具有保持函数依赖具有无损分解，但不具有保持函数依赖分解。分解。45 数据库设计者在进行关系数据库设计时，数据库设计者在进行关系数据库设计时，一般尽可能设计成一般尽可能设计成BCNF模式集。如果设计成模式集。如果设计成BCNF模式集时达不到保持函数依赖和无损分模式集时达不到保持函数依赖和无损分解的特点，那么只能降低要求，设计成解的特点，那么只能降低要求，设计成3NF模模式集，以求达到保持

49、函数依赖和无损分解的特式集，以求达到保持函数依赖和无损分解的特点。点。46一个好的数据库模式设计方法应符合一个好的数据库模式设计方法应符合三条原则三条原则：表达性表达性涉及到数据库模式的涉及到数据库模式的等价问题等价问题，即数据等价和，即数据等价和语义等价，分别用无损分解和保持函数依赖分解来衡量。语义等价，分别用无损分解和保持函数依赖分解来衡量。分离性分离性是指在关系中只存储有直接联系的属性值，而是指在关系中只存储有直接联系的属性值，而不要把有间接联系的属性值放在一张表中。应该不要把有间接联系的属性值放在一张表中。应该把有间接把有间接联系的属性值放在不同的表中联系的属性值放在不同的表中。实际上

50、。实际上“分离分离”就是清除就是清除冗余和异常现象。如能达到这个目的，就分离。分离的基冗余和异常现象。如能达到这个目的，就分离。分离的基准是一系列范式。在分解成准是一系列范式。在分解成BCNF模式集时，分离与依赖模式集时，分离与依赖等价有时是不兼容的。等价有时是不兼容的。最小冗余性最小冗余性要求分解后的要求分解后的模式个数模式个数和模式中和模式中属性总数属性总数应应最少最少。目的是节省存储空间，提高操作效率，消除不必。目的是节省存储空间，提高操作效率，消除不必要的冗余。但要注意，实际使用时并不一定要达到最小冗要的冗余。但要注意，实际使用时并不一定要达到最小冗余，因为有时带点冗余对提高查询速度是