Time Calendar Data Structure

Question

We are looking at updating (rewriting) our system which stores information about when people can reserve rooms etc. during the day. Right now we store the start and time and the date the room is available in one table, and in another we store the individual appointment times.

On the surface it seemed like a logical idea to store the information this way, but as time progressed and the system came under heavy load, we began to realize that this data structure appears to be inefficient. (It becomes an intensive operation to search all rooms for available times and calculate when the rooms are available. If the room is available for a given time, is the time that it is available long enough to accommodate the requested time).

We have gone around in circles about how to make the system more efficient, and we feel there has to be a better way to approach this. Does anyone have suggestions about how to go about this, or have any places where to look about how to build something like this?

Answer 1

I found this book to be inspiring and a must-read for any kind of database involving time management/constraints:

Developing Time-Oriented Database Applications in SQL

(Added by editor: the book is available online, via the Richard Snodgrass's home page. It is a good book.)

Answer 2

@Radu094 has pointed you to a good source of information - but it will be tough going processing that.

At a horribly pragmatic level, have you considered recording appointments and available information in a single table, rather than in two tables? For each day, slice the time up into 'never available' (before the office opens, after the office closes - if such a thing happens), 'available - can be allocated', and 'not available'. These (two or) three classes of bookings would be recorded in contiguous intervals (with start and end time for each interval in a single record).

For each room and each date, it is necessary to create a set of 'not in use' bookings (depending on whether you go with 'never available', the set might be one 'available' record or it might include the early shift and late shift 'never available' records too).

Then you have to work out what questions you are asking. For example:

• Can I book Room X on Day Y between T1 and T2?
• Is there any room available on Day Y between T1 and T2?
• At what times on Day Y is Room X still available?
• At what times on Day Y is a room with audio-visual capabilities and capacity for 12 people available?
• Who has Room X booked during the morning of Day Y?

This is only a small subset of the possibilities. But with some care and attention to detail, the queries become manageable. Validating the constraints in the DBMS will be harder. That is, ensuring that if the time [T1..T2) is booked, then no-one else books [T1+00:01..T2-00:01) or any other overlapping period. See Allen's Interval Algebra at Wikipedia and other places (including this one at uci.edu).