No sé si esta es la mejor manera de hacer esto, pero como no tengo ideas de nadie más, esto es lo que estaría haciendo. Espero que esta respuesta también pueda ayudar a otros.
Tenemos 2 mesas
notification
-----------------
id (pk)
userid
notification_type (for complexity like notifications for pictures, videos, apps etc.)
notification
time
notificationsRead
--------------------
id (pk) (i dont think this field is required, anyways)
lasttime_read
userid
La idea es seleccionar notificaciones de la tabla de notificaciones y unirse a la tabla de notificacionesLeer y verificar la última notificación leída y las filas con ID> id de notificación. Y cada vez que se abra la página de notificaciones, actualice la fila de la tabla de notificacionesLeer.
Supongo que la consulta de notificaciones no leídas sería así...
SELECT `userid`, `notification`, `time` from `notifications` `notificationsRead`
WHERE
`notifications`.`userid` IN ( ... query to get a list of friends ...)
AND
(`notifications`.`time` > (
SELECT `notificationsRead`.`lasttime_read` FROM `notificationsRead`
WHERE `notificationsRead`.`userid` = ...$userid...
))
La consulta anterior no está marcada. Gracias a la idea de db design de @espais