数据库上课 第十讲 关系数据理论与范式

第十讲关系数据理论

与范式主讲：顾曦电话mail：guxi@数据库系统原理与设计主要内容1、

问题的提出2、函数依赖的概念3、函数依赖理论4、范式5、模式的分解*21、问题的提出1.1回顾：关系模式的形式化定义关系模式是一个五元组：

R(U,D,DOM,F)R：关系名U：组成该关系的属性名集合D：属性组U中属性所来自的域DOM：属性向域的映象集合F：属性间数据的依赖关系集合*4简化表示简化为一个三元组：

R（U,F）当且仅当U上的一个关系r满足F时，r称为关系模式R（U,F）的一个关系*51.2数据冗余定义：同一信息在数据库中存储了多个副本。[例5.1]

学生选课关系模式SCE(studentNo,courseNo, studentName,courseName,score)若：一个学生可选修多门课程一门课程可被多个学生选修可能的数据：*6主码studentNoStudentNamecourseNocourseNamescoreS0700001李小勇C001高等数学98S0700001李小勇C002离散数学82S0700001李小勇C006数据库系统原理56S0700002刘方晨C003计算机原理69S0700002刘方晨C004C语言程序设计87S0700002刘方晨C005数据结构77S0700002刘方晨C007操作系统90S0700003王红敏C001高等数学46S0700003王红敏C002离散数学38S0700003王红敏C007操作系统50出现的问题冗余存储：学生姓名和课程名被重复存储多次；更新异常：当修改某学生的姓名或某课程的课程名时，可能只修改了部分数据；插入异常：如果某学生没有选修课程，或某门课程未被任何学生选修时，则该学生或该课程信息不能存入数据库，因为主码值不能为空；删除异常：当一学生的所有选修课程信息都被删除时，则该学生的信息将被丢失。对课程也是如此。*7数据冗余带来的问题冗余存储：信息被重复存储，导致浪费大量存储空间。更新异常：当重复信息的一个副本被修改，所有副本都必须进行同样的修改。插入异常：只有当一些信息事先已经存放在数据库中时，另外一些信息才能存入数据库中。删除异常：删除某些信息时可能丢失其它信息。*8数据冗余产生原因及解决方法产生问题的原因:该模式中某些属性之间存在依赖关系studentNo→studentName（即学号决定姓名）courseNo→courseName（即课程编号决定课程名称）{studentNo,courseNo}→score解决方法：将一个关系模式分解为较小的关系模式。上例分解为三个关系模式

S(studentNo,studentName)C(courseNo,courseName)E(studentNo,courseNo,score)*9如何分解[例5.2]设一关系模式STU(studentNo,studentName,sex,birthday,native,classNo)，其中studentNo为主码。假设将STU分解为以下两个子模式：STU1(studentNo,studentName)STU2(studentName,sex,birthday,native,classNo)分解后会发生什么问题？*10studentNostudnetNamesexbirthdaynativeclassNoS0700005王红男1992-4-26江西省南昌市CS0702S0800005王红女1995-8-10湖北省武汉市CP0802studentNostudnetNameS0700005王红S0800005王红studnetNamesexbirthdaynativeclassNo王红男1992-4-26江西省南昌市CS0702王红女1995-8-10湖北省武汉市CP0802studentNostudnetNameSexbirthdaynativeclassNoS0700005王红男1992-4-26江西省南昌市CS0702S0700005王红女1995-8-10湖北省武汉市CP0802S0800005王红男1992-4-26江西省南昌市CS0702S0800005王红女1995-8-10湖北省武汉市CP0802*11模式分解存在的问题有损分解：两个分解后的关系通过连接运算还原得到的信息与原来关系的信息不一致。如果能够通过连接分解后所得到的较小关系完全还原被分解关系的所有实例，称之为无损分解(losslessdecomposition)，也称该分解具有无损连接特性。依赖关系丢失：sex、birthday、age、native、classNo等与属性studentNo依赖关系不再存在。如果被分解关系模式上的所有依赖关系都在分解得到的关系模式上保留，称该分解为保持依赖分解。一个“好”的关系模式数据冗余尽可能少不发生插入异常、删除异常、更新异常等问题。模式分解时，分解后的模式应具有无损连接、保持依赖等特性。*13问题？为什么模式分解能解决数据冗余问题？什么样的关系模式需要进一步分解？是否所有的模式分解都是有益的？如何分解？*142、函数依赖与码2.1函数依赖定义函数依赖(functionaldependency,简称FD)：

一种完整性约束，是事物属性之间的一种制约关系。定义5.1设r(R)为关系模式，属性集R，R。对任意合法关系r及其中任两个元组ti和tj，ij，当ti[]=tj[]时，则ti[]=tj[]，则称函数确定或函数依赖于，记作。函数依赖图*16返回例如图所示的是满足函数依赖ABC的关系模式r(A,B,C,D)的一个关系实例。对于任意两个在属性集{A,B}上取值相同的元组，它们在属性C上的取值也相同。ABCDa1b1c1d1a1b1c1d2a1b2c2d1a2b1c3d1

满足函数依赖ABC的一个关系实例问：如果在图中再增加一个元组(a1,b1,c2,

d1)，ABC

还成立吗？函数依赖说明函数依赖指关系模式r(R)的所有关系实例均要满足的约束条件。函数依赖是语义范畴的概念，只能根据数据的语义来确定函数依赖，是不能够被证明的。数据库设计者可以对现实世界作强制的规定。码约束是函数依赖的一个特例。码属性(集)相当于定义“”中的，关系中的所有属性相当于定义。*182.2平凡与非平凡函数依赖定义5.2

在关系模式r(R)中，R，R。若，但，则称是非平凡函数依赖。否则，若,则称是平凡函数依赖。对于任一关系模式，平凡函数依赖总是成立的。(a)非平凡函数依赖(b)平凡函数依赖*192.3完全函数依赖和部分函数依赖定义5.3

在关系模式r(R)中，R，R，且。若对任意的，都不成立，则称是完全函数依赖，简称完全依赖，记作

F

。当是单属性时，则完全函数依赖总是成立的。否则，若存在非空的，且成立,则称是部分函数依赖，简称部分依赖，记作

P

。部分依赖可能会导致数据冗余及产生各种异常。*20举例例如，在关系SCESCE(studentNo,courseNo, studentName,courseName,score)中完全依赖：studentNostudentNamecourseNocourseName{studentNo,courseNo}score部分依赖：{studentNo,courseNo}studentName{studentNo,courseNo}courseName*212.4传递函数依赖定义5.4

在关系模式r(R)中，R，R，，R。若，，，则必存在函数依赖，并称是传递函数依赖，简称传递依赖，→。与部分依赖一样，传递依赖也可能会导致数据冗余及产生各种异常。传递*22传递[例5.4]关系模式SCI(studentNo,classNo,institute)存在下列函数依赖：studentNoclassNoinstitutestudentNoinstitute（传递函数依赖）关系模式SCI中存在传递依赖studentNoinstitute，因此可能导致数据冗余、更新异常、插入异常及删除异常（p166）。*232.5码定义

设K为R<U,F>中的属性或属性组合。若K

U，则K称为R的侯选码（CandidateKey）。候选码多于一个，则选定其中的一个做为主码（PrimaryKey）。侯选码的超集称为超码。F*24主属性与非主属性主属性（Primeattribute）:包含在任何一个候选码中的属性。非主属性(非码属性):不包含在任何码中的属性全码:整个属性组是码，称为全码（All-key）*25例:Student（StudentNo,sex,native)中：单个属性StudentNo是码，StudentNo是主属性。SC（StudentNo，CourseNo，score）：（StudentNo，CourseNo）是码，StudentNo是主属性，score是非主属性。关系模式R（P，W，A）。其中

P：演奏者W：作品A：听众一个演奏者可以演奏多个作品某一作品可被多个演奏者演奏听众可以欣赏不同演奏者的不同作品码为(P，W，A)，即All-Key*262.6外部码定义

关系模式R中属性或属性组X并非R的码，但X是另一个关系模式S的码，则称X是R的外部码（Foreignkey）也称外码如在SC（StudentNo，CourseNo，score）中，StudentNo不是码，但StudentNo是关系模式Student（StudentNo,sex,native)的码，则StudentNo是关系模式SC的外部码

主码与外部码一起提供了表示关系间联系的手段*273、函数依赖理论*283.1函数依赖集闭包对于给定关系模式r(R)及其函数依赖集F，需要考虑在r(R)上总是成立的所有函数依赖。[例5.5]

给定关系模式r(R)=r(A,B,C)及函数依赖集F={AB,BC}，证明AC成立。证明：假设对于关系实例r中的任意元组ti,tj,ij，满足ti[A]=tj[A]。由于存在AB，则可推出ti[B]=tj[B]。又由于BC，则又可推出ti[C]=tj[C]。因此，ti[A]=tj[A]

ti[C]=tj[C]。按定义5.1有AC。证毕。函数依赖集闭包定义5.5

若给定函数依赖集F，可以证明其他函数依赖也成立，则称这些函数依赖被F逻辑蕴涵。定义5.6

令F为一函数依赖集，F逻辑蕴涵的所有函数依赖组成的集合称为F的闭包，记为F+。函数依赖集F的闭包计算方法Armstrong公理的推理规则Armstrong公理及推论Armstrong公理自反律(reflexivityrule)：若存在，则有增补律(augmentationrule)：若存在，则有传递律(transitivityrule)：若存在且，则有Armstrong公理三个推论合并律(unionrule)：若有且，则有分解律(decompositionrule)：若有，则有和伪传递律(pseudotransitivityrule)：若有且，则有函数依赖集闭包计算举例[例5.6]

令r(R)=r(A,B,C,G,H,I)，函数依赖集F={AB,AC,CGH,CGI,BH}，计算F+中的依赖。由传递律可得AH，因为AB且BH；由合并律可得CGHI，因为CGH，CGI；由伪传递律可得AGI，因为AC且CGI。还可以使用上述规则推导出更多的函数依赖。

3.2属性集闭包定义5.7令r(R)为关系模式，F为函数依赖集，属性集AR，则称在函数依赖集F下由A函数确定的所有属性的集合为F下A的闭包，记为A+。属性集闭包计算举例[例5.7]r(R)=r(A,B,C,G,H,I)，

F={AB,AC,CGH,CGI,BH}，计算(AG)+。

算法：

步骤

FD

closure

1．初值AG2．

ABABG3．ACABCG4．CGHABCGH5．CGIABCGHI6．BHABCGHI第一次循环结果：closure=ABCGHI。算法第二次循环后的结果为closure=ABCGHI，没有变化，算法终止。属性集AG的闭包：(AG)+＝ABCGHI。计算属性集闭包的作用验证是否在F+中：看是否有+。判断是否为r(R)的超码：通过计算+，看其是否包含R的所有属性。例如，(AG)+＝ABCGHI，则AG为r(R)的超码。判断是否为r(R)的候选码：若是超码，可检验包含的所有子集的闭包是否包含R的所有属性。若不存在任何这样的属性子集，则是r(R)的候选码。计算F+。对于任意R，可通过找出+，对任意的S+，可输出一个S。判断属性集是否为候选码举例[例5.8]

r(R)和F定义同例5.7，判断AG是否为r(R)的候选码。例5.7已计算出(AG)+＝ABCGHI,则还要进一步分别计算A+和G+。经计算得，A+=ABCH、G+=G，它们都不包含R的所有属性。因此，AG为r(R)的候选码。3.3无关属性定义5.8

给定函数依赖集F及→F，如果去除或的一个属性不会改变F+，则称该属性是无关的。定义5.9

给定函数依赖集F及→F，若A，且F逻辑蕴涵(F-{→}){(-A)

}（即，没有产生新的函数依赖），则属性A在中是无关的（左无关）。定义5.10

给定函数依赖集F及→F，若A，且(F-{}){((-A)}逻辑蕴涵F，则属性A在中是无关的（右无关）。

(-A)

=>

[例5.9]设F＝{AB→CD,A→E,E→C}，证明C在AB→CD中为无关属性。证明：步骤：计算F'F‘={AB→D,A→E,E→C}下(AB)+：(AB)+=ABCDE；所以，F‘逻辑蕴含AB→CD，即F‘逻辑蕴含F。因此，C是AB→CD中的无关属性。证毕。无关属性检测算法（p169图5-9）思路:

由于C是AB→CD依赖关系中的右边属性，需证明F‘={AB→D,A→E,E→C}逻辑蕴含F，即证明F‘逻辑蕴含F’中没有的函数依赖：AB→CD3.4正则覆盖定义5.11

正则覆盖(canonicalcover)Fc是一个依赖集，使得F逻辑蕴涵Fc中的所有依赖，Fc逻辑蕴涵F中的所有依赖，而且必须具有下列特性：Fc中的任何函数依赖都不包含无关属性；Fc中函数依赖的左半部都是唯一的，即Fc中不存在两个依赖1→1和1→2。计算F的正则覆盖Fc的步骤合并函数依赖将F中所有形如1→1、1→2的函数依赖合并为1→12，得到新函数依赖集F'。去除无关属性对F'中的每个函数依赖，依次判断是否包含无关属性。若发现无关属性，则用去除无关属性后的函数依赖代替F'中的原函数依赖。*40关于验证无关属性的方法左属性无关算去掉验证属性的左属性集闭包包含右，则无关*41算左看右右属性无关去掉验证属性，得F’算左属性集闭包包含原右，则无关计算正则覆盖举例[例5.10]考虑关系模式r(R)=r(A,B,C)和函数依赖集F={A→BC,B→C,A→B,AB→C},计算F的正则覆盖Fc。解题步骤合并函数依赖：将A→BC和A→B合并为A→BC。

故

F'={A→BC,B→C,AB→C}。去除无关属性：对于AB→C，根据图5-9(a)的算法可检测A是无关的。因此，去除无关属性A后，AB→C变为B→C，而B→C已在F'中存在，则F'={B→C,A→BC}。对于B→C，由于其左右两边都为单属性，故不存在无关属性。对于A→BC，根据图5-9(b)的算法可检测C是无关的。因此，去除无关属性C后，A→BC变为A→B，则F'={B→C,A→B}。F'中的函数依赖左半部都是唯一的，且都不存在无关属性，因此Fc={B→C,A→B}。*43正则覆盖说明Fc与F具有相同的闭包；Fc不包含无关属性，每个依赖是最小的，且是必要的；正则覆盖不一定唯一。函数依赖小结函数依赖是指关系模式中属性之间存在的一种约束关系这种约束关系既可以是现实世界事物或联系的属性之间客观存在的约束，也可以是数据库设计者根据应用需求或设计需要强加给数据的一种约束。正确了解数据的意义及确定属性之间的函数依赖关系，对设计一个好的关系模式是十分重要的。*454、设计范式（规范化）*46

范式概述范式是符合某一种级别的关系模式的集合关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式范式的种类：

*47第一范式(1NF)第二范式(2NF)第三范式(3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF)各种范式之间存在联系某一关系模式R为第n范式，可简记为R∈nNF。一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化

*484.1第一范式(1NF)——码定义5.16

如果一关系模式r(R)的每个属性对应的域值都是不可分的（即原子的），则称r(R)属于第一范式，记为r(R)1NF。第一范式的目标是：将基本数据划分成称为实体集或表的逻辑单元，当设计好每个实体后，需要为其指定主码。studentNostudentNamesexbirthdayageaddressclassNoprovincecitystreet图5-10非规范化的关系模式studentNostudentNamesexbirthdayageprovincecitystreetclassNo图5-111NF规范化后的关系模式问题：例4.1(参考教材p175)关系模式S-L-C(Sno,Cno,Sdept,Sloc,Score)，Sloc为学生住处假设：，假设每个系的学生住在同一个地方。关系S-L-C的码为(Sno,Cno)关系S-L-C满足第一范式。*50非主属性Sdept和Sloc部分函数依赖于码(Sno,Cno)*51函数依赖包括：(Sno,Cno)FScoreSno→Sdept(Sno,Cno)PSdeptSno→Sloc(Sno,Cno)PSlocSdept→Sloc...出现的问题：(1)插入异常：未选课的学生无法加入。(2)删除异常：只选一门课的学生取消选择时，该学生信息（元组）被删除。(3)数据冗余度大：多选课时，学生信息多次录入。(4)修改复杂：学生转系时，需多处修改Sloc。*52原因:

Sdept、Sloc部分依赖于码4.2第二范式(2NF)——全部码定义5.18

若R∈1NF，且每一个非主属性完全函数依赖于码，则R∈2NF。第二范式的目标是：将只部分依赖于主码（即依赖于主码的部分属性）的数据移到其他表中。在满足第一范式的实体中，如果有复合主码（即多个属性共同构成主码），那么所有非主属性必须依赖于全部的主码，而不能只是依赖于部分的主码属性。违背了2NF的模式，即存在非主属性对候选码的部分依赖，则可能导致例5.1所述的数据冗余及异常问题*53修改例4.1*54SnoCnoScoreSCS-LSnoSdeptSloc

S-L-C分解为两个关系模式，以消除这些部分函数依赖SC（Sno，Cno，Score）S-L（Sno，Sdept，Sloc）关系模式SC的码为（Sno，Cno）关系模式S-L的码为Sno非主属性对码都是完全函数依赖;

SC∈2NF、S-L∈2NF函数依赖图问题：如果学生转系，或某系更换住处，会发生什么情况？*55S-LSnoSdeptSloc函数依赖：

Sno→SdeptSdept→Sloc

Sno→Sloc，即S-L中存在非主属性对码的传递函数依赖4.3第三范式(3NF)——仅仅是码定义

关系模式R（U，F）

中若不存在这样的码X、属性组Y及非主属性Z（ZY）,使得X→Y，Y→Z成立，

Y→X，则称R（U，F）∈3NF。若R∈3NF，则每一个非主属性既不部分依赖于码也不传递依赖于码。*56第三范式的目标是：去掉表中不依赖于主码的数据。在满足第二范式的实体中，非主属性不能依赖于另一个非主属性，即所有的非主属性应该直接依赖于全部的主属性（即必须完全依赖，这是2NF的要求），并且彼此之间无相互依赖关系（即不能存在部分依赖，这是3NF的要求）。换一句话说，非主属性不能包括它们自己的属性，如果属性不包括属性，则它们就是真正的实体。*57例3NF解决办法采用投影分解法（以决定性的非主属性为码），把S-L分解为两个关系模式，以消除传递函数依赖：S-D（Sno，Sdept）D-L（Sdept，Sloc）S-D的码为Sno，D-L的码为Sdept。分解后的关系模式S-D与D-L中不再存在传递依赖*58SnoSdeptS-DSdeptSlocD-L问题：在关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示课程。每个教师只教一门课。每门课有若干教师，某一学生选定某门课，就对应一个固定的教师。函数依赖：(S，J)→T，(S，T)→J，T→J(S，J)和(S，T)是候选码∵一个非主属性都没有∴R∈3NF*59SJTSTJ问题：插入异常：（无法存放没有选的课和老师）删除异常：（删除选课信息时，丢失课程和老师的对应信息）修改复杂：（如修改课程对应的老师）*60BCNFBCNF是由Boyce和Codd提出的,比3NF又进了一步,通常认为是修正的第三范式.定义5.19

给定关系模式r(R)及函数依赖集F，若F+中的所有函数依赖

(R，R)至少满足下列条件之一：是平凡函数依赖(即)；是r(R)的一个超码(

+包含R的全部属性，起决定作用的属性必须是超码)。则称r(R)属于Boyce-Codd范式，记为r(R)BCNF。即：*61推论在关系模式r(R)中，如果F+中的每一个非平凡函数依赖的决定属性集都包含候选码，则r(R)BCNF。所有非主属性对每一个码都是完全函数依赖（3NF）所有的主属性对每一个不包含它的码都是完全函数依赖没有任何属性完全函数依赖于非码的一组属性*623NF的问题函数依赖：(S，J)→T，(S，T)→J，T→J（每个教师只教一门课）(S，J)和(S，T)是候选码主属性J部分依赖码(S，T)解决方法：可分解为ST(S,T)与TJ（T,J)它们都是BCNF。*63BC范式判断举例[例5.13]

r(R)=r(A,B,C)，F={A→B,B→C}，候选码为A。r(R)BCNF，因为函数依赖B→C中的决定属性B不是超码。[例5.14]

r(R)=r(A,B,C)，候选码为AB或BC，F={AB→C,C→A}。r(R)BCNF，因为C→A的决定属性C不是超码。[例5.15]

r(R)=r(A,B,C)，F={AB→C,BC→A}。候选码为AB或BC。r(R)BCNF，因为两个函数依赖中的决定属性AB或BC都是r(R)的候选码。*643NF与BCNF比较BCNF比3NF严格。BCNF要求所有的非平凡函数依赖中的是超码，而3NF则放松了该约束，允许不是超码。若关系模式属于BCNF范式就一定属于3NF范式。反之，则不一定成立。3NF存在数据冗余和异常问题，而BCNF是基于函数依赖理论能够达到的最好关系模式。*65关系模式规范化的基本步骤*66规范化小结规范化程度越高的关系模式不一定就越好在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式上面的规范化步骤可以在其中任何一步终止*675、模式的分解5.1无损连接分解5.2保持依赖分解模式的分解的概念把低一级的关系模式分解为若干个高一级的关系模式的方法不是唯一的只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义即：分解既要保持函数依赖，又要具有无损连接性*695.1无损连接分解定义5.12

给定关系模式r(R)及函数依赖集F，若r(R)的任意一个满足函数依赖集F的关系实例r都有

=r，其中r1(R1)、r2(R2)分别为分解后的子模式，则称该分解对于F是无损连接的。无损连接分解能够根据分解后的关系通过连接来还原原来的关系实例。具有无损连接性的分解保证不丢失信息.如何判定一分解是否是无损的？*70无损连接分解判断方法定义5.13

给定关系模式r(R)及函数依赖集F，则将r(R)分解成r1(R1)、r2(R2)的分解是无损连接分解，当且仅当F+包含函数依赖R1R2→R1或R1R2→R2。即，当一个关系模式分解为两个关系模式时，该分解为无损连接分解的充要条件是两分解关系的公共属性包含r1(R1)的码或r2(R2)的码。*715.2保持依赖分解[例5.12]

设关系模式r(R)=r(A,B,C)，F={AB,BC}，有两种分解：r1(R1)=r1(A,B)、r2(R2)

=r2(B,C)r1(R1)=r1(A,B)、r2(R2)=r2(A,C)。分解1是保持依赖分解；分解2不是保持依赖分解（函数依赖BC丢失）因为分解后，函数依赖BC既不能从F在R1的投影F1中推导出来，也不能从F在R2的投影F2中推导出来。*726、模式求精*73定义模式求精：运用关系理论(如函数依赖理论、多值依赖理论等)对已有关系模式进行结构调整、分解、合并和优化，以满足应用系统的功能及性能等需求。模式求精步骤基于函数依赖理论的模式求精步骤：确定函数依赖。确定关系模式所属范式。分析是否满足应用需求。模式分解。根据范式要求(是选择BCNF还是3NF)，运用规范化方法将关系模式分解成所要