Matlab在求候選關鍵字的替換算法中的應用

吳榮海，范曉梅

（大理學院數(shù)學與計算機學院，云南大理 671003）

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

1 基本概念

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

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

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

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

X+={A |A?U且X→A可由Armstrong公理導出} 。

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

2 Matlab中關系模式R（U,F）的描述

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

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

3 算法實現(xiàn)

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

3.1 函數(shù)依賴集預處理函數(shù)normalizeFDsSet（） 替換算法〔4〕規(guī)定關系模式R（U,F）中的F為右部是單屬性的非平凡函數(shù)依賴集，因此需要對一般的函數(shù)依賴集依據(jù)函數(shù)依賴Armstrong公理進行分解〔5〕。下面給出實現(xiàn)函數(shù)依賴集預處理的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（） 給定關系模式R（U,F），計算屬性集X關于函數(shù)依賴集F的閉包X+算法〔12〕簡述為：遍歷F，如果 ?Y→Z∈F且Y?X，那么X∪Z?X，循環(huán)迭代結束就可得到X關于F的閉包，記為。實現(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（） 文獻〔4〕給出了一個從給定候選關鍵字替換出一個新候選關鍵字的定理并加以了證明，定理如下。

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

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

由定義4可知，要驗證(w1-{x})→A∈F+是否成立，可以驗證是否成立，根據(jù)定義4和定理1實現(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 求所有候選關鍵字函數(shù)allkeys（） 文獻〔4〕給出推論1并進行了證明，推論如下。

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

推論1給出了從一個候選關鍵字通過替換法導出所有候選關鍵字的方法，根據(jù)定理1和推論1，實現(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 實例計算

為了便于對比，計算所用例子來自文獻〔5〕。

例2 給定關系模式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}，計算R的全部候選關鍵字。

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

圖1 例2所給關系模式R對應的文本文件

圖1所示文本文件利用M函數(shù)txt2cell（）對其進行讀取，并初始化屬性集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;

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

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

fds2=normalizeFDsSet（fds）;

ck=removeRedundantAttributes（uset,fds2）;

cks=allkeys（ck,fds2）;

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

圖2 元胞數(shù)組cks的結構

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

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

5 結論

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

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

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

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

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

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

〔4〕周定康.求候選關鍵字的替換算法及其正確性和完備性證明〔J〕.計算機學報,1994,17（10）:743-749.

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

〔6〕馮玉才.候選關鍵字的求解理論和算法研究〔J〕.計算機應用與軟件,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〕劉國華,郝忠孝,陳子軍.一種求解全部候選關鍵字的快速替換算法〔J〕.計算機學報,1998,21（10）:890-895.

〔9〕程昌品.一種搜索關系模式的所有候選關鍵字的算法〔J〕.計算機應用與軟件,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ù)庫基礎與應用〔M〕.北京:清華大學出版社,2009:109-143.