ок

Kuznetsov, Ну и? foreach в помощь. Если имеется ввиду эти "несколько категорий" были выбраны checkbox'ом

А вообще постарайтесь научится сначало корректно описывать суть проблемы/вопроса, ибо чётко поставленый вопрос - уже половина ответа.

Какие еще связи?! Конкретно не понятно вот это "Мне нужно присвоить каждой записи свои категории" С самим запросом проблем вроде не должно быть

SELECT * FROM записи WHERE ид_записи IN(SELECT ид_категории FROM категории) WHERE связной_ид = 'Q'

Я не совсем понял, а зачем три таблицы? 1я - категории, 2я - записи, что за третья таблица, в чём конкретно проблема?
Я не вижу проблемы составить запрос на выборку записей из какой-то категории с сортировкой по этой же категории, но видимо я не до конца допёр что у тебя не получается