傳遞閉包的增量式更新研究

汪小燕，楊思春，葉紅，周建平

（安徽工業大學計算機科學與技術學院，安徽馬鞍山243032）

傳遞閉包的增量式更新研究

汪小燕，楊思春，葉紅，周建平

（安徽工業大學計算機科學與技術學院，安徽馬鞍山243032）

針對二元關系中添加序偶原有傳遞閉包更新問題，先提出一種新的傳遞閉包算法，并基于新的傳遞閉包算法給出傳遞閉包的增量式更新方法，只需要在原有傳遞閉包的基礎上，根據所添加的不同序偶，進行簡單的更新即可，利用該方法可以較快地實現動態變化的二元關系傳遞閉包的求解。

二元關系；傳遞閉包；恒等關系；增量；更新

近年來,很多學者對關系的傳遞閉包運算進行過研究，傳遞閉包在圖論、數據庫、編譯原理、計算機形式語言中都有重要的應用。關系的傳遞閉包一般根據定義來計算，需要進行多次的集合復合運算，運算量大，如果二元關系發生了變化，在其中增加了某些序偶，一般的計算方法是將變化的二元關系按照原方法重新計算傳遞閉包，顯然這種計算方法增加了重復運算量。Warshall在1962年提出了計算傳遞閉包的有效算法[1]，但是二元關系中增加了一些序偶，計算其傳遞閉包時，還需要按照Warshall算法重新計算傳遞閉包。目前也很少有文獻涉及到傳遞閉包的增量式更新，文獻[2-6]提出了傳遞閉包的各種改進算法，但都沒有涉及到更新問題。為了減少傳遞閉包的增量式更新時間，先提出一種改進的傳遞閉包計算方法，并基于改進的傳遞閉包計算方法，給出一種傳遞閉包的增量式更新算法：當二元關系中增加不同類型的序偶時，不需要按照原方法重新計算添加序偶后二元關系的傳遞閉包，只需要在原有傳遞閉包的基礎上，根據所添加的不同序偶，進行簡單的更新即可，減少了動態變化二元關系傳遞閉包計算的時間。

1 相關理論

定義1[7]R為集合A上的二元關系，如果對于?＜a，b＞∈R，有＜b，c＞?R，或＜b，c＞∈R且＜a，c＞∈R，則稱R為A上的傳遞關系，或者說R在A上具有傳遞性。

定義2[1]設R是集合A上的二元關系，在R中添加最少的序偶集合R′，使得R∪R′具有傳遞性，則t（R）=R∪R′是R的傳遞閉包。

如果關系R本身具有傳遞性質，則t（R）=R。

定理1[1]設A是含有n個元素的集合，R是A上的二元關系，則存在一個正整數k≤n，使得t（R）=R∪R2∪R3∪…∪Rk。

定理1給出了傳遞閉包的計算公式，其中Rk（Rk=Rk-1?R，k≤n）表示k個R復合，n越大，復合的次數就越多，計算傳遞閉包就越復雜。

定義3[6]設R是集合A上的二元關系，若IR={＜x，x＞|x∈A且＜x，x＞∈R}，則稱IR為R中的恒等關系的集合。集合A中的恒等關系，記作IA。

定義4[6]設R是集合A上的二元關系，x，y，z是A中的任意三個元素，若?s，t∈R，且s=＜x，y＞，t=＜y，z＞，若以y為中間元素，則s和t可以形成新的序偶＜x，z＞，將這一運算稱為序偶的復合，記作s?t=＜x，z＞。

定理2[6]設R是集合A上的二元關系，IR≠φ，判斷R是否具有傳遞性，可以不考慮IR中的所有序偶。

推論1[8]R為A上的二元關系，且R具有傳遞性質，令C=IA-IR，如果將關系C中的任何一個序偶添加到R中，都不會改變R的傳遞性質。

2 計算傳遞閉包的改進算法

文獻[6]提出在計算傳遞閉包時，如果關系R中包含＜x，x＞這一類的序偶，可以在復合計算時，先不考慮＜x，x＞這一類的序偶，將刪除＜x，x＞類序偶后得到的二元關系R′和其自身進行增量式復合計算，也就是R′和其自身復合時，如果產生了新的序偶＜x，y＞?R′且x≠y，則將＜x，y＞并入R′的末尾，更新R′，然后繼續復合。一次復合完畢，根據復合后的R′，原有的＜x，x＞類序偶，以及可能新產生的＜x，x＞類序偶取并集，就可以計算出傳遞閉包。

由于在復合時，不考慮關系R中包含的＜x，x＞這一類的序偶，文獻[6]所提出的傳遞閉包算法優越性是很明顯的，節省了復合計算的時間。但是還可以再進一步減少復合的時間，當計算R′?R′時，若產生新的序偶＜x，y＞?R′且x≠y，將＜x，y＞并入R′的末尾，每個新產生的這種序偶只需要和R中的非＜x，x＞類的序偶復合。設A是一非空集合，R是集合A上的二元關系，R1=φ，新的傳遞閉包計算方法步驟如下：

（1）計算R′=R-IR，其中IR是R中＜x，x＞類序偶的集合。

（2）計算R′?R′，對產生的序偶做如下處理：（a）如果產生的序偶＜x，y＞∈R′，則將產生的序偶＜x，y＞舍棄；（b）如果產生的序偶＜x，y＞?R′且x≠y，則R1=R1∪{＜x，y＞}；（c）如果產生的序偶＜x，x＞∈IR，則將產生的序偶＜x，x＞舍棄；（d）如果產生的序偶＜x，x＞?IR，則IR=IR∪{＜x，x＞}。

（3）計算R1?R′，如果產生的序偶＜x，y＞?R′∪R1且x≠y，則將產生的序偶＜x，y＞并入R1的末尾，繼續復合，如果產生其他的序偶，則按照（2）進行處理。

（4）R1?R′復合完成后，計算二元關系R的傳遞閉包：t（R）=R′∪R1∪IR。

例1設集合A={1，2，3，4}，R是A上的二元關系，R={＜1，1＞，＜1，2＞，＜1，3＞，＜2，3＞，＜3，4＞，＜3，3＞，＜4，4＞}，求二元關系R的傳遞閉包。

解由于IR={＜1，1＞，＜3，3＞，＜4，4＞}，則R′=R-IR={＜1，2＞，＜1，3＞，＜2，3＞，＜3，4＞}，計算R′?R′，則R1= {＜1，4＞，＜2，4＞}，IR不變，再計算R1?R′，復合完成后，R1和IR都沒有變化，則二元關系R的傳遞閉包t（R）計算結果為：t（R）=R′∪R1∪IR={＜1，2＞，＜1，3＞，＜2，3＞，＜3，4＞，＜1，4＞，＜2，4＞，＜1，1＞，＜3，3＞，＜4，4＞}。

3 計算傳遞閉包的增量式更新算法

當二元關系R中增加不同的序偶時，計算動態變化R的傳遞閉包，一般是按照求傳遞閉包的計算方法，重新計算動態變化R的傳遞閉包。實際上，計算動態變化R的傳遞閉包，可以在R原先的傳遞閉包基礎上進行更新即可。

通過對動態變化R的傳遞閉包計算進行研究，有如下結論。

推論2設R是集合A上的二元關系，t（R）是二元關系R的傳遞閉包，如果R2=R∪{＜x，y＞}且＜x，y＞∈R，則R2的傳遞閉包為：t（R）。

推論3設R是集合A上的二元關系，t（R）是二元關系R的傳遞閉包，如果R2=R∪{＜x，x＞}且＜x，x＞∈IA-IR，則R2的傳遞閉包為：t（R）∪{＜x，x＞}。

證明由定理2和推論1可證。

推論4設R是集合A上的二元關系，t（R）是二元關系R的傳遞閉包，如果R2=R∪{＜x，y＞}且x≠y，＜x，y＞∈t（R）-R，則R2的傳遞閉包為：t（R）。

證明由于＜x，y＞∈t（R）-R，R?t（R），則R∪{＜x，y＞}?t（R），t（R）是包含R∪{＜x，y＞}且具有傳遞性質的二元關系，根據定義2知t（R）就是R2的傳遞閉包。

推論5設R是集合A上的二元關系，R′=R-IR，t（R）是二元關系R的傳遞閉包，如果R2=R∪{＜x，y＞}且＜x，y＞?t（R），x≠y，若{＜x，y＞}?R′和（t（R）-It（R））?{＜x，y＞}兩種復合沒有產生序偶或沒有產生新的序偶，則R2的傳遞閉包為：t（R）∪{＜x，y＞}。

證明如果在二元關系R中添加序偶＜x，y＞且＜x，y＞?t（R），x≠y，R2=R∪{＜x，y＞}，當{＜x，y＞}?R′和（t（R）-It（R））?{＜x，y＞}兩種復合沒有產生序偶或沒有產生新的序偶時，根據新的傳遞閉包算法，R1和IR都沒有變化，所以R2的傳遞閉包為：t（R）∪{＜x，y＞}。

設A是一非空集合，R是集合A中的二元關系，R′=R-IR，傳遞閉包的增量式更新算法步驟如下：

（1）按照文中計算傳遞閉包的方法，計算R傳遞閉包為：t（R）=R′∪R1∪IR。

（2）在二元關系R中增加序偶，根據所增加的序偶，對t（R）進行更新：①如果在R上增加一序偶＜x，y＞且＜x，y＞∈R，R2=R∪{＜x，y＞}，則t（R2）=t（R）；②如果在R上增加一序偶＜x，x＞且＜x，x＞∈IA-IR，R2=R∪{＜x，x＞}，則t（R2）=t（R）∪{＜x，x＞}；③如果在R上增加一序偶＜x，y＞且x≠y但＜x，y＞∈t（R）-R，R2=R∪{＜x，y＞}，則t（R2）=t（R）；④如果在R上增加一序偶＜x，y＞且＜x，y＞?t（R），x≠y，R2=R∪{＜x，y＞}，若{＜x，y＞}?R′和（t（R）-It（R））?{＜x，y＞}兩種復合沒有產生序偶或沒有產生新的序偶，則t（R2）=t（R）∪{＜x，y＞}。

（3）如果在二元關系R上增加一序偶＜x，y＞且＜x，y＞?t（R），x≠y，R2=R∪{＜x，y＞}，若{＜x，y＞}?R′和（t（R）-It（R））?{＜x，y＞}這兩種復合中只要有一種產生了新的序偶，設IR′=φ，R1′=φ，將新產生的＜x，x＞類序偶并入IR′，將新產生的其他序偶并入R1′，如果R1′=φ，則t（R2）=t（R）∪{＜x，y＞}∪IR′。

（4）如果在二元關系R上增加一序偶＜x，y＞且＜x，y＞?t（R），x≠y，R2=R∪{＜x，y＞}，若{＜x，y＞}?R′和（t（R）-It（R））?{＜x，y＞}這兩種復合中只要有一種產生了新的序偶，設IR′=φ，R1′=φ，將新產生的＜x，x＞類序偶并入IR′，將新產生的其他序偶并入R1′，如果R1′≠φ，按照新的傳遞閉包算法的步驟（3），計算R1′?（R′∪{＜x，y＞}），并更新R1′和IR′，當R1′?（R′∪{＜x，y＞}）復合完成后，則t（R2）=t（R）∪{＜x，y＞}∪R1′∪IR′。

在二元關系R中，當添加新的序偶時，不需要重新計算R的傳遞閉包。根據所添加序偶的各種情況更新原有傳遞閉包即可，減少了傳遞閉包更新時的工作量，而且該方法適合批量更新。

例2設集合A={1，2，3，4}，R是A上的二元關系，R={＜1，1＞，＜1，2＞，＜1，3＞，＜2，3＞，＜3，4＞，＜3，3＞，＜4，4＞}，當在R中添加不同的序偶時，試求動態變化二元關系的傳遞閉包。

解由于IR={＜1，1＞，＜3，3＞，＜4，4＞}，則R′=R-IR={＜1，2＞，＜1，3＞，＜2，3＞，＜3，4＞}，在例1中計算出二元關系R的傳遞閉包計算結果為：t（R）=R′∪IR={＜1，2＞，＜1，3＞，＜2，3＞，＜3，4＞，＜1，4＞，＜2，4＞，＜1，1＞，＜3，3＞，＜4，4＞}。

在二元關系R中添加不同的序偶時，動態變化二元關系的傳遞閉包更新過程如下：（1）如果在R上增加一序偶＜1，3＞，由于＜1，3＞∈R，則動態變化二元關系的傳遞閉包保持不變；（2）如果在R上增加一序偶＜2，4＞，由于＜2，4＞∈t（R）-R′，則動態變化二元關系的傳遞閉包保持不變；（3）如果在R上增加一序偶＜2，2＞且＜2，2＞∈IA-IR，則動態變化二元關系的傳遞閉包更新為：t（R）∪{＜2，2＞}；（4）如果在R上增加一序偶＜4，2＞，由于＜4，2＞?t（R），計算{＜4，2＞}?R′和（t（R）-It（R））?{＜4，2＞}，這兩種復合有新的序偶產生，設IR′=φ，R1′=φ，則R1′={＜3，2＞，＜4，3＞}，IR′={＜2，2＞}，再按照新的傳遞閉包算法計算R1′?（R′∪{＜4，2＞}），復合完成后，R1′和IR′沒有變化，則動態變化二元關系的傳遞閉包更新為：t（R）∪{＜4，2＞，＜3，2＞，＜4，3＞，＜2，2＞}。

4 結語

文中首先提出一種改進的傳遞閉包的求解方法，并在改進的傳遞閉包求解方法基礎上，提出傳遞閉包的增量式更新方法。當二元關系發生動態變化時，可以在原有傳遞閉包的基礎上進行更新，節省了動態變化的二元關系計算傳遞閉包的時間，新方法簡單高效，易于實現。

[1]左孝凌，李為鑒，劉永才．離散數學[M]．上海：上海科學技術文獻出版社，1982．

[2]陳顯強．二元關系的傳遞性和傳遞閉包探討[J]．數學的實踐與認識，2004，34（9）：135-137．

[3]翟璐璐，謝維奇．關系傳遞閉包的計算[J]．河南教育學院學報：自然科學版，2005，14（1）：25-26．

[5]孫鳳芝．有限集上二元關系傳遞閉包的構造[J]．大慶師范學院學報，2009，29（6）：44-47．

[6]何小亞，王洪山．利用關系矩陣求傳遞閉包的一種方法[J]．數學的實踐與認識，2005，35（3）：172-175．

[6]汪小燕．一種新的傳遞閉包算法研究[J]．蘇州科技學院學報：自然科學版，2011，28（4）：72-74．

[7]楊思春，王小林.二元關系傳遞性研究[J].微機發展，2003，13（10）：88-89.

[8]汪小燕.二元關系中傳遞性的若干研究[J].蘇州科技學院學報：自然科學版，2011，28（2）：37-39.

Research on the incremental updating of the transitive closure

WANG Xiaoyan，YANG Sichun，YE Hong，ZHOU Jianping
（School of Computer Science&Technology，Anhui University of Technology，Ma'anshan 243032，China）

Aimed at the updating problem for transitive closure when ordered pairs added to a binary relation，we put forward a new transitive closure algorithm.Based on this new transitive closure algorithm，the paper proposed a new method for the incremental updating of the transitive closure.According to the different ordered pairs added to a binary relation，the transitive closure of the new binary relation can be obtained by simply updating the original transitive closure.Using this method，we can achieve the solution for the transitive closure of a dynamic binary relation more effectively.

binary relation；transitive closure；identity relations；increment；updating

O158

A

1672－0687（2015）01－0045－04

責任編輯：艾淑艷

2014－04－02

安徽省高校自然科學基金資助項目（KJ2012Z024；KJ2012Z031）

汪小燕（1974-），女，安徽桐城人，副教授，碩士，研究方向：數據挖掘，粗糙集理論，概念格，本體。