吳榮海，范曉梅

（大理學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003）

候選關(guān)鍵字（candidate keys）在關(guān)系模式（relational schema）分解及規(guī)范化過(guò)程中有重要作用〔1-3〕。但求解給定關(guān)系模式候選關(guān)鍵字是NP完全問(wèn)題〔4〕，很多關(guān)系數(shù)據(jù)庫(kù)理論工作者提出過(guò)求解算法〔4-9〕，但部分文獻(xiàn)并未對(duì)算法的正確性、完備性給予證明。文獻(xiàn)〔4〕給出了一個(gè)替換法求解關(guān)系模式全部候選關(guān)鍵字算法，并對(duì)算法的正確性和完備性進(jìn)行了證明。文獻(xiàn)〔4〕中算法涉及的運(yùn)算多是集合運(yùn)算，與VC++、Java等程序設(shè)計(jì)語(yǔ)言相比，Matlab中的基本數(shù)據(jù)單元是數(shù)組，并提供了多個(gè)基于集合運(yùn)算的函數(shù)，從而使繁瑣復(fù)雜的集合操作變得易于實(shí)現(xiàn)〔10〕。文獻(xiàn)〔5〕利用Matlab實(shí)現(xiàn)了文獻(xiàn)〔4〕中算法的M函數(shù)，但文獻(xiàn)〔5〕給出M函數(shù)為了便于計(jì)算機(jī)實(shí)現(xiàn)，對(duì)用字符串表示的關(guān)系模式上的屬性集、函數(shù)依賴集事先轉(zhuǎn)換為數(shù)值表示，而且實(shí)現(xiàn)過(guò)程不完全符合文獻(xiàn)〔4〕所給算法，后者造成當(dāng)關(guān)系模式函數(shù)依賴集不變，屬性集個(gè)數(shù)2倍遞增時(shí)，所給M函數(shù)計(jì)算時(shí)間呈現(xiàn)指數(shù)級(jí)增長(zhǎng)。本文在文獻(xiàn)〔5〕工作的基礎(chǔ)上，給出幾個(gè)改進(jìn)的M函數(shù)，實(shí)驗(yàn)表明，本文所給M函數(shù)運(yùn)行時(shí)間顯著減少，求解正確，結(jié)果直觀,易于理解。

1 基本概念

關(guān)系模式中候選關(guān)鍵字的定義〔11〕如下：給定關(guān)系模式R（U，F(xiàn)），U為屬性集，F(xiàn)為函數(shù)依賴集。

定義1 給定關(guān)系模式R（U，F(xiàn)），若?X?U，滿足：

則稱X為關(guān)系模式R（U,F）的候選關(guān)鍵字。

定義3 屬性集的閉包〔12〕：給定關(guān)系模式R（U,F），設(shè)X?U，則屬性集X關(guān)于函數(shù)依賴集F的閉包X+定義為

X+={A |A?U且X→A可由Armstrong公理導(dǎo)出} 。

定義4 X→Y能由Armstrong公理導(dǎo)出的充分必要條件是Y?X+。

2 Matlab中關(guān)系模式R（U,F）的描述

一般而言，關(guān)系模式屬性集、函數(shù)依賴集用字符串表示。文獻(xiàn)〔5〕為了便于計(jì)算機(jī)處理，通過(guò)建立屬性集U{A1,A2,…,An}與1維數(shù)組〔1,2,…,n〕的映射關(guān)系，即屬性Ai對(duì)應(yīng)數(shù)組元素i，給出了屬性集U、函數(shù)依賴集F與Matlab中數(shù)值數(shù)組、元胞數(shù)組（cell array）的一一對(duì)應(yīng)關(guān)系。本文采用字符數(shù)組與元胞數(shù)組結(jié)合的辦法來(lái)建立屬性集U、函數(shù)依賴集F與Matlab中元胞數(shù)組的一一對(duì)應(yīng)關(guān)系，這樣可以省去轉(zhuǎn)換，也使計(jì)算過(guò)程更為直觀并便于理解。下面以文獻(xiàn)〔5〕中所給例子進(jìn)行說(shuō)明。

例1 給出關(guān)系模式R（U,F），其中屬性集U={A,B,C,D}，F(xiàn)={A→BD,CD→B}，X={C,D}。在MATLAB中使用字符數(shù)組、元胞數(shù)組描述該關(guān)系模式如下：

3 算法實(shí)現(xiàn)

替換算法〔4〕涉及并、差、包含于、屬于等集合運(yùn)算，在Matlab中可以利用union（）、setdiff（）、ismember（）等函數(shù)來(lái)實(shí)現(xiàn)〔5〕，下面給出算法實(shí)現(xiàn)過(guò)程中涉及的M函數(shù)。

3.1 函數(shù)依賴集預(yù)處理函數(shù)normalizeFDsSet（） 替換算法〔4〕規(guī)定關(guān)系模式R（U,F）中的F為右部是單屬性的非平凡函數(shù)依賴集，因此需要對(duì)一般的函數(shù)依賴集依據(jù)函數(shù)依賴Armstrong公理進(jìn)行分解〔5〕。下面給出實(shí)現(xiàn)函數(shù)依賴集預(yù)處理的M函數(shù)normalizeFDsSet（）：

function fs2=normalizeFDsSet（FDset）

〔r0,c0〕=size（FDset）;

fs2={};

for i=1:r0

Left=FDset{i,1};

Right=FDset{i,2};

〔r1,c1〕=size（Right）;

for j=1:c1

if～ismember（Right（j）,Left）

fs2=〔fs2;{Left,〔Right（j）〕}〕;

end;

end;

end;

3.2 屬性集閉包求解函數(shù)attributesSetClosure（） 給定關(guān)系模式R（U,F），計(jì)算屬性集X關(guān)于函數(shù)依賴集F的閉包X+算法〔12〕簡(jiǎn)述為：遍歷F，如果 ?Y→Z∈F且Y?X，那么X∪Z?X，循環(huán)迭代結(jié)束就可得到X關(guān)于F的閉包，記為。實(shí)現(xiàn)該算法的M函數(shù)attributesSetClosure（）如下。

function cl=attributesSetClosure（X,FDset）

〔r,c〕=size（FDset）;

flag=ones（1,r）;

cl=X;cl0={};

while～isequal（cl,cl0）

cl0=cl;

for i=1:r

if flag（i）&all（ismember（FDset{i,1},cl））

cl=union（cl,FDset{i,2}）;

flag（i）=0;

end;

end;

end;

3.3 去除屬性子集冗余屬性函數(shù)removeRedundantAttributes（） 文獻(xiàn)〔4〕給出了一個(gè)從給定候選關(guān)鍵字替換出一個(gè)新候選關(guān)鍵字的定理并加以了證明，定理如下。

定理1 給定關(guān)系模式R（U,F）上的一個(gè)候選關(guān)鍵字W，若 ?B→c∈F,c?B,c?W ，令 w1=（W-{c}+B），且執(zhí)行如下操作：

對(duì)于每一個(gè) A→x∈F，只要x∈w1和(w1-{x})→A∈F+，就執(zhí)行操作(w1-{x})?w1，則最終 w1必為關(guān)系模式R（U,F）上的一個(gè)候選關(guān)鍵字。

由定義4可知，要驗(yàn)證(w1-{x})→A∈F+是否成立，可以驗(yàn)證是否成立，根據(jù)定義4和定理1實(shí)現(xiàn)去除屬性子集中存在的冗余屬性的M函數(shù)removeRedundantAttributes（）如下：

function ck=removeRedundantAttributes（w,FDset）

〔r,c〕=size（FDset）;

ck=w;

for i=1:r

A=FDset{i,1};

x=FDset{i,2};

if ismember（x,ck）

c=attributesSetClosure（setdiff（ck,x）,FDset）;

if all（ismember（A,c））

ck=setdiff（ck,x）;

end;

end;

end;

3.4 求所有候選關(guān)鍵字函數(shù)allkeys（） 文獻(xiàn)〔4〕給出推論1并進(jìn)行了證明，推論如下。

推論1 給定關(guān)系模式R（U,F）上的任一個(gè)候選關(guān)鍵字W，則可從W出發(fā)，導(dǎo)出關(guān)系模式上的所有候選關(guān)鍵字。

推論1給出了從一個(gè)候選關(guān)鍵字通過(guò)替換法導(dǎo)出所有候選關(guān)鍵字的方法，根據(jù)定理1和推論1，實(shí)現(xiàn)該方法的M函數(shù)allkeys（）如下。

function sk=allkeys（w,FDset）

〔r0,c0〕=size（FDset）;

sk={};keys={};w1={};

sk{end+1}=w;keys{end+1}=w;

while ～isempty（keys）

w1=keys{end};

keys（end）=〔〕;

for j=1:r0

if all（ismember（FDset{j,2},w1））

w2=union（setdiff（w1,FDset{j,2}）,FDset{j,1}）;

w2=removeRedundantAttributes（w2,FDset）;

flag=1;

〔r1,c1〕=size（sk）;

for i=1:c1

if isequal（w2,sk{r1,i}）

flag=0;

break;

end;

end;

if flag

keys{end+1}=w2;

sk{end+1}=w2;

end;

end;

end;

end;

4 實(shí)例計(jì)算

為了便于對(duì)比，計(jì)算所用例子來(lái)自文獻(xiàn)〔5〕。

例2 給定關(guān)系模式R（U,F），其中屬性U={A,B,C,D,G,H}，函數(shù)依賴集F={AB→C,C→AB,B→D,D→B,A→G,G→H,H→A}，計(jì)算R的全部候選關(guān)鍵字。

上述關(guān)系模式R（U,F）以圖1所示格式存放為文本文件。

圖1 例2所給關(guān)系模式R對(duì)應(yīng)的文本文件

圖1所示文本文件利用M函數(shù)txt2cell（）對(duì)其進(jìn)行讀取，并初始化屬性集U和函數(shù)依賴集F，函數(shù)代碼如下：

function〔uset,fdset〕=txt2cell（fname）

fid=fopen（fname,'rt'）;

uset={};fdset={};

nline=0;literal='＞';

while feof（fid）==0

tline=fgetl（fid）;nline=nline+1;

if nline==1

〔token,rem〕=strtok（tline,','）;

uset{end+1}=token;

while length（rem）＞0

〔token,rem〕=strtok（rem,','）;

uset{end+1}=token;

end;

else

matches=findstr（tline,'＞'）;

if matches＞0

tmpLeft={};

Left=tline（1:matches-1）;

〔token,rem〕=strtok（Left,','）;

tmpLeft{end+1}=token;

while length（rem）＞0

〔token,rem〕=strtok（rem,','）;

tmpLeft{end+1}=token;

end;

fdset{nline-1,1}=tmpLeft;

tmpRight={};

Right=tline（matches+1:end）;

〔token,rem〕=strtok（Right,','）;

tmpRight{end+1}=token;

while length（rem）＞0

〔token,rem〕=strtok（rem,','）;

tmpRight{end+1}=token;

end;

fdset{nline-1,2}=tmpRight;

end;

end;

end;

下面給出替換算法求解關(guān)系模式R（U,F）所有候選關(guān)鍵字的M主函數(shù)GetAllCandidateKeys（），函數(shù)代碼如下：

〔uset,fds〕=txt2cell（‘fds.txt’）;

fds2=normalizeFDsSet（fds）;

ck=removeRedundantAttributes（uset,fds2）;

cks=allkeys（ck,fds2）;

運(yùn)行上述M函數(shù)得到元胞數(shù)組cks，如圖2所示，從圖2中可非常直觀地得出關(guān)系模式R（U,F）的7 個(gè)候選關(guān)鍵字：{D,H}、{B,H}、{D,G}、{B,G}、{A,D}、{C}、{A,B}。該例取自文獻(xiàn)〔5〕，但文獻(xiàn)〔5〕結(jié)果中的{G,B}與{B,G}顯然是同一個(gè)候選關(guān)鍵字，即文獻(xiàn)〔5〕實(shí)際得出的候選關(guān)鍵字個(gè)數(shù)為6個(gè)，少了1個(gè){B,H}。

圖2 元胞數(shù)組cks的結(jié)構(gòu)

本文在PC機(jī)上（CPU:Intel Mobile Core 2 Duo T5600,1.83 GHz；內(nèi)存:DDR2,2 GB,333 MHz），利用MATLAB測(cè)試了文獻(xiàn)〔5〕所給M函數(shù)（記為m1）與本文所給M函數(shù)（記為m2）在關(guān)系模式R（U,F）函數(shù)依賴集不變，屬性個(gè)數(shù)分別為 16、32、64、128、256、512、1024、2048、4096時(shí)計(jì)算所有候選關(guān)鍵字所需時(shí)間。函數(shù)m1和m2在每個(gè)給定屬性個(gè)數(shù)情況下，各自運(yùn)行3次，取3次測(cè)試結(jié)果的平均值，結(jié)果如圖3。

圖3 函數(shù)m1和m2求解全部候選關(guān)鍵字所需時(shí)間對(duì)比

5 結(jié)論

從圖3可以看出，與文獻(xiàn)〔5〕相比，本文所給M函數(shù)在函數(shù)依賴集不變，屬性個(gè)數(shù)呈2倍遞增過(guò)程中，計(jì)算所需時(shí)間增長(zhǎng)趨勢(shì)明顯減緩，在屬性個(gè)數(shù)較大（即問(wèn)題規(guī)模較大）的情況下，具有較大優(yōu)勢(shì)。

造成差別的主要原因?yàn)椋何墨I(xiàn)〔5〕所給M函數(shù)OneKey（）在從給定超關(guān)鍵字規(guī)約出一個(gè)關(guān)鍵字過(guò)程（即去除超關(guān)鍵字中存在的冗余屬性），實(shí)際上是窮舉了給定超關(guān)鍵字的所有可能組合，并且每一個(gè)組合都需要計(jì)算其閉包。這在屬性個(gè)數(shù)增加后所帶來(lái)的計(jì)算工作量是非常大的，因此算法的時(shí)間復(fù)雜度對(duì)屬性個(gè)數(shù)（問(wèn)題規(guī)模）較為敏感。本文所給的M函數(shù)removeRedundantAttributes（）是建立在定理1之上，在去除超關(guān)鍵字中存在的冗余屬性過(guò)程中，只考慮屬性依賴集中函數(shù)依賴右部包含于給定超關(guān)鍵字的情況，因此算法的時(shí)間復(fù)雜度對(duì)函數(shù)依賴集大小較為敏感，而屬性個(gè)數(shù)（問(wèn)題規(guī)模）對(duì)算法時(shí)間復(fù)雜度影響不大，這也與仿真結(jié)果相符。

以上M函數(shù)均在Microsoft Windows XP Professional Service Pack 3（Build 2600），Matlab 6.5.0.180913a Release 13環(huán)境下調(diào)試通過(guò)。

〔1〕董玉杰,劉海波.基于規(guī)范化理論的關(guān)系模式優(yōu)化策略研究〔J〕.北京電子科技學(xué)院學(xué)報(bào),2010,18（2）:34-40.

〔2〕肖治軍,彭小寧.基于特定關(guān)系模式下函數(shù)依賴集的閉包的研究〔J〕.懷化學(xué)院學(xué)報(bào),2012,31（5）:27-30.

〔3〕黃燦輝,陳瑛.關(guān)系模式規(guī)范化算法理論的分析應(yīng)用〔J〕.現(xiàn)代計(jì)算機(jī),2012（31）:12-14.

〔4〕周定康.求候選關(guān)鍵字的替換算法及其正確性和完備性證明〔J〕.計(jì)算機(jī)學(xué)報(bào),1994,17（10）:743-749.

〔5〕胡立輝.MATLAB在求解關(guān)系模式上全部候選關(guān)鍵字中的應(yīng)用〔J〕.計(jì)算機(jī)應(yīng)用與軟件,2004,21（5）:35-38.

〔6〕馮玉才.候選關(guān)鍵字的求解理論和算法研究〔J〕.計(jì)算機(jī)應(yīng)用與軟件,1989,6（5）:43-49.

〔7〕Hossein Saiedian,Thomas Spencer.An Efficient Algorithm to Compute the Candidate Keys of a Relational Database Schema〔J〕.The Computer Journal,1996,39（2）:124-132.

〔8〕劉國(guó)華,郝忠孝,陳子軍.一種求解全部候選關(guān)鍵字的快速替換算法〔J〕.計(jì)算機(jī)學(xué)報(bào),1998,21（10）:890-895.

〔9〕程昌品.一種搜索關(guān)系模式的所有候選關(guān)鍵字的算法〔J〕.計(jì)算機(jī)應(yīng)用與軟件,2005,22（1）:107-108.

〔10〕Stephen J Chapman.Matlab Programming for Engineers〔M〕.Fourth edition.Canada:Thomson Learning,2007.

〔11〕Ullman J D.Principle of Database System〔M〕.Rockville MD:Computer Science Press,1982.

〔12〕劉亞軍,高莉莎.數(shù)據(jù)庫(kù)基礎(chǔ)與應(yīng)用〔M〕.北京:清華大學(xué)出版社,2009:109-143.