规范化方法(数据库)

时间：2022-12-25 12:30:01 | 来源：信息时代

时间：2022-12-25 12:30:01 来源：信息时代

    规范化方法 : 将非规范化关系模式分解成多个规范化模式的方法,亦即是将一个函数依赖模式(R,∑)分解成属于第3范式或属于BC范式的几个函数依赖模式,或将一个多值依赖模式(R,∑)分解成几个属于第4范式的几个多值依赖模式,或将一个连接依赖模式(R,∑)分解成几个属于第5范式的几个连接依赖模式的方法。
无损依赖地分解成属于第3范式的方法,是于1977年由Bernstein给出的。既无损连接又无损依赖地分解成属于第3范式的方法是于1979年由Biskup、Dayal及Berestein给出的。包含函数依赖及多值依赖的多值依赖模式无损连接地分解为第4范式的方法是于1978年由Aho、Beeri及Ulman给出的。无损连接地分解为第5范式的算法是于1979年由Linj及Demers给出的。
为了将一个函数依赖模式(R,∑)分解成几个属于第3范式的函数依赖模式,需要先计算与∑等价(等价请参看函数依赖条目)的正则最小函数依赖集(正则函数依赖集及最小函数依赖集请见函数依赖条目),即需要先计算与∑等价的满足以下条件的函数依赖集∑₀:
(1)∑₀中每个函数依赖右部都只有一个属性,
(2)∑₀中不存在这样的函数依赖X→A,使得∑₀^*＝(∑₀-{X→A})^*,即∑₀中无多余依赖。
(3)∑₀中不存在这样的函数依赖X→A及Y⊂X使∑₀^*＝((∑₀∪{Y→A}-{X→A})^*,即每个函数依赖左部都无多余属性。
求给定的函数依赖集合∑的等价正则最小函数依赖集合的方法如下:
(1)右部化为单个属性形成∑₁: 将∑中的每个函数依赖X→Y全用{X→A|A∈Y}来代替,即形成集合∑₁＝{X→A|A∈Y,X→Y∈∑}。
(2)去掉多余依赖形成∑₂:在∑₁中依次取函数依赖X→A,令∑₀`=∑₁-{X→A},并求X_∑′⁺,若A∈X_∑′⁺,即(∑-{X→A})⊧X→A, 则删除X→A,删除后仍记为∑₁。依次将函数依赖全部取完,并都做了相应的处理完后,将最终的∑₁改记为∑₂。
(3)去掉左边的多余属性形成∑₀: 逐个取出∑₂中的每个X→A,做以下工作,设X=B₁,…,B_m。
①令X₀＝X,i=0。

③i<m则i=i+1转②,否则(i=m),则令∑₀＝{X_m→A|X→A∈∑₂}即为所求。
在计算出正则最小函数依赖集的基础上,将(R,∑)分解成几个无损连接无损依赖的属于第3范式的函数依赖模式的方法如下:
首先求出与∑等价的最小函数依赖集,并仍记为∑,然后按以下几种方法进行:
若有X→A∈∑且X∪{A}=R,则输出μ={R₀,∑₀₎}结束,其中R₀＝R,∑₀＝∑。
若不是情况1,则把不在∑中出现的属性合在一起形成R₀, 并令∑₀＝{∅}。
对每一个X_i→A_i∈∑(i=1,…,n),令R_i＝X_i∪{A_i},令∑_i＝{X→Y|X→Y∈∑^*,X, YR_i}, 任取(R,∑)的一个键X`,令R<sub>n+1</sub>＝X`,令∑_n+1＝{X→Y|X→Y∈∑^*∧X,YR_n+1}。
输出μ={(R₀,∑₀),(R₁,∑₁),…,(R_n+1,∑_n+1)}结束。
将一个函数依赖模式(R,∑)分解成几个属于第BC范式的无损连接的函数依赖模式的算法是(下面用KEY(R,∑)表示函数依赖模式(R,∑)的全部键的集合):
(1)首先求出∑的等价的正则最小函数依赖集合,不失一般性我们仍记它为∑。
(2)令ρ₁＝{(R,∑)}。
(3)若已知ρ_k(k=1,2,…),检查ρ_k中的每一个(R_i,∑_i)是否都属于BCNF,若都属于,则ρ_k即为所求的ρ,输出ρ,算法终止。
(4)若ρ_k中有(R_i,∑_i)不属于BCNF,那么必有X→A∈X_∑i^*,A∉X且X∉KEY(R_i,∑_i)。这时令R_i1＝X∪{A},R_i2＝R_i-{A},并令:ρ_k+1＝{(R₁,∑₁),…,(R_((i-1)),∑_i-1),(R_i1,∑_i1),(R_i2,∑_i2),(R_i+1,∑_i+1),…,(R_n,∑_n)}。其中,∑_i1＝{X→Y|X_{∑_((i))}^*⊧X→Y且X,YR_i1},∑_i2＝{X→Y|X_{∑_((i))}^*⊧X=Y且X,YR_i2}。然后再回到步骤(3)。
已证明这个分解是无损连接的,但一般情况下不能保证是无损依赖的。
将一个不属于4NF的多值依赖模式分解为几个属于4NF的多值依赖模式的无损连接的方法是:
对于多值依赖模式(R,∑),令R₁＝R,∑₁＝∑,ρ₁＝{(R₁,∑₁)},及i=1。
若已知ρ_i＝{(R₁,∑₁),…,(R_i,∑_i)}中仍有(R_k,∑_k)不属于4NF,则用(R_k1,∑_k1)及(R_k2,∑_k2)来代替(R_k,∑_k),而其他多值依赖模式不变,生成一个ρ_i+1,这里R_k1＝X∪Y,R_k2＝R_k-Y,∑_k1用以下方法给出: 对每个X→Y∈X_{∑_((i))}^*, 若XR_k1, 则X→(Y∩R_k1)∈∑_k1,对每个X→→Y∈X_{∑_((i))}^*,若XR_k1,则X→→(Y∩R_k1)∈∑_k1; R_k2用以下方法给出: 对每个X→Y∈X_{∑_((i))}^*,若XR_k2, 则X→(Y∩R_k2)∈∑_k2, 对每个X→→Y∈X_{∑_((i))}^*, 若XR_k2,则X→→(Y∩R_k2)∈∑_k2。
直到某个ρ_n＝{(R₁,∑₁),…,(R_n,∑_n)}中每个(R_k,∑_k)都属于4NF为止,ρ_n即为所求。已证明这种分解是无损连接的但不一定是无损依赖的。
将一个不属于5NF的连接依赖模式分解为几个无损连接的属于5NF的连接依赖模式的方法是:
(1)对于连接依赖模式(R,∑),令R₁＝R,∑₁＝∑,ρ₁＝{(R₁,∑₁)},及i=1。
(2)若已知ρ_i＝{(R₁,∑₁),…,(R_i,∑_i)}中仍有(R_k,∑_k)不属于5NF,则在∑_k中取使其不属于5NF的连接依赖μ=R_k⁽¹⁾⋈R_k⁽²⁾⋈…⋈R_k^(p)。 用(R_k⁽ⁱ⁾⁾,∑_k⁽ⁱ⁾⁾(i=1,…,p)来代替(R_k,∑_k),而其他多连接赖模式不变,生成一个ρ_i+1,其中∑_k⁽ⁱ⁾是∑在R_k⁽ⁱ⁾上的投影。
直到某个ρ_n＝{(R₁,∑₁),…,(R_n,∑_n)}中每个(R_k,∑_k)都属于5NF为止,ρ_n即为所求。
已证明这种分解是无损连接的。