table structure for personal messages

What is the best table structure to store dialogs between users in private messages? Each user can send personal message to many recepients. Each message has flag for sender: is message deleted or not Each message has flag for receiver: is message unread, read or deleted Each message can be deleted (set flag 'deleted')

PrivateMessages' main page should look like this:

E.g. User1 sends Message1 to User2 and User3. On private message page I have to show 2 same messages:

1. sent Message1 to user2
2. sent Message1 to user3

next step - User2 replies to Message2, I'll see on the same page following:

1. received Message2 from user2 (reply on Message1)
2. sent Message1 to user3

next step, I answer to message3, I'll see

1. sent Message3 to user2
2. sent Message1 to user3

and so on.

Can anyone provide a table-structure? I'm using MySQL 5.5

Main question. How can I get only the last non-deleted message of each dialog?

UPD.

I need to see on main page dialog list, between current user and other users (with pagination, sorted by Date DESC).

I will answer your main question first, then show the table structure I will use for this.

To get only the last non-deleted message of a particular dialog:

select
    Message.Id
   ,Message.Subject
   ,Message.Content
from Message
join Junc_Message_To on Fk_Message = Message.Id
where Junc_Message_To.Fk_User =  {RECIPIENT_ID}
  and Message.Fk_User__From   =  {SENDER_ID}
  and Junc_Message_To.Deleted is null
order by Junc_Message_To.Sent desc
limit 1

A simple three table structure could be used.

Table 1 stores user records - one record per user.

Table 2 stores message record - one record per message, foreign key relates to the user that sent the message.

Table 3 stores the correlation between messages and users that have had the messages sent to them.

Here is the SQL that is used to create the above table diagram:

create table `User` (
  `Id`            int          not null auto_increment ,
  `Username`      varchar(32)  not null ,
  `Password`      varchar(32)  not null ,
  primary key     (`Id`) ,
  unique index     `Username_UNIQUE` (`Username` ASC) )
engine = InnoDB

create table `Message` (
  `Id`            int          not null auto_increment ,
  `Fk_User__From` int          not null ,
  `Subject`       varchar(256) not null ,
  `Content`       text         not null ,
  primary key   (`Id`) ,
  index          `Fk_Message_User__From` (`Fk_User__From` ASC) ,
  constraint     `Fk_Message_User__From`
    foreign key (`Fk_User__From` )
    references   `User` (`Id` )
    on delete cascade
    on update cascade)
engine = InnoDB

create table `Junc_Message_To` (
`Fk_Message`      int          not null ,
  `Fk_User`       int          not null ,
  `Sent`          datetime     not null ,
  `Read`          datetime     not null ,
  `Deleted`       datetime     not null ,
  PRIMARY KEY    (`Fk_Message`, `Fk_User`) ,
  INDEX           `Fk_Junc_Message_To__Message` (`Fk_Message` ASC) ,
  INDEX           `Fk_Junc_Message_To__User` (`Fk_User` ASC) ,
  constraint      `Fk_Junc_Message_To__Message`
    foreign key  (`Fk_Message` )
    references    `Message` (`Id` )
    on delete cascade
    on update cascade,
  constraint      `Fk_Junc_Message_To__User`
    foreign key  (`Fk_User` )
    references    `User` (`Id` )
    on delete cascade
    on update cascade)
engine = InnoDB