Search code examples
algorithmdatabase-designschedulingrelational-databasetimetable

Time table modelling in relational db

I know that it has been told almost anything related to time table modeling in RDBS, but I can not find any well written documentation about available techniques to store time tables in DB.

My case:

  • I have table which holds available places, and table with actual classes.
  • Each place has it's own unique schedule
  • Each class can be scheduled in any place, and any time, with few exceptions:
    • One class can take one time-slot (Example: If class A is scheduled in place P1 at 12:00 for 1hour duration, next occurrence of class A can only be placed before 12:00 or after 13:00, in any place, which has free time-slot; It's forbidden to schedule class A in one time in two places)
    • In one place it can be one class with time-slot
  • Model should support versioning/history of scheduled classes

Now, how I can represent this data model in an SQL DB?

I'm not looking ready-to-use exact schema, rather I will be glad if anyone can write available modelling techniques and their comparison, which I can use to solve this task

For example: For tree-structure/hierarchical data, there is well documented "modified preorder tree traversal algorithm", is there some similar algorithm/technique to deal with time-slots?

Solution

  • A timetable is a matrix. Down the left hand side we have LOCATIONS. Across the top we have TIMESLOTS. The intersection of any given permutation of LOCATION and TIMESLOT is a cell with either a CLASS or null.

    To model this we need a table (entity) of LOCATIONS, which is pretty fixed data. We need a table of TIMESLOTS (date/times) which is ever growing. We need a table CLASSES, which is also pretty fixed. Finally we need an intersection table CLASS_TIMESLOT_LOCATIONS. This is where the magic happens. This table has three foreign keys, one to CLASSES, one to LOCATIONS, one to TIMESLOTS. Its primary key is (LOCATION_ID, TIMESLOT_ID) but it also needs a unique constraint on (CLASS_ID, TIMESLOT_ID).

    You are asking a modelling question, but there are a couple of implementation details which you will need to think about. They won't chnage the logical model but they will affect how you work with the physical tables. The first consideration is whether to spawn all the potential TIMESLOTS, and, if so, how big a window you store. The second is whether to store null entries for the intersection table, CLASS_TIMESLOT_LOCATIONS.

    There are no straightforward answers here: some database products will find it easier to "fill in the gaps" than others. Also, generating the absent records on the fly may be too much of a performance hit, in which case disk space is a good trade-off.

    As for storing history, this is presumably for storing changes to the schedule. Use separate tables for this, populated by triggers (you could use stored procedures but triggers is the industry standard). Don't be tempted to store history in the main tables. It breaks the normalised model and causes all sorts of grief.