模式分解、最小函数依赖集
|
函数依赖的公理系统： 设有关系模式R(U)，X，Y，Z，W均是U的子集，F是R上只涉及到U中属性的函数依赖集，推理规则如下：
注意：
模式分解的几个重要事实：
试分析下列分解是否具有无损联接和保持函数依赖的特点： 设R(ABC)，F1={A→B} 在R上成立，ρ1={AB,AC}。
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是一个最小依赖集，记FDi为Xi→Alj，其步骤如下： ①对R<U,F>的函数依赖集F进行极小化处理（处理后的结果仍记为F）； ②找出不在F中出现的属性，将这样的属性构成一个关系模式。把这些属性从U中去掉，剩余的属性仍记为U； ③若有X→AF，且XA=U，则ρ={R}，算法终止； ④否则，对F按具有相同左部的原则分组(假定分为k组)，每一组函数依赖Fi所涉及的全部属性形成一个属性集Ui。若UiUj(i≠j)，就去掉Ui。由于经过了步骤②，故 ，于是构成的一个保持函数依赖的分解。并且，每个Ri(Ui,Fi)均属于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(0)=CS 计算X(1)：扫描F1中各个函数依赖，找到左部为CS或CS子集的函数依赖，找到一个C→T函数依赖。故有X(1)=X(0)∪T=CST。 计算X(2)：扫描F1中的各个函数依赖，找到左部为CST或CST子集的函数依赖，没有找到任何函数依赖。故有X(2)=X(1)。算法终止。 (CS)F1+= CST不包含G，故CS→G不是冗余的函数依赖，不能从F1中去掉。 B．设C→T为冗余的函数依赖，则去掉C→T，得： F2={CS→G,HS→I} 计算(C)F2+： 设X(0)=C 计算X(1)：扫描F2中的各个函数依赖，没有找到左部为C的函数依赖。故有X(1)=X(0)。算法终止。故C→T不是冗余的函数依赖，不能从F2中去掉。 C．设TH→I为冗余的函数依赖，则去掉TH→I，得： F3={CS→G,HS→I} 计算(TH)F3+： 设X(0)=TH 计算X(1)：扫描F3中的各个函数依赖，没有找到左部为TH或TH子集的函数依赖。故有X(1)=X(0)。算法终止。故TH→I不是冗余的函数依赖，不能从F3中去掉。 D．设HI→C为冗余的函数依赖，则去掉HI→C，得： F4={CS→G,HS→I} 计算(HI)F4+： 设X(0)=HI 计算X(1)：扫描F4中的各个函数依赖，没有找到左部为HI或HI子集的函数依赖。故有X(1)=X(0)。算法终止。故HI→C不是冗余的函数依赖，不能从F4中去掉。 E．设HS→I为冗余的函数依赖，则去掉HS→I，得： F5={CS→G,HI→C} 计算(HS)F5+： 设X(0)=HS 计算X(1)：扫描F5中的各个函数依赖，没有找到左部为HS或HS子集的函数依赖。故有X(1)=X(0)。算法终止。故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>的一个分解ρ={R1<U1,Fk>}，Ri为3NF，且ρ具有无损连接又保持函数依赖的分解。 步骤 ①根据算法1求出保持函数依赖的分解ρ={R1,R2,Rk} ②判断分解ρ是否具有无损连接性，若有，转④ ③令ρ=ρ∪{X}，其中X是R的候选关键字（候选码）； ④输出ρ
例2：关系模式R<U,F>，其中：U={C,HS→I}，将其分解成3NF并保持无损连接和函数依赖。 解： ①根据例1，得到3NF并保持函数依赖的分解如下： ρ={R1(CSG),R5(HSI)}。 ②判断是否是无损连接 构造一个初始的二维表，若“属性”属于“模式”中的属性，则填aj，否则填bij。
根据C→T，对上表的处理结果如下表。
根据HI→C，对上表的处理结果如下表。
根据CS→G，对上表的处理结果如下表。
根据C→T，对上表的处理结果如下表。
通过上述的修改，使第五行成为a1a2a3a4a5a6，则算法终止。且分解具有无损连接性。
三、转换成BCNF的保持无损连接的分解算法： 输入关系模式R和R的函数依赖集F。 输出R<U,Fk>}，Ri为BCNF，且ρ具有无损连接的分解。 步骤 ①令ρ={R}，根据算法1求出保持函数依赖的分解ρ={R1,Rk} ②若ρ中的所有模式都是BCNF，转④ ③若ρ中有一个关系模式Ri不是BCNF，则Ri中必能找到一个函数依赖X→A，且X不是Ri的候选码，且A不属于X，设Ri1(XA)，Ri2(Ri-A)，用分解{Ri1,Ri2}代替Ri，转②； ④输出ρ
例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,Fk>}，Ri为4NF，且ρ具有无损连接的分解。 步骤 ①令ρ={R}，根据算法1求出保持函数依赖的分解ρ={R1,Rk} ②若ρ中的所有模式都是4NF，转④ ③若ρ中有一个关系模式Ri不是4NF，则Ri中必能找到一个函数依赖X→→A，且X不是Ri的候选码，且A-X≠φ，XA≠Ri，令Z=A-X，由分解规则得出X→→Z。令Ri1(XZ)，Ri2(Ri-Z)，用分解{Ri1,Ri2}代替Ri，由于(Ri1∩Ri2)→→(Ri1-Ri2)，所以分解具有无损连接性，转②； ④输出ρ
①②③④⑤⑥⑦⑧ （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |