数据库系统概论 课件 第06章-关系数据理论

数据库系统原理

第六章关系数据理论

a第六章关系数据理论

CQ主要内容

用介绍关系数据库规范化理论，这是数据库逻

辑设计的理论依据。

R本章要解决的主要问题

应如何评价关系模式的优劣？

苞怎样将关系模式分解为一组较理想的关系模

式？------

DBS

a第六章关系数据理论

区重点与难点

G了解规范化理论的研究动机及其在数据库设计

中的作用

G掌握函数依赖的有关概念，第一范式、第二范

式、第三范式、BC范式的定义

G重点掌握并能够灵活运用关系模式规范化的方

法和关系模式分解的方法，这也是本章的曲呈

DBS

▲第六章关系数据理论

AR问题的提出

G6.2规范化

r6.3数据依赖的公理系统*

r6.4模式的分解*

E6.5小结

a6.1问题的提出

S关系数据库逻辑设计

应针对一个具体问题，如何构造一个适合于它的

数据库模式

S数据库逻辑设计的工具

3关系数据库的规范化理论

导关系数据库设计理论主要包括三方面的内容：数

据依赖，范式，模式设计方法。数据依赖在此起

着核心作用。------

DBS

a6.1问题的提出

一、概念回顾

二、关系模式的形式化定义

三、什么是数据依赖

四、关系模式的简化定义

五、数据依赖对关系模式影响

DBS

•、概念回顾

G关系：描述实体、属性、实体间的联系。

B从形式上看，它是一张二维表，是所涉及属性的

笛卡尔积的一个子集。

r关系模式：用来定义关系。

G关系数据库：基于关系模型的数据库，利用关系

来描述现实世界。

B从形式上看，它由一组关系组成。

r关系数据库的模式：定义这组关系的关系模式的

全体。

DBS

a二、关系模式的形式化定义

关系模式由五部分组成，即它是一个五元组：

R(U,D,DOM,F)

eR：关系名，是符号化的元组语义

KU:组成该关系的属性名集合

KD：属性组U中属性所取值的域

KDOM：属性到域的映射集合

KF：属性间数据的依赖关系集合------

DBS

a二、关系模式的形式化定义

7关系数据库模式

e一个关系数据库由多个关系构成，一个关系数据库

对应多个不同的关系模式

关系数据库模式——,T数据库中所有关系模式的集合

X.艇/

关系数僻库的全点逻辑结相

G关系数据库模式可表示为：

S={Ri<UizDizD0Mi,Fi>|i=l,2,...n}

G关系，作为一张二维表，我们对它有一个最起码的要求:

畲每一个分量必须是不可分的数据。

DBS

a三、什么是数据依赖

工、完整性约束的表现形式

G限定属性取值范围：如学生的学号取唯一值、

成绩必须在0~100之间、性别是男或女等。

应定义属性值间的相互关连（主要体现于值单相

等与否），这就是数据依赖，它是数据库模式

设计的关键

DBS

a三、什么是数据依赖

2、数据依赖

s是通过一个关系中属性间值的相等与否体现出

来的数据间的相互关系

e是现实世界属性间相互联系的抽象

导是数据内在的性质

鼠是语义的体现------

DBS

a三、什么是数据依赖

3、数据依赖的类型

G函数依赖(FunctionalDependency,简记

为FD)

G多值依赖(MultivaluedDependency,审

记为MVD)

DBS

四、关系模式的简化表示

位关系模式R(U,D,DOM,F),简化为一个三

元组：

R(u,F)

K当且仅当U上的一个关系r满足F时，r称为

关系模式R(U,F)的一个关系

GRn关系的型

nrn关系的值，每一个值称为R的一个关k

DBS

a五、数据依赖对关系模式的影响

用关系模式的评价：什么样的关系模式是一个“好

”的关系模式？

£1、关系数据库设计的核心：关系模式设计

匠2、关系模式的设计：按照一定的原则从数量

众多而又相互关联的数据中，构造出一组既能较

好地反映现实世界，而又有良好的操作性能的关

系模式。

向3、关系模式优劣：如何评价，如何改进^一""

a五、数据依赖对关系模式的影响

例工：设计教学管理关系数据库模型

a五、数据依赖对关系模式的影响

r解法——：SCT(sno,eno,tno,sname,grade,cname,tnaine)

ISNOCNOTNOSnaineGradeCnameTname

SiCiTi赵民90OS彭

SiC2T」赵民90DS杨I

SiT<赵民85C++刘

Si■.T4赵民87DB张I

SaClT4李军90OS张I

S3CiT4陈江75QS张

杨|

SBc?Ta陈江70DS

张|

S3CA陈江56DE

S4CITi魏致90OS彭

S4工魏致85DS杨

S5CiT-乔远95OS彭

张|

S5C4L乔远80DB

a五、数据依赖对关系模式的影响

位解法一的问题分析

位数据冗余度高：

位更新异常(UpdateAnomalies)：

e插入异常(InsertAnomalies)：

e删除异常(DeleteAnomalies)：

位产生问题的原因：属性间约束关系(即数据

间的依赖关系)太强。_____

DBS

%五、数据依赖对关系模式的影响

DBS

Courses(Cno,Tno,cname)

o解法三：

Students(Sno,Sname)

Courses(Cno,Cname)

Teachers(Tno,Tname)

Enrolls(Sno,Cno,Grade)

HTeaching(Tno,Cno)

五、数据依赖对关系模式的影响

DBS

Enrolls

StudentsTeachers

SNOCNOGrade

SiCl90

Si90

SiC385

SiC487

Ci90

Cl75

TeachingCoursesS3C270

S356

S4Cl90

S4685

S5Ci95

S5C480

DBS

a五、数据依赖对关系模式的影响

例2：描述学校数据库，对象有：

用学生：用学号Sno描述；

e所在系：用系名Sdept描述；

用系负责人：用系主任姓名Mname描述；

e课程：用Cno描述；

用成绩：用Grade描述。

n单一的关系模式：Student<U,F>

U={Sno,Sdept,Mname,Cno,GradeyDBS

a五、数据依赖对关系模式的影响

学校数据库的语义：

1、一个系有若干学生，一个学生只属于一个系；

2、一个系只有一名（正职）负责人；

3、一个学生可以选修多门课程，每门课程有若［干

学生选修；

4、每个学生学习的每门课程都有一个成绩】上

DBS

a五、数据依赖对关系模式的影响

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

F={Sno-Sdept,SdeptfMname,

(Sno,Cno)->Grade}

系模式StudentvU,F＞中存在的问题

工、数据冗余太大

艮浪费大量的存储空间

例：每一个系主任的姓名重复出现

2、更新异常(UpdateAnomalies)

艮数据冗余，更新数据时，维护数据完整性伸

价大。

仞J：某系更换系主任后，系统必须修改与该系卜

生有关的每一个元组一^

DBS

介(关系模式StudentvU,F＞中存在的问题

3、插入异常(InsertionAnomalies)

E该插入的数据插不进去

例：如果一个系刚成立，尚无学生，我们就无法

把这个系及其系主任的信息存入数据库。

4、删除异常(DeletionAnomalies)

R不该删除的数据不得不被删除了

彳列：如果某个系的学生全部毕业了，我们在删除

该系学生信息的同时，把这个系及其系主任的信

息也丢掉了。二

五、数据依赖对关系模式的影响

应结论：

KStudent关系模式不是一个好的模式

R“好”的模式：不会发生插入异常、删除异常

、更新异常，数据冗余应尽可能少。

包原因：由存在于模式中的某些数据依赖引起的

n解决方法：通过分解关系模式来消除其中不合

适的数据依赖。------

DBS

五、数据依赖对关系模式的影响

r把单一的模式分解成三个关系模式：

S<Sno,Sdept,Sno->Sdept>;

SC<Sno,Cno,Grade,(Sno,Cno)->Grade>;

DEPT<Sdept,Mname,Sdept^Mname>;

e这样，就不会发生更新异常、插入异常、删

除异常的毛病，数据冗余也得到了控制^____

—DBS

6.2规范化

£规范化理论正是用来改造关系模式，通过

分解关系模式来消除其中不合适的数据

依赖，以解决插入异常、删除异常、更新

异常和数据冗余问题。

DBS

6.2规范化

R621函数依赖

R6.2.2码/关键字

-6.2.3范式

-6.2.42NF

-6253NF

F:6.2.6BCNF

度*6.2.7多值依赖与4NF

♦■6.2.8规范化小结

6.2,1函数依赖

一、函数依赖

一平凡函数依赖与非平凡函数依赖

三」完全函数依赖与部分函数依赖

四、传递函数依赖

DBS

A一、函数依赖

DBSFunctionalDependency

定义6.1设R(U)是属性集U上的一个关系模式。

均为的子集，「为

X、YU={A1，A2,An}

R(U)的任意一个可能的关系，如果对于r中的任

意两个元组u、v,只要有u[X]=v[X],就有

u[Y]=v[Y],则称“X函数确定Y”或“Y唱

数依赖于X”，记作：XfY。

称X为这个函数依赖的决定因素(Determ2a吩

DBS

一、函数依赖

例I：对SCT关系模式，判断以下函数依赖的对错

SCT(sno,eno,tno,sname,grade,cname,tname)

1、snofsname,cno^cname,

(sno,eno)—grade<

2、sname->snoztno—eno,snoftnamex

DBS

a说明：

1.函数依赖不是指关系模式R的某个或某些关系实例满足

的约束条件，而是指R的所有关系实例均要满足的约束

条件。

2.函数依赖是语义范畴的概念。只能根据语义来确定一个

函数依赖。例如：“姓名一年龄”这个函数依赖只有在

不允许有同名人的条件下成立

3.数据库设计者可以对现实世界作强制的规定。例如规定

不允许同名人出现，函数依赖“姓名-年龄”成立。所

插入的元组必须满足规定的函数依赖，若发现有同名人

存在，则拒绝插入该元组。—此

属性间的联系决定函数依赖关系

同设X、Y均是U的子集：

BSX和Y间联系是1:1,卜JXfY,YfX,

同乂和丫间联系是乂：1,贝IJX一丫。

eX和Y间联系是M:N,则X、丫间不存件

函数依赖。

DBS

a函数依赖图

例：关系模式SCT(sno,eno,tno,sname,

grade,cname,tname)的FD图

一、函数依赖

例：Student(Sno,Sname,Ssex,Sage,Sdept)

假设不允许重名，则有：

SnotSsex,SnofSage,Sno->Sdept,

Sno—Sname,

SnamefSsex,SnamefSage,SnamefSdept

但：SsexvSage

n若XfY,并且YfX,则记为X―Y。

e若Y不函数依赖于X,则记为XvYo______________

—DBS

二、平凡函数依赖与非平凡函数依赖

在关系模式R(U)中，对于U的子集X和Y,

R若XfY,但YzX,则称XfY是非平凡的函数依赖

R若XfY,但YQX,则称XfY是平凡的函数依赖

例：

解：XfY为平凡函数依赖，X->W,W->Y为非平

凡函数依赖。DBS

二、平凡函数依赖与非平凡函数依赖

例：在关系SC(Sno,Cno,Grade)中，

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

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

(Sno,Cno)fCno

K对于任一关系模式，平凡函数依赖都是必然成立

的，它不反映新的语义，因此若不特别声明，我

.们总是讨论非平凡函数依赖。------

—DBS

三、完全函数依赖与部分函数依赖

定义6・2在关系模式R(U)中，

R若XfY,并且对于X的任何一个真子集X',都有

X''Y,则称Y完全函数依赖于X,记作XJ。

R若XfY,但Y不完全函数依赖于X,则称Y部个

函数依赖于X,记作X上Y。

DBS

三、完全函数依赖与部分函数依赖

例：在SCT中，

SCT(sno,eno,tno,sname,grade,

cname,tname)

(sno,cno)旦cname

(sno,cno)_£»tname

enofcname

enovtname

(sno,cno)_^grade

DBS

三、完全函数依赖与部分函数依赖

例：在关系SC(Sno,Cno,Grade)中，

由于：SnovGrade,CnovGrade,

因止匕：(Sno,Cno)^>Grade

DBS

四、传递函数依赖

定义6.3在关系模式R(U)中，如果X-Y,Y-乙

且YzX,YvX,则称Z传递函数依赖于X,记作:

X&Z

注：如果YfX,即X―Y,则Z直接依赖于X。

例：在关系Std(Sno,Sdept,Mname)中,有:

Sno^Sdept,Sdept^Sno,Sdept->Mname

二•Mname传递函数依赖于Sno：Snci.^Mnam

\DBS

6,2,2关键字

定义6.4设K为关系模式RvU,F＞中的属性或属

性组合，若K^u,则K称为R的一个侯选关键字

(CandidateKey)。若关系模式R有多个候选关键

字，则选定其中的一个作为主键(Primarykey)。

m主属性：包含在任何一个候选关键字中的属性，叫

做主属性

(Primeattribute)o

E非主属性：不包含在任何关键字中的属性称为非主

属性(Nonprimeattribute)或非键属性(Non-key

attribute)o1

冬6.2.2关键字

最简单的情况，单个属性是关键字。

最极端的情况，整个属性组是关键字，称

为全码(All-key)。

应组合关键字：一般用于描述实体之间已联

系。

DBS

a6,2,2关键字

例：在学生选课数据库中，关系模式：

RS(Sno,Sdept,Sage)中单个属性Sno为

关键字，用下划线显示出来。

RSC(Sno,Cno,Grade)中属性组合

(Sno,Cno)是关键字。

DBS

a6,2,2关键字

例：关系模式R(P,W,A)中，属性P表示演奏

者、W表示作品、A表示听众。

同假设一个演奏者可以演奏多个作品，某一作

品可被多个演奏者演奏。听众也可以欣赏不

同演奏者的不同作品，这个关系模式的关忸

字为(P,W,A),即All-key。

DBS

a外部关键字

定义6・5关系模式R中属性或属性组X并非R的

关键字，但X是另一个关系模式的关键字，则称X

是R的外部关键字(Foreignkey),也称外键。

E主键和外键一起提供了表示关系间联系的手段。

e如：在SC(Sno,Cno,Grade)中Sno不是

SC的关键字，但是S的主键，所以Sno是SC

的外键。-----

6,2,2关键字

r关系关键字的完整性约束条件：

包实体完整性：关系的主属性值不能取空值或部

分为空值。

G参照完整性：关系的外部关键字要么是空”,

要么等于参照关系主键的属性值。

DBS

6.2.3范式

DBSS范式是符合某一种级别的关系模式的集合。

K关系数据库中的关系必须满足一定的要求。满足不

同程度要求的为不同范式。

K范式的种类：

,第一范式(1NF)

第二范式(2NF)

I第三范式(3NF)

]BC范式(BCNF)

第四范式(4NF)

＜第五范式(5NF)—C

6.2.3范式

g某一关系模式R为第n范式，可简记为RwnNF。

g各种范式之间存在联系：

INFo2NFn3NFnBCNFn4NFo5NF

r一个低一级范式的关系模式，通过模式分解可以

转换为若干个高一级范式的关系模式的集合，这

种过程就叫规范化。

6.2.42NF

屋INF的定义

如果一个关系模式R的所有属性都是不可分的基本

数据项，则R£1NF。

E第一范式是对关系模式的最起码的要求。不满足

第一范式的数据库模式不能称为关系数据库。

E但是满足第一范式的关系模式并不一定是一个好

的关系模式。----

a规范化关系

例：

工资（工号，姓名，工资（基本工资，业绩津贴，煤电补贴））

E不满足1NF的关系称为非规范化关系。

K关系数据模型不能存储上述例子（非规范化关系），在关

系数据库中不允许非规范化关系的存在。

屋转化方法：

工资（工号，姓名，基本工资，业绩津贴，煤电补贴）------

DBS

6.2.42NF

例：关系模式:

SLC(Sno,Sdept,Sloe,Cno,Grade)

Sloe为学生住处，假设每个系的学生住在同一个地方。

函数依赖包括：

(Sno,Cno)-UGrade,Sno—Sdept

(Sno,Cno)冬Sdept,SnofSloe

(Sno,Cno)-^SIoc,SdeptfSloe

DBS

aSLC不是一个好的关系模式

(1)插入异常

假设Sno=20021521,Sdept=IS,Sloc=

BLD2的学生还未选课，因Cno是主属性，因此

该学生的信息无法插入SLCo

(2)删除异常

假定某个学生本来只选修了3号课程这一门课，

现在因身体不适，他连3号课程也不选修了。E

Cno是主属性，此操作将导致该学生信息迎金

元组都要删除。—C

aSLC不是一个好的关系模式

(3)数据冗余度大

如果一个学生选修了10门课程，那么他的Sdept

和Sloe值就要重复存储了工。次。

(4)修改复杂

例如学生转系，在修改此学生元组的Sdept啊的

同时，还可能需要修改住处(Sloe)。如果q个

学生选修了K门课，则必须无遗漏地修改K个，组

中全部Sdept、Sloe信息。一—

DBS

6.2.42NF

度原因

Sdept^Sloe部分函数依赖于码。

E解决方法

SLC分解为两个关系模式，以消除这些部分华

数依赖：

Cno,Grade)

SL(SnozSdept,Sloe)------

DBS

6.2.42NF

定义6.6若关系模式R£INF,并且每一个非主属

性都完全函数依赖于R的关键字，则RW2NF。

例：SLC(Sno,Sdept,Sloe,Cno,Grade)elNF

但SLC(Sno,Sdept,Sloe,Cno,Grade)e2NF

分解为：SC(Sno,Cno,Grade)e2NF

SL(Sno,Sdept,SIOC)G2NF

DBS

6.2.42NF

n采用投影分解法将一个1NF的关系分解为多个

2NF的关系，可以在一定程度上减轻原1NF关系中

存在的插入异常、删除异常、数据冗余度大、修改

复杂等问题。

e将一个1NF关系分解为多个2NF的关系，并不能完

全消除关系模式中的各种异常情况和数据冗余。

万如果R£2NF,则R£1NF。------

—DBS

6.2.53NF

用解决方法

采用投影分解法，把SL分解为两个关系模式,

以消除传递函数依赖：

SD(Sno,Sdept),DL(SdeptrSloe)

Sno---->SdeptSdept------>Sloe

SDDL

DBS

6.2.53NF

定义6・7关系模式RvU,F＞中若不存在这样的关

键字X、属性组Y及非主属性Z(ZaZ),使得XfK

KvX,hZ成立，则称RvU,尸＞£3/VE

例：SL(Sno,Sdept,Sloc)e2NF,

但SL(Sno,Sdept,Sloc"3NF

分解为：SD(Sno,Sdept)e3NF

DL(Sdept,SIOC)G3NF

DBS

6.2.53NF

位若R£3NF,则R的每一个非主属性既不部分函数

依赖于候选码也不传递函数依赖于候选码。

G如果R£3NF,贝URW2NF。

度采用投影分解法将一个2NF的关系分解为多个

3NF的关系，可以在一定程度上解决原2NF关系

中存在的插入异常、删除异常、数据冗余度大、

修改复杂等问题。

度将一个2NF关系分解为多个3NF的关系后，并不能

<完全消除关系模式中的各种异常情况和数据冗i蓝

6.2.6BC范式（BCNF）

定义6・8设关系模式RvU,F>£lNF,如果对于R

的每个函数依赖XfY,若Y.X,贝UX必含有候选关

键字，那么RWBCNF。

r若R£BCNF

R每一个决定属性集（因素）都包含（候选）关键字

RR中的所有属性（主，非主属性）都完全函数依螂于

关维学

应若R£BCNF,RE3NF

G若RW3NF,则R不一定WBCNF-------

6.2.6BC范式(BCNF)

例5：关系模式C(Cno,Cname,Pcno),Cno是

关系c的唯一关键字，没有任何属性对码的部分

函数依赖或传递函数依赖，所以CW3NF。

鼠同时C中的Cno是唯一的决定因素，所以

CeBCNFo

DBS

6.2.6BC范式(BCNF)

例6：关系模式S(Sno,Sname,Sdept,Sage),

假定Sname也具有唯一性，那么关系S应有两个

关键字，没有任何属性对码的部分函数依赖或传

递函数依赖，所以S£3NF。

m同时S中的Sno,Sname外没有其他的决定因

素，所以S&BCNF。

DBS

6.2.6BC范式(BCNF)

例7：关系模式SJP(SJP)中,S是学生、J表示课程、

P表示名次。

每一个学生选修每门课程的成绩有一定的名次，每门

课程中每一名次只有一个学生(即没有并列名次)。

则函数依赖为：(S,J)-P,(J,P)-S

即(S,J)与(J,P)都可以作为候选关键字。

•・•在这个关系模式中，显然没有属性对关键字传递依

赖或部分依赖。

ASJPe3NF,又・・•除(SJ)与(J,P)以外没有其它

决定因素，・•・SJPGBCNFODBS

6.2.6BC范式(BCNF)

例8：在关系模式STJ(S,T,J)中，S表示学生，

T表示教师，J表示课程。

K每一教师只教一门课。

K每门课由若干教师教，某一学生选定某门课，就

确定了一个固定的教师。

用某个学生选修某个教师的课就确定了所选课的名

称。

(S,J)-T,(S,T)-J,TfJ____

DBS

6.2.6BC范式(BCNF)

G函数依赖图

STJ

DBS

6.2.6BC范式(BCNF)

eSTJG3NF

r(S,J)和(S,T)都可以作为候选关键字

ES、T、J都是主属性

eSTJeBCNF

eT-J,T是决定因素，但T不是候选关键」

DBS

6.2.6BC范式(BCNF)

R解决方法：将STJ分解为二个关系模式：

SJ(S,J)eBCNF,TJ(T,J)eBCNF

SJTJ

r没有任何属性对关键字的部分函数依赖和年

递函数依赖一^

DBS

3NF与BCNF的关系

G如果关系模式R£BCNF,必定有R£3NF

m如果R£3NF,且R只有一个候选关键字，

贝尔必属于BCNF。

DBS

BCNF的关系模式所具有的性质

1、所有非主属性都完全函数依赖于每个候选关键字

2、所有主属性都完全函数依赖于每个不包含它的候

选关键字

3、没有任何属性完全函数依赖于非主属性的任何一

组属性

4、主属性不传递依赖于任何一个侯选关键字

5、非主属性不传递依赖于任何一个侯选关键字

—DBS

6.2.8规范化小结

K关系数据库的规范化理论是数据库逻辑设

计的工具。

用一个关系只要其分量都是不可分的数据项

,它就是规范化的关系，但这只是最基本

的规范化。(1NF)

E规范化程度可以有多个不同的级别(2NF、

3NF、BCNF、4NF、5NF)-----

DBS

6.2.8规范化小结

位规范化程度过低的关系不一定能够很好地描

述现实世界，可能会存在插入异常、删除

异常、修改复杂、数据冗余等问题

同一个低一级范式的关系模式，通过模式号

解可以转换为若干个高一级范式的关系模

式集合，这种过程就叫关系模式的规范兀

DBS

6.2.8规范化小结

DBS

F!关系模式规范化的基本步骤

1NF

J消除非主属性对码的部分函数依赖

消除决定因素2NF

非码的非平凡J消除非主属性对码的传递函数依赖

函数依赖3NF

J消除主属性对码的部分和传递函数依赖

-BCNF

J消除非平凡且非函数依赖的多值依赖

4NF

DBS

a规范化的基本思想

用消除不合适的数据依赖的各关系模式达到

某种程度的“分离”

G采用“一事一地”的模式设计原则

G让一个关系只描述一个概念、一个实体

或者实体间的一种联系。若多于一个在

念就把它“分离”出去。

所谓规范化实质上是概念的单一化标

DBS

6.2.8规范化小结

注意：

E不能说规范化程度越高的关系模式就越好。

屋在设计数据库模式结构时，必须对现实世界的

实际情况和用户应用需求作进一步分析，确定

一个合适的、能够反映现实世界的模式。

E上面的规范化步骤可以在其中任何一步终止，

DBS

6.3数据依赖的公理系统

位为了求得给定关系模式的关键字，为了从一

组函数依赖求得蕴涵的函数依赖，

e例如从已知函数依赖集F,要问XfY是否为

F所蕴涵，就需要一套推理规则。|

E这组推理规则是1974年首先由Armstrc4g

提出来的。

DBS

令6.3数据依赖的公理系统

二、函数依赖的逻辑蕴涵

二、Armstrong公理

三、函数依赖的闭包

四、属性集闭包

五、Armstrong公理系统的有效性与完备性

衣、函数依赖集等价和覆盖

士、最小函数依赖集

#△、极小化过程一

a—、函数依赖的逻辑蕴涵

定义6,工工设有关系模式R(U)及其函数依赖集尸，

如果对于R的任何一个满足F的关系r,

函数依赖XfY都成立(即r中任意两元组t、s,若

t[X]=s[X],则t[Y]=s[Y]),

则称尸逻辑蕴涵XfY,或称XfY可以由尸推出。

DBS

a—、函数依赖的逻辑蕴涵

例：关系模式R=(A,B,C),函数依赖集

F={A->B,B->C},F逻辑蕴涵A-C。

证：设u,v为r中任意两个元组：若AfC不成立，

则有u[A]=v[A],而u[C]Hv[C],

由A—>B,B—>C,矢口：

u[A]=v[A]=>u[B]=v[B]=>u[C]=v[C],

即若u[A]=v[A],则u[C]=v[C],与假设矛盾

▲故F逻辑蕴涵A->Co——

二、Armstrong公理

b一套推理规则，是模式分解算法的理论基础

应用途

应求给定关系模式的关键字।

G从一组函数依赖求得蕴涵的函数依赖

DBS

1.Armstrong公理系统

e设u为属性集总体，尸是u上的一组函数依赖:

R<U,F>

r对关系模式RvU/Q来说有以下的推理规贝ij：

AL自反律(Reflexivity)：若贝UXfV

为尸所蕴涵。(Al，：XfX)

A2,增广律(Augmentation)：若XfY为F所蕴

涵，且z=u,则xzfyz为尸所蕴涵。

(A2‘：XZ-Y)_____

DBS

1.Armstrong公理系统

rA3,传递律(Transitivity)：若X4Y及Y—Z为

尸所蕴涵，则XfZ为尸所蕴涵。

e注意：由自反律所得到的函数依赖均是平凡的

函数依赖，自反律的使用并不依赖于尸。I

DBS

1.Armstrong公理系统

定理6.1Armstrong推理规则是正确的。

(1)自反律：若七则XfY为尸所蕴涵。

证：设丫=x=u

应对RvU,尸〉的任一关系r中的任意两个元组。£：

若江X]=S[X],由于XqX,有t[H=s[H，

•••XfV成立，自反律得证。

DBS

1.Armstrong公理系统

（2）增广律：若xfy为尸所蕴涵，且z=u,则xzfyz

为尸所蕴涵。

证：设XfY为F所蕴涵，且Z=U。

R设RvU,F＞的任一关系r中任意的两个元组。s：

若t[XZ]=s[XZ],则有t[X]=s[X]和t[Z]=s[Z]；

由XFK于是有t[y]=s[y],所以"yz]=s[yz],

・••XZ-YZ为F所蕴涵，增广律得证。一■晨

1.Armstrong公理系统

(3)传递律：若X-V及为尸所蕴涵，贝！J

XfZ为尸所蕴涵。

证：设x-y及yfz为F所蕴涵。

K对RvU,尸〉的任一关系r中的任意两个元组t,s：

若江X]=s[X],由于XfK有tm=s[X]；

再由YfZ,有江Z]=s[Z],

•••X-Z为尸所蕴涵，传递律得证。一■-

2.导出规则

1)根据Al,A2,A3这三条推理规则可以得到下面

三条推理规则：

G合并规则：由X-KXfZ,有X-YZ。

(A2：X->XY,XYfYZA3：XfYZ)

g伪传递规则：由X-Kw/y->z,有xi/Vfz。

(A2：XWfYW,A3：XWfZ)

g分解规则：由x->y及Z=K有xfz。

(Al：ZoYoX,A3：X->Z)----

2.导出规则

2）根据合并规则和分解规则，可得引理6.1

引理6.工X-44...4成立的充分必要条件是

X-4成立（了=1,2,…，k）o

DBS

隹三、函数依赖的闭包

定义6,工2若F为关系模式R(U)的函数依赖集，

我们把F以及所有被F逻辑蕴涵的函数依赖的

集合称为F的闭包，记为F+。即：

rF+={X->Y|X->YeFV"应用Armstrong公理从

F中导出的任何XfY”}

mF屋F+,如果F=F+,贝UF为函数依赖的一个

完备集。

G规定：若X为U的子集，Xf①属于F+。DBS

三、函数依赖的闭包

施R=ABC,F={A―B,B—C},求：F+

解：F+=

{A一①，AB->①,AC-①，ABC一①，B-①，C一①，

A-A,AB-A,AC-A,ABC-A,B-B,C-C,

A-B,AB-B,AC-B,ABC-B,B-C,

A一C,AB一C,AC->C,ABC-C,B-BC,

A-AB,AB-AB,AC-AB,ABC-AB,BC-①，

A-AC,AB-AC,AC-AC,ABC-AC,BC-B,

A-BC,AB-BC,AC一BC,ABC-BC,BC->C,

A-ABC,AB-ABC,AC-ABC,ABC-ABC,BC-BC}

DBS

三、函数依赖的闭包

例：已知关系模式R中：U={A,B,C,D,E,G},

F={AB-C,C-A,BC-D,ACD-B,D-EG,

BE-C,CG-BD,CE-AG},

判断BD-AC是否属于F+

解：由D-EG知：D-E、BD-BE…①

又知BE-C,C-A,所以BE-A,BE-AC...②

由①、②知：BD-AC,所以BD-AC被F所蕴涵,

即BD-AC属于F+。：

DBS

保三、函数依赖的闭包

例：已知关系模式R中：U={A,B,C,E,H,P,G},

F={AC-PE,PG-A,B-CE,A-P,GA-B,

GC-A,PAB-G,AE-GB,ABCP—H},

证明BG-HE属于F+

证：由B-CE知B-C,B-E,BG-GC.・・①

又知GC-A,AT,所以：BG-A,BG-ABCP...②

又ABCP-H,由①、②知BG-HE,所以BG-HE被F

所蕴涵，即BG-HE属于F+。一■/

保三、函数依赖的闭包

K人们把自反律、传递律和增广律称为Armstrong

公理系统。

包Armstrong公理系统是有效的、完备的。

同有效性指的是：由F出发根据Armstrong公理

推导出来的每一个函数依赖一定在F+中；|

H完备性指的是：F+中的每一个函数依赖，4定

.可以由F出发根据Armstrong公理推导出去一

—IDBS

四、属性集闭包

定义6・13设尸为属性集U上的一组函数依赖，

+

X=U,XF={A能由尸根据Armstrong

公理导出},X/称为属性集X关于函数依赖集

尸的闭包。

G用途

将判定X->Y是否能由尸根据Armstrong公理

导出的问题，就转化为求出力+,判定丫是否为

X/的子集的问题。-----

DBS

四、属性集闭包

例:^R=ABC,F={A―B,

当X分别为A,B,C时，求：X/o

解:当X=A时,A/=ABC；

当X=B时,B/=BC；

当x=c时,

关于闭包的引理

引理6.2设F为属性集U上的一组函数依赖，X、

YyU,XfY能由F根据Armstrong公理导出的

充分必要条件是

证：^Y=A1A2...An

①充分条件：当X/时，对于每个i,XfA「叩

公理导出。再用合并规则可得：XfY。

②必要条件：若XfY能够由公理导出，则根据分解

规则，XfAi(i=l,2,…,n)成立，所以：丫/上

DBS

a求闭包的算法

用工、算法依据：

£若F为关系模式R(U)的函数依赖集，X,Z,W是

U的子集，对于任意的ZfWRF,若Z"贝I：

XfXW。

DBS

a求闭包的算法

r2、算法:

r(l)令XF+=X;

位(2)在F中依次查找每个没有被标记的函数依赖,

若“左边属性集”包含于X/,则令：

X尸+=xru''右边属性集”，

为被访问过的函数依赖设置访问标记。

G(3)反复执行(2)直到X/不改变为止。

DBS

四、属性集闭包

例已知关系模式RvU,F>,其中：

U={A,B,C,D,E}；

F={AB.C,B.D,C.E,ECfB,AC->B}O

求：(AB)F+O

解：

所有函数依赖(AB)F+

ABfCABC

BfDABCD

CfEABCDE

四、属性集闭包

例：已知关系模式R中：U={A,B,C,D,E,G},

F={AB-C,C-A,BC-D,ACD-B,D-EG,

BE-C,CG-BD,CE-AG},

求：(BDF，判断BD-AC是否属于F+o

解：(BD)F+=ABCDEG,

BD-AC可由F导出，即BD-AC属于F+。

DBS

八^五、Armstrong公理系统的

/D不有效性与完备性

用建立公理系统体系目的：从已知的f推导出未知的f

E明确：L公理系统推导出来的f正确？

2.F+中的每一个f都能推导出来？

Z五、Armstrong公理系统的

/jy有效性与完备性

应有效性：由尸出发，根据Armstrong公理推导出

来的每一个函数依赖一定在尸中。

⑻完备性：产中的每一个函数依赖，必定可以由尸

出发根据Armstrong公理推导出来。

导所有不能用Armstrong公理推导出来f,都上

为真；

B若f不能用Armstrong公理推导出来，fiEio

DBS

a有效性与完备性的证明

证明：

1.有效性

Armstrong公理有效性可由定理6.1得证。

2.完备性

只需证明完备性的逆否命题：

R若函数依赖不能由F从Armstrong公

理导出，那么它必然不为尸所蕴涵

G分三步证明：------

DBS

a有效性与完备性的证明

(1)若I/fIV成立，且则=

证：=・,•有XfI/成立；

又V->W,于是XfI/I/成立，

・•・IVoX/o

(由引理6.2)

DBS

a有效性与完备性的证明

(2)/*若f不能用Armstrong公理推导出来，feF+

/*若存在小户中的全部函数依赖在「上成立。

/*而不能用Armstrong公理推导出来的f,在「上不成立

n构造一张二维表几它由下列两个元组构成，可以证明

「必是RvU,尸》的一个关系，即F+中的全部函数依

赖在「上成立。

DBS

a有效性与完备性的证明

r由下列两个元组构成的二维表厂,必是RvU,尸〉的一

个关系，即满足尸中的全部函数依赖在「上成立。

U-X；

11...................100.：：.................0

11••・・••111••・・・•1

DBS

a有效性与完备性的证明

K若「不是RvU,尸》的关系，则必由于尸中有某个函

数依赖Vf1/1/在厂上不成立所致。

R由广的构成可知，1/必定是X/的子集，而1/1/不是

X/的子集，可是由第(1)步，I/I/QX/,矛盾。

所以r必是Rvu,尸〉的一个关系。

DBS

a有效性与完备性的证明

(3)/*若f不能用Armstrong公理推导出来，fe尸+

/*而不能用Armstrong公理推导出来的f,在厂上不成立

r若不能由尸从Armstrong公理导出，

贝UY不是Xr的子集。(引理6.2)

K因此必有V的子集/满足Y&U-X尸+,则XfY在广

中不成立，即XfY必不为RvU,Q蕴涵。

/*因为尸+中的全部函数依赖在「上成立。#-----

DBS

五、Armstrong公理系统的

有效性与完备性

eArmstrong公理的完备性及有效性说明：

R“蕴含”与“导出”是完全等价的概念

包户可说成是由尸出发借助Armstrong公

理导出的函数依赖的集合。