Database – How does Facebook calculate mutual friends

I don't suggest you to use another table as a cache.

If you want to cache data, It's more appropriate use a technology like memcached (http://memcached.org/). This specialized storage should operate near your data access layer.

In addition I'll use a IoC/DI framework to integrate the code devoted to manage caching into the existing data layer. In this way the code used to manipulate data should not change at all.

The best practice is to store a datetime stamp in the user's table that indicates the last pull by the browser for notifications. Any notifications created after this datetime stamp would be counted as new and unread.

The database can index notifications by their created datetime stamp efficiently, and adding a flag if read shouldn't impact performance. Since you are always searching for notifications after a give datetime the performance should be okay.

You just need to update the user's table of what the oldest unread datetime stamp is. That gives you a place to query the notifications for new and unread items.

If there are no unread items then the user's timestamp is updated to the last time the browser pulled for a check.