All X for which all Y are Z (relational division)

from the Artful Common Queries page


You have an election database with tables listing political parties, election districts, and candidates running for parties in those districts. You want to know which parties have candidates running in all districts. Under Aggregates we show a 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.

Return to the Artful Common Queries page