We have tables for recipes (r), ingredients required for recipes (ri), and ingredients now available in the pantry (p). In table ri there may be many rows for a given recipe r, each specifying one ingredient p.
drop table if exists r,p,ri;
create table r(id int);
insert into r values(1),(2),(3);
create table p(id int);
insert into p values(1),(2),(3);
create table ri(rid int,pid int);
insert into ri values (1,1),(1,2),(2,1),(2,4),(3,5),(3,6),(3,7);
select id as recipes from r;
+---------+
| recipes |
+---------+
| 1 |
| 2 |
| 3 |
+---------+
select id as 'available ingredients' from p;
+-----------------------+
| available ingredients |
+-----------------------+
| 1 |
| 2 |
| 3 |
+-----------------------+
select rid as recipe, pid as ingredient from ri;
+--------+------------+
| recipe | ingredient |
+--------+------------+
| 1 | 1 |
| 1 | 2 |
| 2 | 1 |
| 2 | 4 |
| 3 | 5 |
| 3 | 6 |
| 3 | 7 |
+--------+------------+
Given our ingredients, what recipes can we make? Inspection shows the answer is recipe #1.
SQL has no universal quantifier, so how do we proceed? 'All A is B' is logically equivalent to the double negative 'there is no A that is not B', so we can reformulate the requirement ...
list the recipes for which we have all ingredients
... into terms SQL can handle ...
list the recipes for which there is no ingredient we do not have
A double negative, so a double query. One inner query, one outer. Tackle the inner one first: find the recipes for which we are missing an ingredient.
That's a straight exclusion join, i.e., a left join on ingredient from 'required' to 'available', plus a where clause that restricts the resultset to nulls on the right ('available') side of the join:
SELECT DISTINCT rid AS 'Recipes for which the pantry is missing some ingredients'
FROM ri
LEFT JOIN p ON ri.pid=p.id
WHERE p.id IS NULL;
+----------------------------------------------------------+
| Recipes for which the pantry is missing some ingredients |
+----------------------------------------------------------+
| 2 |
| 3 |
+----------------------------------------------------------+
Our outer query has to find the recipes which are not in this list. That's another exclusion join, this time from recipes to the above derived table:
SELECT r.id
FROM r
LEFT JOIN (
SELECT DISTINCT rid
FROM ri
LEFT JOIN p ON ri.pid=p.id
WHERE p.id IS NULL
) AS rno ON r.id = rno.rid
WHERE rno.rid IS NULL;
+------+
| id |
+------+
| 1 |
+------+
It's an example of relational division, one of Codd's eight basic relational operations. Dividing a divisor table into a dividend table yields a quotient or results table:
dividend ÷ divisor = quotient
As in arithmetic, multiplication reverses it:
divisor * quotient = dividend
+-----------+
+-----+ +------+ | table AxB |
| A | | B | +-----+-----+
+-----+ +------+ |key_a|key_b|
|key_a| |key_b | +-----+-----+
+-----+ +------+ | 2 | 1 |
| 2 | | 1 | | 2 | 7 |
| 4 | | 7 | | 2 | 3 |
+-----+ | 3 | | 4 | 1 |
+------+ | 4 | 7 |
| 4 | 3 |
+-----+-----+
When we multiply (CROSS JOIN) tables A and B to yield AxB, AxB gets a row combining every row of A with every row of B, and all the columns from A and B. When we reverse that operation, dividing AxB by B, we get back A by listing distinct B values associated with A values in AxB.