Пока склоняюсь к такой схеме:
table message:
id | subject | body |… other… | user_id
— здесь user_id — отправитель, он всегда один, в отличие от получателей
table message_user_rel (связь сообщения с пользователями)
id | message_id | type (входящее, исходящее) | trash (корзина)
Но здесь тоже проблема:
Если сообщение удалит получатель, то при выборке исходящих для отправителя невозможно определить, кто получатель (сообщение удалено)
Как быть, два флага trash и deleted иметь у каждой связанной записи к сообщению (корзина, удален)
но опять избыток всех этих флагов получается, и избыток данных в базе (реально нельзя удалять записи, а только помечать)
