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

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

（安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山243032）

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

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

（安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山243032）

針對(duì)二元關(guān)系中添加序偶原有傳遞閉包更新問(wèn)題，先提出一種新的傳遞閉包算法，并基于新的傳遞閉包算法給出傳遞閉包的增量式更新方法，只需要在原有傳遞閉包的基礎(chǔ)上，根據(jù)所添加的不同序偶，進(jìn)行簡(jiǎn)單的更新即可，利用該方法可以較快地實(shí)現(xiàn)動(dòng)態(tài)變化的二元關(guān)系傳遞閉包的求解。

二元關(guān)系；傳遞閉包；恒等關(guān)系；增量；更新

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

1 相關(guān)理論

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

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

如果關(guān)系R本身具有傳遞性質(zhì)，則t（R）=R。

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

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

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

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

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

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

2 計(jì)算傳遞閉包的改進(jìn)算法

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

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

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

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

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

（4）R1?R′復(fù)合完成后，計(jì)算二元關(guān)系R的傳遞閉包：t（R）=R′∪R1∪IR。

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

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

3 計(jì)算傳遞閉包的增量式更新算法

當(dāng)二元關(guān)系R中增加不同的序偶時(shí)，計(jì)算動(dòng)態(tài)變化R的傳遞閉包，一般是按照求傳遞閉包的計(jì)算方法，重新計(jì)算動(dòng)態(tài)變化R的傳遞閉包。實(shí)際上，計(jì)算動(dòng)態(tài)變化R的傳遞閉包，可以在R原先的傳遞閉包基礎(chǔ)上進(jìn)行更新即可。

通過(guò)對(duì)動(dòng)態(tài)變化R的傳遞閉包計(jì)算進(jìn)行研究，有如下結(jié)論。

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

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

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

推論4設(shè)R是集合A上的二元關(guān)系，t（R）是二元關(guān)系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＞}且具有傳遞性質(zhì)的二元關(guān)系，根據(jù)定義2知t（R）就是R2的傳遞閉包。

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

證明如果在二元關(guān)系R中添加序偶＜x，y＞且＜x，y＞?t（R），x≠y，R2=R∪{＜x，y＞}，當(dāng){＜x，y＞}?R′和（t（R）-It（R））?{＜x，y＞}兩種復(fù)合沒(méi)有產(chǎn)生序偶或沒(méi)有產(chǎn)生新的序偶時(shí)，根據(jù)新的傳遞閉包算法，R1和IR都沒(méi)有變化，所以R2的傳遞閉包為：t（R）∪{＜x，y＞}。

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

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

（2）在二元關(guān)系R中增加序偶，根據(jù)所增加的序偶，對(duì)t（R）進(jìn)行更新：①如果在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＞}兩種復(fù)合沒(méi)有產(chǎn)生序偶或沒(méi)有產(chǎn)生新的序偶，則t（R2）=t（R）∪{＜x，y＞}。

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

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

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

例2設(shè)集合A={1，2，3，4}，R是A上的二元關(guān)系，R={＜1，1＞，＜1，2＞，＜1，3＞，＜2，3＞，＜3，4＞，＜3，3＞，＜4，4＞}，當(dāng)在R中添加不同的序偶時(shí)，試求動(dòng)態(tài)變化二元關(guān)系的傳遞閉包。

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

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

4 結(jié)語(yǔ)

文中首先提出一種改進(jìn)的傳遞閉包的求解方法，并在改進(jìn)的傳遞閉包求解方法基礎(chǔ)上，提出傳遞閉包的增量式更新方法。當(dāng)二元關(guān)系發(fā)生動(dòng)態(tài)變化時(shí)，可以在原有傳遞閉包的基礎(chǔ)上進(jìn)行更新，節(jié)省了動(dòng)態(tài)變化的二元關(guān)系計(jì)算傳遞閉包的時(shí)間，新方法簡(jiǎn)單高效，易于實(shí)現(xiàn)。

[1]左孝凌，李為鑒，劉永才．離散數(shù)學(xué)[M]．上海：上海科學(xué)技術(shù)文獻(xiàn)出版社，1982．

[2]陳顯強(qiáng)．二元關(guān)系的傳遞性和傳遞閉包探討[J]．?dāng)?shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2004，34（9）：135-137．

[3]翟璐璐，謝維奇．關(guān)系傳遞閉包的計(jì)算[J]．河南教育學(xué)院學(xué)報(bào)：自然科學(xué)版，2005，14（1）：25-26．

[5]孫鳳芝．有限集上二元關(guān)系傳遞閉包的構(gòu)造[J]．大慶師范學(xué)院學(xué)報(bào)，2009，29（6）：44-47．

[6]何小亞，王洪山．利用關(guān)系矩陣求傳遞閉包的一種方法[J]．?dāng)?shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2005，35（3）：172-175．

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

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

[8]汪小燕.二元關(guān)系中傳遞性的若干研究[J].蘇州科技學(xué)院學(xué)報(bào)：自然科學(xué)版，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

責(zé)任編輯：艾淑艷

2014－04－02

安徽省高校自然科學(xué)基金資助項(xiàng)目（KJ2012Z024；KJ2012Z031）

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