I have a user and a notifications table. I want to make sure that every users sees a new notification once and only once. Not more, not less. The intuitive idea is to have a n:m relation table with userId:notificationId. But isn´t it a little too much overhead to create a new table just for that?

What about NoSQL databases? Would it be a good idea to just add an array of notification ids to the individual user in the user table?

  • 2
    What do you mean by 'overhead'? You are storing a fact consisting of two ids as two ids - where's the overhead?
    – AakashM
    Jul 25, 2014 at 8:15

1 Answer 1


@Amberlamps your question is very generic and from one perspective, AakashM did answer it in a comment already.

However let's look at it's basics to illustrate some ideas and techniques and their design considerations..

For a single user, what is the least amount of records (of the smallest size) that will address your need. On the surface (m) records per user. However more carefully, you can see it is likely to be a sparse set or the opposite of it, i.e. a mostly filled set.

You can, based on your data, come up with more complex representations if space is your concern.. i.e. for each user represent all "seen" records in ranges, i.e. (user1, lowid1, highid1), (user1, lowid2, highid2), (user2, lowid1, highid1) and so on. Separately system wide you'd have a system lowid and system highid to give boundaries to your queries. In essence this is one way to represent a sparse set (I haven't seen this exact structure anywhere else but if someone has seen it formally represented elsewhere please comment)..

You can find other ways to represent sparse sets too.

OTOH, if speed of lookup is more important then a straight n:m takes extra space compared to other representations but gives you very high speed for almost any operation you can think of.

Now switching topics.. In relational DB;s Having a separate table is actually not much more overhead, because the storage is efficient. In NoSQL DB, adding an array to each user will take less space, however when you're searching for all users who have "read" a particular notification, it forces you into an expensive query, unless you have indexes (which can be the same overhead as having them in a separate table). In this case if you switch the query around and search for all users who have "not" read a notification, it could be even more expensive.

Write a comment or update your question and I'll expand more if as needed.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.