The construction of a bicategory of spans can be made in some categories C which do not have pullbacks in the traditional sense. The PROP for monoids is a good example of such a C. While reviewing Marco Grandis' 2012 book on Homological Algebra for Zentralblatt, I wondered about the existence of a nice proof of associativity of relations in a Puppe-exact category. I am trying to obtain any published proof at all; Marco attributes it to a 1967 paper of Tsalenko. In any case, I seem to have a decent proof in the vein of the first sentence of this abstract.