規(guī)范化方法(數(shù)據(jù)庫)

時間：2022-12-25 12:30:01 | 來源：信息時代

時間：2022-12-25 12:30:01 來源：信息時代

    規(guī)范化方法 : 將非規(guī)范化關(guān)系模式分解成多個規(guī)范化模式的方法,亦即是將一個函數(shù)依賴模式(R,∑)分解成屬于第3范式或?qū)儆贐C范式的幾個函數(shù)依賴模式,或?qū)⒁粋€多值依賴模式(R,∑)分解成幾個屬于第4范式的幾個多值依賴模式,或?qū)⒁粋€連接依賴模式(R,∑)分解成幾個屬于第5范式的幾個連接依賴模式的方法。
無損依賴地分解成屬于第3范式的方法,是于1977年由Bernstein給出的。既無損連接又無損依賴地分解成屬于第3范式的方法是于1979年由Biskup、Dayal及Berestein給出的。包含函數(shù)依賴及多值依賴的多值依賴模式無損連接地分解為第4范式的方法是于1978年由Aho、Beeri及Ulman給出的。無損連接地分解為第5范式的算法是于1979年由Linj及Demers給出的。
為了將一個函數(shù)依賴模式(R,∑)分解成幾個屬于第3范式的函數(shù)依賴模式,需要先計算與∑等價(等價請參看函數(shù)依賴條目)的正則最小函數(shù)依賴集(正則函數(shù)依賴集及最小函數(shù)依賴集請見函數(shù)依賴條目),即需要先計算與∑等價的滿足以下條件的函數(shù)依賴集∑₀:
(1)∑₀中每個函數(shù)依賴右部都只有一個屬性,
(2)∑₀中不存在這樣的函數(shù)依賴X→A,使得∑₀^*＝(∑₀-{X→A})^*,即∑₀中無多余依賴。
(3)∑₀中不存在這樣的函數(shù)依賴X→A及Y⊂X使∑₀^*＝((∑₀∪{Y→A}-{X→A})^*,即每個函數(shù)依賴左部都無多余屬性。
求給定的函數(shù)依賴集合∑的等價正則最小函數(shù)依賴集合的方法如下:
(1)右部化為單個屬性形成∑₁: 將∑中的每個函數(shù)依賴X→Y全用{X→A|A∈Y}來代替,即形成集合∑₁＝{X→A|A∈Y,X→Y∈∑}。
(2)去掉多余依賴形成∑₂:在∑₁中依次取函數(shù)依賴X→A,令∑₀`=∑₁-{X→A},并求X_∑′⁺,若A∈X_∑′⁺,即(∑-{X→A})⊧X→A, 則刪除X→A,刪除后仍記為∑₁。依次將函數(shù)依賴全部取完,并都做了相應(yīng)的處理完后,將最終的∑₁改記為∑₂。
(3)去掉左邊的多余屬性形成∑₀: 逐個取出∑₂中的每個X→A,做以下工作,設(shè)X=B₁,…,B_m。
①令X₀＝X,i=0。

③i<m則i=i+1轉(zhuǎn)②,否則(i=m),則令∑₀＝{X_m→A|X→A∈∑₂}即為所求。
在計算出正則最小函數(shù)依賴集的基礎(chǔ)上,將(R,∑)分解成幾個無損連接無損依賴的屬于第3范式的函數(shù)依賴模式的方法如下:
首先求出與∑等價的最小函數(shù)依賴集,并仍記為∑,然后按以下幾種方法進(jìn)行:
若有X→A∈∑且X∪{A}=R,則輸出μ={R₀,∑₀₎}結(jié)束,其中R₀＝R,∑₀＝∑。
若不是情況1,則把不在∑中出現(xiàn)的屬性合在一起形成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)}結(jié)束。
將一個函數(shù)依賴模式(R,∑)分解成幾個屬于第BC范式的無損連接的函數(shù)依賴模式的算法是(下面用KEY(R,∑)表示函數(shù)依賴模式(R,∑)的全部鍵的集合):
(1)首先求出∑的等價的正則最小函數(shù)依賴集合,不失一般性我們?nèi)杂浰鼮椤啤?br>(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即為所求。
已證明這種分解是無損連接的。