# Finding representatives of equivalence classes

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.

The most efficient way known of doing this is the union-find algorithm. The idea is to keep a forest (but with links "upwards", not downwards), and squash long branches. You start with each element in its own forest. To make $a$ and $b$ equivalent, you check it $a$ and $b$ are already in the same class by following their links to the respective roots. If the roots are different, make the smaller tree a subtree of the larger one. And each time you follow a chain to a root, afterwards revisit all nodes on the path and make them point directly to the root, effectively making later searches take one step.