How to store sets of objects that have occurred together during events?

Question

I'm looking for an efficient way of storing sets of objects that have occurred together during events, in such a way that I can generate aggregate stats on them on a day-by-day basis.

To make up an example, let's imagine a system that keeps track of meetings in an office. For every meeting we record how many minutes long it was and in which room it took place.

I want to get stats broken down both by person as well as by room. I do not need to keep track of the individual meetings (so no meeting_id or anything like that), all I want to know is daily aggregate information. In my real application there are hundreds of thousands of events per day so storing each one individually is not feasible.

I'd like to be able to answer questions like:

In 2012, how many minutes did Bob, Sam, and Julie spend in each conference room (not necessarily together)?

Probably fine to do this with 3 queries:

>>> query(dates=2012, people=[Bob])
{Board-Room: 35, Auditorium: 279}
>>> query(dates=2012, people=[Sam])
{Board-Room: 790, Auditorium: 277, Broom-Closet: 71}
>>> query(dates=2012, people=[Julie])
{Board-Room: 190, Broom-Closet: 55}

In 2012, how many minutes did Sam and Julie spend MEETING TOGETHER in each conference room? What about Bob, Sam, and Julie all together?

>>> query(dates=2012, people=[Sam, Julie])
{Board-Room: 128, Broom-Closet: 55}
>>> query(dates=2012, people=[Bob, Sam, Julie])
{Board-Room: 22}

In 2012, how many minutes did each person spend in the Board-Room?

>>> query(dates=2012, rooms=[Board-Room])
{Bob: 35, Sam: 790, Julie: 190}

In 2012, how many minutes was the Board-Room in use?

This is actually pretty difficult since the naive strategy of summing up the number of minutes each person spent will result in serious over-counting. But we can probably solve this by storing the number separately as the meta-person Anyone:

>>> query(dates=2012, rooms=[Board-Room], people=[Anyone])
865

What are some good data structures or databases that I can use to enable this kind of querying? Since the rest of my application uses MySQL, I'm tempted to define a string column that holds the (sorted) ids of each person in the meeting, but the size of this table will grow pretty quickly:

2012-01-01 | "Bob"           | "Board-Room" | 2
2012-01-01 | "Julie"         | "Board-Room" | 4
2012-01-01 | "Sam"           | "Board-Room" | 6

2012-01-01 | "Bob,Julie"     | "Board-Room" | 2
2012-01-01 | "Bob,Sam"       | "Board-Room" | 2
2012-01-01 | "Julie,Sam"     | "Board-Room" | 3

2012-01-01 | "Bob,Julie,Sam" | "Board-Room" | 2

2012-01-01 | "Anyone"        | "Board-Room" | 7

What else can I do?

Answer 1

Your question is a little unclear because you say you don't want to store each individual meeting, but then how are you getting the current meeting stats (dates)? In addition any table given the right indexes can be very fast even with alot of records.

You should be able to use a table like log_meeting. I imagine it could contain something like:

employee_id, room_id, date (as timestamp), time_in_meeting

Where foreign keys to employee id to employee table, and room id key to room table

If you index employee id, room id, and date you should have a pretty quick lookup as mysql multiple-column indexes go left to right such that you gain index on (employee id, employee id + room id, and employee id + room id + timestamp) when do searches. This is explained more in the multi-index part of:

http://dev.mysql.com/doc/refman/5.0/en/mysql-indexes.html

Answer 2

By refusing to store meetings (and related objects) individually, you are loosing the original source of information.

You will not be able to compensate for this loss of data, unless you memorize on a regular basis the extensive list of all potential daily (or monthly or weekly or ...) aggregates that you might need to question later on!

Believe me, it's going to be a nightmare ...

Answer 3

If the number of people are constant and not very large you can then assign a column to each person for present or not and store the room, date and time in 3 more columns this can remove the string splitting problems.

Also by the nature of your question I feel first of all you need to assign Ids to everything rooms,people, etc. No need for long repetitive string in DB. Also try reducing any string operation and work using individual data in each column for better intersection performance. Also you can store a permutation all the people in a table and assign a id for them then use one of those ids in the actual date and time table. But all techniques will require that something be constant either people or rooms.

Answer 4

I do not understand whether you know all "questions" in design time or it's possible to add new ones during development/production time - this approach would require to keep all data all the time.

Well if you would know all your questions it seems like classic "banking system" which recalculates data on daily basis.

How I think about it.

1. Seems like you have limited number of rooms, people, days etc.
2. Gather logging data on daily basis, one table per day. Just one event, one database row, all information (field) what you need.
3. Start to analyse data using some crone script at "midnight".
4. Update stats for people, rooms, etc. Just increment number of hours spent by Bob in xyz room etc. All what your requirements need.
5. As analyzed data are limited and relatively small as you analyzed (compress) them, your system can contain also various queries as indexes would be relatively small etc.

You could be able to use scalable map/reduce algorithm.

Answer 5

You can't avoid storing the atomic facts as follows: (the meeting room, the people, the duration, the day), which is probably only a weak consolidation when the same people meet multiple times in the same room on the same day. Maybe that happens a lot in your office :).

Making groups comparable is an interesting problem, but as long as you always compose the member strings the same, you can probably do it with string comparisons. This is not "normal" however. To normalise you'll need a relation table (many to many) and compose a temporary table out of your query set so it joins quickly, or use an "IN" clause and a count aggregate to ensure everyone is there (you'll see what I mean when you try it).

I think you can derive the minutes the board room was in use as meetings shouldn't overlap, so a sum will work.

For storage efficiency, use integer keys for everything with lookup tables. Dereference the integers during the query parsing, or just use good old joins if you are feeling traditional.

That's how I would do it anyway :).

Answer 6

You'll probably have to store individual meetings to get the data you need anyway. However you'll have to make sure you aggregate and anonymise it properly before creating your reports. Make sure to separate concerns and access levels to stay within the proper legal limits on data.