王小兵，于思江

(1.西安電子科技大學(xué)計(jì)算機(jī)學(xué)院，陜西西安 710071;2.西安郵電大學(xué)財(cái)務(wù)處，陜西西安 710121)

關(guān)系模型具有嚴(yán)格的數(shù)學(xué)理論基礎(chǔ)，規(guī)范化理論在數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)中具有重要的作用。關(guān)系屬性之間存在的約束關(guān)系通過數(shù)據(jù)依賴體現(xiàn)出來(lái)［1］。函數(shù)依賴是一種常見的數(shù)據(jù)依賴，在模式設(shè)計(jì)的過程中，通常需要判定某一個(gè)特定的函數(shù)依賴是否成立。然而，計(jì)算函數(shù)依賴集閉包的方法過于復(fù)雜，是一個(gè)NPC難題，可以借助于計(jì)算屬性集閉包進(jìn)行簡(jiǎn)化。

計(jì)算屬性集閉包一般需要使用集合操作，如判等、并。如果使用一般高級(jí)語(yǔ)言，如C、C++，雖然效率較高，但需要定義集合操作［2］，代碼量較大，不易于實(shí)現(xiàn)與維護(hù)。若使用專用的語(yǔ)言，如 Matlab［3］、Mathematica［4］，可以用數(shù)組或表來(lái)描述函數(shù)依賴集，借助于語(yǔ)言自帶的集合操作，可方便地實(shí)現(xiàn)計(jì)算，但函數(shù)依賴的描述并不直觀［3－4］。PHP是一種通用的腳本語(yǔ)言，適用于Web開發(fā)，可生成用戶瀏覽的網(wǎng)頁(yè)［5］。PHP語(yǔ)言中的數(shù)組具有集合的特性，并且支持經(jīng)典的并、交、差等操作，能夠?qū)崿F(xiàn)屬性集閉包的計(jì)算。另外，PHP程序可在Web服務(wù)器軟件中運(yùn)行，還可以和C程序一樣獨(dú)立運(yùn)行。

本文介紹了函數(shù)依賴、邏輯蘊(yùn)含、函數(shù)依賴集閉包與屬性集閉包的相關(guān)定義與算法，基于PHP中的數(shù)組實(shí)現(xiàn)了計(jì)算屬性集閉包的函數(shù)Closure，并通過一個(gè)具體的程序?qū)嵗齺?lái)說明函數(shù)依賴集的初始化與Closure函數(shù)的調(diào)用方法。

1 相關(guān)定義與算法

本文討論涉及到函數(shù)依賴、邏輯蘊(yùn)含、函數(shù)依賴集閉包F+與屬性集閉包X+F，它們的定義［1］及相互聯(lián)系介紹如下。

定義1 R(U)是屬性集U上的關(guān)系模式。X，Y是U的子集。若對(duì)于R(U)的任意一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X上的屬性值相等，而在Y上的屬性值不等，則稱X函數(shù)確定Y或Y函數(shù)依賴于X，記作 X→Y。

定義2 對(duì)于滿足一組函數(shù)依賴F的關(guān)系R＜U，F(xiàn)＞，其任何一個(gè)關(guān)系r，若函數(shù)依賴X→Y都成立，則稱F邏輯蘊(yùn)含X→Y。

定義3 在關(guān)系模式R＜U，F(xiàn)＞中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作 F的閉包(Closure)，記為F+。

F+包含了給定函數(shù)依賴集F所蘊(yùn)含的屬性集U上的全部函數(shù)依賴。判定一個(gè)函數(shù)依賴X→Y是否成立，即是計(jì)算F+，再判定其是否包含X→Y。然而，根據(jù)Armstrong公理系統(tǒng)計(jì)算F+是一個(gè)NPC問題，需要通過其它的方法進(jìn)行簡(jiǎn)化。

判定X→Y是否成立，只需要計(jì)算出X+F，再判定Y是否為其子集。該方法計(jì)算的僅是X能夠函數(shù)確定的所有屬性，較前一種方法無(wú)目標(biāo)的計(jì)算F+大幅減少了計(jì)算量，從而使問題得到了簡(jiǎn)化。

算法1 求屬性集X(X?U)關(guān)于U上的函數(shù)依賴集F的閉包X+F。

輸入:X，F(xiàn)，U

輸出:XF+

(1)令 X(0)=X，i=0;

(3)X(i+1)=B∪X(i);

(4)判斷X(i+1)=X(i)嗎?

(5)如相等或X(i)=U則X(i)就是XF+，算法終止;

(6)若否，則i=i+1，返回第(2)步。

2 PHP實(shí)現(xiàn)Closure函數(shù)

PHP是一種服務(wù)器端的嵌入式HTML腳本語(yǔ)言。最初時(shí)稱作Personal Home Page Tools，當(dāng)PHP使用范圍日趨廣泛后，它被認(rèn)為是PHP:Hypertext Preprocessor的縮寫。PHP一般適用于Web開發(fā)，用戶通過瀏覽器向服務(wù)器發(fā)送執(zhí)行PHP程序的請(qǐng)求，解釋器解釋運(yùn)行后，用戶可以瀏覽網(wǎng)頁(yè)形式的輸出結(jié)果。PHP可以在Web服務(wù)器軟件，如IIS、Apache等中運(yùn)行，還可以直接運(yùn)行，如執(zhí)行php.exe compute.php將compute.php的結(jié)果輸出到屏幕。

PHP支持的數(shù)組具有數(shù)據(jù)集合的特性，支持修改、刪除、排序、查詢、并、交、差等操作，為計(jì)算屬性集閉包提供了足夠的前提條件。函數(shù)依賴X→Y可以通過PHP中的一個(gè)二維數(shù)組來(lái)表示，例如AB→C對(duì)應(yīng)array(array(‘A’，‘B’)，array(‘C’))。計(jì)算屬性集閉包涉及到的數(shù)組函數(shù)介紹如下。

array array_diff(array array1，array array2 ［，array...］):返回一個(gè)數(shù)組，該數(shù)組包括了所有在array1中但不在任何其它參數(shù)數(shù)組中的值。

array array_merge(array array1，array array2 ［，array...］):將兩個(gè)或多個(gè)數(shù)組的單元合并起來(lái)，一個(gè)數(shù)組中的值附加在前一個(gè)數(shù)組的后面。返回作為結(jié)果的數(shù)組。

array array_unique(array array):接受 array作為輸入并返回沒有重復(fù)值的新數(shù)組。

int count(mixed var［，int mode］):返回 var中的單元數(shù)目，通常是一個(gè) array(任何其它類型都只有一個(gè)單元)。mode參數(shù)設(shè)為 COUNT_RECURSIVE(或1)，count()將遞歸地對(duì)數(shù)組計(jì)數(shù)，默認(rèn)值是0。

基于上述的數(shù)組函數(shù)和算法1，定義PHP函數(shù)Closure在Closure.php中，如下所示。輸入?yún)?shù)$U為全體屬性數(shù)組，$F為全體函數(shù)依賴數(shù)組，$X為需要計(jì)算閉包的屬性集數(shù)組。輸出為$X在$F上的屬性集閉包。

若array_diff($U，$X)為空數(shù)組，則$U是$X的子集，而$X肯定是$U的子集，所以此時(shí)$U與$X 相等，算法終止。若 array_diff($F［$i］［0］，$X)為空數(shù)組，則第$i個(gè)函數(shù)依賴的左部是$X的子集，則該函數(shù)依賴的右部應(yīng)該加入到結(jié)果$X中，通過 array_merge($X，$F［$i］［1］)來(lái)實(shí)現(xiàn)，然后調(diào)用array_unique排除當(dāng)中重復(fù)的屬性。3程序?qū)嵗?/p>

例1 已知關(guān)系模式R＜U，F(xiàn)＞，其中U={A，B，C，D，G，H}，F(xiàn)={AB→C，C→AB，B→D，D→B，A→G，G→H，H→A}，求(AB)+F。

編寫調(diào)用Closure函數(shù)的程序compute.php如下

運(yùn)行執(zhí)行php.exe compute.php，輸出結(jié)果為 A，B，C，D，G，H。

3 結(jié)束語(yǔ)

Closure函數(shù)使用PHP語(yǔ)言編寫，基于數(shù)組和語(yǔ)言自帶的數(shù)組函數(shù)實(shí)現(xiàn)屬性集閉包的計(jì)算。使用PHP中的數(shù)組直觀的描述函數(shù)依賴，再調(diào)用Closure函數(shù)即可計(jì)算特定函數(shù)依賴集下的屬性集閉包。該方法的PHP程序結(jié)構(gòu)簡(jiǎn)單，代碼量少，易于實(shí)現(xiàn)與維護(hù)，可以獨(dú)立解釋執(zhí)行，也可以嵌入到HTML中解釋執(zhí)行。

［1］王珊，薩師煊.數(shù)據(jù)庫(kù)系統(tǒng)概論［M］.4版.北京:高等教育出版社，2006.

［2］汪韜，敬茂華.屬性集閉包求解算法的C++實(shí)現(xiàn)［J］.電腦編程技巧與維護(hù)，2009(14):26－28.

［3］胡立輝.Matlab在求解關(guān)系模式上全部候選關(guān)鍵字的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用與軟件，2004，21(5):35 －38.

［4］章美月，劉文斌.Mathematica在求解關(guān)系模式全部候選關(guān)鍵字上的應(yīng)用［J］.電腦學(xué)習(xí)，2009(1):75－76.

［5］陳晨，李隱峰，孫薇.基于PHP的陜西省醫(yī)學(xué)會(huì)會(huì)議管理系統(tǒng)的設(shè)計(jì)［J］.電子科技，2012，25(10):26－28.