函数依赖与范式

数据库原理和应用地理信息系统0423.1问题的提出3.2函数依赖3.3关系模式的规范化3.4函数依赖的公理系统（选）第三章关系数据库设计理论3.1规范化问题的提出3.1规范化问题的提出1.规范化理论的主要内容关系数据库的规范化理论最早是由关系数据库的创始人E.F.Codd提出的，后经许多专家学者对关系数据库理论作了深入的研究和发展，形成了一整套有关关系数据库设计的理论。在该理论出现以前，层次和网状数据库的设计只是遵循其模型本身固有的原则，而无具体的理论依据可言，因而带有盲目性，可能在以后的运行和使用中发生许多预想不到的问题。•在关系数据库系统中，关系模型包括一组关系模式，各个关系不是完全孤立的，数据库的设计较层次和网状模型更为重要。•如何设计一个适合的关系数据库系统，关键是关系数据库模式的设计，一个好的关系数据库模式应该包括多少关系模式，而每一个关系模式又应该包括哪些属性，又如何将这些相互关联的关系模式组建一个适合的关系模型，这些工作决定了到整个系统运行的效率，也是系统成败的关键所在，所以必须在关系数据库的规范化理论的指导下逐步完成。•关系数据库的规范化理论主要包括三个方面的内容：–函数依赖–范式（NormalForm）–模式设计•其中，函数依赖起着核心的作用，是模式分解和模式设计的基础，范式是模式分解的标准。关系模式的存储异常问题•数据库的逻辑设计为什么要遵循一定的规范化理论？•什么是好的关系模式？•某些不好的关系模式可能导致哪些问题？•下面通过例子进行分析:例如，要求设计教学管理数据库，其关系模式SCD如下：–SCD(SNO,SN,AGE,DEPT,MN,CNO,SCORE)•其中，SNO表示学生学号，SN表示学生姓名，AGE表示学生年龄，DEPT表示学生所在的系别，MN表示系主任姓名，CNO表示课程号，SCORE表示成绩。根据实际情况，这些数据有如下语义规定：–1.一个系有若干个学生，但一个学生只属于一个系；–2.一个系只有一名系主任，但一个系主任可以同时兼几个系的系主任；–3.一个学生可以选修多门功课，每门课程可有若干学生选修；–4.每个学生学习课程有一个成绩。•在此关系模式中填入一部分具体的数据，则可得到SCD关系模式的实例，即一个教学管理数据库，如图4.1所示。图3.1关系SCDSNOSNAGEDEPTMNCNOSCORES1赵亦17计算机刘伟C190S1赵亦17计算机刘伟C285S2钱尔18信息王平C557S2钱尔18信息王平C680S2钱尔18信息王平C770S2钱尔18信息王平C570S3孙珊20信息王平C10S3孙珊20信息王平C270S3孙珊20信息王平C485S4李思男自动化刘伟C193•根据上述的语义规定，并分析以上关系中的数据，我们可以看出：(SNO,CNO)属性的组合能唯一标识一个元组，所以(SNO,CNO)是该关系模式的主关系键。但在进行数据库的操作时，会出现以下几方面的问题。–1.数据冗余。每个系名和系主任的名字存储的次数等于该系的学生人数乘以每个学生选修的课程门数，同时学生的姓名、年龄也都要重复存储多次，数据的冗余度很大，浪费了存储空间。–2.插入异常。如果某个新系没有招生，尚无学生时，则系名和系主任的信息无法插入到数据库中。•因为在这个关系模式中，(SNO,CNO)是主关系键。根据关系的实体完整性约束，主关系键的值不能为空，而这时没有学生，SNO和CNO均无值，因此不能进行插入操作。•另外，当某个学生尚未选课，即CNO未知，实体完整性约束还规定，主关系键的值不能部分为空，同样不能进行插入操作。–3.删除异常。–某系学生全部毕业而没有招生时，删除全部学生的记录则系名、系主任也随之删除，而这个系依然存在，在数据库中却无法找到该系的信息。–另外，如果某个学生不再选修C1课程，本应该只删去C1，但C1是主关系键的一部分，为保证实体完整性，必须将整个元组一起删掉，这样，有关该学生的其它信息也随之丢失。–4.更新异常。–如果学生改名，则该学生的所有记录都要逐一修改SN；–又如某系更换系主任，则属于该系的学生记录都要修改MN的内容，稍有不慎，就有可能漏改某些记录，这就会造成数据的不一致性，破坏了数据的完整性。•由于存在以上问题，我们说，SCD是一个不好的关系模式。产生上述问题的原因，直观地说，是因为关系中“包罗万象”，内容太杂了。•那么，怎样才能得到一个好的关系模式呢？•我们把关系模式SCD分解为下面三个结构简单的关系模式，如图3.2所示。–学生关系S(SNO,SN,AGE,DEPT)–选课关系SC(SNO,CNO,SCORE)–系关系D(DEPT,MN)SSCSNOSNAGEDEPTSNOCNOSCORES1赵亦17计算机S1C190S2钱尔18信息S1C285S3孙珊20信息S2C557S4李思21自动化S2C680S2C7DS2C570DEPTMNS3C10计算机刘伟S3C270信息王平S3C485自动化刘伟S4C193图3.2分解后的关系模式•在以上三个关系模式中，实现了信息的某种程度的分离，–S中存储学生基本信息，与所选课程及系主任无关；–D中存储系的有关信息，与学生无关；–SC中存储学生选课的信息，而与所学生及系的有关信息无关。•与SCD相比，分解为三个关系模式后，数据的冗余度明显降低。–当新插入一个系时，只要在关系D中添加一条记录。–当某个学生尚未选课，只要在关系S中添加一条学生记录，而与选课关系无关，这就避免了插入异常。–当一个系的学生全部毕业时，只需在S中删除该系的全部学生记录，而关系D中有关该系的信息仍然保留，从而不会引起删除异常。–同时，由于数据冗余度的降低，数据没有重复存储，也不会引起更新异常。•经过上述分析，我们说分解后的关系模式是一个好的关系数据库模式。•从而得出结论，一个好的关系模式应该具备以下四个条件：–1.尽可能少的数据冗余。–2.没有插入异常。–3.没有删除异常。–4.没有更新异常。•但要注意，一个好的关系模式并不是在任何情况下都是最优的，–比如查询某个学生选修课程名及所在系的系主任时，要通过连接，而连接所需要的系统开销非常大，因此要以实际设计的目标出发进行设计•如何按照一定的规范设计关系模式，将结构复杂的关系分解成结构简单的关系，从而把不好的关系数据库模式转变为好的关系数据库模式，这就是关系的规范化。•规范化又可以根据不同的要求而分成若干级别。•我们要设计的关系模式中的各属性是相互依赖、相互制约的，这样才构成了一个结构严谨的整体。•因此在设计关模式时，必须从语义上分析这些依赖关系。•数据库模式的好坏和关系中各属性间的依赖关系有关，因此，我们先讨论属性间的依赖关系，然后再讨论关系规范化理论。3.2函数依赖关系模式中的各属性之间相互依赖、相互制约的联系称为数据依赖。这种约束关系是通过属性值之间的依赖关系来体现的。数据依赖一般分为函数依赖、多值依赖和连接依赖。其中,函数依赖是最重要的数据依赖。函数依赖（FunctionalDependency）是关系模式中属性之间的一种逻辑依赖关系。属性间的这种依赖关系类似于数学中的函数y=f（x），自变量x确定之后，相应的函数值y也就惟一地确定了。现在我们建立一个描述学校教务的数据库，该数据库涉及的对象包括学生的学号（Sno）、所在系（Sdept）、系主任姓名（Mname）、课程名（Cname）成绩（Grade）假设我们用一个单一的关系模式Student来表示，则该关系模式的属性集为：U＝{Sno，Sdept，Mname，Cname，Grade}现实世界的已知事实（语义）告诉我们：（1）一个系有若干学生，但一个学生只属于一个系。（2）一个系只有一名主任。（3）一个学生可以选修多门课程，每门课程有若干学生选修。（4）每个学生所学的每门课程都有一个成绩。从上述事实我们可以得到属性集U上的一组函数依赖F：F＝{Sno→Sdept，Sdept→Mname，(Sno，Cname)→Grade}如果只考虑函数依赖这一种数据依赖，我们就得到了一个描述学生的关系模式：StudentU，F函数依赖的定义：设关系模式R(U，F)，U是属性全集，F是U上的函数依赖集，X和Y是U的子集，如果对于R(U)的任意一个可能的关系r，对于X的每一个具体值，Y都有唯一的具体值与之对应，则称X决定函数Y，或Y函数依赖于X，记作X→Y。我们称X为决定因素，Y为依赖因素。当Y不函数依赖于X时，记作：XY。当X→Y且Y→X时，则记作：XY。•对于关系模式SCDU={SNO,SN,AGE,DEPT,MN,CNO,SCORE}F={SNO→SN，SNO→AGE，SNO→DEPT}有关函数依赖的几点说明：1．平凡的函数依赖与非平凡的函数依赖。–当属性集Y是属性集X的子集时，则必然存在着函数依赖X→Y,这种类型的函数依赖称为平凡的函数依赖。–如果Y不是X的子集，则称X→Y为非平凡的函数依赖。–若不特别声明，我们讨论的都是非平凡的函数依赖。2．函数依赖是语义范畴的概念。–我们只能根据语义来确定一个函数依赖，而不能按照其形式化定义来证明一个函数依赖是否成立。–例如，对于关系模式S，当学生不存在重名的情况下，可以得到：•SN→AGE•SN→DEPT–这种函数依赖关系，必须是在没有重名的学生条件下才成立的，否则就不存在函数依赖了。–所以函数依赖反映了一种语义完整性约束。3．函数依赖与属性之间的联系类型有关。（1）在一个关系模式中，如果属性X与Y有1:1联系时，则存在函数依赖X→Y，Y→X，即XY。例如，当学生无重名时，SNOSN。（2）如果属性X与Y有1:m的联系时，则只存在函数依赖X→Y。例如，SNO与AGE，DEPT之间均为1:m联系，所以有SNO→AGE，SNO→DEPT。（3）如果属性X与Y有m:n的联系时，则X与Y之间不存在任何函数依赖关系。例如，一个学生可以选修多门课程，一门课程又可以为多个学生选修，所以SNO与CNO之间不存在函数依赖关系。•由于函数依赖与属性之间的联系类型有关，所以在确定属性间的函数依赖关系时，可以从分析属性间的联系类型入手，便可确定属性间的函数依赖。4．函数依赖关系的存在与时间无关。–因为函数依赖是指关系中的所有元组应该满足的约束条件，而不是指关系中某个或某些元组所满足的约束条件。–当关系中的元组增加、删除或更新后都不能破坏这种函数依赖。–因此，必须根据语义来确定属性之间的函数依赖，而不能单凭某一时刻关系中的实际数据值来判断。–例如，对于关系模式S，假设没有给出无重名的学生这种语义规定，则即使当前关系中没有重名的记录，也只能存在函数依赖SNO→SN，而不能存在函数依赖SN→SNO，因为如果新增加一个重名的学生，函数依赖SN→SNO必然不成立。–所以函数依赖关系的存在与时间无关，而只与数据之间的语义规定有关。5．函数依赖可以保证关系分解的无损连接性。–设R（X，Y，Z），X，Y，Z为不相交的属性集合，如果X→Y或X→Z,则有R(X，Y，Z)=R[X，Y]*R[X，Z]，–其中，R[X，Y]表示关系R在属性（X，Y）上的投影，即R等于其投影在X上的自然连接，这样便保证了关系R分解后不会丢失原有的信息，称作关系分解的无损连接性。–例如，对于关系模式SCD，有SNO→（SN，AGE，DEPT，MN），SCD（SNO，SN，AGE，DEPT，MN，CNO，SCORE）=SCD[SNO，SN，AGE，DEPT，MN]*SCD[SNO，CNO，SCORE]，也就是说，用其投影在SNO上的自然连接可复原关系模式SCD。–这一性质非常重要，在后一节的关系规范化中要用到。函数依赖的基本性质1．投影性。–根据平凡的函数依赖的定义可知，一组属性函数决定它的所有子集。–例如，在关系SCD中，（SNO，CNO）→SNO和（SNO，CNO）→CNO。2．扩张性。–若X→Y且W→Z，则（X，W）→（Y，Z）。–例如，SNO→（SN，AGE），DEPT→MN，则有（SNO，DEPT）→（SN，AGE，MN）。3．合并性。–若X→Y且X→Z则必有X→（Y，Z）。–例如