数据库6-关系数据理论

AnIntroductiontoDatabaseSystem数据库系统概论AnIntroductiontoDatabaseSystem第六章关系数据理论6.1函数依赖用形式化方法研究一个关系中各属性之间的语义关系。函数依赖的定义：

若关系R的任意两个元组在属性A1、A2、…、An上一致(即有相同分量值)，则这两个元组在属性B上也一致，则称属性A1A2…An函数决定B，或称属性B函数依赖于A1A2…An。记为：A1A2…An→BAnIntroductiontoDatabaseSystemtuAB若t和u在A上一致,则在B上也一致函数依赖的定义关系：学生(学号,姓名,性别)中为何学号→姓名成立？在一个关系中，不存在（键值）完全相同的元组。如果不存在两个元组具有相同学号，即每个元组各表示一个学生，则学号→姓名成立。关系：学生(学号,姓名,课号,成绩)中学号→姓名？如果两个元组具有相同学号，则两个元组指同一个学生，故具有相同姓名。但是：学号→成绩？如果两个元组学号相同，但课程号不同，其成绩亦可能不同。只有在学号，课号都确定的情况下，成绩才被确定，因此：学号，课号→成绩函数依赖的定义(续)AnIntroductiontoDatabaseSystem函数依赖的定义(续)[例1]建立一个描述学校教务的数据库： 学生的学号（Sno）、所在系（Sdept） 系主任姓名（Mname）、课程名（Cname） 成绩（Grade）单一的关系模式：Student<U、F>U＝｛Sno,Sdept,Mname,Cname,Grade｝AnIntroductiontoDatabaseSystem函数依赖的定义(续)

属性组U上的一组函数依赖F：

F＝｛Sno→Sdept,Sdept→Mname,(Sno,Cname)→Grade｝

SnoCnameSdeptMnameGradeExampleMovies(title,year,length,filmType,studioname,starName)ReasonableFD’stoassert:titleyear→lengthtitleyear→filmTypetitleyear→studioNameBut titleyear→starNametitleyearlengthfilmtypestudioNamestarNameStarWarsStarWarsStarWarsMightyDucksWayne’sWorldWayne’sWorld1977197719771991199219921241241241049595colorcolorcolorcolorcolorcolorFoxFoxFoxDisneyParamountParamountCarrieFisherMarkHamillHarrisonFordEmilioEstevezDanaCarveyMikeMeyers6.2函数依赖规则什么是函数依赖规则？为何需要它？在一个给定关系上，已知一组函数依赖作为前提条件。根据一组函数依赖规则，就可推断另一些函数依赖。这种计算和验证可有效减少冗余，得到良好的关系设计。函数依赖规则重要的函数依赖规则：分解／合并(Splitting/combining)规则平凡依赖(TrivialDependance)规则

传递(Transitivy)规则

Armstrong公理

分解/合并规则分解／合并规则(Splitting/CombiningRule)：A1A2…An→B1B2…Bm等价于

A1A2…An→B1A1A2…An→B2…A1A2…An

→Bm注意：函数依赖的左面不能分解合并。分解/合并规则（续）

例如：关系Movies中，

titleyear→lengthfilmTypestudioName

等价于：

titleyear→length titleyear→fileType titleyear→studioName

但是，学号课号→成绩不能分解为： 学号→成绩 课号→成绩AnIntroductiontoDatabaseSystem平凡函数依赖与非平凡函数依赖在关系模式R(U)中，对于U的子集X和Y，如果X→Y，但YX，则称X→Y是非平凡的函数依赖若X→Y，但YX,则称X→Y是平凡的函数依赖例：在关系SC(Sno,Cno,Grade)中，非平凡函数依赖：(Sno,Cno)→

Grade

平凡函数依赖：(Sno,Cno)→

Sno(Sno,Cno)→CnoAnIntroductiontoDatabaseSystem平凡函数依赖与非平凡函数依赖（续）若X→Y，则X称为这个函数依赖的决定属性组，也称为决定因素（Determinant）。若X→Y，Y→X，则记作X←→Y。若Y不函数依赖于X，则记作X→Y。AnIntroductiontoDatabaseSystem完全函数依赖与部分函数依赖定义

在R(U)中，如果X→Y，并且对于X的任何一个真子集X’，都有X’Y,则称Y对X完全函数依赖，记作

XFY。若X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作XPY。

AnIntroductiontoDatabaseSystem完全函数依赖与部分函数依赖（续）[例1]中(Sno,Cno)→Grade是完全函数依赖，

(Sno,Cno)→Sdept是部分函数依赖因为Sno→Sdept成立，且Sno是（Sno，Cno）的真子集

FPAnIntroductiontoDatabaseSystem传递函数依赖定义6.3

在R(U)中，如果X→Y，(YX),Y→XY→Z，则称Z对X传递函数依赖。记为：X→Z

注:如果Y→X，即X←→Y，则Z直接依赖于X。例:在关系Std(Sno,Sdept,Mname)中，有：

Sno→Sdept，Sdept→MnameMname传递函数依赖于Sno传递AnIntroductiontoDatabaseSystem码定义：

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

U，则K称为R的侯选码（CandidateKey）。若候选码多于一个，则选定其中的一个做为主码（PrimaryKey）。FAnIntroductiontoDatabaseSystem码（续）主属性与非主属性包含在任何一个候选码中的属性，称为主属性（Primeattribute）不包含在任何码中的属性称为非主属性（Nonprimeattribute）或非码属性（Non-keyattribute）全码整个属性组是码，称为全码（All-key）AnIntroductiontoDatabaseSystem码（续）[例2]

关系模式S(Sno,Sdept,Sage)，单个属性Sno是码，

SC（Sno，Cno，Grade）中，（Sno，Cno）是码[例3]

关系模式R（P，W，A）

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

关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码（Foreignkey）也称外码如在SC（Sno，Cno，Grade）中，Sno不是码，但Sno是关系模式S（Sno，Sdept，Sage）的码，则Sno是关系模式SC的外部码

主码与外部码一起提供了表示关系间联系的手段计算属性的闭包属性闭包的概念设S是关系R上的函数依赖集，A={A1,A2,…,An}是R上的属性集，则属性集A可函数决定的最大属性集合（一定存在这样的集合）称做A的闭包，记做：A+

。这个集合如何计算？这种计算有何用途？属性的闭包：

设S是关系R上的函数依赖集，A={A1,A2,…,An}是R上的属性集，属性集A在函数依赖集S下的闭包(closure)是这样一个属性集B，对于关系R的所有实例，函数依赖：A1A2…An→B均成立，即A1A2…An→B“逻辑蕴含于”函数依赖集S。

属性集{A1,A2,…,An}的闭包表示为{A1,A2,…,An}+。 显然：{A1,A2,…,An}含于{A1,A2,…,An}+若A1A2…An→X，则X含于B计算属性的闭包(续)计算属性的闭包(续)计算属性的闭包：

给定函数依赖集S，和属性集A={A1,A2,…,An}，如何计算A+？设属性集X是A的闭包，将X初始化为{A1,A2,…,An}，即为闭包的最小集合。遍历S中的每个函数依赖，对于每个函数依赖式：B1B2…Bm→C。如果B1、B2、…、Bm都在X中，而C不在X中，则把C加入X中。重复第2步，直到遍历完S中所有函数依赖，而没有新属性能加入到X中。最终属性集X即为属性集A在函数依赖集S下的闭包A+。

Y+newY+XAExampleR=(A,B,C,G,H,I)F={A

B

A

C

CG

H

CG

I

B

H}(AG)+1. result=AG2. result=ABCG (A

CandAB)3. result=ABCGH (CG

HandCGAGBC)4. result=ABCGHI (CG

IandCGAGBCH)IsAGacandidatekey?IsAGasuperkey?DoesAG

R?==Is(AG)+RIsanysubsetofAGasuperkey?DoesA

R?==Is(A)+RDoesG

R?==Is(G)+R6.2关系数据库模式设计关系模式设计中出现冗余的原因：关系模式设计中可能出现各种冗余，即同一事实在多个元组中重复。造成冗余的原因通常是将同一个对象的单值和多值特征混合在同一个关系中。例如：学生关系学号

姓名家庭地址课号

成绩

系号

系主任

S1S1S1S2S3S3S4S4

N1N1N1N2N3N3N4N4A1A1A1A2A3A3A4A4C1C2C3C2C1C3C1C2

AABBAABA

D1D1D1D1D2D2D2D2

M1M1M1M1M2M2M2M2

关系数据库模式设计（续）“异常”指什么？

异常anomaly，即不符合规范的设计，导致操作数据库时，出现影响数据一致性的现象。关系设计中可能出现哪些异常？冗余。同一信息在多个元组中不必要的重复。浪费空间，增加更新操作的复杂度，影响数据一致性。修改异常。修改某个元组的信息，而重复的信息可能未修改而破坏一致性。或插入数据时，某些有用信息暂时无法插入。删除异常。删除某个对象时，必须删除多个元组而不是一个元组，操作不当有可能破坏数据一致性。或删除元组时，同时删除了其它有用信息。插入异常AnIntroductiontoDatabaseSystem解决方法结论：学生关系模式不是一个好的模式。“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少原因：由存在于模式中的某些数据依赖引起的解决方法：通过分解关系模式来消除其中不合适的数据依赖关系分解关系分解：

给定一个关系R{A1,A2,…,An}，将R分解为两个关系S{B1,B2,…,Bm}和T{C1,C2,…,Ck}，使得：{A1,A2,…,An}={B1,B2,…,Bm}∪{C1,C2,…,Ck}S中的元组是R的所有元组在{B1,B2,…,Bm}上的投影；

T中的元组是R的所有元组在{C1,C2,…,Ck}上的投影。

投影：

R中的一个元组在属性B1,B2,…,Bm上的分量，构成S中的一个元组，且保持元组不重复。为何进行分解： 为了避免异常，用几个关系代替原有的关系，且保持数据一致性。

关系分解（续）上例学生(学号,姓名,家庭地址,课号,成绩,系号，系主任)可分解为右面的学生、选修两个关系。分解后的两个关系减少了异常。这两个关系应可连接(join)得到原有的关系元组，且不改变原有语义。学号姓名家庭地址系号系主任S1S2S3S4

N1N2N3N4A1A2A3A4D1D1D2D2M1M1M2M2学号课号成绩S1S1S1S2S3S3S4S4

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

第一范式(1NF)

第二范式(2NF)

第三范式(3NF) BC范式(BCNF)

第四范式(4NF)

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

AnIntroductiontoDatabaseSystem1NF1NF的定义 如果一个关系模式R的所有属性都是不可分的基本数据项，则R∈1NF第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库但是满足第一范式的关系模式并不一定是一个好的关系模式AnIntroductiontoDatabaseSystem1NF（续）[例4]关系模式S-L-C(Sno,Sdept,Sloc,Cno,Grade)Sloc为学生住处，假设每个系的学生住在同一个地方函数依赖包括：

(Sno,Cno)FGradeSno→Sdept(Sno,Cno)PSdeptSno→Sloc(Sno,Cno)PSlocSdept→SlocAnIntroductiontoDatabaseSystem1NF（续）S-L-C的码为(Sno,Cno)S-L-C满足第一范式。非主属性Sdept和Sloc部分函数依赖于码(Sno,Cno)SnoCnoGradeSdeptSlocS-L-CAnIntroductiontoDatabaseSystemS-L-C不是一个好的关系模式（续）(1)插入异常(2)删除异常(3)数据冗余度大(4)修改复杂AnIntroductiontoDatabaseSystemS-L-C不是一个好的关系模式（续）原因

Sdept、Sloc部分函数依赖于码。解决方法

S-L-C分解为两个关系模式，以消除这些部分函数依赖SC（Sno，Cno，Grade）

S-L（Sno，Sdept，Sloc）AnIntroductiontoDatabaseSystem1NF（续）函数依赖图：SnoCnoGradeSCS-LSnoSdeptSloc关系模式SC的码为（Sno，Cno）关系模式S-L的码为Sno这样非主属性对码都是完全函数依赖

AnIntroductiontoDatabaseSystem2NF2NF的定义

定义：

若R∈1NF，且每一个非主属性完全函数依赖于码，则R∈2NF。 例：S-L-C(Sno,Sdept,Sloc,Cno,Grade)∈1NFS-L-C(Sno,Sdept,Sloc,Cno,Grade)∈2NF SC（Sno，Cno，Grade）∈

2NF S-L（Sno，Sdept，Sloc）∈

2NF1NF分解为2NF范式的方法分解的原则： 把一个关系模式分解成一个由若干个关系模式构成的集合，且这些关系模式应满足如下条件：每个关系模式都满足2NF。分解后的元组能如实反映原有关系中的数据，即能由分解的关系准确重构原有关系。分解策略：消除违背2NF的函数依赖：找一个违背2NF的非平凡函数依赖A1A2…An→B1B2…Bm。

把关系R分解成两个关系：

R1(A1,A2,…,An,B1,B2,…,Bm)。R2(A1,A2,…,An,所有其它属性)。(即从R中删除B1,B2,…,Bm列)R1,R2若不满足2NF，则再分解。

1NF分解为2NF范式的方法

例如：R(学号,姓名,家庭地址,课号,成绩,系号,系主任)不满足2NF。

1R中违背2NF的非平凡函数依赖： 学号→姓名,家庭地址,系号,系主任

2分解为：R1(学号,姓名,家庭地址,系号,系主任) R2(学号,课号,成绩)

AnIntroductiontoDatabaseSystem3NF3NF的定义

定义6.7

关系模式R<U，F>

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

Y→X，则称R<U，F>∈3NF。若R∈3NF，则每一个非主属性既不部分依赖于码也不传递依赖于码。AnIntroductiontoDatabaseSystem3NF（续）例：2NF关系模式S-L(Sno,Sdept,Sloc)中函数依赖：

Sno→SdeptSdept→SnoSdept→Sloc

可得：

Sno→Sloc，即S-L中存在非主属性对码的传递函数依赖，S-L∈3NF传递AnIntroductiontoDatabaseSystem3NF（续）函数依赖图：S-LSnoSdeptSlocAnIntroductiontoDatabaseSystem3NF（续）解决方法采用投影分解法，把S-L分解为两个关系模式，以消除传递函数依赖：S-D（Sno，Sdept）

D-L（Sdept，Sloc）S-D的码为Sno，D-L的码为Sdept。分解后的关系模式S-D与D-L中不再存在传递依赖AnIntroductiontoDatabaseSystem3NF（续）S-D的码为Sno，D-L的码为SdeptSnoSdeptS-DSdeptSlocD-LS-L(Sno,Sdept,Sloc)∈2NFS-L(Sno,Sdept,Sloc)∈3NFS-D(Sno，Sdept)∈3NFD-L(Sdept，Sloc)∈3NFAnIntroductiontoDatabaseSystem3NF（续）采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。将一个2NF关系分解为多个3NF的关系后，仍然不能完全消除关系模式中的各种异常情况和数据冗余。AnIntroductiontoDatabaseSystemBC范式（BCNF）定义6.8

关系模式R<U，F>∈1NF，若X→Y且YX时X必含有码，则R<U，F>∈BCNF。等价于：每一个决定属性因素都包含码AnIntroductiontoDatabaseSystemBCNF（续）若R∈BCNF所有非主属性对每一个码都是完全函数依赖所有的主属性对每一个不包含它的码，也是完全函数依赖没有任何属性完全函数依赖于非码的任何一组属性R∈BCNFR∈3NF充分不必要AnIntroductiontoDatabaseSystemBCNF（续）[例5]关系模式C（Cno，Cname，Pcno）C∈3NFC∈BCNF[例6]关系模式S（Sno，Sname，Sdept，Sage）假定S有两个码Sno，SnameS∈3NF。S∈BCNFAnIntroductiontoDatabaseSystemBCNF（续）［例7］关系模式SJP（S，J，P）函数依赖：（S，J）→P；(J，P）→S（S，J）与（J，P）都可以作为候选码,属性相交SJP∈3NF，SJP∈BCNFAnIntroductiontoDatabaseSystemBCNF（续）[例8]在关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示课程。函数依赖：

(S，J)→T，(S，T)→J，T→J(S，J)和(S，T)都是候选码AnIntroductiontoDatabaseSystemBCNF（续）

JSJTSTSTJ中的函数依赖AnIntroductiontoDatabaseSystemBCNF（续）STJ∈3NF

没有任何非主属性对码传递依赖或部分依赖

STJ∈BCNFT是决定因素，T不包含码AnIntroductiontoDatabaseSystemBCNF（续）解决方法：将STJ分解为二个关系模式：

ST(S，T)∈BCNF，TJ(T，J)∈BCNF

没有任何属性对码的部分函数依赖和传递函数依赖SJSTTJTJAnIntroductiontoDatabaseSystem3NF与BCNF的关系R∈BCNFR∈3NF如果R∈3NF，且R只有一个候选码

R∈BCNFR∈3NF充分不必要充分必要思考(S#,C#,ORDER)，表示学生选修课程的名次，有函数依赖(S#，C#)ORDER，(C#，ORDER)S#，它属于BCNF吗？全码属于BCNF吗？任何一个二目关系模式R（A，B）一定属于BCNF吗？一个全是主属性的关系模式一定可以达到第几范式？一个全码的关系模式一定可以达到第几范式？Exercise商品销售业务管理系统的关系设计符合最高范式是什么？Customer(custid,name,prov,city,phone,unit)

Product(prodid,factory,type,spec,price,desc)