数据库范式与关系模式示例.docx

数据库范式与关系模式示例.docx

《数据库范式与关系模式示例.docx》由会员分享，可在线阅读，更多相关《数据库范式与关系模式示例.docx（30页珍藏版）》请在冰点文库上搜索。

数据库范式与关系模式示例

第七章补充讲义

亠、范式举例

例1:

已知R,请问R为几范式?

零件号

单价

P1

25

P2

8

P3

25

P4

9

BCNF。

（25改成15还是BCNF如：

课程号与学号）

例2:

已知R,请问R为几范式?

材料号

材料名

生产厂

M1

线材

武汉

M2

型材

武汉

M3

板材

广东

M4

型材

武汉

2NF。

有部分依赖

例3:

已知R,请问R为几范式?

A

D

E

A1

D1

E2

A2

D6

E2

A3

D4

E3

A4

D4

E4

BCNF。

例4:

R（X,Y,Z）,F={XY->Z},R为几范式?

BCNF。

例5:

R（X,Y,Z）,F={Y->Z,XZ->Y},R为几范式?

3NF。

R的候选码为{XZ,XY}（R中所有属性都是主属性，无传递依赖）

、求闭包

数据库设计人员在对实际应用问题调查中，得到的结论往往是零散的、不规范的（直观

问题好办，复杂问题难办了），所以，这对分析数据模型，达到规范化设计要求，还有差距，为此，从规范数据依赖集合的角度入手，找到正确分析数据模型的方法，以确定关系模式的

规范化程度。

例1.已知关系模式R（U、F），其中，U={A,B,C,D,E};F={ABC,BD,ECB,ACB},求（AB）f.

解：

设X（0）=AB

1计算X⑴，在F中找出左边为AB子集的FD,其结果是：

ABC,BD

•••X⑴=X（0）UB=ABUCD=ABCD显然，X⑴工X⑼

2计算X⑵在F中找出左边为ABCD子集的FD,其结果是：

CE,ACB

（2）⑴

（2）

•X=XUB=ABCDUBE=ABCDE显然，X=U

所以，（AB）+f=ABCDE.（等于U，所以AB是唯一候选关键字）

例2•设有关系模式R（U、F）,其中U={A,B,C,D,E,l};F={AD,ABE,BE,CDI,EC},计算

+

（AE）

解：

令X={AE},X（0）=AE

①在F中找出左边是AE子集的FD,其结果是：

AD,EC

•X

（1）=X（0）UB=X（0）UDC=ACDE显然，X⑴工X（0）

①在F中找出左边是ACDE子集的FD,其结果是：

CDI

（2）⑴亠

•X=XUI=ACDEI

显然，X

（2）工X⑴，但F中未用过的函数依赖的左边属性已含有X⑵的子集，所以不必

再计算下去，即（AE）+=ACDEI.

因为，x（3）=x

（2）,所以，算法结束。

三、求最小依赖集

最小依赖集是对函数依赖集合进行规范的结果，这样才能对一般关系模式进行准确分

析。

例1.设函数依赖集F={ABCE,AC,GPB,EPA,CDEP,HBP,DHG,ABCPG},求与F等价的最小函数依赖集。

解：

①将F中依赖右部属性单一化:

F1=AB、ABE

HBPAC

DHGPB

DGEPA

ABCPCDEP

ABCG

②由于有AC,所以ABC为多余成份:

所以F2=

久BE

AC

GPB

EPA

jCDEP

HBP

DH

DG

ABCP

ABCG/

Fmin=F2为最小函数依赖集。

即

Fmin={ABE,HBP,AC,DH,GPB,D

G,

EPA,ABCP,CDEP,ABCG}.

例2.已知F={AB,BA,B

C,AC,CA},求Fmin.

解:

②F仁

2）Fmin仁

Fmin2=

已知F={AC,CA,BAC,DAC}，求Fmin。

解：

②将F中依赖的右部属性单一化:

F1=

BA

CA

BC

DCJ

②由于BA,AC所以BC是多余成份。

又由于DA,AC,所以DC是多余成份。

②经过分析认为F2中无多余依赖，则:

所以F2=

"AC

CA”

.BA

DA/

因为F2中所有依赖的左部都是单属性，所以不存在依赖左部的有多余属性。

所以FminACCA、

BADA

VJ

即Fmin={AC,CA,BA,DA}.

设有关系模式R（U,F）其中：

U={E,F,G,H},F={E小依赖集。

G,GE,FEG,HEG,FHE}求F的最

解：

①将F中依赖右部属性单一化:

F1=「EGHE，

GEHG

FEFH\—E

lFG丿

HE,而是，F后面加一个H和不加一样）

r

E

G

H

E

G

E

H

G

F

E

F

G

丿

F

E和F

G以及

H

⑦由于有F

所以F2=

③由于F2中,

E,FHE为多余成份：

（不是因为有

E和H

G之一为多余，则:

Fmin1={EG,G

Fmin2={EG,G

E,FG,HG}

E,FE,HE}Fmin3,Fmin4同理。

四、求候选码

1.候选关键字求解理论

对于给定的关系R（A1,A2,…,An）和函数依赖集F,可将其属性分为四类:

L类：

仅出现在F的函数依赖左部的属性

R类：

仅出现在F的函数依赖右部的属性

N类：

在F的函数依赖左右两边均未出现的属性

LR类：

在F的函数依赖左右两边均出现的属性

定理1:

对于给定的关系模式R及其函数依赖集F,若X（X€R）是L类属性，则X必为R的任一候选关键字成员。

推论1:

对于给定的关系模式R及其函数依赖集F,若X（X€R）是L类属性，且X包含了R的全部属性，贝UX必为R的唯一候选关键字。

定理2:

对于给定的关系模式R及其函数依赖集F,若X（X€R）是R类属性，则X不在任何候选关键字中。

定理3:

设有关系模式R及其函数依赖集F,若X是R的N类属性，则X必包含在R的任一候选关键字中。

推论2:

对于给定的关系模式R及其函数依赖集F,若X是R的N类和L类组成的属性集，且X+包含了R的全部属性，则X必为R的唯一候选关键字。

2.单属性依赖集图论求解法（多属性不行）

I：

关系模式R,R的单属性函数依赖集F。

O:

R的所有候选关键字。

算法：

1求F的最小依赖集Fmin。

2构造FDG（函数依赖图）。

◎从图中找出关键属性集X（X可为空）。

（可查看G中有无独立回路，若无则输出X即为R的唯一候选关键字，转O6，若有，则转

㈤。

◎从各独立回路中各取一结点对应的属性与X组合成一候选关键字，并重复这一过程取

尽所有可解的组合，即为R的全部候选关键字。

◎结束。

3•多属性依赖集候选关键字求解法

I：

关系模式R及其函数依赖集F。

O:

R的所有候选关键字。

算法：

①将R的所有属性分为L,R,N和LR四类，并令X代表L,N两类，Y代表LR类。

3求X+，若X包含了R的全部属性，则X即为R的唯一候选关键字，转O5，否则，转©。

◎在Y中取一属性A,求（XA）+.若它包含了R的全部属性，则转O4，否则，调换一属性反复进行这一过程，直到试完所有Y中的属性。

◎若已找出所有候选关键字，则转O5，否则在Y中依次取2个，3个…，求它们的属性闭包，直到其闭包包含R的全部属性。

◎停止,输出结果。

例仁设R=（O,B,I,S,Q,D）,F={SD,D

S,IB,BI,BO,O

B}求R的所有候选关键字。

解:

1）Fmin={S

D,D

S,IB,BI,BO,OB}.

◎构造FDG.

③关键属性集{Q}.

）

◎有两个独立回路，SDS,IBOBI.

所以R的所有候选关键字为：

QSI,QSB,QSO,QDI,QDB,QDO.

例2.设R={X,Y,Z},F={XY,YX},求R的所有候选关键字。

解：

（^Fmin={XY,YX}。

②构造FDG

关键属性{Z}.

4有1个独立回路，

1）.候选关键字个数=各独立回路中结点个数乘积=2（1个回路，2个结点）。

2）.候选关键字所含属性个数=关键属性个数+独立回路个数=1+1=2。

所以R的所有候选关键字为：

ZX,ZY.

例3.设有关系模式R（A,B,C,D）,其函数依赖集F={DB,BD,ADB,ACD},求R的所有候

选关键字。

解：

经考虑F发现，A,C两属性是L类属性，由定理知，AC必是R的一候选关键字字

成员。

又因（AC）+=ABCD,所以AC是R的唯一候选关键字。

例4.设有关系模式R（A,B,C,D,E,P）,F={AD,ED,DB,BCD,DCA},求R的所有候选关键字。

解：

经考察发现，C,E两属性是L类属性，故C,E必在R的任何候选关键字中，又P

是N类属性，故P也必在R的任何候选关键字中。

又因（CEP）+=ABCDEP所以CEP是R的唯一候选关键字。

五、模式分解

对存在数据冗余、插入异常、删除异常问题的关系模式，应采取将一个关系

模式分解为多个关系模式的方法进行处理。

在分解处理中会涉及一些新问题，为使分解后的模式保持原模式所满足的特性，要求分解处理具有无损联接性和保持函数依赖性。

即分解后的关系模式子集，应能通过自然连接运算恢复原状。

1、关系模式规范化时一般应遵循以下原则：

（1）关系模式进行无损连接分解。

关系模式分解过程中数据不能丢失或增加，必须把全局关系模式中的所有数据无损地分解到各个子关系模式中，以保证数据的完整性。

（2）保持原来模型的函数依赖关系。

因为这些函数依赖关系是数据模型反映的客观事物的固有属性，一般是不能舍弃的。

（3）合理选择规范化程度。

考虑到存取效率，低级模式造成的冗余度很

大，既浪费了存储空间，又影响了数据的一致性，因此希望一个子模式的属性越少越好，即取高级范式；若考虑到查询效率，低级范式又比高级范式好，此时连接运算的代价较小，这是一对矛盾，所以应根据情况，合理选择规范化程度。

2、对模式分解的两个基本要求：

模式分解可以提高关系模式的规范化程度，但是必须考虑如下问题：

1避免信息丢失：

简单的说，就是模式R分解为R1，R2，…，Rn后，将R1,R2,…Rn自然连接还应该等于模式R。

这就是“无损失联接”准则。

2避免数据关系丢失：

简单地说，就是模式R分解为R1,R2，…，Rn后，函数依赖集合F也被对应分解为F1,F2,…，Fn，应满足F与各Fi（i=1，2,…n）的并集等价，即满足F+=（UFi）+。

这就是“保持函数依赖”准则。

关系模式的规范化过程是通过对关系模式的分解来实现的，但是把低一级

的关系模式分解为若干个高一级关系模式的方法并不是唯一的。

在这些分解方

法中，只有能够保证分解后的关系模式与原关系模式等价的方法才有意义。

3、关系模式分解的三个定义：

（1）分解具有“无损联接性”。

（2）分解要“保持函数依赖”。

（3）分解既要“保持函数依赖性”，又要具有“无损连接性”。

规范化理论提供了一套完整的模式分解算法，按照这套算法可以做到：

•若要求分解具有无损联接性，那么模式分解一定能够达到4NF。

•若要求分解保持函数依赖，那么模式分解一定能够达到3NF，但不一定能

达至UBCNF。

•若要求分解具有无损联接性又保持函数依赖，则模式分解一定能够达到

3NF，但不一定能达到BCNF。

我们希望最好能够既要“保持函数依赖”，又要具有“无损联接性”，从上面结论可以看到只能达到3NF，至于能否达到BCNF或更高，要看具体情况。

这就是在数据库设计中一般采用“基于3NF的数据设计方法”的根本原因。

4、模式设计方法的原则：

关系模式R相对于函数依赖集F分解成p={R1,R2,…Rk},应具有以下特性：

（1）p中每个关系模式Ri上应有某种范式性质（3NF或BCNF）

（2）无损联接

（3）保持函数依赖集

（4）最小性（p中模式个数应最少和模式中属性总数应最少）

一个好的设计方法应符合下列3个原则：

表达性，分离性，最小冗余性。

5、模式分解的算法：

算法一：

把关系模式无损分解成BCNF

输入：

关系模式R和函数依赖集F

输出：

R的一个无损分解p={R1,R2,…，Rk}

方法：

设关系模式R（U,F）

（1）置初值:

p={R}。

（2）对于关系模式R的分解p（初始时p={R}）,如果p中有一个关系模式Ri相对于nRi（F）不是BCNFo由定义可知，Ri中存在一个非平凡FDXY,有X不包含码。

此时把R分解成XY和Ri-Y两个模式。

重复上述过程，一直到p中每一个模式都是BCNFo

（3）算法结束，p就是分解结果。

例1:

R（U,F）,U=ABCDEF={ABC,BD,DE}码是AB。

分解过程如下：

（1）先分出DE,p={R1（ABCD）,R2（DE）}

（2）再从R1中分出BD,p={R1（ABC）,R2（DE）,R3（BD）}

（3）R1,R2,R3都属于BCNF,分解完成。

例2:

设有关系模式R（U,F）,其中:

U={C,T,H,R,S,G}F={CSG,CT,THR,HRC,HSR}

将其无损联接地分解为BCNF。

解：

R上只有一个侯选键HS。

（1）令p={CTHRSG}

（2）p中的模式不是BCNF。

（3）考虑CSG,这个函数依赖不满足BCNF条件（CS不包含侯选键

HS）,将CTHRSG分解为CSG和CTHRS计算nCSG（F）和nCTHRS（F）,前者的最小覆盖是：

CSG;后者的最小覆盖是：

CT,HRC,THR,HSR。

模式CTHRS的侯选关键字是HS。

CSG已是BCNF,进一步分解CTHRS选择CT,把CTHRS分解成CT和

CHRS,计算nCT（F）和nCHRS（F）,前者的最小覆盖是：

CT;后者的最小覆盖是：

HCR,HSR,HRC。

模式CHRS的侯选关键字是HS。

CT已是BCNF,再分解CHRS选择HCR,把CHRS分解成CHR和CHS,

计算nCHR（F）和nCHS（F）,前者的最小覆盖是：

CHR,HRC;后者的最小覆盖是：

HSC。

这时CHR和CHS均为BCNFo

（4）p={CSG,CT,CHR,CHS}（HSR,HSHRHRC=>HSC）算法二：

把一个关系模式分解为3NF，使它具有依赖保持性。

输入：

关系模式R和R的最小依赖集Fmin。

输出：

R的一个分解p={R1,R2,…Rk},Ri为3NF（i=1,…，k）,p具有依赖保持性。

达到3NF保持函数依赖分解的方法：

设关系模式R（U,F）:

（1）将F化为最小函数依赖集，令F=Fmin

（2）把在F中不出现的属性从U中去掉，属性集合仍然为U。

（3）对照F中的函数依赖集，将所有函数依赖左端相同的划为一组，相应的

右端以及函数依赖均归入该组。

（4）这些分组就是分解后的模式组成。

（5）这种分解方法得到的就是达到3NF且保持函数依赖的分解。

例1：

F={B—>G,CEB,CA,CEG,BD,CD},码是CE,分解成三个模式。

R1:

U仁BDG,F1={BG,BD}

R2:

U2=ACD,F2={CA,CD}

R3:

U3=BCEG,F3={CEB,CEG}

分解后，R1，R2，R3均达到3NF，且分解符合保持函数依赖的规则。

例2:

设有关系模式R（U，F）,其中：

U={C，T，H，R，S，G}

F={CSG,CT,THR,HRC,HSR},将其保持依赖性分解为3NF。

解：

（1）求出F的最小依赖集，Fmin={CSG,CT,THR,HRC,HSR}。

（2）无。

（3）R1：

U1=CSG,F仁{CSG}

U2=CT，F2={CT}

U3=THR，F3={THR}

U4=HRC，F4={HRC}

U5=HSR，F5={HSR}

（4）p={CSG,CT,THR,HRC,HSR}

算法三：

把一个关系模式分解为3NF，使它既具有无损联接性又具有依赖保持性。

设关系模式R（U，F）：

①对于关系模式R和R上成立的FD集F,先求出F的最小依赖集，然后再把最小依赖集中那些左部相同的FD用合并性合并起来。

②对最小依赖集中，每个FDX丫去构成一个模式XY

3在构成的模式集中，如果每个模式都不包含R的候选键，那么把候选

键作为一个模式放入模式集中。

这样得到的模式集是关系模式R的一个分解，并且这个分界既是无损分解，又能保持FD。

检验无损联接性的方法：

输入：

关系模式R（A1，A2，…，An），它的函数依赖集F以及分解p={R1，R2,…，Rk}。

输出：

确定p是否具有无损联接性。

设关系模式R（U，F）:

（1）构造一个k行n列的表，若i行对应于关系模式Ri，第j列对应于属性Aj。

如果Aj€Ri，则在第i行第j列上放符号aj，否则放符号bij。

（2）逐个检查F中的每一个函数依赖，并修改表中的元素。

其方法如下：

取F中一个函数依赖X—>Y，在X的分量中寻找相同的行，然后将这些行中Y的分量改为相同的符号，如果其中有aj，则将bij改为aj；若其中无aj，则改为bij。

这样反复进行，如果发现某一行变成了al，a2，…，ak，则分解p具有无损联接性；如果F中所有函数依赖都不能再修改表中的内容，且没有发现这样的行，则分解p不具有无损联接性。

例1:

对于上例的关系模式R（U,F），将其无损联接性和依赖保持性分解为3NF。

解：

依据算法：

（1）由上例求出依赖保持性分解为：

p={CSG,CT,THR,HRC,HSR}

（2）判断其无损联接性如下图所示

Ri

C

T

H

R

S

G

CSG

al

b12

b13

b14

a5

a6

CT

al

a2

b23

b24

b25

b26

THR

b31

a2

a3

a4

b35

b36

HRC

al

b42

a3

a4

b45

b46

HSR

b51

b52

a3

a4

a5

b56

（在已知F={CSG,CT,THR,HRC,HSR}

1看CS上相同的，再改G的成分一一没有

看C上相同的，再改T的成分一一2个a2①

看TH上相同的，再改R的成分一一没有

看HR上相同的，再改C的成分一一2个al①

看HS上相同的，再改R的成分一一没有

2再看CS上相同的，再改G的成分一一有一个a6②

看C上相同的，再改T的成分一一有一个a2②，其它未发生变化，略）

Ri

C

T

H

R

S

G

CSG

al

a2①

b13

b14

a5

a6

CT

al

a2

b23

b24

b25

b26

THR

al①

a2

a3

a4

b35

b36

HRC

al

a2①

a3

a4

b45

b46

HSR

al①

a2②

a3

a4

a5

a6②

Ri

C

T

H

R

S

G

CSG

al

a2

b13

b14

a5

a6

CT

al

a2

b23

b24

b25

b26

THR

b31

a2

a3

a4

b35

b36

HRC

a1

a2

a3

a4

b45

b46

HSR

a1

a2

a3

a4

a5

a6

（3）不执行。

（4）由于表中有一行从a1,a2,…,a6全满，由此可知，p具有无损联接性,

输出p={CSG,CT,THR,HRC,HSR}

例2:

已知，U={A,B,C,D},F={A—>B,A-->C,BC—>D,D-->A}

判断一个分解p={AB,AC,BCD,DA}是否具有无损联接性。

Ri

A

B

C

D

AB

a1

a2

b13

b14

AC

a1

b22

a3

a4

BCD

b41

a2

a3

a4

DA

a1

b42

b43

a4

由于，A—>B,b22a2,b42a2

BC—>D,b14a4

D-->A,b41al

Ri

A

B

C

D

AB

al

a2

a3

a4

AC

al

a2

a3

a4

BCD

al

a2

a3

a4

DA

al

a2

a3

a4

所以，p={AB,AD,BCD,DA}具有无损联接性。

例3:

设有关系模式R（U,F）,其中：

U={A，C，B}，F={A—>B,C-->B}

判断一个分解p={AC，BC}是否具有无损联接性。

解：

p的无损联接性判断结果表如下所示：

由此判断具有无损联接性。

Ri

A

B

C

AC

al

b12

a3

BC

b21

a2

a3

由于，A—>B没有变化,C-->B

Ri

A

B

C

AC

al

a2

a3

BC

b21

a2

a3

所以，p={AC,BC}具有无损联接性。

例4:

设有关系模式R（A,,B,C,D）,其上的函数依赖集:

F={A—C,C—A,B—AC,D^AC}

（1）计算（AD几

（2）求F的最小等价依赖集Fm。

（3）求R的关键字。

（4）将R分解使其满足BCNF且无损连接性。

（5）将R分解成满足3NF并具有无损连接性与保持依赖性。

解：

（1）令X={AD},,X（0）=AD,X

（1）=ACD,X

（2）=ACD，故（AD）+=ACD

（2）将F中的依赖右部属性单一化：

A—C

Fi="B—A

C—A

D—A

在Fi中去掉多余的函数依赖：

TBfA,AfCBfC是多余的。

又vDfA,AfC二DfC是多余的

AfC

F2=BfA

CfA

DfA

函数依赖集的最小集不是惟一的，本题中还可以有其他答案。

vF2中所有依赖的左部却是单属性，二不存在依赖左部有多余的属性。

AfC

F/=BfA

CfA

—

DfA

（3）vBD在F中所有函数依赖的右部均未出现，•••候选关键字中一定包含BD,而（BD）+=ABCD,因此，BD是R惟一的候选关键字。

（4）考虑AfC，vAC不是BCNF（AC不包含候选关键字BD