“Schedule conflict” — it’s one of the simplest and most common constraints for business or any other organization. One person cannot be in two places at the same time; and in many cases a only a single person can use a given resource at any time.
Does your database system know anything about a schedule conflict? Should it?
Constraints are always enforced at some point, it’s just a matter of when, how, and the cost of correcting the situation.
Consider two professors who try to reserve the same lecture hall at overlapping times (let’s say 1-2pm, and 1:30-2:30pm). Now imagine two possible resolutions:
- They are blissfully unaware of the schedule conflict until they have already promoted their lecture, attracted an audience, and arrived at the building. The professor scheduled for 1:30-2:30pm will be disappointed to find it already in use, and the students will be confused. The second lecture may have to be canceled due to the confusion, or lose a substantial number of attendees.
- At the time of scheduling, one professor is given an error message to the effect of “this room is already reserved, please choose a different time”.
Observe that neither one really solves the problem: the second resolution still forces one professor to choose a less-desirable time. However, it is a much cheaper resolution. As with many problems, early detection is simplest and cheapest to resolve.
Of course, there are many resolutions that fall between the first and the second. For instance, you might run a program every hour that checks for conflicts and alerts the parties involved. That may work, but there are still problems:
- You’ve now introduced uncertainty into the system: do I have a reservation or not? If there is a conflict later, will I be kicked out or will they?
- You have to come up with rules for resolution: does the first one win? How do you define “first” if transactions are running for a while? What if someone makes a reservation “first” but then makes all kinds of changes later; were they really first or did they just game the system?
- If someone’s reservation gets bumped, you have to now have a new strange state for a reservation, in which it is disabled, the organizer has (hopefully) been notified, and it needs to change.
- Notice that everything is very procedural and specific to the business. You have to have a notification mechanism, and rules for how to resolve it.
- Let’s go back to the definition of “first”: say you have made a reservation, and you get bumped by the conflict detector. In between the time you made the reservation and the time you were notified of a conflict, someone else reserved your second choice. Are you now first in line for that time slot? If so, that has a cascading effect such that it’s almost impossible for the person that took the second-choice slot to know that they are at risk of being bumped.
These thought experiments might seem like edge cases, but reservation systems have two common traits that make these problems very real:
- They tend to start allowing reservations of a specific resource at a specific time, published in advance.
- There tend to be some resources and time slots that have a much higher value than the others.
These two traits lead to heavy contention.
Now, how would you go about enforcing such a constraint (non-overlapping time periods) in the database? While considering possible solutions, think about:
- Does the solution work for a wide variety of use cases, or only in special cases?
- How well would it perform, under low contention and high contention, and under varied workloads?
- Can it be implemented in a general purpose RDBMS, like PostgreSQL?
- Is it procedural in nature, or declarative?
I think it’s worthwhile to consider the problem, so I will end this article now, and provide some approaches, as well as my real answer, in the next article. In the meantime, feel free to post ideas as comments.