GROUP BY solution (here).
If there are reasons not to aggregate, relational division can solve the problem. The basic idea in relational division is that, aside from aggregation, SQL has no direct way to express "all Xs for which all Y are Z", but does have a NOT EXISTS operator, so we can express "all Xs for which all Y are Z" in SQL as a double negative: "all Xs for which no Y is not Z". Once you think of formulating the question this way, the query almost writes itself:
SELECT DISTINCT party FROM parties
WHERE NOT EXISTS (
SELECT * FROM districts
WHERE NOT EXISTS (
SELECT * FROM candidates
WHERE candidates.party=parties.party AND candidates.district=districts.district
)
);
Why is it called relational division? See the All possible recipes with given ingredients entry. Here the dividend is candidates, the divisor is districts and the quotient is a party count.
Most NOT EXISTS() queries can be translated into exclusion joins, which are often much faster. An exclusion join from A to B excludes A rows for which the LEFT JOIN condition finds NULLs in B. The query we are translating has two NOT EXISTS clauses, so we need two exclusion joins:
SELECT p.party
FROM parties p
LEFT JOIN (
SELECT a.party
FROM (
SELECT DISTINCT party,district
FROM parties CROSS JOIN districts
) a
LEFT JOIN candidates c ON a.party=c.party AND a.district=c.district
WHERE c.party IS NULL
) b ON p.party=b.party
WHERE b.party IS NULL;
Like numeric division, relational division has a gotcha: divide by zero. If the divisor table has zero rows, the quotient counts all distinct dividend instances. If that is not what you want, use aggregation.
Most "all Xs for which all Y are Z" queries can be written in any of these three ways. Try each one to see which performs best for your problem.
Last updated 22 May 2009
