基于PHP計算屬性集的閉包

王小兵，于思江

(1.西安電子科技大學計算機學院，陜西西安 710071;2.西安郵電大學財務處，陜西西安 710121)

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

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

本文介紹了函數依賴、邏輯蘊含、函數依賴集閉包與屬性集閉包的相關定義與算法，基于PHP中的數組實現了計算屬性集閉包的函數Closure，并通過一個具體的程序實例來說明函數依賴集的初始化與Closure函數的調用方法。

1 相關定義與算法

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

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

定義2 對于滿足一組函數依賴F的關系R＜U，F＞，其任何一個關系r，若函數依賴X→Y都成立，則稱F邏輯蘊含X→Y。

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

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

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

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

輸入:X，F，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實現Closure函數

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

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

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

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

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

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

基于上述的數組函數和算法1，定義PHP函數Closure在Closure.php中，如下所示。輸入參數$U為全體屬性數組，$F為全體函數依賴數組，$X為需要計算閉包的屬性集數組。輸出為$X在$F上的屬性集閉包。

若array_diff($U，$X)為空數組，則$U是$X的子集，而$X肯定是$U的子集，所以此時$U與$X 相等，算法終止。若 array_diff($F［$i］［0］，$X)為空數組，則第$i個函數依賴的左部是$X的子集，則該函數依賴的右部應該加入到結果$X中，通過 array_merge($X，$F［$i］［1］)來實現，然后調用array_unique排除當中重復的屬性。3程序實例

例1 已知關系模式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}，求(AB)+F。

編寫調用Closure函數的程序compute.php如下

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

3 結束語

Closure函數使用PHP語言編寫，基于數組和語言自帶的數組函數實現屬性集閉包的計算。使用PHP中的數組直觀的描述函數依賴，再調用Closure函數即可計算特定函數依賴集下的屬性集閉包。該方法的PHP程序結構簡單，代碼量少，易于實現與維護，可以獨立解釋執(zhí)行，也可以嵌入到HTML中解釋執(zhí)行。

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

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

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

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

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