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

函数依赖的公理系统： 设有关系模式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:

(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的保持函数依赖的分解

算法：

ρ={R₁<U₁,F₁>,R₂<U₂,F₂>,...,R_k<U_k,F_k>}是关系模式R<U,F>的一个分解，U={A₁,A₂,A_n}，F={FD₁,FD₂,FD_p}，并设F是一个最小依赖集，记FD_i为X_i→A_lj，其步骤如下：

①对R<U,F>的函数依赖集F进行极小化处理（处理后的结果仍记为F）；

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

③若有X→AF，且XA=U，则ρ={R}，算法终止；

④否则，对F按具有相同左部的原则分组(假定分为k组)，每一组函数依赖F_i所涉及的全部属性形成一个属性集U_i。若U_iU_j(i≠j)，就去掉U_i。由于经过了步骤②，故

，于是构成的一个保持函数依赖的分解。并且，每个R_i(U_i,F_i)均属于3NF且保持函数依赖。

例1：关系模式R<U,F>，其中U={C,T,H,I,S,G}，F={CS→G,C→T,TH→I,HI→C,HS→I}，将其分解成3NF并保持函数依赖。

解：根据算法进行求解

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

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

②去掉F中多余的函数依赖

A．设CS→G为冗余的函数依赖，则去掉CS→G，得：

F1={C→T,HS→I}

计算(CS)_F1⁺：

设X⁽⁰⁾=CS

计算X⁽¹⁾：扫描F1中各个函数依赖，找到左部为CS或CS子集的函数依赖，找到一个C→T函数依赖。故有X⁽¹⁾=X⁽⁰⁾∪T=CST。

计算X⁽²⁾：扫描F1中的各个函数依赖，找到左部为CST或CST子集的函数依赖，没有找到任何函数依赖。故有X⁽²⁾=X⁽¹⁾。算法终止。

(CS)_F1⁺= CST不包含G，故CS→G不是冗余的函数依赖，不能从F1中去掉。

B．设C→T为冗余的函数依赖，则去掉C→T，得：

F2={CS→G,HS→I}

计算(C)_F2⁺：

设X⁽⁰⁾=C

计算X⁽¹⁾：扫描F2中的各个函数依赖，没有找到左部为C的函数依赖。故有X⁽¹⁾=X⁽⁰⁾。算法终止。故C→T不是冗余的函数依赖，不能从F2中去掉。

C．设TH→I为冗余的函数依赖，则去掉TH→I，得：

F3={CS→G,HS→I}

计算(TH)_F3⁺：

设X⁽⁰⁾=TH

计算X⁽¹⁾：扫描F3中的各个函数依赖，没有找到左部为TH或TH子集的函数依赖。故有X⁽¹⁾=X⁽⁰⁾。算法终止。故TH→I不是冗余的函数依赖，不能从F3中去掉。

D．设HI→C为冗余的函数依赖，则去掉HI→C，得：

F4={CS→G,HS→I}

计算(HI)_F4⁺：

设X⁽⁰⁾=HI

计算X⁽¹⁾：扫描F4中的各个函数依赖，没有找到左部为HI或HI子集的函数依赖。故有X⁽¹⁾=X⁽⁰⁾。算法终止。故HI→C不是冗余的函数依赖，不能从F4中去掉。

E．设HS→I为冗余的函数依赖，则去掉HS→I，得：

F5={CS→G,HI→C}

计算(HS)_F5⁺：

设X⁽⁰⁾=HS

计算X⁽¹⁾：扫描F5中的各个函数依赖，没有找到左部为HS或HS子集的函数依赖。故有X⁽¹⁾=X⁽⁰⁾。算法终止。故HS→I不是冗余的函数依赖，不能从F5中去掉。即：F5={CS→G,HS→I}

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

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

F={CS→G,HS→I}

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

(三)对F按具有相同左部的原则分为：R1=CSG，R2=CT，R3=THI，R4=HIC，R5=HSI。所以ρ={R1(CSG),R2(CT),R3(THI),R4(HIC),R5(HSI)}。

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

算法：

输入关系模式R和R的最小函数依赖集F。

输出R<U,F>的一个分解ρ={R₁<U₁,F_k>}，R_i为3NF，且ρ具有无损连接又保持函数依赖的分解。

步骤

①根据算法1求出保持函数依赖的分解ρ={R₁,R₂,R_k}

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

③令ρ=ρ∪{X}，其中X是R的候选关键字（候选码）；

④输出ρ

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

解：

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

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

②判断是否是无损连接

构造一个初始的二维表，若“属性”属于“模式”中的属性，则填a_j，否则填b_ij。

根据C→T，对上表的处理结果如下表。

根据HI→C，对上表的处理结果如下表。

根据CS→G，对上表的处理结果如下表。

根据C→T，对上表的处理结果如下表。

通过上述的修改，使第五行成为a₁a₂a₃a₄a₅a₆，则算法终止。且分解具有无损连接性。

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

算法：

输入关系模式R和R的函数依赖集F。

输出R<U,F_k>}，R_i为BCNF，且ρ具有无损连接的分解。

步骤

①令ρ={R}，根据算法1求出保持函数依赖的分解ρ={R₁,R_k}

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

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

④输出ρ

例3：关系模式R<U,HS→I}，将其分解成BCNF并保持无损连接。

解：

①令ρ={R(U,F)}。

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

③分解R：R上的候选关键字为HS（因为所有函数依赖的右边没有HS）。考虑CS→G函数依赖不满足BCNF条件（因CS不包含候选键HS），将其分解成R1(CSG)、R2(CTHIS)。计算R1和R2的最小函数依赖集分别为：F1={CS→G}，F2={C→T,HS→I}。

分解R2：R2上的候选关键字为HS。考虑C→T函数依赖不满足BCNF条件，将其分解成R21(CT)、R22(CHIS)。计算R21和R22的最小函数依赖集分别为：F21={C→T}，F22={CH→I,HS→I}。其中CH→I是由于R22中没有属性T且C→T,TH→I。

分解R22：R22上的候选关键字为HS。考虑CH→I函数依赖不满足BCNF条件，将其分解成R221(CHI)、R222(CHS)。计算R221和R222的最小函数依赖集分别为：F221={CH→I,HI→C}，F222={HS→C}。其中HS→C是由于R222中没有属性I且HS→I,HI→C。

由于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={A→C,C→D,B→C,DE→C,CE→A}，将其分解成BCNF并保持无损连接。

解：

①令ρ={R(U,F)}。

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

③分解R：R上的候选关键字为BE（因为所有函数依赖的右边没有BE）。考虑A→C函数依赖不满足BCNF条件（因A不包含候选键BE），将其分解成R1(AC)、R2(ABDE)。计算R1和R2的最小函数依赖集分别为：F1={A→C}，F2={B→D,DE→D,BE→A}。其中B→D是由于R2中没有属性C且B→C,C→D；DE→D是由于R2中没有属性C且DE→C,C→D；BE→A是由于R2中没有属性C且B→C,CE→A。又由于DE→D是蕴含关系，可以去掉，故F2={B→D,BE→A}。

分解R2：R2上的候选关键字为BE。考虑B→D函数依赖不满足BCNF条件，将其分解成R21(BD)、R22(ABE)。计算R21和R22的最小函数依赖集分别为：F21={B→D}，F22={BE→A}。

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

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

算法：

输入关系模式R和R的函数依赖集F。

输出R<U,F_k>}，R_i为4NF，且ρ具有无损连接的分解。

步骤

①令ρ={R}，根据算法1求出保持函数依赖的分解ρ={R₁,R_k}

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

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

④输出ρ

①②③④⑤⑥⑦⑧

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!