Не понял зачем здесь таблица users_messages, если все связи уже есть в messages.
Вместо неё сделайте таблицу dialogs: id | from_user_id | to_user_id | date. А таблицу messages привести к виду: id | dialog_id | user_id | text | date
Алгоритм такой:
- Ю1 начинает диалог с Ю2 - добавляем запись в таблицу dialogs. В поля from_user_id и to_user_id заносим айдишники юзеров Ю1 и Ю2 соответственно.
- Ю1 пишет Ю2 - добавляем запись в таблицу messages. В поле user_id ставим айдишник юзера Ю1, в dialog_id ставим айдишник текущей беседы, с остальными полями думаю понятно.
- Ю2 отвечает Ю1 - добавляем запись в таблицу messages. В поле user_id ставим айдишник юзера Ю2, в dialog_id ставим айдишник текущей беседы.
Собственно всё :)
Если диалогов как таковых нет, то из алгоритма шаг 1 вычёркиваете и таблицу соответствующую удаляете.
Выборку затем делаете что-то типа:
/* Выбираем все сообщения в хронологическом порядке из диалога с id = :some_dialog_id */
SELECT m.*
FROM messages m
INNER JOIN dialogs d ON d.id = m.dialog_id
WHERE d.id = :some_dialog_id
ORDER BY m.date ASC