冷強(qiáng)奎，秦玉平

（渤海大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 錦州 121000）

一種典型的模式分解算法分析與應(yīng)用

冷強(qiáng)奎，秦玉平

（渤海大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 錦州 121000）

從非優(yōu)化關(guān)系存在的問題出發(fā)，結(jié)合模式分解準(zhǔn)則和規(guī)范化理論，分析了一種典型的模式分解算法，并給出其在抽象關(guān)系中的應(yīng)用.最后，通過該算法將存在問題的關(guān)系分解，分解后的關(guān)系符合較高級(jí)的范式，達(dá)到了應(yīng)用系統(tǒng)邏輯結(jié)構(gòu)設(shè)計(jì)的要求.

模式分解；規(guī)范化；關(guān)系；邏輯結(jié)構(gòu)；范式

關(guān)系模式邏輯結(jié)構(gòu)設(shè)計(jì)是數(shù)據(jù)庫應(yīng)用系統(tǒng)開發(fā)的核心環(huán)節(jié)，這個(gè)階段不但能夠調(diào)整數(shù)據(jù)模型結(jié)構(gòu)，還能夠提升系統(tǒng)性能[1].一個(gè)非優(yōu)化的關(guān)系中存在大量的數(shù)據(jù)冗余和異常，不能滿足系統(tǒng)性能要求，制約系統(tǒng)后續(xù)開發(fā)進(jìn)程的實(shí)施.本文從分析非優(yōu)化關(guān)系存在的問題出發(fā)，結(jié)合模式分解準(zhǔn)則和規(guī)范化理論[2]，分析了一種典型的模式分解算法，并對(duì)非優(yōu)化關(guān)系執(zhí)行分解，實(shí)際應(yīng)用取得了較好的效果.

1 非優(yōu)化關(guān)系存在的問題

對(duì)于一個(gè)典型的非優(yōu)化關(guān)系S={Sno,Sdept,Mname, Cno,Grade}，其中Sno為學(xué)號(hào)、為系別、Sdept為系主任姓名、為課程號(hào)、為成績(jī)，為的一個(gè)函數(shù)依賴集，中部分?jǐn)?shù)據(jù)如表1.

表1 學(xué)生信息表

根據(jù)關(guān)系S的基本數(shù)據(jù)信息，可得到關(guān)系的碼為(Sno, Cno)，在F中存在Mname對(duì)碼的傳遞函數(shù)依賴，以及Sdept對(duì)碼的部分函數(shù)依賴，所以S不能達(dá)到3Nf.達(dá)不到3Nf的關(guān)系S存在如下問題：

(1)數(shù)據(jù)冗余，當(dāng)關(guān)系S中再出現(xiàn)信息系的學(xué)生時(shí)，Mname屬性的值還為“程前”；

(2)插入異常，學(xué)生入學(xué)還未選課，則信息無法存入S中；

(3)刪除異常，若S中體育系學(xué)生全部畢業(yè)了，在刪除學(xué)生信息時(shí)，系信息也隨之刪除；

(4)更新異常，某系更換系主任后，所在系學(xué)生元組的Mname屬性都要更新.

對(duì)關(guān)系S的優(yōu)化是數(shù)據(jù)庫邏輯結(jié)構(gòu)設(shè)計(jì)階段必須要解決的問題，為了消除數(shù)據(jù)冗余和三種異常情況，需要對(duì)S執(zhí)行模式分解操作.

2 一種典型的模式分解算法分析

2.1 模式分解的原則

模式分解要遵循兩個(gè)基本原則[3]，即分解具有“無損連接性”和“保持函數(shù)依賴”，保證分解后的關(guān)系與原關(guān)系模式等價(jià).設(shè)ρ={R1,…,RK}為R的一個(gè)分解，r是R的任意一個(gè)子關(guān)系,定義mρ(r)=πR1 πR2(r) …πRk(r)，即mρ(r)是r在ρ中各關(guān)系模式上投影的連接，這里πRi={t,Ui|t∈r}，兩個(gè)分解原則如下：

無損連接原則：ρ={R1,…,RK}是R的一個(gè)分解，若對(duì)R的任何一個(gè)子關(guān)系r均有r=mρ(r)成立，則稱分解ρ具有無損連接性.

2.2 屬性閉包和最小依賴集理論

公理系統(tǒng)[4]是模式分解算法的理論基礎(chǔ)，設(shè)U為屬性全體，F(xiàn)是U上的一組函數(shù)依賴，對(duì)于關(guān)系模式R，存在

A1自反律：若Y哿X哿U，則X→Y為F所蘊(yùn)含；

A2增廣律：若X→Y為F所蘊(yùn)含，且Z哿U，則XZ→YZ為F所蘊(yùn)含；

A3傳遞律：若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含.

定義1 根據(jù)Armstrong公理系統(tǒng)和推理規(guī)則，設(shè)F為屬性集U上的一組函數(shù)依賴，X哿U，X+F={A|X→A能由F根據(jù)Armstrong公理得出}，X+F稱為屬性集X關(guān)于函數(shù)依賴集F的閉包.

X+F求得結(jié)果即為屬性X所能決定的因素，當(dāng)X+F=U時(shí)，且X的真子集不能決定U時(shí)，則說明X是可以充當(dāng)關(guān)系R的碼值，這是屬性閉包的一個(gè)典型應(yīng)用.由Armstrong公理系統(tǒng)推導(dǎo)得出的F中所邏輯蘊(yùn)含的函數(shù)依賴的全體稱為F的閉包，記作F+.F+是一個(gè)完備的集合，但使用F+參與運(yùn)算會(huì)使計(jì)算非常復(fù)雜，于是要找到一個(gè)與F+等價(jià)的最小函數(shù)依賴集Fm.Fm的求解由算法(1)描述：

算法1 求關(guān)系R的一個(gè)最小函數(shù)依賴集Fm.

(1)根據(jù)分解規(guī)則，將F中各函數(shù)依賴右側(cè)元素單一化.逐一檢查F中各函數(shù)依賴FDi：X→Y，若Y=A1A2…Ak,k>2，則用{X→Aj|j=1,2,…,k}來取代X→Y.

(2)將冗余的函數(shù)依賴去掉.逐一檢查F中各函數(shù)依賴FDi：X→A，令G=F-{X-A}，若A∈X+G，則從F中去掉此函數(shù)依賴.

(3)將決定因素中多余的屬性去掉.逐一取出F中各函數(shù)依賴FDi：X→A，設(shè)X=B1B2…Bm，逐一考查Bi(i=1,2,…,m)，若A∈(X-Bi)+F，則以X-Bi取代X.

2.3 轉(zhuǎn)換為3NF的模式分解算法[5]

算法2 求達(dá)到3NF的既保持函數(shù)依賴又無損連接的分解

(1)求R中的函數(shù)依賴集F的最小函數(shù)依賴集Fm，并用Fm代替F.

(2)找出不在F中出現(xiàn)的屬性，把這樣的屬性構(gòu)成一個(gè)關(guān)系模式.把這些屬性從U中去掉，剩余的屬性仍記為U.

(3)若有X→A∈F，且XA=U，則ρ={R}，轉(zhuǎn)(5).

(4)否則，對(duì)F按具有相同左部分組，每一組函數(shù)依賴F'i所涉及全部屬性形成一個(gè)屬性集Ui.若Ui∈Uj則去掉Ui，得到的分解ρ={R1,…,RK}.

(5)利用屬性閉包求關(guān)系碼值，假設(shè)求得X+F，則X為碼.令τ=ρU{R*}.

(6)若有某個(gè)Ui,U哿Ui，，將R*從τ中去掉. (7)τ為所求.

3 模式分解算法的應(yīng)用

利用算法(2)對(duì)一個(gè)抽象的關(guān)系R執(zhí)行分解，U= {A,B,C,D,E,G}，F(xiàn)={A→G,AE->B,CD->A.CE->D,CG->D}.將R轉(zhuǎn)換為達(dá)到3NF既無損連接又能保持函數(shù)依賴的分解，步驟如下：

(1)根據(jù)算法 (1)，由F可得Fm=A→G,AE->B,CD->A, CE->D,CG->D}.

(2)關(guān)系R函數(shù)依賴集合F中不存在X→A∈F且XA=U的情況，算法繼續(xù)執(zhí)行.

(3)對(duì)F按具有相同左部分組，共分五組R1，其中U1={A,G},F1={A→G}；R2，其中U2={A,B,E}，F(xiàn)2={AE→B}；R3，其中U3={A,C,D}，F(xiàn)3={CD→A}；R4，其中U4={C,D,E}，F(xiàn)4={CE→D}；R5，其中U5={C,D,G}，F(xiàn)5= {CG→D}.ρ={R1,…,R5}

(4)利用屬性閉包求關(guān)系R的碼X，可得X=CE，R*<{C, E},覬>0.

(5)由于碼值(CE)∈U4，則最后的分解為ρ.ρ為無損連接且保持函數(shù)依賴的分解.同時(shí)ρ中各關(guān)系均能夠達(dá)到3NF.

4 總結(jié)

引入模式分解的目的就是解決關(guān)系中數(shù)據(jù)冗余和各種異常情況.通過對(duì)模式分解算法的分析，在抽象關(guān)系R進(jìn)行的驗(yàn)證表明算法的可行性.根據(jù)模式分解算法，將表1給出的非優(yōu)化關(guān)系模式S，可以分解為三個(gè)子關(guān)系S1，S2，S3，各關(guān)系內(nèi)容如下：

表2 學(xué)生信息關(guān)系

表3 系信息關(guān)系

表4 選課關(guān)系

容易證明，S1，S2，S3都能夠達(dá)到3NF，并且消除了數(shù)據(jù)冗余和異常情況.模式分解可將處于低級(jí)范式的關(guān)系規(guī)范到高級(jí)，使之符合數(shù)據(jù)庫邏輯結(jié)構(gòu)設(shè)計(jì)要求，是數(shù)據(jù)庫應(yīng)用系統(tǒng)設(shè)計(jì)的核心環(huán)節(jié)，直接決定應(yīng)用系統(tǒng)性能的優(yōu)劣.

〔1〕王珊，薩師煊.數(shù)據(jù)庫系統(tǒng)概論[M].北京：高等教育出版社，2006.

〔2〕吳榮海,范曉梅.關(guān)系規(guī)范化理論及非規(guī)范化設(shè)計(jì)在數(shù)據(jù)庫中的運(yùn)用[J].計(jì)算機(jī)與數(shù)字工程.2005,33(1):112-115.

〔3〕劉永山.基于矩陣關(guān)系模式到2NF、3NF(保FD)的分解[J].燕山大學(xué)學(xué)報(bào)，2000,24(3):96-99.

〔4〕胡立輝.基于閉屬性集的Armstrong關(guān)系的構(gòu)造算法[J].計(jì)算機(jī)應(yīng)用與軟件，2004,21(6):71-75.

〔5〕賈超.基于屬性集的歷史關(guān)系模式的規(guī)范化[J].計(jì)算機(jī)工程與應(yīng)用，2002,38(16):84-88.

T P 311.132

A

1673-260X（2010）07-0033-02