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

吳榮海，范曉梅

（大理學院數學與計算機學院，云南大理 671003）

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

1 基本概念

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

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

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

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

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

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

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

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

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

3 算法實現

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

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

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

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

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

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

推論1給出了從一個候選關鍵字通過替換法導出所有候選關鍵字的方法，根據定理1和推論1，實現該方法的M函數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}，函數依賴集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函數txt2cell（）對其進行讀取，并初始化屬性集U和函數依賴集F，函數代碼如下：

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主函數GetAllCandidateKeys（），函數代碼如下：

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

fds2=normalizeFDsSet（fds）;

ck=removeRedundantAttributes（uset,fds2）;

cks=allkeys（ck,fds2）;

運行上述M函數得到元胞數組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〕實際得出的候選關鍵字個數為6個，少了1個{B,H}。

圖2 元胞數組cks的結構

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

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

5 結論

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

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

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

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

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

〔3〕黃燦輝,陳瑛.關系模式規范化算法理論的分析應用〔J〕.現代計算機,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〕劉亞軍,高莉莎.數據庫基礎與應用〔M〕.北京:清華大學出版社,2009:109-143.