数据库系统原理_7

1、1第七章第七章 关系数据库设计理论关系数据库设计理论广东工业大学CIMS重点实验室2=关系模式规范化的必要性关系模式规范化的必要性=函数依赖的概念函数依赖的概念=关系的范式关系的范式=关系模式分解关系模式分解广东工业大学CIMS重点实验室3数据冗余数据冗余：如系名、系主任存储次数为：如系名、系主任存储次数为=学生人数学生人数*选课门数选课门数插入异常插入异常：当某系没有招生时，有关系的信息无法插入：当某系没有招生时，有关系的信息无法插入删除异常删除异常：学生全部毕业后，有关系的基础信息也无：学生全部毕业后，有关系的基础信息也无更新异常更新异常：某系换主任：某系换主任规范化的必要性规范化的必要性

2、SnoSnameSageSdept系主任系主任CnoGrade01李用李用20计算机计算机王五王五19201李用李用20计算机计算机王五王五28501李用李用20计算机计算机王五王五38803赵扬赵扬21材料材料马八马八25004张昕昕张昕昕19材料材料马八马八378SnoSnameSageSdept系主任系主任CnoGrade01李用李用20计算机计算机王五王五19201李用李用20计算机计算机王五王五28501李用李用20计算机计算机王五王五38803赵扬赵扬21材料材料马八马八25004张昕昕张昕昕19材料材料马八马八378广东工业大学CIMS重点实验室4规范化的必要性规范化的必要性数据

3、冗余尽可能少数据冗余尽可能少数据冗余：数据量猛增，系统负担加重数据冗余：数据量猛增，系统负担加重数据冗余：数据冗余：为保证数据的一致、完整，维护工作量增加为保证数据的一致、完整，维护工作量增加数据冗余：易产生错误的统计数据冗余：易产生错误的统计/查询结果查询结果外码是关系数据库不可缺少的外码是关系数据库不可缺少的“数据冗余数据冗余”不能产生插入不能产生插入/删除异常删除异常多种信息混合存储在一张表内多种信息混合存储在一张表内将将“静态信息静态信息”与与“动态信息动态信息”分开分开不能由于更新引起数据不一致不能由于更新引起数据不一致当数据冗余过大，冗余数据不能全面更新当数据冗余过大，冗余数据不能

4、全面更新外码的更新一致性通过外码的更新一致性通过DBMS自动控制自动控制广东工业大学CIMS重点实验室5R(U, F)简化表示简化表示关于数据依赖关于数据依赖R(U, D, DOM, F)关系名关系名属性名集合属性名集合域的集合域的集合属性向域属性向域的映象的映象属性间数据属性间数据的依赖关系的依赖关系广东工业大学CIMS重点实验室6例：例： U= Sno, Sname, Sdept, Mname, Cname, Grade一个系有若干学生，但一个学生只属于一个系一个系有若干学生，但一个学生只属于一个系一个系只有一个系主任一个系只有一个系主任一个学生可选修多门课，每门课有多个学生选修一个学生可

5、选修多门课，每门课有多个学生选修每个学生只有一个名字每个学生只有一个名字每个学生所学的每门课程都有一个成绩每个学生所学的每门课程都有一个成绩FSno Sdept, Sdept Mname, (Sno, Cname) Grade关于数据依赖关于数据依赖主主码码广东工业大学CIMS重点实验室7n一对一关系（一对一关系（1 1） U= Sno, Sname, Sdept, Mname, Cname, Gradeu如果该学校中学生无重名如果该学校中学生无重名, 则学号与姓名之间是则学号与姓名之间是1 1关系关系u一个学号唯一地决定一个姓名一个学号唯一地决定一个姓名u一个姓名也可决定唯一的学号一个姓名也

6、可决定唯一的学号u设设X、 Y是关系是关系R的两个属性（集）。的两个属性（集）。 如果对于如果对于X中的任一中的任一具体值，具体值，Y中至多有一个值与之对应，且反之亦然中至多有一个值与之对应，且反之亦然,则称则称X、 Y两属性间是一对一关系。两属性间是一对一关系。关于数据依赖关于数据依赖广东工业大学CIMS重点实验室8n一对多关系（一对多关系（1 m） U= Sno, Sname, Sdept, Mname, Cname, Gradeu如：学号与系如：学号与系(Sdept) 之间是之间是1 m关系关系u一个学号唯一地决定一个系一个学号唯一地决定一个系(Sdept)u一个系一个系(Sdept)

7、不能决定唯一的学号（对应多个）不能决定唯一的学号（对应多个）u设设X、 Y是关系是关系R的两个属性（集）。的两个属性（集）。 如果对于如果对于X中的任一中的任一具体值，具体值，Y中至多有一个值与之对应，而中至多有一个值与之对应，而Y中的一个值却可中的一个值却可以和以和X中的中的n个值（个值（n0）相对应，则称）相对应，则称Y对对X是一对多关系。是一对多关系。关于数据依赖关于数据依赖广东工业大学CIMS重点实验室9n多对多关系（多对多关系（n m） U= Sno, Sname, Sdept, Mname, Cname, Gradeu如：学号与课程名称如：学号与课程名称(Cname) 之间是之间是

8、n m关系关系u一个学号对应了多门课程名称一个学号对应了多门课程名称(Cname) u一个课程名称一个课程名称(Cname) 对应了多个学号对应了多个学号u设设X、 Y是关系是关系R的两个属性（集）。的两个属性（集）。 如果对于如果对于X中的任一具体值，中的任一具体值，Y中有中有m（m0）个值与之对应，）个值与之对应，而而Y中的一个值也可以和中的一个值也可以和X中的中的n个值（个值（n0）相对）相对应应,则称则称Y对对X是多对多关系。是多对多关系。关于数据依赖关于数据依赖广东工业大学CIMS重点实验室10=属性间的三种关系实际上是：属性间的三种关系实际上是：属性值之间相互依赖又相互制约的反映，

9、称为属属性值之间相互依赖又相互制约的反映，称为属性间的数据依赖。性间的数据依赖。 数据依赖是现实世界属性间相互联系的抽象，是数据依赖是现实世界属性间相互联系的抽象，是世界内在的性质世界内在的性质,是语义的体现。是语义的体现。 =数据依赖共有三种数据依赖共有三种函数依赖（函数依赖（Functional Dependency,简称简称FD）多值依赖（多值依赖（Multivalued Dependency,简称简称MVD）连接依赖（连接依赖（Join Dependency,简称简称JD）关于数据依赖关于数据依赖广东工业大学CIMS重点实验室11设设R(U)是一个关系模式，是一个关系模式，X和和Y是是

10、U的子集。对于任意的子集。对于任意一个可能的关系一个可能的关系r，如果不存在两个元组，它们在如果不存在两个元组，它们在X上上的属性值相同，在的属性值相同，在Y上的属性值不同，则：上的属性值不同，则： X函数确定函数确定Y 或或 Y函数依赖于函数依赖于XABCDEFa1b15d137a1b15d27da2b35d32ra2b35d32ga3b26d136a6b66d528YABCDEFa1b15d137a1b15d13da2b35d32ra2b35d32ga3b26d136a6b66d528X YX Y关于数据依赖关于数据依赖XXY广东工业大学CIMS重点实验室12=如果两属性集如果两属性集X、

11、Y间是间是1 1关系，则存在函关系，则存在函数依赖：数依赖： XY。 如：如果不允许同名学生如：如果不允许同名学生存在，则有：存在，则有： SnoSname。 =如果两属性集如果两属性集Y 、 X间是间是1 m关系关系,则存在函则存在函数依赖：数依赖： XY。 如：如： SnoSdept=如果两属性集如果两属性集X、 Y间是间是m n关系关系,则不存在则不存在函数依赖。函数依赖。 如如Sno与与Cname之间即如此。之间即如此。 U= Sno, Sname, Sdept, Mname, Cname, Grade关于数据依赖关于数据依赖广东工业大学CIMS重点实验室13=在关系模式在关系模式R(

12、U)中，如果中，如果 ，并且对于，并且对于X的任意真子集的任意真子集X,都有都有 ，则称则称Y完全函数依赖于完全函数依赖于X, 记作记作 。否。否则称则称Y部分函数依赖于部分函数依赖于X，记作记作 部分函数依赖部分函数依赖YX YX YXfYXpSnoSnameSsexSageSdept98001李用李用M20计算机计算机98002王仪王仪M18机电工程机电工程98003赵扬赵扬F21材料材料98004张昕昕张昕昕F19材料材料98005王顺德王顺德M20机电工程机电工程关于数据依赖关于数据依赖XXY广东工业大学CIMS重点实验室14=若若R(U)是一个关系模式，对于是一个关系模式，对于U的子

13、集的子集X和和Y，有有XABCDEa1 b15d13a1 b15d13a2 b35d32a2 b15d42a3 b26d13a6 b66d52平凡函数依赖平凡函数依赖是非平凡函数依赖那么称但YXXYYX,是平凡函数依赖那么称但YXXYYX,非平凡函非平凡函数依赖数依赖ABCDEa1 b15d13a1 b15d13a2 b35d32a2 b15d42a3 b26d13a6 b66d52关于数据依赖关于数据依赖YXY广东工业大学CIMS重点实验室15=在关系模式在关系模式R(U)中，如果中，如果 ， ， ， 则则称称Z对对X传递函数依赖。传递函数依赖。传递函数依赖传递函数依赖YX XY SnoSn

14、ameSsexSageSdeptMname98001李用李用M20计算机计算机陈一陈一98002王仪王仪M18机电工程机电工程王五王五98003赵扬赵扬F21材料材料李四李四98004张昕昕张昕昕F19材料材料李四李四98005王顺德王顺德M20机电工程机电工程王五王五XZY ）（ZY YZ关于数据依赖关于数据依赖广东工业大学CIMS重点实验室16设设K为关系模式为关系模式R(U，F)中的属性或属性集合中的属性或属性集合，若若则则 K称为称为R的一个候选码。的一个候选码。 =码码UKfSnoSname Ssex SageSdeptMname98001李用李用M20计算机计算机陈一陈一98002

15、王仪王仪M18机电机电王五王五98003赵扬赵扬F21材料材料李四李四98004张昕昕张昕昕F19材料材料李四李四98005王顺德王顺德M20机电机电王五王五关于数据依赖关于数据依赖码码广东工业大学CIMS重点实验室17=符合某种级别的关系模式的集合符合某种级别的关系模式的集合关系必须满足一定的要求关系必须满足一定的要求满足不同程度的要求满足不同程度的要求INF非规范化关系非规范化关系2NF5NF3NF4NFNFNFBCNFNFNFNF54321关系范式关系范式1NF广东工业大学CIMS重点实验室18=非规范化的关系非规范化的关系当一个关系中的所有分量都是不可分的数据项时当一个关系中的所有分量

16、都是不可分的数据项时,该关系是规范化的该关系是规范化的关系范式关系范式具有组合数据项的非规范化的表具有多值数据项非规范化表广东工业大学CIMS重点实验室19=如果一个关系模式如果一个关系模式R的所有属性都是不可分的基本的所有属性都是不可分的基本数据项，则：数据项，则：NFR1SLC(Sno, Sname, Sdept, Dloc, Cno, Grade)满足满足NFSLC 1CnoSnoSdeptDlocGrade候选码候选码DlocCnoSnoSnameCnoSnoSdeptCnoSnoppp),(),(),(GradeCnoSnof),(部分函数依赖部分函数依赖数据冗余太多数据冗余太多。如

17、：选修。如：选修10门课，其他相关信息重复门课，其他相关信息重复10次次更新复杂更新复杂。如：转系需修改。如：转系需修改 Dloc插入异常插入异常。如：未选课的学生，无法插入。如：未选课的学生，无法插入删除异常删除异常。如：若某学生全部的课程都不选了，将删除他的其他信息。如：若某学生全部的课程都不选了，将删除他的其他信息关系范式关系范式Sname广东工业大学CIMS重点实验室20=如果一个关系模式如果一个关系模式 ，且每个非主属性都完且每个非主属性都完全函数依赖于全函数依赖于R的码，则：的码，则：NFR1关系范式关系范式NFR2SC(Sno, Cno, Grade)NFSC 2CnoSnoSn

18、ameSdeptDlocGrade候选码候选码传递函传递函数依赖数依赖将将SL与与SC分开降低冗余度分开降低冗余度转系需修改转系需修改 SL中的记录中的记录未选课的学生，可插入未选课的学生，可插入SL删除选课只与删除选课只与SC有关有关SL(Sno, Sname, Sdept, Dloc)NFSL 2Sno存在问题得到缓解存在问题得到缓解数据冗余太多数据冗余太多。如：。如：Dloc更新复杂更新复杂。如：转系需修改如：转系需修改 Dloc插入异常插入异常。如：无学生的系如：无学生的系删除异常删除异常。如：学生全毕业如：学生全毕业仍有问题仍有问题广东工业大学CIMS重点实验室21=对于关系模式对于

19、关系模式R，每个非主属性既不部分函数依赖于每个非主属性既不部分函数依赖于R的候的候选码，也不传递函数依赖于选码，也不传递函数依赖于R的候选码，则：的候选码，则：关系范式关系范式NFR3SnameSdept一个系的地址信息只存储一次一个系的地址信息只存储一次转系只需修改对应转系只需修改对应Sno中的中的Sdept新系无学生可插入新系无学生可插入DL关系中关系中学生全毕业学生全毕业DL关系中有关系关系中有关系Sdept和和Dloc的信息的信息SD(Sno, Sname, Sdept)NFSD3Sno候选码候选码存在问题存在问题得到缓解得到缓解DL( Sdept, Dloc)NFDL3DlocSde

20、pt候选码候选码广东工业大学CIMS重点实验室22=推论：推论：不存在非主属性的关系模式一定为不存在非主属性的关系模式一定为3NF。关系范式关系范式例例 ：授课（学生：授课（学生,教师教师,课程）课程） 假设该校规定： 一个教师只能教一门课,每门课可由多个教师讲授。 学生一旦选定某门课,教师就相应地固定。 根据语义关系的函数依赖集为： F= 教师教师课程课程,（学生（学生,课程）课程）教师教师,（学生（学生,教师）教师）课程课程 该关系的候选码为（学生学生, ,课程课程）或（学生学生, ,教师教师）,因此三个属性都是主属性，由于不存在非主属性不存在非主属性,该关系一定是3NF的。广东工业大学C

21、IMS重点实验室23关系范式关系范式CnoSTC(Sno, Tno, Cno)NFSD3Sno候选码候选码TnoTnoSno候选码候选码Cno存在存在问题问题数据冗余数据冗余。如：。如：Sno更新复杂更新复杂。如：教师改课后。如：教师改课后插入异常插入异常。如：未选课的学生。如：未选课的学生删除异常删除异常。如：学生全毕业。如：学生全毕业所有的属性都是主属性所有的属性都是主属性广东工业大学CIMS重点实验室24=所有非主属性都完全函数依赖于每个候选码所有非主属性都完全函数依赖于每个候选码=所有主属性都完全函数依赖于每个不包含它的候选码所有主属性都完全函数依赖于每个不包含它的候选码=无任何属性传

22、递函数依赖于非码的任何一组属性无任何属性传递函数依赖于非码的任何一组属性TnoST(Sno, Tno)BCNFST SnoCnoTnoTC(Cno, Tno)BCNFTC关系范式关系范式广东工业大学CIMS重点实验室25=3NF与与BCNF是以函数依赖为基础的关系模式规范化程是以函数依赖为基础的关系模式规范化程度的测度度的测度=如果满足如果满足BCNF，在函数依赖的范畴内，达到了最高在函数依赖的范畴内，达到了最高的规范化程度，消除了插入异常和删除异常的规范化程度，消除了插入异常和删除异常关系范式关系范式(Sno, Sname, Ssex, Sage, Sdept)BCNFStudent( Cn

23、o, Cname, Cpno,Ccredit)BCNFCourse(Sno, Cno, Grade)BCNFSC广东工业大学CIMS重点实验室26=例：开课表例：开课表关系范式关系范式教师教师课程课程班级班级王富强王富强张海水张海水李小平李小平机制工艺机制工艺00级机自本科级机自本科00级机自专科级机自专科01级机自本科级机自本科陈小毛陈小毛肖小兵肖小兵控制工程控制工程01级机自本科级机自本科00级机自本科级机自本科吴桂华吴桂华王嫦娥王嫦娥生产管理生产管理00级工业工程本科级工业工程本科01级工业工程本科级工业工程本科每门课由哪每门课由哪些老师开设些老师开设每门课哪些班每门课哪些班级需要开设级

24、需要开设广东工业大学CIMS重点实验室27=例：规范化的开课表例：规范化的开课表关系范式关系范式教师教师课程课程班级班级王富强机制工艺00级机自本科王富强机制工艺00级机自专科王富强机制工艺01级机自本科张海水机制工艺00级机自专科张海水机制工艺00级机自本科张海水机制工艺01级机自本科李小平机制工艺00级机自本科李小平机制工艺00级机自专科李小平机制工艺01级机自本科陈小毛控制工程01级机自本科陈小毛控制工程00级机自本科肖小兵控制工程01级机自本科肖小兵控制工程00级机自本科广东工业大学CIMS重点实验室28=多值依赖多值依赖 与函数依赖不同，函数依赖是属性值之间的约束与函数依赖不同，函数

25、依赖是属性值之间的约束关系，而多值依赖是元组值之间的约束关系。关系，而多值依赖是元组值之间的约束关系。=设设 R(U) 是属性集是属性集U上的一个关系模式，上的一个关系模式，X、 Y、 Z是是U的子（属性）集，且的子（属性）集，且Z=U-X-Y。 如果对如果对R（U）的任一关系的任一关系r，给定一对（，给定一对（x,z）值）值,都有一组都有一组Y值与之值与之对应，这组对应，这组Y值仅仅决定值仅仅决定于于x值而与值而与z值无关。值无关。 称称Y多多值依赖于值依赖于X，或，或X多值决定多值决定Y，记作，记作XY。上例：课程上例：课程教师，课程教师，课程班级班级如果如果Z=（即（即Z为空集）为空集）

26、,则称则称XY为平凡的多为平凡的多值依赖值依赖,否则为非平凡多值依赖否则为非平凡多值依赖关系范式关系范式广东工业大学CIMS重点实验室29=多值依赖的性质多值依赖的性质多值依赖具有对称性。多值依赖具有对称性。 4若若XY，则，则XZ，其中，其中Z=U-X-Y多值依赖具有传递性。多值依赖具有传递性。 4若若XY，YZ，则，则XZ-Y。 若若XY，XZ，则，则XYZ。 若若XY，XZ，则，则XYZ。 若若XY，XZ，则，则XY-Z，XZ-Y。关系关系R（A,B,C）,如果如果A决定决定B的多个值的多个值,A决定决定C的的多个值多个值,B和和C相互独立相互独立,这时才存在多值依赖这时才存在多值依赖关

27、系范式关系范式广东工业大学CIMS重点实验室30=第四范式（第四范式（4NF）如果关系模式如果关系模式R1NF，对于，对于R的每个的每个平凡的多平凡的多值依赖值依赖XY（YX），），X含有码，则称含有码，则称R是第是第四范式，即四范式，即R4NF。 一个关系模式如果属于一个关系模式如果属于4NF,则一定属于则一定属于BCNF,但但一个一个BCNF的关系模式不一定是的关系模式不一定是4NF的的,R中所有的中所有的非平凡多值依赖实际上是函数依赖。非平凡多值依赖实际上是函数依赖。 在前面例子中，课程在前面例子中，课程教师，课程教师，课程班级，班级，且都是非平凡的多值依赖。且都是非平凡的多值依赖。但该

28、关系的码是全码，但该关系的码是全码，而课程没有包含码（只是码的一部分），所以该而课程没有包含码（只是码的一部分），所以该关系模式属于关系模式属于BCNF而不属于而不属于4NF 关系范式关系范式广东工业大学CIMS重点实验室31=第四范式（第四范式（4NF）如将其分解为两个关系：可达到如将其分解为两个关系：可达到4NF： 教师开课（课程，教师）教师开课（课程，教师） 班级选课（课程，班级）班级选课（课程，班级）4这两个关系中：这两个关系中：课程课程教师教师，课程课程班级班级，它，它们均是平凡多值依赖。们均是平凡多值依赖。 即关系中已不存在非平凡、即关系中已不存在非平凡、 非非函数依赖的多值依赖函

29、数依赖的多值依赖,所以它们均是所以它们均是4NF。关系范式关系范式广东工业大学CIMS重点实验室32=例：例：关系范式关系范式广东工业大学CIMS重点实验室33=例例：项目项目供应商供应商, 项目项目零件。多值依赖具有以下性质零件。多值依赖具有以下性质但该关系的码是全码（项目但该关系的码是全码（项目,供应商供应商,零件）零件）,而项目没有包而项目没有包含码（只是码的一部分）含码（只是码的一部分）,所以该关系模式属于所以该关系模式属于BCNF而不而不属于属于4NF。 如将其分解为两个关系，可达到如将其分解为两个关系，可达到4NF： 需求（项目需求（项目, ,零件）零件） 供应（项目供应（项目,

30、,供应商）供应商）这两个关系中这两个关系中,项目项目零件零件,项目项目供应商供应商,它们均是平它们均是平凡多值依赖。凡多值依赖。 即关系中已不存在非平凡、即关系中已不存在非平凡、 非函数依赖的多非函数依赖的多值依赖值依赖,所以它们均是所以它们均是4NF。 关系范式关系范式广东工业大学CIMS重点实验室34=第四范式（第四范式（4NF）函数依赖可看成是多值依赖的特例函数依赖可看成是多值依赖的特例,即函数依赖的即函数依赖的一定是多值依赖；多值依赖是函数依赖的概括一定是多值依赖；多值依赖是函数依赖的概括,即即存在多值依赖的关系存在多值依赖的关系,不一定存在函数依赖。不一定存在函数依赖。 在一般应用中

31、，即使作数据存储操作，也只要达在一般应用中，即使作数据存储操作，也只要达到到BCNF就可以了。就可以了。 4因为应用中具有多值依赖的关系较少，因此需要达到因为应用中具有多值依赖的关系较少，因此需要达到4NF的情况也就比较少。的情况也就比较少。 还有与数据依赖中的连接依赖（还有与数据依赖中的连接依赖（JD）有关的第五）有关的第五范式（范式（5NF）.关系范式关系范式广东工业大学CIMS重点实验室35=什么是规范化什么是规范化一个低一级范式的关系模式，通过一个低一级范式的关系模式，通过模式分解模式分解可可以转化为若干个高一级范式的关系模式的集合，以转化为若干个高一级范式的关系模式的集合，这一过程叫

32、做关系模式的规范化。这一过程叫做关系模式的规范化。 规范化理论是在与规范化理论是在与SQL编程语言结合时产生的。编程语言结合时产生的。数据库被规范化后数据库被规范化后,其中的任何数据子集都可以用其中的任何数据子集都可以用基本的基本的SQL操作符获取。操作符获取。 数据库不进行规范化，就必须通过编写大量复杂数据库不进行规范化，就必须通过编写大量复杂代码来查询数据。代码来查询数据。 这就是规范化的重要性所在这就是规范化的重要性所在广东工业大学CIMS重点实验室36关系范式模式规范化关系范式模式规范化广东工业大学CIMS重点实验室37关系范式模式规范化关系范式模式规范化=满足第三范式为基本要求满足第

33、三范式为基本要求=把一个非规范化的数据结构转换成第三范式把一个非规范化的数据结构转换成第三范式一般经过以下几步：一般经过以下几步： 对那些存在组合码的属性，进行结构分解，使之对那些存在组合码的属性，进行结构分解，使之成为属于第一范式的关系。成为属于第一范式的关系。 对有非主属性部分函数依赖的关系继续分解，使对有非主属性部分函数依赖的关系继续分解，使所得关系都是属于第二范式。所得关系都是属于第二范式。若有非主属性传递依赖于码，则继续分解之，使若有非主属性传递依赖于码，则继续分解之，使得关系都属于第三范式。得关系都属于第三范式。广东工业大学CIMS重点实验室38关系范式模式规范化关系范式模式规范化

34、=规范化程度越高，分解就越细，所得数据库的数据规范化程度越高，分解就越细，所得数据库的数据冗余就越小，且更新错误也可相对减少冗余就越小，且更新错误也可相对减少。 =数据库设计满足的范式数据库设计满足的范式越高，其数据处理的越高，其数据处理的开销也越大开销也越大。如果某一关系经过数据大量加载后，主要用于如果某一关系经过数据大量加载后，主要用于检索，那么，即使它是一个低范式的关系，也检索，那么，即使它是一个低范式的关系，也不要去追求高范式而将其不断进行分解。不要去追求高范式而将其不断进行分解。 4因为在检索时，又会通过多个关系的自然连接才能获因为在检索时，又会通过多个关系的自然连接才能获得全部信息

35、，从而降低了数据的检索效率。得全部信息，从而降低了数据的检索效率。 广东工业大学CIMS重点实验室39关系范式模式规范化关系范式模式规范化=在规范化理论中，模式分解以及判断在规范化理论中，模式分解以及判断分解是否等价是有一定算法的。分解是否等价是有一定算法的。 =函数依赖的公理系统是模式分解算法函数依赖的公理系统是模式分解算法的基础，它可以从已知的函数依赖，推的基础，它可以从已知的函数依赖，推导出其他函数依赖。导出其他函数依赖。=1974年由年由Armstrong提出来的，常被称提出来的，常被称为为Armstrong公理系统公理系统广东工业大学CIMS重点实验室40=Armstrong公理系统

36、公理系统 设有关系模式设有关系模式R（U,F），），X,Y,Z,WU，则对则对R（U,F）有：）有： 4A1（自反律）：（自反律）： 若若YX,则则XY； 4A2（增广律）：（增广律）： 若若XY,则则XZYZ； 4A3（传递律）：（传递律）： 若若XY,YZ,则则XZ。说明：说明： XZ表示表示XZ。关系范式模式规范化关系范式模式规范化广东工业大学CIMS重点实验室41=由由Armstrong公理系统公理系统,可以得到以下三个可以得到以下三个推论：推论： 合成规则：合成规则： 若若XY，XZ，则：，则： XYZ； 分解规则：分解规则： 若若XYZ，则：，则：XY，XZ； 伪传递规则：若伪传递

37、规则：若XY，WYZ，则：，则： XWZ。=引理：引理： XA1A2Ak 成立的充分必要条件是成立的充分必要条件是 XAi （i=1,2,k） 成立成立关系范式模式规范化关系范式模式规范化广东工业大学CIMS重点实验室42= 例例 ： 设关系模式设关系模式R（A,B,C,G,H,I）, 函数依赖集为函数依赖集为 F=AB, AC, CGH, CGI, BH, 利用规则利用规则, 可以得到可以得到 R中存在以下几个函数依赖：中存在以下几个函数依赖： 1. AH。 l由于由于AB，BH，使用传递律可得到，使用传递律可得到AH。 2. CGHI。 l由于由于CGH，CGI，由合成律可得，由合成律可得

38、CGHI。 3. AGI。 l由于由于AC，CGI，由伪传递律可推出，由伪传递律可推出AGI。关系范式模式规范化关系范式模式规范化广东工业大学CIMS重点实验室43=分解的方法不是唯一的分解的方法不是唯一的=保证分解后的关系模式与原关系模式等价保证分解后的关系模式与原关系模式等价=例：例：SdeptSloc传递函数依赖传递函数依赖SL(Sno, Sdept, Sloc)NFSL2SnoSnoSdeptSloc98001计算机计算机一舍一舍98002机电工程机电工程五舍五舍98003材料材料四舍四舍98004材料材料四舍四舍98005机电工程机电工程五舍五舍98006自动化自动化一舍一舍关系范式

39、模式规范化关系范式模式规范化广东工业大学CIMS重点实验室44=例：例：SL(Sno, Sdept, Sloc)NFSL2关系范式模式规范化关系范式模式规范化Sno980019800298003980049800598006分解分解SD(Sdept)SN(Sno)SO(Sloc)Sdept计算机计算机机电工程机电工程材料材料自动化自动化Sloc一舍一舍五舍五舍四舍四舍NFSL598002在哪个系？在哪个系？98003住第几舍？住第几舍？信息丢失信息丢失广东工业大学CIMS重点实验室45=例：例：SL(Sno, Sdept, Sloc)NFSL2关系范式模式规范化关系范式模式规范化分解分解NL(

40、Sno, Sloc)DL(Sdept, Sloc)98001在哪个系？在哪个系？SnoSloc98001一舍一舍98002五舍五舍98003四舍四舍98004四舍四舍98005五舍五舍98006一舍一舍SdeptSloc计算机计算机一舍一舍机电工程机电工程五舍五舍材料材料四舍四舍自动化自动化一舍一舍信息丢失信息丢失广东工业大学CIMS重点实验室46=例：例：SL(Sno, Sdept, Sloc)NFSL2关系范式模式规范化关系范式模式规范化分解分解ND(Sno, Sdept)NL(Sno, Sloc)SnoSloc01一舍一舍02五舍五舍03四舍四舍04四舍四舍05五舍五舍06一舍一舍Sno

41、Sdept01计算机计算机02机电机电03材料材料04材料材料05机电机电06自动化自动化什么都知道了但还有麻烦仍有仍有问题问题数据冗余太多数据冗余太多如：同一个系更新复杂更新复杂如：转系需修改 Sloc插入异常插入异常如：无学生的系删除异常删除异常如：学生全毕业广东工业大学CIMS重点实验室47=例：例：SL(Sno, Sdept, Sloc)NFSL2关系范式模式规范化关系范式模式规范化分解分解DL(Sdept, Sloc)ND(Sno, Sdept)这样就全这样就全好了！好了！SnoSdept01计算机计算机02机电机电03材料材料04材料材料05机电机电06自动化自动化SdeptSlo

42、c计算机计算机一舍一舍机电工程机电工程五舍五舍材料材料四舍四舍自动化自动化一舍一舍广东工业大学CIMS重点实验室48设关系模式设关系模式R被分解为若干：被分解为若干：R1, R2, . Rn, 若若R与与R1、 R2、 Rn自然连接的结自然连接的结果相当，则称果相当，则称R的这个分解具有无损连接的这个分解具有无损连接性。性。关系范式模式规范化关系范式模式规范化广东工业大学CIMS重点实验室49 设设=R1,R2,Rk是关系模式是关系模式R（U,F）的一）的一个分解，如果对于个分解，如果对于R的任一满足的任一满足F的关系的关系r，都有，都有 则称分解则称分解满足函数依赖集满足函数依赖集F的无损连

43、接。的无损连接。关系范式模式规范化关系范式模式规范化广东工业大学CIMS重点实验室50ND(Sno, Sdept)NL(Sno, Sloc)= SL(Sno, Sdept, Sloc)SnoSdeptSloc01计算机计算机一舍一舍02机电机电五舍五舍03材料材料四舍四舍04材料材料四舍四舍05机电机电五舍五舍06自动化自动化一舍一舍=无损连接关系范式模式规范化关系范式模式规范化SnoSloc01一舍一舍02五舍五舍03四舍四舍04四舍四舍05五舍五舍06一舍一舍SnoSdept01计算机计算机02机电机电03材料材料04材料材料05机电机电06自动化自动化广东工业大学CIMS重点实验室51=

44、检验分解的无损连接性检验分解的无损连接性 输入：输入： 关系模式关系模式R（A1,A2,An）；）； R上的函数依赖集上的函数依赖集F； R上的分解上的分解=R1,R2,Rk。 输出：输出： 是否具有无损连接性。是否具有无损连接性。 =步骤：步骤： 构造一构造一k行行n列的表（或矩阵），第列的表（或矩阵），第i行对应于分行对应于分解后的关系模式解后的关系模式Ri，第，第j列对应于属性列对应于属性Aj关系范式模式规范化关系范式模式规范化jjiijijjiaARMbAR广东工业大学CIMS重点实验室52=检验分解的无损连接性检验分解的无损连接性=步骤：步骤： 构造一构造一k行行n列的表（或矩阵），

45、第列的表（或矩阵），第i行对应于分解行对应于分解后的关系模式后的关系模式Ri，第，第j列对应于属性列对应于属性Aj对对F中的每一个函数依赖进行反复的检查和处理。中的每一个函数依赖进行反复的检查和处理。4取取F中一个函数依赖中一个函数依赖XY，在，在X的分量中寻找相同的行，的分量中寻找相同的行，然后将这些行中的然后将这些行中的Y分量改为相同的符号。分量改为相同的符号。 即如果其中即如果其中之一为之一为aj,则将则将bij改为改为aj； 若其中无若其中无aj，则改为，则改为bij 如：如： 两个符号分别为两个符号分别为b23和和b13,则将它们统一改为则将它们统一改为b23或或b13。如此反复进行

46、，直至如此反复进行，直至M无可改变为止。如果发现某无可改变为止。如果发现某一行变成了一行变成了a1,a2,an，则，则具有无损连接性；具有无损连接性； 否则否则,不具有无损连接性不具有无损连接性关系范式模式规范化关系范式模式规范化广东工业大学CIMS重点实验室53=例例 ：设关系模式设关系模式R（U,F）中）中,U=A,B,C,D,E, F=ABC,CD,DE R的一个分解：的一个分解： =R1(A,B,C)，R2(C,D)，R3(D,E)。 试判断试判断具有无损连接性具有无损连接性。关系范式模式规范化关系范式模式规范化广东工业大学CIMS重点实验室54设关系模式设关系模式R被分解为若干被分解

47、为若干R1, R2, .Rn, 若若F所逻辑蕴涵的函数依赖一定也由分解得所逻辑蕴涵的函数依赖一定也由分解得 到的某个关系模式中的函数依赖到的某个关系模式中的函数依赖Fi所逻辑蕴所逻辑蕴 涵，则称涵，则称R的这个分解是保持函数依赖。的这个分解是保持函数依赖。关系范式模式规范化关系范式模式规范化广东工业大学CIMS重点实验室55设关系模式设关系模式R的一个分解的一个分解=R1,R2,Rk，F是是R的依赖集，的依赖集，如果如果F等价于等价于 则称分解则称分解具有依赖保持性。具有依赖保持性。 关系范式模式规范化关系范式模式规范化12( )( )( )KRRRFFF广东工业大学CIMS重点实验室56跨在两个关系跨在两个关系模式上模式上SL(Sno, Sdept, Sloc)NFSL2分解分解SnoSlocSnoSdept传递函数依赖关系范式模式规范化关系范式模式规范化SdeptSlocSnoND(Sno, Sdept)NL(Sno, Sloc)=SL(Sno, Sdept, Sloc)广东工业大学CIMS重点实验室57SL(Sno, Sdept, Sloc)NFSL2