What is a good way to find gaps in a set of datespans?

Question

What is a way to find gaps in a set of date spans?

For example, I have these date spans:

1/ 1/11 - 1/10/11  
1/13/11 - 1/15/11  
1/20/11 - 1/30/11

Then I have a start and end date of 1/7/11 and 1/14/11.

I want to be able to tell that between 1/10/11 and 1/13/11 there is a gap so the start and end date is not possible. Or I want to return only the datespans up to the first gap encountered.

If this can be done in SQL server that would be good.

I was thinking to go through each date to find out if it lands in a datespan... if it does not then there's a gap on that day.

Fairspoken

Answer 1

• Jump to 2nd last code block for: *I want to be able to tell that between 1/10/11 and 1/13/11 there is a gap so the start and end date is* not possible.
• Jump to last code block for: *I want to return only the datespans up to the first gap encountered.*

First of all, here's a virtual table to discuss

create table spans (date1 datetime, date2 datetime);
insert into spans select '20110101', '20110110';
insert into spans select '20110113', '20110115';
insert into spans select '20110120', '20110130';

This is a query that will list, individually, all the dates in the calendar

declare @startdate datetime, @enddate datetime
select @startdate = '20110107', @enddate = '20110114'
select distinct a.date1+v.number
from spans A
inner join master..spt_values v
  on v.type='P' and v.number between 0 and datediff(d, a.date1, a.date2)
-- we don't care about spans that don't intersect with our range
where A.date1 <= @enddate
  and @startdate <= A.date2

Armed with this query, we can now test to see if there are any gaps, by counting the days in the calendar against the expected number of days

declare @startdate datetime, @enddate datetime
select @startdate = '20110107', @enddate = '20110114'

select case when count(distinct a.date1+v.number)
    = datediff(d,@startdate, @enddate) + 1
    then 'No gaps' else 'Gap' end
from spans A
inner join master..spt_values v
  on v.type='P' and v.number between 0 and datediff(d, a.date1, a.date2)
-- we don't care about spans that don't intersect with our range
where A.date1 <= @enddate
  and @startdate <= A.date2
-- count only those dates within our range
   and a.date1 + v.number between @startdate and @enddate

Another way to do this is to just build the calendar from @start to @end up front and look to see if there is a span with this date

declare @startdate datetime, @enddate datetime
select @startdate = '20110107', @enddate = '20110114'
-- startdate+v.number is a day on the calendar
select @startdate + v.number
from master..spt_values v
where v.type='P' and v.number between 0
  and datediff(d, @startdate, @enddate)

-- run the part above this line alone to see the calendar
-- the condition checks for dates that are not in any span (gap)
  and not exists (
    select *
    from spans
    where @startdate + v.number between date1 and date2)

The query returns ALL dates that are gaps in the date range @start - @end A TOP 1 can be added to just see if there are gaps

To return all records that are before the gap, use the query as a derived table in a larger query

declare @startdate datetime, @enddate datetime
select @startdate = '20110107', @enddate = '20110114'
select *
from spans
where date1 <= @enddate and @startdate <= date2 -- overlaps
  and date2 < ( -- before the gap
    select top 1 @startdate + v.number
    from master..spt_values v
    where v.type='P' and v.number between 0
      and datediff(d, @startdate, @enddate)
      and not exists (
        select *
        from spans
        where @startdate + v.number between date1 and date2)
    order by 1 ASC
)

Rhizogenic

Answer 2

Assuming MySQL, something like this would work:

select @olddate := null;

select start_date, end_date, datediff(end_date, @olddate) as diff, @olddate:=enddate
from table
order by start_date asc, end_date asc
having diff > 1;

Basically: cache the previous row's end_date in the @olddate variable, and then do a diff on that "old" value with the currel enddate. THe having clause will return only the records where the difference between two rows is greater than a day.

disclaimer: Haven't tested this, but the basic query construct should work.

Musing

Answer 3

I want to be able to tell that between 1/10/11 and 1/13/11 there is a gap so the start and end date is not possible.

I think you're asking this question: does the data in your table have a gap between the start date and the end date?

I created a one-column table, date_span, and inserted your date spans into it.

You can identify a gap by counting the number of days between start date and end date, and comparing that the the number of rows in date_span for the same range.

select 
  date '2011-01-14' - date '2011-01-07' + 1 as elapsed_days,  
  count(*) from date_span 
where cal_date between '2011-01-07' and '2011-01-14';

returns

elapsed_days count    
--           --
8            6

Since they're not equal, there's a gap in the table "date_span" between 2011-01-07 and 2011-01-14. I'll stop there for now, because I'm really not certain what you're trying to do.

Synoptic