Одна простая опция использует агрегацию:
SELECT
p.id,
p.name
FROM Products p
INNER JOIN ProductsToCategories pc
ON p.id = pc.product_id
WHERE
pc.category_id IN (9, 35, 36)
GROUP BY
p.id,
p.name
HAVING
COUNT(DISTINCT pc.category_id) = 3;
Основная идея здесь - агрегировать по каждому продукту, сначала удаляя все записи, кроме тех, которые относятся к трем категориям, представляющим интерес. Затем мы утверждаем, что то, что осталось, - это три отдельные категории, подразумевая, что продукт соответствует.