Como verificar se um registro está relacionado a todos os registros de outra tabela em SQL?

Resposta

Utilize uma subconsulta correlacionada com NOT EXISTS.

Explicação:
Para cada registro A, confirme que não existe nenhum registro B que não esteja associado a A.
Padronamente usa-se uma dupla negação:
SELECT ... FROM A a WHERE NOT EXISTS (SELECT 1 FROM B b WHERE NOT EXISTS (SELECT 1 FROM Rel r WHERE r.a_id = a.id AND r.b_id = b.id));
Observação: prefira NOT EXISTS em vez de NOT IN quando houver possibilidade de NULL, para evitar resultados inesperados.