传递闭包的增量式更新研究

汪小燕，杨思春，叶红，周建平

（安徽工业大学计算机科学与技术学院，安徽马鞍山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-），女，安徽桐城人，副教授，硕士，研究方向：数据挖掘，粗糙集理论，概念格，本体。