How to know if a set of date range covers a bigger date range?

Question

I have to entities: postes and bookings. There is a oneToMany relationship between poste and booking: one poste may have many bookings (at different dates).

bookings is defined by 4 columns:

• booking_id: id
• poste_id: jointure postes table
• start_datetime: start date booking
• number_day: number of days (integer)

postes is defined by 4 columns:

• poste_id: poste id
• pattern (string): defined the allowed day (1 is allowed, 0 no). The 8th day is defined as the 1st day of the pattern (modulo 7)
• start: poste beginning date (all the date in bookings are included between start and end)
• end: poste end date

Goal: I would like to define a query that selects all postes that are not fully reserved (e.g. some new reservations are possible). I'm stuck because I can't select any data for the free date range since only bookings are stored.

Example

Booking table
| booking_id | poste_id |       start_datetime | number_day |
|------------|----------|----------------------|------------|
|          1 |        1 | 2019-07-10T00:00:00Z |          4 |
|          4 |        1 | 2019-07-14T00:00:00Z |          1 |
|          7 |        1 | 2019-07-16T00:00:00Z |          4 |
|          2 |        2 | 2019-07-10T00:00:00Z |          2 |
|          9 |        2 | 2019-07-13T00:00:00Z |          2 |
|          5 |        3 | 2019-07-15T00:00:00Z |          2 |
|          8 |        3 | 2019-07-21T00:00:00Z |          3 |
|         11 |        3 | 2019-07-28T00:00:00Z |          1 |
|         12 |        3 | 2019-07-29T00:00:00Z |          1 |
|          3 |        4 | 2019-07-15T00:00:00Z |          1 |
|         13 |        4 | 2019-07-21T00:00:00Z |          2 |

Postes table:
| poste_id | pattern |                start |                  end |
|----------|---------|----------------------|----------------------|
|        1 | 1111101 | 2019-07-10T00:00:00Z | 2019-07-20T00:00:00Z |
|        2 | 1101101 | 2019-07-10T00:00:00Z | 2019-07-20T00:00:00Z |
|        3 | 1100001 | 2019-07-15T00:00:00Z | 2019-07-30T00:00:00Z |
|        4 | 1011001 | 2019-07-15T00:00:00Z | 2019-07-30T00:00:00Z |

The expected output of the example is : 2,4. (no more booking are available for the poste 1 and 3).

Note:

• This is a simple example. Actually, the date ranges are bigger e.g. over several months.
• The database assumes bookings do not overlap.
• The pattern length might be different from 7. There are no link between the first day of the pattern and the number of days in a week. For example, if the pattern is '1101' with a starting date of "10-07-2019", that means the days 10, 11, 13, 14, 15, 17 and so on are available, not the others.
• The booking dates are always between the starting and ending date of the poste.

---

Reproductibility:

// Build the tables:
CREATE TABLE bookings
    (`booking_id` int, `poste_id` int, `start_datetime` datetime, `number_day` int)
;

INSERT INTO bookings
    (`booking_id`, `poste_id`, `start_datetime`, `number_day`)
VALUES
    (1, 1, '2019-07-10', '4'),
    (4, 1, '2019-07-14', '1'),
    (7, 1, '2019-07-16', '4'),
    (2, 2, '2019-07-10', '2'),
    (9, 2, '2019-07-13', '2'),
    (5, 3, '2019-07-15', '2'),
    (8, 3, '2019-07-21', '3'),
    (11, 3, '2019-07-28', '1'),
    (12, 3, '2019-07-29', '1'),
    (3, 4, '2019-07-15', '1'),
    (13, 4, '2019-07-21', '2')
;

CREATE TABLE postes
    (`poste_id` int, `pattern` VARCHAR(7), `start` datetime, `end` datetime);

INSERT INTO postes VALUES 
  (1, "1111101", "2019-07-10", "2019-07-20"),
  (2, "1101101", "2019-07-10", "2019-07-20"),
  (3, "1100001", "2019-07-15", "2019-07-30"),
  (4, "1011001", "2019-07-15", "2019-07-30");

My work: so far, I managed to find for a given day the available poste:

   SELECT DISTINCT p.* 
     FROM postes p
LEFT JOIN bookings b
       ON b.poste_id = p.poste_id
    WHERE
          /* Ignore date in past */
          MOD(DATEDIFF("2019-07-16", p.start), LENGTH(p.pattern)) >= -1

      AND
          /* Filter poste with pattern = 1 */
          SUBSTRING(p.pattern, MOD(DATEDIFF("2019-07-16", p.start),
                                   LENGTH(p.pattern)) + 1 , 1) = 1
      AND 
          /* Filter those available this day */
          p.poste_id NOT IN (
                SELECT b.poste_id
                  FROM bookings b
                 WHERE b.start_datetime <= "2019-07-16"
                   AND "2019-07-16" < DATE_ADD(b.start_datetime, INTERVAL b.number_day DAY)
                             );

Output:

| poste_id | pattern |                start |                  end |
|----------|---------|----------------------|----------------------|
|        2 | 1101101 | 2019-07-10T00:00:00Z | 2019-07-20T00:00:00Z |

Answer 1

Because of poste.pattern, I don't see how it would be possible to work with date ranges directly. It is possible to extend the 1-day solution by joining to a table that lists all dates from a range in separate rows, which can be generated as in:

How to populate a table with a range of dates?

...replacing "2019-07-16" with the _date column from that table.

Note: for this task, using a programming language could be more performant than a SQL-only approach.

Answer 2

(Not yet a complete answer, but at least some tips...)

• Is the 2nd column of bookings poste_id or room_id? (I guess "room" would be the better word for English??)
• Use DATE datatype instead of DATETIME. (Also, MySQL will choke on T and Z in datetime literals`.)
• Instead of VARCHAR(7), use TINYINT UNSIGNED. This will let you use Boolean operations, shift operations, and the BIT_COUNT() function. (See https://dev.mysql.com/doc/refman/8.0/en/bit-functions.html .) These should facilitate the desired computations.
• Your bit string is 7 long, as if it is related to days of the week. But is it? That is, is the first bit tied to, say, Sunday? Or is it tied to poste.start?
• What version of MySQL are you using? Before 8.0, bit operations are limited to 64, hence limiting a bit-manipulation solution to about 2 months. With 8.0, the operations are virtually unlimited in size.

So, with 8.0, I might

1. Replicate the bit (not char) pattern a sufficient number of times. (Hmmm... REPEAT works easily for chars, but not bits. Maybe do the repeat with char strings, then convert to bits.)
2. Chop off bits after the end date.
3. BIT_COUNT() to see how many days are available in the range.
4. SUM(number_day) to get the number of days reserved.
5. Subtract to see how many days are not reserved. (Note: this assumes the data is 'valid', that is, not having any "overlaps" in bookings.

(I would probably write the code in a 'real' programming language, as suggested by Aprillion. My steps above might be useful there.)

With an older version of MySQL, and/or with VARCHAR(7) instead of TINYINT, the above steps might work, but with some substitutions. For example, BIT_COUNT could be replaced by LENGTH(s) - LENGTH(REPLACE(s, '1', ''))

Answer 3

This is a pretty common problem in SQL questions — how to match data that isn't present in the database? SQL is better at matching data that is present.

Another quality of SQL is that it works better against sets of rows, instead of imaginary ranges defined by start and end. So my strategy is to transform the range into sets of actual rows.

First, create a table of all dates:

CREATE TABLE dates (date DATE PRIMARY KEY);
INSERT INTO dates SET date = '2019-07-01';
... 
INSERT INTO dates SET date = '2019-07-30';

Create a table of all dates used by any poste:

CREATE TABLE poste_dates (
  poste_id INT, 
  date DATE, 
  booking_id INT,
  PRIMARY KEY (poste_id, date)
);

Populate it with all dates for each poste, between the start and end of the poste date range. Filter using a join condition such that days of the week corresponding to your pattern are '1'.

INSERT INTO poste_dates (poste_id, date) 
SELECT poste_id, d.date FROM postes p JOIN dates d 
  ON SUBSTR(p.pattern, MOD(DATEDIFF(d.date, p.start), LENGTH(p.pattern))+1, 1) 
WHERE d.date BETWEEN p.start AND p.end;

Query OK, 34 rows affected (0.01 sec)

Now you have all the dates for all the postes:

+----------+------------+------------+
| poste_id | date       | booking_id |
+----------+------------+------------+
|        1 | 2019-07-10 |       NULL |
|        1 | 2019-07-11 |       NULL |
|        1 | 2019-07-12 |       NULL |
|        1 | 2019-07-13 |       NULL |
|        1 | 2019-07-14 |       NULL |
|        1 | 2019-07-17 |       NULL |
|        1 | 2019-07-18 |       NULL |
|        1 | 2019-07-19 |       NULL |
|        1 | 2019-07-20 |       NULL |
|        2 | 2019-07-10 |       NULL |
|        2 | 2019-07-11 |       NULL |
|        2 | 2019-07-13 |       NULL |
|        2 | 2019-07-14 |       NULL |
|        2 | 2019-07-17 |       NULL |
|        2 | 2019-07-18 |       NULL |
|        2 | 2019-07-20 |       NULL |
|        3 | 2019-07-15 |       NULL |
|        3 | 2019-07-16 |       NULL |
|        3 | 2019-07-22 |       NULL |
|        3 | 2019-07-23 |       NULL |
|        3 | 2019-07-29 |       NULL |
|        3 | 2019-07-30 |       NULL |
|        4 | 2019-07-15 |       NULL |
|        4 | 2019-07-17 |       NULL |
|        4 | 2019-07-18 |       NULL |
|        4 | 2019-07-22 |       NULL |
|        4 | 2019-07-24 |       NULL |
|        4 | 2019-07-25 |       NULL |
|        4 | 2019-07-29 |       NULL |
+----------+------------+------------+

For each booking, use UPDATE to set the booking id in the poste_dates table. Use LIMIT with the length of the booking. We have to do this one at a time, because in MySQL, LIMIT doesn't work when an UPDATE has a JOIN.

UPDATE poste_dates SET booking_id =  1 WHERE poste_id = 1 AND date >= '2019-07-10' ORDER BY date LIMIT 4;
UPDATE poste_dates SET booking_id =  4 WHERE poste_id = 1 AND date >= '2019-07-14' ORDER BY date LIMIT 1;
UPDATE poste_dates SET booking_id =  7 WHERE poste_id = 1 AND date >= '2019-07-16' ORDER BY date LIMIT 4;
UPDATE poste_dates SET booking_id =  2 WHERE poste_id = 2 AND date >= '2019-07-10' ORDER BY date LIMIT 2;
UPDATE poste_dates SET booking_id =  9 WHERE poste_id = 2 AND date >= '2019-07-13' ORDER BY date LIMIT 2;
UPDATE poste_dates SET booking_id =  5 WHERE poste_id = 3 AND date >= '2019-07-15' ORDER BY date LIMIT 2;
UPDATE poste_dates SET booking_id =  8 WHERE poste_id = 3 AND date >= '2019-07-21' ORDER BY date LIMIT 3;
UPDATE poste_dates SET booking_id = 11 WHERE poste_id = 3 AND date >= '2019-07-28' ORDER BY date LIMIT 1;
UPDATE poste_dates SET booking_id = 12 WHERE poste_id = 3 AND date >= '2019-07-29' ORDER BY date LIMIT 1;
UPDATE poste_dates SET booking_id =  3 WHERE poste_id = 4 AND date >= '2019-07-15' ORDER BY date LIMIT 1;
UPDATE poste_dates SET booking_id = 13 WHERE poste_id = 4 AND date >= '2019-07-21' ORDER BY date LIMIT 2;

Now the dates look like:

+----------+------------+------------+
| poste_id | date       | booking_id |
+----------+------------+------------+
|        1 | 2019-07-10 |          1 |
|        1 | 2019-07-11 |          1 |
|        1 | 2019-07-12 |          1 |
|        1 | 2019-07-13 |          1 |
|        1 | 2019-07-14 |          4 |
|        1 | 2019-07-16 |          7 |
|        1 | 2019-07-17 |          7 |
|        1 | 2019-07-18 |          7 |
|        1 | 2019-07-19 |          7 |
|        1 | 2019-07-20 |       NULL |
|        2 | 2019-07-10 |          2 |
|        2 | 2019-07-11 |          2 |
|        2 | 2019-07-13 |          9 |
|        2 | 2019-07-14 |          9 |
|        2 | 2019-07-16 |       NULL |
|        2 | 2019-07-17 |       NULL |
|        2 | 2019-07-18 |       NULL |
|        2 | 2019-07-20 |       NULL |
|        3 | 2019-07-15 |          5 |
|        3 | 2019-07-16 |          5 |
|        3 | 2019-07-21 |          8 |
|        3 | 2019-07-22 |          8 |
|        3 | 2019-07-23 |          8 |
|        3 | 2019-07-28 |         11 |
|        3 | 2019-07-29 |         12 |
|        3 | 2019-07-30 |       NULL |
|        4 | 2019-07-15 |          3 |
|        4 | 2019-07-17 |       NULL |
|        4 | 2019-07-18 |       NULL |
|        4 | 2019-07-21 |         13 |
|        4 | 2019-07-22 |         13 |
|        4 | 2019-07-24 |       NULL |
|        4 | 2019-07-25 |       NULL |
|        4 | 2019-07-28 |       NULL |
|        4 | 2019-07-29 |       NULL |
+----------+------------+------------+

Now it's quite simple to search for any postes that have any dates in this table with a NULL booking_id.

SELECT DISTINCT poste_id FROM poste_dates WHERE booking_id IS NULL;

This still differs from your expected result of poste 2 and 4.

• poste 1 includes the date 2019-07-20 because the pattern is 1111101-1111 which puts a 1 on the 20th, but no booking for poste 1 covers the 20th. Therefore 1 is not fully booked.
• poste 3 includes the date 2019-07-30 because the pattern is 1100001-1100001-11 which puts a 1 on the 30th, but no booking for poste 3 covers the 30th. Therefore 3 is not fully booked.

Answer 4

Since 8.0 you can do it with on-the-fly generated table of numbers and a little help of LATERAL. You may wish to create a persistant table of numbers instead.

with e1(n) as (
        select 1 union all select 1 union all select 1 union all
        select 1 union all select 1 union all select 1 union all
        select 1 union all select 1 union all select 1 union all select 1
), e2(n) as (select 1 from e1 a, e1 b), -- 100 rows
   e4(n) as (select 1 from e2 a, e2 b), -- 10,000 rows
numbers(n) as (
   select row_number() over(order by n) N from e4
)
select distinct poste_id, pattern, start, `end` 
from postes p 
join numbers n on adddate(start, n.N-1) <= `end`
   --  compute the date and respective position in the pattern for further usage
   , lateral (select adddate(start, n.N-1) dt, (n.N-1) % length(pattern) + 1 pos) x
where substring(pattern, x.pos, 1)
and not exists (
     select 1 
     from bookings b
     where b.poste_id = p.poste_id and x.dt >= b.start_datetime and x.dt <= adddate(b.start_datetime, b.number_day))
order by p.poste_id;

Fiddle