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

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

（安徽工业大学计算机科学与技术学院，安徽马鞍山243032）

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

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

（安徽工业大学计算机科学与技术学院，安徽马鞍山243032）

针对二元关系中添加序偶原有传递闭包更新问题，先提出一种新的传递闭包算法，并基于新的传递闭包算法给出传递闭包的增量式更新方法，只需要在原有传递闭包的基础上，根据所添加的不同序偶，进行简单的更新即可，利用该方法可以较快地实现动态变化的二元关系传递闭包的求解。

二元关系；传递闭包；恒等关系；增量；更新

近年来,很多学者对关系的传递闭包运算进行过研究，传递闭包在图论、数据库、编译原理、计算机形式语言中都有重要的应用。关系的传递闭包一般根据定义来计算，需要进行多次的集合复合运算，运算量大，如果二元关系发生了变化，在其中增加了某些序偶，一般的计算方法是将变化的二元关系按照原方法重新计算传递闭包，显然这种计算方法增加了重复运算量。Warshall在1962年提出了计算传递闭包的有效算法[1]，但是二元关系中增加了一些序偶，计算其传递闭包时，还需要按照Warshall算法重新计算传递闭包。目前也很少有文献涉及到传递闭包的增量式更新，文献[2-6]提出了传递闭包的各种改进算法，但都没有涉及到更新问题。为了减少传递闭包的增量式更新时间，先提出一种改进的传递闭包计算方法，并基于改进……