Categorie multiple. Come strutturare per una facile ricerca?

Ho un dubbio da molto tempo e non sono mai riuscito a risolvere purtroppo...
Nel caso volessi creare un qualcosa da memorizzare nel database e correlarlo in qualche modo a più opzioni, come potrei strutturare il tutto anche per una facile ricerca e mostra dei risultati completi?

Supponiamo di avere un messaggio che va correlato a 2 categorie ed immaginiamo di avere queste tre tabelle:
categories:

cat_id		cat_name
1		Categoria_1
2		Categoria_2

messages:

message_id		message_content
1			Testo
2			Test_2_Messaggio

messages_correlation:

correlation_mid		correlation_cid
1			1
2			1
2			2

Facendo un qualcosa di simile:

SELECT c.*, m.*
FROM messages_correlation
LEFT JOIN categories AS c
	ON (correlation_cid = c.cat_id)
LEFT JOIN messages AS m
	ON (correlation_mid = m.message_id)
GROUP BY m.message_id

Riuscirei a mostrare tutti i messaggi e poi affianco mostrare le categorie in cui il messaggio è stato aggiunto? Sto pensando a tanti metodi!

Ho fatto anche quello di creare un campo dopo separo con un apposito separatore le categorie, poi con explode() le mostre, faccio un foreach per mostrare il nome tramite l'id e poi con implode, le mostro con eventuale link, ma se dovessi fare una ricerca parziale in cui sono interessate MENO categorie di quelle in cui il post è inserito, non potrei fare la ricerca in MySQL!

Attendo consigli su come strutturare questo sistema, perché mi sarebbe molto utile...