Структура БД диалогов: как построить?
Можно сделать поле (например, deleted) с битовой маской
00b - видно всем
01b - удалил кто-то один (например, отправитель сообщения)
10b - удалил, соответственно, получатель сообщения
11b - удалили оба, можно удалять запись из базы (например, скриптом по крону, либо сразу проверять условие в момент удаления пользователем)
Я бы хранил всю переписку во-первых, в одной ячейке, а во-вторых, тупо дублировал бы её. Это, конечно, расход места, но зато просто.