Patrick Nappa has implemented a fast & low overhead method of representing equivalence relations in Soufflé. An Honours thesis has been submitted, available here, where corresponding slides can be found here.

The improved version is currently undergoing maintenance pending inclusion into the main branch of Soufflé, however an older (albeit slightly slower) implementation currently exists in Soufflé. The following demo demonstrates the special relation eqrel_fast which is equivalent to the eqrel_slow relation, yet the former carries an upper bounded quadratic speedup & memory improvement over the latter.

.decl eqrel_fast(x : number, y : number) eqrel
eqrel_fast(a,b) :- rel1(a), rel2(b).


.decl eqrel_slow(x : number, y : number)
eqrel_slow(a,b) :- rel1(a), rel2(b).
eqrel_slow(a,a) :- rel1(a).             // reflexivity
eqrel_slow(b,a) :- eqrel_slow(a,b).     // symmetry
eqrel_slow(a,c) :- eqrel_slow(a,b), eqrel_slow(b, c).   // transitivity