1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

This is rather simple to program with an array for the nodes, and array indices for links.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I take it, this implies that there is no pretty way to write it in relational algebra? $\endgroup$ – Karolis Juodelė Mar 4 '14 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.