I have a table of pairs of objects, which defines an equivalence relation. How can I extract a single object from each of the equivalence classes using relational algebra?
It can easily be done with iteration. For example, associate a unique classId
with every object, then for every pair (a, b)
set classId(a) = classId(b) = min(classId(a), classId(b))
, until all pairs share the same classId
on both ends.
I wouldn't know how to do it more efficiently.