How to print all pairs of ID numbers such that the corresponding people don't belong to the same socieities

Question

I want to express the following in relational algebra:

Given a table of

PEOPLE: ID, SocietyName

Where the combination of ID and SocietyName form a key such that we could have the same ID in the table more than once but paired with a different society name.

I would like to be able to output all pairs of people, ID1 and ID2 such that they do not both attend any of the same societies. I am struggling to structure this in my head, I think I will need to rename PEOPLE to p1 and p2 say, then do some kind of join but I am not sure how to refine the output so it is only pairs where none share the same society.

Answer 1

Firstly $\Pi_{i_1, i_2}(\sigma_{i_1\leq i_2}{(\rho_{c_1(i_1, s)}People\times \rho_{c_2(i_2, s)}People)})$ gives all possible permutations of ID pairs in the form $(a, b)$ with $a\leq b$.

By $\Pi_{i_1, i_2}(\sigma_{i_1\leq i_2}{(\rho_{c_1(i_1, s)}People\bowtie \rho_{c_2(i_2, s)}People)}$, we can gain all pairs of people who attend a same society.

So the answer is

$$\Pi_{i_1, i_2}\Big(\sigma_{i_1\leq i_2}{(\rho_{c_1(i_1,s)}People\times\rho_{c_2(i_2, s)}People)}-\sigma_{i_1\leq i_2}{(\rho_{c_1(i_1, s)}People\bowtie \rho_{c_2(i_2, s)}People)}\Big)$$