模式分解、最小函数依赖集

前端之家收集整理的这篇文章主要介绍了模式分解、最小函数依赖集前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

函数依赖的公理系统:

设有关系模式R(U),X,Y,Z,W均是U的子集,F是R上只涉及到U中属性函数依赖集,推理规则如下:

  • 自反律:如果YXU,则X→Y在R上成立。

  • 增广律:如果X→Y为F所蕴涵,ZU,则XZ→YZ在R上成立。(XZ表示X∪Z,下同)

  • 传递律:如果X→Y和Y→Z在R上成立,则X→Z在R上成立。
    以上三条为Armstrong公理系统

  • 合并律:如果X→Y和X→Z成立,那么X→YZ成立。

  • 伪传递律:如果X→Y和WY→Z成立,那么WX→Z成立。

  • 分解律:如果X→Y和ZY成立,那么X→Z成立。
    这三条为引理

注意:

  • 函数依赖推理规则系统(自反律、增广律和传递律)是完备的。

  • 由自反律所得到的函数依赖均是平凡的函数依赖。

模式分解的几个重要事实:

  • 若只要求分解具有“无损连接性”,一定可以达到4NF;
  • 若要求分解要“保持函数依赖”,可以达到3NF,但不一定能达到BCNF;
  • 若要求分解既要“保持函数依赖”,又要具有“无损连接性”,可以达到3NF,但不一定能达到BCNF;

试分析下列分解是否具有无损联接和保持函数依赖的特点:

设R(ABC),F1={A→B} 在R上成立,ρ1={AB,AC}。

首先,检查是否具有无损联接特点:
第1种解法--算法4.2:

A

B

C

AB

a1

a2

b13

AC

a1

b22

a3

A

B

C

a1

a2

b13

a1

a2

a3

(1) 构造表

(2)根据A→B进行处理


结果第二行全是a行,因此分解是无损联接分解

第2种解法:(定理4.8)
  R1(AB)∩R2(AC)=A
  R2- R1=B
  ∵A→B,∴该分解是无损联接分解。

然后,检查分解是否保持函数依赖
  πR1(F1)={A→B,以及按自反率推出的一些函数依赖}
  πR2(F1)={按自反率推出的一些函数依赖}
  F1被πR1(F1)所蕴涵,所以该分解保持函数依赖。

5.4.3保持函数依赖的模式分解

一、转换成3NF的保持函数依赖的分解

算法

ρ={R1<U1,F1>,R2<U2,F2>,...,Rk<Uk,Fk>}是关系模式R<U,F>的一个分解,U={A1,A2,An}F={FD1,FD2,FDp},并设F是一个最小依赖集,记FDiXiAlj,其步骤如下:

R<U,F>函数依赖集F进行极小化处理(处理后的结果仍记为F);

找出不在F中出现的属性,将这样的属性构成一个关系模式。把这些属性U中去掉,剩余的属性仍记为U

若有XAF,且XA=U,则ρ={R},算法终止;

否则,对F按具有相同左部的原则分组(假定分为k),每一组函数依赖Fi所涉及的全部属性形成一个属性Ui。若UiUj(ij),就去掉Ui。由于经过了步骤②,故

,于是构成的一个保持函数依赖的分解。并且,每个Ri(Ui,Fi)均属于3NF且保持函数依赖。

1:关系模式R<U,F>,其中U={C,T,H,I,S,G}F={CSG,CT,THI,HIC,HSI},将其分解成3NF并保持函数依赖。

解:根据算法进行求解

()计算F的最小函数依赖集

利用分解规则,将所有的函数依赖变成右边都是单个属性函数依赖。由于F的所有函数依赖的右边都是单个属性,故不用分解。

去掉F中多余的函数依赖

A.设CSG为冗余的函数依赖,则去掉CSG,得

F1={CT,HSI}

计算(CS)F1+

X(0)=CS

计算X(1):扫描F1中各个函数依赖,找到左部为CSCS子集的函数依赖,找到一个CT函数依赖。故有X(1)=X(0)T=CST

计算X(2):扫描F1中的各个函数依赖,找到左部为CSTCST子集的函数依赖,没有找到任何函数依赖。故有X(2)=X(1)。算法终止。

(CS)F1+= CST不包含GCSG不是冗余的函数依赖,不能从F1中去掉。

B.设CT为冗余的函数依赖,则去掉CT,得

F2={CSG,HSI}

计算(C)F2+

X(0)=C

计算X(1):扫描F2中的各个函数依赖,没有找到左部为C函数依赖。故有X(1)=X(0)。算法终止。故CT不是冗余的函数依赖,不能从F2中去掉。

C.设THI为冗余的函数依赖,则去掉THI,得

F3={CSG,HSI}

计算(TH)F3+

X(0)=TH

计算X(1):扫描F3中的各个函数依赖,没有找到左部为THTH子集的函数依赖。故有X(1)=X(0)。算法终止。故THI不是冗余的函数依赖,不能从F3中去掉。

D.设HIC为冗余的函数依赖,则去掉HIC,得

F4={CSG,HSI}

计算(HI)F4+

X(0)=HI

计算X(1):扫描F4中的各个函数依赖,没有找到左部为HIHI子集的函数依赖。故有X(1)=X(0)。算法终止。故HIC不是冗余的函数依赖,不能从F4中去掉。

E.设HSI为冗余的函数依赖,则去掉HSI,得

F5={CSG,HIC}

计算(HS)F5+

X(0)=HS

计算X(1):扫描F5中的各个函数依赖,没有找到左部为HSHS子集的函数依赖。故有X(1)=X(0)。算法终止。故HSI不是冗余的函数依赖,不能从F5中去掉。即:F5={CSG,HSI}

去掉F5中各函数依赖左边多余的属性(只检查左部不是单个属性函数依赖)

没有发现左边有多余属性函数依赖。故最小函数依赖集为:

F={CSG,HSI}

()由于R中的所有属性均在F中都出现,所以转下一步。

()F按具有相同左部的原则分为:R1=CSGR2=CTR3=THIR4=HICR5=HSI。所以ρ={R1(CSG),R2(CT),R3(THI),R4(HIC),R5(HSI)}

二、转换成3NF的保持无损连接和函数依赖的分解

算法

输入关系模式RR的最小函数依赖集F

输出R<U,F>的一个分解ρ={R1<U1,Fk>}Ri3NF,且ρ具有无损连接又保持函数依赖的分解。

步骤

根据算法1求出保持函数依赖的分解ρ={R1,R2,Rk}

判断分解ρ是否具有无损连接性,若有,转④

令ρ=ρ∪{X},其中XR的候选关键字(候选码);

输出ρ

2:关系模式R<U,F>,其中:U={C,HSI},将其分解成3NF并保持无损连接和函数依赖。

解:

根据例1,得到3NF并保持函数依赖的分解如下:

ρ={R1(CSG),R5(HSI)}

判断是否是无损连接

构造一个初始的二维表,若“属性”属于“模式”中的属性,则填aj,否则填bij

根据CT,对上表的处理结果如下表。

根据HIC,对上表的处理结果如下表。

根据CSG,对上表的处理结果如下表。

根据CT,对上表的处理结果如下表。

通过上述的修改,使第五行成为a1a2a3a4a5a6,则算法终止。且分解具有无损连接性。

三、转换成BCNF的保持无损连接的分解

算法

输入关系模式RR函数依赖集F

输出R<U,Fk>}RiBCNF,且ρ具有无损连接的分解。

步骤

令ρ={R},根据算法1求出保持函数依赖的分解ρ={R1,Rk}

若ρ中的所有模式都是BCNF,转④

若ρ中有一个关系模式Ri不是BCNF,则Ri中必能找到一个函数依赖XA,且X不是Ri的候选码,且A不属于X,设Ri1(XA)Ri2(Ri-A),用分解{Ri1,Ri2}代替Ri,转②;

输出ρ

3:关系模式R<U,HSI},将其分解成BCNF并保持无损连接。

解:

令ρ={R(U,F)}

ρ中不是所有的模式都是BCNF,转入下一步。

分解RR上的候选关键字为HS(因为所有函数依赖的右边没有HS)。考虑CSG函数依赖不满足BCNF条件(因CS不包含候选键HS),将其分解成R1(CSG)R2(CTHIS)。计算R1R2的最小函数依赖集分别为:F1={CSG}F2={CT,HSI}

分解R2R2上的候选关键字为HS。考虑CT函数依赖不满足BCNF条件,将其分解成R21(CT)R22(CHIS)。计算R21R22的最小函数依赖集分别为:F21={CT}F22={CHI,HSI}。其中CHI是由于R22中没有属性TCT,THI

分解R22R22上的候选关键字为HS。考虑CHI函数依赖不满足BCNF条件,将其分解成R221(CHI)R222(CHS)。计算R221R222的最小函数依赖集分别为:F221={CHI,HIC}F222={HSC}。其中HSC是由于R222中没有属性IHSI,HIC

由于R221上的候选关键字为H,而F221中的所有函数依赖满足BCNF条件。由于R222上的候选关键字为HS,而F222中的所有函数依赖满足BCNF条件。故R可以分解为无损连接性的BCNF如:ρ={R1(CSG),R21(CT),R221(CHI),R222(CHS)}

4:关系模式R<U,F>,其中:U={A,B,C,D,E}F={AC,CD,BC,DEC,CEA},将其分解成BCNF并保持无损连接。

解:

令ρ={R(U,F)}

ρ中不是所有的模式都是BCNF,转入下一步。

分解RR上的候选关键字为BE(因为所有函数依赖的右边没有BE)。考虑AC函数依赖不满足BCNF条件(因A不包含候选键BE),将其分解成R1(AC)R2(ABDE)。计算R1R2的最小函数依赖集分别为:F1={AC}F2={BD,DED,BEA}。其中BD是由于R2中没有属性CBC,CDDED是由于R2中没有属性CDEC,CDBEA是由于R2中没有属性CBC,CEA。又由于DED是蕴含关系,可以去掉,故F2={BD,BEA}

分解R2R2上的候选关键字为BE。考虑BD函数依赖不满足BCNF条件,将其分解成R21(BD)R22(ABE)。计算R21R22的最小函数依赖集分别为:F21={BD}F22={BEA}

由于R22上的候选关键字为BE,而F22中的所有函数依赖满足BCNF条件。故R可以分解为无损连接性的BCNF如:ρ={R1(AC),R21(BD),R22(ABE)}

四、转换成4NF的保持无损连接的分解

算法

输入关系模式RR函数依赖集F

输出R<U,Fk>}Ri4NF,且ρ具有无损连接的分解。

步骤

令ρ={R},根据算法1求出保持函数依赖的分解ρ={R1,Rk}

若ρ中的所有模式都是4NF,转④

若ρ中有一个关系模式Ri不是4NF,则Ri中必能找到一个函数依赖X→→A,且X不是Ri的候选码,且A-X≠φ,XARi,令Z=A-X,由分解规则得出X→→Z。令Ri1(XZ)Ri2(Ri-Z),用分解{Ri1,Ri2}代替Ri,由于(Ri1Ri2)→→(Ri1-Ri2),所以分解具有无损连接性,转②;

输出ρ

①②③④⑤⑥⑦⑧

原文链接:https://www.f2er.com/javaschema/287526.html

猜你在找的设计模式相关文章