Örneğin 1 id li kullancı 15 ve 12 id li kategorileri seçti.

select kategoriid from kullanici where kategoriid not in (select id from kategori)

şeklinde yapabilirsin. 15 ve 12 nin dışında seçilmeyen diğer kategorileri görüntüleyebilirsin. Tabi burada field'larını bilemedeğim için bu şekilde belirttim.

Mail veya sms bildirimini php ile mi yapmayı düşünüyorsun bilemiyorum. Mysql ile yapmayı düşünüyorsan biraz uğraştırır.