Оповещения (notification) как правило о чём-то ( object = существительное = событие, дружба) что изменяется ( verb = глагол = добавлено, запрошено) кем-то ( actor = другим пользователем, системой) и кому-то показывается (userID = пользователю, группе, компании). По сути это модель естественного языка — на этом же основаны триплеты RDF.
Вот нормализованная структура данных, хотя я использовал Mongo.
Оповещать надо конкретных пользователей, поэтому тут зависимость от userID. Тоесть если надо оповестить 100 пользователей, надо сгенерировать 100 оповещений. Табличка посередине — для группировки по существительному, что-бы можно было сказать «У вас 3 новых запроса дружбы «. Третья табличка — что-бы можно было сказать » James Bond достиг новых высот в альпинизме «. Имея такую схему, можно делать и переводимые предложения.
Но поскольку объект о котором я рассказываю (дружба, событие..) описывается только как ID, вы должны сами присоединить нужную информацию. Это не так тривиально, поскольку там могут быть динамически штуки, например..
пользователь X переименовал событие «свадьба» в «день рождения»
Поскольку эти события должны генерироваться в реальном времени для активных пользователей, то я бы прикрутил их к nodejs + socket.io. А для всего остального есть API соц. сетей (vk, одноклассники), телефонов (APNS, C2DM), хостинга (Amazon SNS) и браузера (HTML5 Notifications)