Friday, January 17, 2014

How to Determine if Two Date Ranges Overlap in SQL

By the many possible configurations two time intervals can have with respect to each other, the most common is when two or more date ranges overlap. How to express it in relational terms?

Suppose we have a reference time range X. X will be in SQL represented by a pair of date columns or variables (how else?): @pr_DateFrom and @pr_DateTo.

We are now interested in determining whether the date ranges contained in one table, tb_DateRanges, are overlapping with our reference date range. tb_DateRanges has two column, DateFrom and DateTo. Moreover, if only one of those ranges are overlapping, our query should return a positive result. In SQL, the solution to this problem can be easly determined by an aggregating query.


The reference date range (black), the overlapping date ranges (green) and the non-overlapping date ranges (red).



We begin by expressing the opposite condition, i.e. if date range A does NOT overlap with reference range X. This happens when:
   
tb_DateRanges.DateTo <= @pr_DateFrom

OR

tb_DateRanges.DateFrom >= @pr_DateTo

Now, according to deMorgan's law:
   
not(A OR B)

is equivalent to  

not(A) AND not(B)

which means:

NOT(tb_DateRanges.DateTo <= @pr_DateFrom)

AND

NOT(tb_DateRanges.DateFrom >= @pr_DateTo)
   


By cross-applying this condition for every row of tb_DateRanges, we obtain a sequence of "true" (1) and "false" (0) values. By aggregating this raw result with the MAX() SQL function, we simulate an "OR" condition within the values.
   
This solution admits configurations where the edges overlap exactly. If you wish to exclude that, you may change the non-equijoins operators to ">= "to ">", and "<=" to "<", and viceversa.

A similar pattern can be used for spatial problems. For istance, for three-dimensional objects the same logic can be applied by listing the relation for each coordinate separately.

No comments:

Post a Comment