Как составить запрос?

Вот мой вариант (чуть подкорректированный вариант Krechet-а):

select deviceId,objectId 
from devices_categories d, (select objectId,categoryId,count(*) over (partition by objectId) cnt from object_categories) o
where d.catId=o.categoryId
--and objectId = ?
group by deviceId,objectId
having count(d.catId)=max(o.cnt)

Кстати, RedQuark написал, что «Среде выполнения остается много возможностей по не оптимальному выполнению кода», хотя это не совсем так. Планировщику выполнения запроса может потребоваться больше времени для выбора оптимального соединения таблиц и возможно, что запрос выполнится не оптимальным образом.
Если указать порядок соединений самому с помощью join-ов, то это сократит время для Планировщика (так как ему не надо думать о выборе лучшего варианта), но сам такой порядок может быть не оптимальным.

Так как статистики по тем таблицам нет, то лучше даже не указывать порядок соединения — по двум таблицам СУБД сама сможет найти оптимальный вариант соединения.