数据库原理-关系数据库规范化理论

一般而言,关系数据库设计的目标是生成一组关系模式,使得我们存储信息的时候避免不必要的冗余和数据不完整的问题,这需要通过设计满足范式(normal form)的模式来实现的,

1.非规范化设计的问题

• 数据冗余

• 插入异常

• 删除异常

• 更新异常

2. 原子域和第一范式(1NF的概念)

E-R模型允许实体集和联系集的属性具有子结构,它允许多值属性(也就是一个实体对应多个属性值,例如电话号码),以及组合属性(比如说address可以分解为street、city等)。

当从包含这些类型的属性的E-R设计创建表的时候就要消除这种子结构了。

• 对于组合属性,我们要让每个子属性成为单独一个属性
• 对于多值属性,我们要给多值集合中的每一个项创建一条元组(可以简单理解为建新表)

原子(atomic)域:如果这个域的元素被认为是不可以再分的单元,或者说这个属性不具有任何的子结构,那么我们就称这个关系模式R就属于第一范式(Firtst Normal Form,1NF)了

3. 使用函数依赖进行分解

• 一般情况下,我们用希腊字母来表示属性集α
• 用一个小写的罗马字母后面跟一对圆括号括住的大写字母来表示关系模式,比如说r(R)
  • r:关系名
  • R:属性集
  • 当我们不关心关系的名字的时候我们通常简化我们的表示法而只用R
• 当属性集是一个超码的时候,我们就用K来表示它,超码属于特殊的关系模式,因此我们使用术语K是r(R)的超码
• 我们对关系使用小写的名字,而在定义和算法中使用单个字母
• 关系在任意给定时间都有特定的值,我们可以将那看作一个实例并使用术语r的实例,当我们在讨论一个实例的时候,就可以只使用关系的名字r了

关系模式由五部分组成:R(U,D,DOM,F)

• R:关系名
• U:组成该关系的属性名集合
• D:属性组U中属性所来自的域(数据类型)
• DOM:属性向域的映射集合值
• F:属性间数据的依赖关系集合

3.1 函数依赖(Functional Dependency)

在数据设计上,通常存在各种约束,如果一个关系的一个实例,满足这种所有约束,我们就叫它为关系的合法实例(legal instance)。

几种最常用的约束可以形式化地表示为码(超码、候选码以及主码),或者下面所定义的函数依赖

• 超码
  • 可以唯一地标识关系中一条元组的一个或者多个属性的集合
  • r(R)是一个关系模式,R的子集K是r(R)的超码,在关系r(R)的任意合法实例中没有两条元组在属性集K上可能具有相同的值,如果r中没有两条元组在K上具有相同的值,那么K就能够在关系模式r中唯一标识一条元组

鉴于超码能够唯一识别整条元组的属性集,函数依赖让我们可以表达唯一标识某些属性的值的约束,考虑一个关系模式r(R),我们令α包含于R而且β包含于R,也就是说α和β都是属性集R的子集

• 给定r(R)的一个实例,我们就说这个实例满足函数依赖α->β,那么我们就说该函数依赖在模式r(R)上成立
• 条件:对实例中所有的元组t1和t2,如果t1[α]=t2[α],那么t1[β]=t2[β]

理解

这个α是R的子集,可能包含一个属性,也可能包含多个属性,如果说对于r(R)的任意一个可能的关系r

也就是任意一个可能的取值下,r中呢不可能存在两个元组,在α上的属性值是完全相等的,但是在β上的属性值是不相等的,注意是不可能存在这样的情况,α叫做这个函数依赖的决定属性集

• 一个特定的α,决定一个特定的β,如果α是确定的,那么β肯定也是确定的

考虑一个这样的关系r,求出它的所有函数依赖。

首先根据定义,可以先找出其函数依赖的决定属性集:

a1是特定的一个,c1也是特定的一个,因此a1->c1

a2是特定的一个,c2也是特定的一个,因此a2->c2

a3是特定的一个,c2是特定的一个,因此a3->c2

说明:存在两条元组A值为a1,这些元组具有相同的C值c1,同样的,存在两条元组A值为a2,这些元组具有相同的C值c2。

因此我们可以得出A->C,但是函数依赖C->A是不满足的,因为我们发现对于具有相同的C值的c2,对应了两个A值,也就是a2和a3,因此不成立

因此,判断函数依赖成不成立的方法如下

• 找到具有相同值的两个以上的元组,作为依赖决定集
• 找到元组中对应的被决定集,观察其被决定集是否相同,如果都相同,那么就证明函数依赖在这个关系上是成立的

有些函数依赖称为是平凡(trivial)的函数依赖,因为它们在所有关系中都满足

比如说A->A在包含属性A的关系都满足的,一般地,对于β是α的子集,那么形如α->β就是平凡的

如果α->β,而,β不是α的子集,那么a->β就不是平凡的函数依赖

因此,判断函数依赖是否平凡,我们只需要观察决定依赖集和被决定依赖集是否有子集关系即可

完全函数依赖和部分函数依赖

如果X->Y而且对于X的任何一个真子集X',都有X'不是Y的函数依赖,那么就说Y完全函数依赖于X

如果X->Y,但Y并不完全函数依赖于X,也就是说如果X存在一个真子集,这个真子集用更少的属性就能够决定Y,那么我们就说Y部分函数依赖于X。

因此,判断X和Y的函数依赖是完全的,还是部分的,只需要观察在决定依赖集中,能否找到一个子集也能够对应一个唯一的Y即可

传递函数依赖

关系模式r(R)中,如果X->Y,Y->Z,而且Y不是X的子集,Y不是X的函数依赖,那么就说Z传递函数依赖于X

原理:如果X->Y,那么也就说如果确定了X的值,那么Y的值也是确定的

如果Y->Z,那么也就是说,如果确定了Y的值,那么Z的值也是确定的

那么综合起来看,如果我确定了X的值,那么Y的值就是确定的,如果Y的值是确定的,那么Z的值也是确定的

因此,X的值是确定的一个,那么Z的值也会是确定的一个

相对的,像X->Y就叫做直接函数依赖。

我们可以使用F+符号来表示F集合的闭包(closure),也就是能够从给定F集合推导出所有的函数依赖。

F+包含F中所有的函数依赖

3.2 码(Key)

设K是关系模式R(U,F)中的属性或者属性组合

如果U完全函数依赖于K,那么K就是R的一个候选码(Candidate Key)

这里的K是一个决定依赖集,这个决定依赖集里面不能再划分出更小的子集(不含多余的属性)来决定U了,我们就说这个属性集K是候选码。这和之前学的候选码的定义是异曲同工的,也就是说这是能够确定另外一个元组的最小属性集定义了。

若关系模式R有多个候选码,那么就选定其中一个作为主码

候选码能够唯一地表示关系的元组,是关系模式中一组最重要的属性

主码和外码一起提供了一个表示关系间联系的手段

4. 范式

关系数据库中的关系必须满足一定的要求,满足不同程度要求的为不同范式

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

范式之间的关系

1NF 2NF 3NF BCNF 4NF 5NF

如果某一关系模式为第n范式,那么就可以记录为R∈nNF

4.1 第一范式

如果一个关系模式R的所有属性都是不可分割的基本数据项,那么就说这个关系模式R∈1NF

• 第一范式是对关系的最基本的要求
• 不满足第一范式的数据库模式不能称之为关系数据库
• 但是满足第一范式的关系模型并不一定是一个好的关系模式

4.2 第二范式

如果关系模式R∈1NF,而且每个非主属性都完全函数依赖于R的码,那么R∈2NF

例子

SLC（Sno,Sdept,Sloc,Cno,Grade）∈1NF,问:

SC(Sno,Cno,Grade)和SL(Sno,Sdept,Sloc)分别满足什么范式?

对于SC(Sno,Cno,Grade)而言:

(Sno,Cno)->Grade,我们可以看到(Sno,Cno)是码,也就是主属性,而Grade是非主属性,根据函数依赖表达式可知Grade完全函数依赖于(Sno,Cno),也就是完全函数依赖于码,因此满足第二范式

对于SL(Sno,Sdept,Sloc)而言:

Sno->Sdept,Sdept->Sloc,因此Sno->Sloc

因此Sno是码,它能够决定其他所有属性,而对于Sdept和Sloc而言,他们完全函数依赖于Sno,因此满足第二范式

这个例子中,Sloc传递函数依赖于Sno,也就是说SL中存在非主属性对码的传递函数依赖

这个关键在于理解传递函数依赖和直接函数依赖,像题目给出的条件就是直接函数依赖,而传递函数依赖则是题目没有给出我们,我们从题目中推出来的函数依赖我们叫做传递函数依赖。

我的理解是这个关系中的码是候选码,而且能够确定非主属性

4.3 第三范式(third normal form)

具有函数依赖集的关系模式R属于第三范式的条件是:对于F+中的所有形如X->Y的函数依赖,以下至少一项成立

• X->Y可以是一个平凡的函数依赖
• X是R的超码
• Y-X中的每个属性A都包含于R的一个候选码中,Y-X的每个属性A都可能包含于不同的候选码中

另一种理解:关系模式R∈1NF,而且不存在非主属性对码的传递函数依赖,那么就称R∈3NF

一个显而易见的结论就是,3NF是可以通过2NF改进而来的,其主要手段是对关系模式进行分解,对其中含有传递函数依赖的关系模式进行拆解,拆解成有各自码的模式,从而达到第三范式的效果

SL(Sno,Sdept,Sloc)属于2NF,存在传递函数依赖Sno->Sloc

于是我们针对函数依赖进行分解为

SD(Sno,Sdept)

DL(Sdept,Sloc)

如果R∈3NF,那么R的每个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码

• 将一个2NF关系分解为多个3NF的关系后,在有些情况下,并不能完全消除关系模式中各种异常情况和数据冗余。

4.4 BC范式

BCNF(Boyce Codd Normal Form):通常认为BCNF是修正的第三范式,设关系模式R∈1NF,如果对于R的每个函数依赖X->Y,如果Y不属于X,那么X必定含有候选码,那么R∈BCNF,BC范式能够消除所有基于函数依赖能够发现的冗余,

BCNF的理解:

• 首先BFNF要满足1NF(关系型数据库)
• 对于任意一个函数依赖,如果这个函数依赖不是平凡的函数依赖,如果它满足BCNF的话,那么X->Y中,X一定含有候选码,也就意味着可以是候选码的超集
• 如果是平凡的函数依赖,那么就跳过检索这个函数依赖。
• 换句话说,在关系模式R中,如果每一个决定属性集都包含了候选码,那么R∈BCNF

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

• 所有非主属性都完全函数依赖于每个候选码
• 所有主属性都完全函数依赖于每个不包含它的候选码
• 没有任何属性完全函数依赖于非码的任何一组属性

3NF和BCNF的关系

• 如果关系模式R∈BCNF,那么R∈3NF
• 如果R∈3NF,而且R只有一个候选码,那么R一定是BCNF

如果一个关系数据库中的所有关系模式都属于BCNF,那么在函数依赖的范畴内,它已经实现了模式的彻底分解,达到了最高的规范化程度,消除了插入异常和删除异常

我们回顾一下之前的那个例子,经过分解之后,最终的效果是这样的:

(Sno,Cno)->Grade

Sno->Sdept

Sdept->Sloc

SC(Sno,Cno,Grade)

SD(Sno,Sdept)

DL(Sdept,Sloc)

它本身是满足第三范式的,然后我们观察其所有的函数依赖,每一个关系模式都满足其内的函数依赖的决定属性集都包含有候选码。因此它也符合BCNF

在关系模式STC(S,T,C)中,S表示学生,T表示教师而C表示课程

函数依赖:

T->C、(S,C)->T、(S,T)->C

对于这个函数依赖,我们可以选出码(S,C)和(S,T),我们发现S、T、C均是主属性,那么也就是非主属性

我们也可以先判断一下这个关系模式符合第几范式:

首先肯定是满足第一范式的,然后不存在非主属性对码的传递函数依赖,而且也不存在部分函数依赖于候选码的情况,因此肯定满足第三范式(因为根本就没有非主属性了,必定成立)

然后我们看到:T->C,也就是说主属性C依赖于T,也就是说主属性C部分依赖于码(S,T),能够找到(S,T)的真子集使之满足函数依赖。。

总结一下

在满足3NF的基础上,我们发现T并不是候选码,但是却存在函数依赖T->C,在这样的情况下,决定属性集中出现了非候选码,这种情况就不满足BC范式了,按照我自己的理解的话,BCNF出现的是为了解决一个关系模式内含有多个候选码的情况

4.5 分解的基本规则

我们假设R不属于BCNF的一个模式,那么就说至少存在一个非平凡的函数依赖X->Y,而且X不是R的超码,那么我们在设计中用以下两种模式取代R

• (X∪Y):X和Y的并集
• (R-(Y-X)):R和(Y与X作差后的差集)作差后的差集

4.6 BCNF和保持依赖

假设有这样的函数依赖:

i_ID->dept_name

s_ID,dept_name->i_ID

我们可以推断出候选码是(s_ID,dept_name),然后我们发现函数依赖i_ID->dept_name中,i_ID并不包含候选码,然后我们依据分解的规则:X={i_ID},Y={dept_name}

然后可以得到两个分解后的关系模式

(i_ID,dept_name)

(i_ID,s_ID)

然后我们观察分解后的关系模式发现,没有任何一个模式包含函数依赖(S_ID,dept_name)->i_ID

这种设计就不是保持函数依赖(dependency preserving)的

5. 函数依赖集的闭包

给定模式上的函数依赖集F,我们可以证明某些其他的函数依赖在模式上也是成立的。

我们称这些函数依赖被F逻辑蕴含,当检验范式的时候,只考虑给定的函数依赖集是不够的。

还需要考虑模式上成立的所有函数依赖

给定关系模式r(R),如果r(R)的每一个满足F的实例也满足f,那么R上的函数依赖f被r上的函数依赖集F逻辑蕴含(logically imply)

例子:

假设我们给定关系模式r(A,B,C,G,H,I)以及函数依赖集

A->B,A->C,CG->H,CG->I,B->H,由依赖的传递原理:

A->B,B->H=>A->H,那我们就说A->H被函数依赖集逻辑蕴含了

令F是一个函数依赖集,F的闭包是被F逻辑蕴含的所有函数依赖的集合,我们把它记作F+,给定F,就可以由函数依赖的形式化定义直接计算出F+。

Armstrong公理

• 自反律(reflexivity rule):如果a是一个属性集,而且b是a的子集,那么a->b是成立的

理解:为什么叫自反律?因为a的子集包含其本身,因此通常有A->A这样的操作

• 增补律(augmentation rule):如果a->b成立而且c是一个属性集,那么ac->bc成立

理解:如果c是单个属性集,我们那么可以把c理解为一个”挂件”,既然a对应的b是唯一的,而c也是单个的唯一的属性集,那么两边同时挂上这个挂件,也是成立的

• 传递律(transitivity rule):如果a->b和b->c成立,那么a->c就成立

另外,还有一些推广的规则

• 合并律(union rule):如果a->b和a->c是成立的,那么a->bc也是成立的

∵a->b,由增补律,那么a->ab,两边同时增加a

∵a->c,由增补律,那么ab->bc,两边同时增加b

∴由传递律就可以知道:a->ab,ab->bc,所以a->bc

• 分解律(decomposition):如果a->bc是成立的,那么a->b和a->c也是成立的

由自反律,我们知道a->bc,我们把bc看作为一个整体d,那么也就是a->d

因为b、c是d的子集,d->b,d->c

也就是说a->d,d->b,所以a->b

a->d,d->c,所以a->c

• 伪传递律(pseudotransitivity rule):如果a->b和bc->d,那么ac->d

∵a->b,由增补律,那么ac->bc,两边同时增加c

∵bc->d,由传递律:ac->bc,bc->d,所以ac->d

让我们回到例子

假设我们给定关系模式r(A,B,C,G,H,I)以及函数依赖集

A->B,A->C,CG->H,CG->I,B->H,试计算函数依赖集的闭包

这里列出F+的几个函数依赖

A->H:A->B,B->H

CG->HI,由CG->H,CG->I,由合并律,那么CG->HI

AG->I,由A->C,CG->I,由增补律:AG->CG,那么AG->I

计算闭包的方法

F+ = F//也就是说初始化函数闭包为题目给的函数依赖集
    repeat
    	for each F+中的函数依赖f //对于每一个函数依赖,考察下面的情况
            在f上应用自反率和增补律//寻找那些平凡的函数依赖
            将结果加入到F+中
        for each F+中的一对函数依赖f1和f1
            if f1和f2可以是使用传递律结合起来//寻找那些逻辑蕴含的函数依赖
                将结果加入到F+中
        until F+不再发生变化

n个元素的集合有2^(2n)个可能的函数依赖

6. 属性集的闭包

如果a->B,那么我们就说属性B被a函数确定(functionlly determine),要判断集合a(注意这个a是属性集来的)是否是超码,计算被a函数所确定的属性集

• 计算集合a的F+,找出所有左半部分为a的函数依赖,然后合并这些函数依赖的右半部分

书上关于计算属性集闭包的算法描述

result := a;
	repeat
        for each 函数依赖β->r in F do//遍历每一个函数依赖
            begin
            	if β 是 result的子集
                    then result := result ∪ y;
			end
        until result不变

例题

假设我们给定关系模式r(A,B,C,G,H,I)以及函数依赖集

A->B,A->C,CG->H,CG->I,B->H,试计算在此函数依赖集下的(AG)+。

解:令result = AG,开始遍历函数依赖集

由A->B,于是将B加入result,result=ABG

解释:因为我们观察到A->B是属于F的,A是result(AG)的自己,所以result = result∪B

由A->C,于是将C加入到result,result=ABCG

由CG->H,于是将H加入到result中,result=ABCGH

由CG->I,于是将I加入到算法中,result=ABCGHI

算法结束

属性闭包算法有如下的用途

• 为了判断a是否为超码,我们可以计算集合a的闭包,检查a是否包含R中的所有属性
• 通过检查是否β是a属性集的闭包的子集,我们就可以检查函数依赖a->β是否成立,换句话说,是否属于F+
• 对于任意的y包含于R,我们找出y的闭包,对于任意的S是y的闭包的子集,我们可以输出一个函数依赖y->S

解释:如果y是R的一个子集,我们计算出y的闭包,然后对于y的闭包,我们把叫做S,那么我们就可以得到一个函数依赖y->S

7. 正则覆盖(最小依赖集)

最小函数依赖集

• D中任意函数依赖的右部仅含有一个属性

• D中不存在这样的函数依赖M->N,函数依赖左部M有真子集Q使得D-{M->N}∪{Q-N}与D等价

  • 换句话说,D中任意一个函数依赖的左部替换为其任意一个真子集的话,都不再与原始的D等价

  • 简单地说,D中的每一个函数依赖的左部都不包含多余的属性

• D中不存在这样的函数依赖M->N,使得D-{M-N}与D等价

  • 不包含多余的函数依赖

总的来说,就是左部不包含多余的属性,右部只包含一个属性,整个函数依赖集不包含多余的函数依赖

假设我们在一个关系模式上有一个函数依赖集F,每当用户在该关系上执行更新的时候,数据库系统必须确保此次更新不会破坏任何的函数依赖。

如果更新操作破坏了F上的任意一个函数依赖,系统必须回滚此更新操作

如果去除函数依赖中的一个属性不改变该函数依赖集的闭包,那么我们就说这个属性是无关的(extraneous)。无关属性的形式化定义如下:考虑函数依赖集F以及F中的函数依赖a->b

• 如果A∈a,并且F逻辑蕴含(F-{a->b})∪{(a-A)->b},那么属性A在a中是无关的
• 如果A∈b,并且函数依赖集(F-{a->b})∪{a->(b-A)}逻辑蕴含F,那么属性A在b是无关的。

计算最小函数依赖集的算法

• 逐个检查D中的各函数依赖Di:M->N,如果N=A1A2...Ak,k>=2,那么就用{M->Aj|j=1,2,...,k}来取代M->N

理解:对右边包含两个或者两个以上属性的函数依赖运用分解规则进行分解,比说原来的N有有k个元素,我们可以运用分解律,全部变成M->A1,…,M->Ak的形式

• 逐一检查D中的各函数依赖Di:M->N,我们假设M=B1B2,...,Bm,逐一考察Bi(i=1,2,..,m),如果说N∈(M-Bi)+,那么就用M-Bi来替代M

理解:就是对左部包含若干个属性进行检查,如果左部的一个子集的属性闭包等于右部,那么就把左部替换为该子集

• 逐一检查D中的各函数依赖Di:M->N,令G=D-{M->N},如果G+=D+,那么就从D中去掉这个函数依赖

也就是说,去掉一个函数依赖,然后我去计算它的闭包发现它的闭包和原来的一样,那么就认为这个函数依赖是多余的

对于检查函数依赖左部和右部的处理方案是不一样的

如果是左部,那么用来计算的函数依赖集是原来的函数依赖集

如果是右部,那么用来计算的函数依赖集是去掉了多余属性的新函数依赖集

例子

计算D的最小函数依赖集,D={a->b,b->a,b->c,a->c,c->a}

在这个例子中,只需要判断是否有多余的函数依赖即可

由于b->c和c->a能够推出b->a,因此b->a是多余的

由于a->b和b->c能够退出a->c,因此a->c是多余的

Dm1={a->b,b->c,c->a}

一个函数依赖集的最小依赖集是不唯一的,一个函数依赖集和它的最小依赖集以及其闭包都是等价的

书本上关于计算最小覆盖的算法描述

Fc=F//初始化最小覆盖的值
    repeat
    	使用合并律将Fc中所有形如a1->b1和a1->b2的依赖替换为a1->b1b2
        在Fc中寻找一个函数依赖a->b,它在a或者在b中具有一个无关属性
        如果找到一个无关属性,那么就将它从Fc中的a->b中删除
    /*注意分清楚左部和右部的情况*/
    until Fc不变

检验是否无关例子1

假定包含AB->CD、A->E、E->C,为了检验C在AB->CD是否是无关属性,我们计算F'={AB->D,A->E,E->C}下AB的属性闭包

计算过程如下:

由A->E,所以AB->DE

由E->C,所以AB->CDE

由自反律AB->ABCDE,包含了CD,我们认为C是无关的

例子2

考虑模式(A,B,C)有如下函数依赖集F:A->BC、B->C、A->B、AB->C,求正则覆盖

第一步:初始化正则覆盖为F={A->BC,B->C,A->B,AB->C}

对于函数依赖左部有相同元素的施行合并律:A->BC、A->B=>A->BC,F={A->BC,B->C,AB->C}

为了检验B在AB->C是否是无关属性,我们计算F’={A->BC,B->C,A->C}下,A的属性闭包(AB去掉B)

初始化(A)+={A}

由A->BC,则(A)+={ABC},包含AB,因此我们推断出B是无关的

所以此时的正则覆盖为F={A->BC,B->C,A->C}

A->BC中由分解律可知A->B、A->C、B->C,因此A->C

可见A->C是多余的函数依赖,我们删除,此时的正则覆盖是F={A->BC,B->C}

这里做出来和答案不一样,但是经过验证,这个应该也是一个正则覆盖,因为和课本上的那个是等价的

例子3

考虑函数依赖集F={A->BC,B->AC,C->AB},求解正则覆盖

第一步:初始化正则覆盖为Fm={A->BC,B->AC,C->AB}

ps:由于这时候没有可用合并律合并的函数依赖了,因此我们开始去除无关的属性

第二步,检查B在A->BC是否是多余的,我们计算(A)+在F'={A->C,B->AC,C->AB}的闭包,计算过程:

A->C,所以(A+)={AC}

C->AB,所以A+={ABC}

因此在这种情况下,B在A->BC是多余的

此时得到的正则覆盖为Fm={A->C,B->AC,C->AB}

---

然后我们检验A在B->AC是否是多余的

计算(B)+在F'={A->C,B->C,C->AB}的闭包,计算过程:

B->C,所以(B)+={BC}

C->AB,所以(B)+={ABC}

因此A在B->AC是多余的

此时得到的正则覆盖为Fm={A->C,B->C,C->AB}

---

检查A在C->AB中是否是多余的

计算(C)+在F'={A->C,B->C,C->B}的闭包,计算过程

C->B,所以(B)+={BC}

然后我们发现无法得到A这个属性,因此A不是多余的

---

然后我们检查B在C->AB是否是多余的

计算(C)+在F'={A->C,B->C,C->A}

(C)+={AC}

此时我们发现无法得到B这个属性,所以B不是多余的

---

最终我们得到的正则覆盖就是Fc={A->C,B->C,C->AB}

8. 无损连接分解(lossless decomposition)

关系模式的规范化过程是通过对关系模式的分解来实现的

• 把低一级的关系模式分解为若干个高一级的关系模式的方法并不唯一
• 在这些分解方法中,只有能够保证分解后的关系模式与原关系模式等价的方法才有意义

将一个关系模式R(U,F)分解为若干个关系模式R1(U1,F1)、R2(U2,F2),…,Rn(Un,Fn)

• 其中:U=U1∪U2∪…∪Un,而且不存在Ui包含于Uj,Fi为F在Ui上的投影
• 意味着相应地将存储在一个二维表t中的数据分散到若干个二维表t1,t2,…,tn中去
• 如果R与R1、R2、…、Rn 自然连接的结果相等,那么就说关系模式的这个分解具有无损连接性
• 如果F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含,那么就说关系模式R的这个分解是保持函数依赖的的

其中ti是t在属性集上的投影

如果分解后的关系可以通过自然连接恢复为原来的关系,那么这种分解就没有丢失信息

如果要求的分解具有无损连接性,那么模式分解一定能够达到BCNF

如果要求分解保持函数依赖,那么模式分解一定呢能够达到3NF,但是不一定能够达到BCNF

如果要求分解既具有无损连接性,又保持函数依赖,那么模式分解一定能够达到3NF,但不一定能够到达BCNF

定理:设p=(S1,S2)是S的一个分解,D是S上的函数依赖集,分解p具有无损连接性的充分必要条件是:

S1∩S2->(S1-S2)∈D+或S1∩S2->(S2-S1)∈D+

理解:分解具有无损连接性当且仅当两个关系模式的公共属性是其中一个模式的键

9. 保持依赖

设关系模式S<A,D>被分解为n个关系模式,S1<A1,D1>…Sn<An,Dn>其中A=A1,A2...,An,而且不存在Ai是Aj的子集,Di是D在Ai上的投影,如果D等价于Di(i=1,2,3...,n)的并集,那么就说关系模式S的这个分解是保持函数依赖的

10. BCNF分解

分解算法的过程:

1.初始化:初始化分解后的结果为p={S<A,D>}

2.检查p中各关系模式是否属于BCNF,如果是的话,那么算法就终止,否则执行3

3.设p中存在Si<Ai,Di>不属于BCNF,那么就一定会存在一个非平凡的函数依赖

• a->b∈Di,a∩b=∅
• a不包含Si的候选码

那么我们将Si分解为Pi={a∪b,Ai-b},后用pi来代替Si,回到2

注意:分解为BCNF的关系不一定能够保持函数依赖

例题,有如下关系:

tutor(t_id,s_id,dept_name)

其中,每个导师可以指导多名研究生但是只能在一个院系中工作

每个研究生可以有多位导师,但是在一个院系中只能有一个

函数依赖表达如下:

(s_id,t_id)->dept_name

t_id->dept_name

(s_id,dept_name)->t_id

候选码:

(t_id,s_id)、(s_id,dept_name)

• 请分析上述关系不满足什么范式?该如何分解为对应的范式?

由函数依赖t_id->dept_name中t_id并不是候选码,因此不满足BCNF

分解为BCNF

• 第一步,初始化分解后的结果为p={tutor(s_id,t_id,dept_name)}
• 第二步,检查是否满足BC范式(不满足)
• 第三步,针对不满足BC范式的函数依赖进行分解(t_id->dept_name)

这时候,t_id=>a,dept_name=>b

因此分解为p'={a∪b,p-b}={{t_id,dept_name},{t_id,s_id}}

同时我们注意到,这个分解使得原模式损失了(s_id,t_id)->dept_name这个函数依赖,因此没有保持依赖

11. 3NF分解

分解的过程:

1.先求出D的极小依赖集,然后把极小依赖集中那些左部相同的函数依赖用合并律合并起来

2.每个函数依赖a->b去构成模式{a∪b}

3.在构成的模式集中,如果每个模式都不包含S(S是原来的完整的关系模式)的候选码,那么就把候选码作为一个模式放入到模式集中

例子,有如下关系和函数依赖

tutor(t_id,name,dept_name,dept_num)

{t_id->name,t_id->dept_name,dept_name->dept_num}

• 请分析上述关系不满足什么范式?该如何分解为对应的范式?

首先要先分析出这个关系的码,计算(t_id)+

由t_id->name,(t_id)+={t_id,name}

由t_id->dept_name,(t_id)+={t_id,name,dept_name}

由dept_name->dept_num,(t_id)+={t_id,name,dept_name,dept_num}=tutor

因此t_id是候选码是主属性,而存在t_id->dept_name,dept_name->dept_num,t_id->dept_num,也就是非主属性对码的传递函数依赖,因此不满足第三范式

分解为第三范式过程:

求解该关系的正则覆盖:

第一步,初始化正则覆盖,对于形如a1->b1和a1->b2的所有函数依赖依据合并律合并起来

则:Fm={t_id->(name,dept_name),dept_name->dept_num}

试检查dept_name在t_id->(name,dept_name)是否是多余的,显然不是,这里省略

因此求得正则覆盖是Fm={t_id->(name,dept_name),dept_name->dept_num}

求解完了正则覆盖后,对Fm进行操作,也就是执行算法的第二步,对每个函数依赖的左部和右部执行合并为一个关系模式的操作

变为p={{t_id,name,dept_name},{dept_name,dept_num}}

第三步,检查是有包含候选码,可以观察到有t_id存在于第一个关系中,分解完成

12. 数据库的设计过程

• 1NF->2NF 消除非主属性对码的部分函数依赖
• 2NF->3NF 消除非主属性对码的传递函数依赖
• 3NF->BCNF 消除主属性对码的部分和传递函数依赖
• BCNF->4NF 消除非平凡且非函数依赖的多值依赖
• 4NF->5NF 消除不是由候选码所蕴含的连接依赖

规范化的基本思想是逐步消除数据依赖中不合适的部分,使模式中个关系模式达到某种程度的分离

让一个关系描述一个概念、一个实体、或者实体间的一种联系

如果多于一个概念,就把它分离出去,所谓规范化实质上就是概念的单一化

课后习题解析

For relation schema r(A,B,C,D,E), and the functional dependencies F={A->BC,CD->E,B->D,E->A}. List all the candidate keys for R and explain why.

题目大意:给你一个关系r和一个函数依赖集F,请你列出r的所有候选码并解释你的过程

解题思路:可以通过计算某一个属性的闭包,观察闭包是否包含了所有属性,如果属性集的闭包包含了所有属性,那么就是候选码

A是候选码吗?

∵A->BC,(A)+={ABC}

∵B->D,(A)+={BCD}

∵CD->E,(A)+={BCDE}

则(A)+={ABCDE},所以A是候选码

---

B是候选码吗?

∵B->D,(B)+={BD}

然后由B和D推不出更多属性了,所以B不是候选码

---

CD是候选码吗?

∵CD->E,(CD)+={CDE}

∵E->A,(CD)+={ACDE}

∵A->BC,(CD)+={ABCDE}

所以CD是候选码

---

E是候选码吗?

∵E->A,(E)+={AE}

∵A->BC,(E)+={ABCE}

∵B->D,(E)+={ABCDE}

所以E是候选码

---

在做完基础的函数依赖的判断之后,还要细心观察一下函数依赖,看下有没有漏网之鱼,怎么看呢

比如说已经知道A、CD、E是候选码了,那么由传递律可以知道,由这三个候选码直接决定的被决定的属性集也是候选码,比如说A->BC,因此BC也是候选码,也可以做简要证明

∵B->D,(BC)+={BCD}

∵CD->E,(BC)+={BCDE}

∵E->A,(BC)+={ABCDE}

综上所述,关系r的候选码有A、CD、BC、E

给你一个关系r和函数依赖集F,请你完成下面的问题

a.计算B这个属性集的闭包

初始化:B+={B}

∵B->D,B+={BD}

∵D->A,B+={ABD}

∵A->BCD,B+={ABCD}

∵BC->DE,B+={ABCDE}

b.证明AF是超码

要验证AF是超码,可以直接计算AF的闭包,如果AF的包含了所有的属性,那么AF就是超码

证明:初始化(AF)+={AF}

∵A->BCD,(AF)+={ABCDF}

∵BC->DE,(AF)+={ABCDEF}

因此AF是超码

c.计算函数依赖集的正则覆盖,每一步要给出你的推导过程

第一步,初始化正则覆盖,Fc={A->BCD,BC->DE,B->D,D->A}

检查B->D这个函数依赖是否是多余的函数依赖,计算方法是这样的,就是去掉D,然后计算B的闭包

经检查,所有的函数依赖都不是多余的。

第二步,检查是否有多余的属性

检查BC->DE中,B是否是多余的属性,那么就要计算C在原函数依赖集下的闭包,发现B不是多余元素

然后检查BC->DE中,D是否是多余的属性,那么就要计算BC在新函数依赖集上的闭包

注意:这是检查左部和右部的区别所在

新函数依赖集Fc={A->BCD,BC->E,B->D,D->A}

初始化,(BC)+={BC}

∵BC->E,(BC)+={BCE}

∵B->D,(BC)+={BCDE}

∵D->A,(BC)+={ABCDE}

看到(BC)+={ABCDE},包含了D,所以说D是多余的属性

∴Fc={A->BCD,BC->E,B->D,D->A}

然后我们检查A->BCD中,右部的属性的情况

检查B是否是多余的:新函数依赖集Fc={A->CD,BC->E,B->D,D->A}

然后计算A的闭包

(A)+={A}

∵A->CD,(A)+={ACD}

然后我发现到此为止B都没有出现,所以B不是多余的

检查C是否是多余的,新函数依赖集Fc={A->BD,BC->E,B->D,D->A}

然后计算A的闭包

(A)+={A}

∵A->BD,(A)+={ABD}

然后我发现到此为止C都没有出现,所以C不是多余的

检查D是否是多余的,新函数依赖集Fc={A->BC,BC->E,B->D,D->A}

然后计算A的闭包

(A)+={A}

∵A->BC,(A)+={ABC}

∵BC->E,(A)+={ABCE}

∵B->D,(A)+={ABCDE}

发现这时候A的闭包出现了D,所以我们确认D是多余的

最终得到正则覆盖是Fc={A->BC,BC->E,B->E,D->A}

另一种答案,我们保持A->BCD中D是多余的条件,我们在检验BC->DE的这个过程中,检验C是否是多余的

计算函数依赖左部的属性是多余的,方法是计算去掉了那个属性的左部的闭包

第一步,初始化闭包(B)+={B}

第二步,根据原函数依赖计算闭包,F={A->BCD,BC->DE,B->D,D->A}

∵B->D,(B)+={BD}

∵D->A,(B)+={ABD}

∵A->BC,(B)+={ABCD}

∵BC->DE,(B)+={ABCDE}

因此C是多余的,我们就可以得到另外一个正则覆盖

Fc={A->BC,B->DE,D->A}

d.在c做出来的正则覆盖基础上给出这个模式的3NF分解

初始化分解后的结果为p={r(A,B,C,D,E)}

我们以Fc={A->BC,B->DE,D->A}为正则覆盖对这个模式进行分解

对每个函数依赖的左部和右部执行合并:

那么p就变成了:p={r1{A,B,C},r2(B,D,E),r3(D,A)}

通过计算A的闭包可知,(A)+={ABCDE},而关系模式r(A,B,C,D,E,F),还少个F

因此AF是候选码

还需要执行算法的最后一步,也就是添加一个元组AF

因此3NF的分解为{A,B,C},{B,D,E},{D,A},{A,F}

e.使用原始的函数依赖集将模式分解为BCNF

r(A,B,C,D,E,F),原本的关系模式只符合1NF,直接开始分解

初始化分解后的模式为p={r}

考察函数依赖集{A->BCD,BC->DE,B->D,D->A}

①对于A->BCD,将A看作a,将BCD看作b,那么就得到r1(A,B,C,D)和r2(A,E,F)

②考察r1,r1中有两个函数依赖成立:A->BCD和B->D,D->A,我们发现A、B、D都是r1的候选码,因此符合BC范式

③考察r2,r2中我们发现A->E是成立的,但是A在r2中不是候选码,因为没有函数依赖表明A->F

④对于A->E,分解r2,分解得到r3(A,E),r4(A,F)

⑤考察r1,r3,r4,均符合BCNF,分解结束

综上所述,分解得到的结果为r={ABCD,AE,AF}

f.你可以基于最小覆盖来分解得到相同的BCNF吗?

可以尝试一下,首先同样初始化r={ABCDEF}

正则覆盖是Fc={A->BC,B->DE,D->A}

①对于A->BC,将A看作a,把BC看作b,那么就得到r1(A,B,C)和r2(ADEF)

②考察r1,r1中只有A->BC是成立的,因此r1符合BCNF

③考察r2,r2中有AF是候选码,但是D->A是成立的,因此基于此分解

r3(D,A),r4(D,E,F)

④考察r3,符合BCNF

⑤考察r4,通过逻辑蕴含的关系,可以知道有函数依赖D->A、A->BC、A->B、B->DE,因此D->DE,也就是D->DE,因此r4不符合BCNF,继续分解,这时候D->E

⑥分解r4,r5(D,E),r6(D,F)

⑦最终分解得到的关系模式为r={ABC,DA,DE,DF}

所以这时候不能够得到与原来一样的分解模式

如果想要得到与原来一样的分解模式,那么需要基于最小覆盖推断出原来的覆盖,才能得到相同的BCNF