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 * FROM districts 
    SELECT * FROM candidates
    WHERE 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:

FROM parties p
  FROM ( 
    SELECT DISTINCT party,district
    FROM parties CROSS JOIN districts
  ) a
  LEFT JOIN candidates c ON AND a.district=c.district
) b ON

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