Question:
[Joe Celko’s Reservations Puzzle]

Since I spend a lot of time this column talking about problems with the order of execution of SQL statements, it is only fair that I use it as the theme of the puzzle this month. The original version of this came from Bob Stearns at the University of Georgia and dealt with allocating pages on an Internet server. I will reword it as a seat reservation problem. The reservations consist of the customer name and the start and finish seat numbers of blocks they own. The rule of ownership is that no two blocks can overlap. The table for the reservations looks like this:

    CREATE TABLE Reservations        (owner CHAR(10) NOT NULL PRIMARY KEY,        start INTEGER NOT NULL,        finish INTEGER NOT NULL);    Reservations    owner    start finish     ======================    Eenie      1     4    Meanie     6     7    Mynie     10    15    Melvin    16    18 

What we want to do is to put a constraint on the table to assure that no rows that violate the overlap rule are ever inserted. This is harder than it looks unless you do things in steps.

Answer:
The first solution might be to add a CHECK() clause. You will probably draw some pictures to see how many ways things can overlap and you might come up with this:

    CREATE TABLE Reservations        (owner CHAR(10) NOT NULL PRIMARY KEY,        start INTEGER NOT NULL,        finish INTEGER NOT NULL,            CONSTRAINT No_Overlaps                 CHECK (NOT EXISTS                     (SELECT R1.owner                        FROM Reservations AS R1                        WHERE start BETWEEN R1.start AND R1.finish                            OR finish BETWEEN R1.start AND R1.finish));

This is a neat trick which will also handle duplicate start and finish pairs with different owners, as well as overlaps.

The two problems are that intermediate SQL-92 does not allow subqueries in a CHECK() clause, but it is allowed in full SQL-92. So this trick is probably not going to work on your current SQL implementation.

If you get around that problem, then you might find that you have trouble inserting an initial row into the table. The PRIMARY KEY and NOT NULL constraints are no problem. However, when the engine does the CHECK() constraint, it will make a copy of the empty Reservations table in the subquery under the name R1. Now things get confusing. The R1.start and R1.finish values cannot be NULLs, according to the CREATE TABLE statement, but R1 is empty so there have to be NULLs in the BETWEEN predicates. There is a very good chance that this self-referencing is going to confuse the constraint checker, and you will never be able to insert a first row into this table. The safest bet is to declare the table, insert a row or two, then add the No_Overlaps constraint afterwards.

Puzzle provided courtesy of:
Joe Celko
[email protected]