Você estava perto
SELECT order_id
FROM orders
WHERE product_id in (222,555)
GROUP BY order_id
HAVING COUNT(DISTINCT product_id) = 2
Em relação à sua pergunta "por curiosidade" em álgebra relacional, isso é obtido simplesmente com divisão . AFAIK no RDBMS implementou qualquer extensão que torna isso tão simples no SQL.
