Das ist eine Frage zum Thema relationale Datenbanken.

Identifikation der Entities:

User, Message, Folder.

Identifikation der Relationships:

User 1 — 0..* Folder
Folder 1..* — 0..* Message

Tabellen:

user(id, login)
folder(id, name, user_id)
message(id, text)
message_folder(message_id, folder_id)

Ein User kann mehrere Folder haben, ein Folder gehört genau einem User. Ein Folder kann beliebig viele Messages enthalten, eine Message kann in mehr als einem Folder liegen. Ist die Message keinem Folder mehr zugeordnet, kann sie im Zuge einer Garbage Collection gelöscht werden.