How did I solve this problem?

Question

While writing a SQL query I had to solve a problem I'd never dealt with before. It was trivial, but I cannot explain the solution without drawing lines on paper or making examples with actual numbers - and I don't like it: I want to give a rigorous answer and I want to learn about this subject.

The problem

• There are objects with starts_on and expires_on properties (SQL type DATE), starts_on must be less or equal to expires_on.
• We say the object is active at date D if starts_on ≤ D ≤ expires_on
• We say the object is active in the range of dates R(range_start, range_end) if it's active in at least one date D, range_start ≤ D ≤ range_end
• It turns out that the final where clause is starts_on ≤ range_end AND expires_on ≥ range_start

How do mathematicians solve this problem? How can I explain where my SQL comes from without any fancy painting? I think the starting point may be the function:

active_at_date = f(starts_on, expires_on, target_date)

which returns:

• TRUE, if starts_on ≤ target_date ≤ expires_on
• FALSE otherwise

But then, how could I go on?

_{Hope my question is not offtopic here. I worded it as best as I can, but it's the first attempt on this stackexchange site (and my math knowledge is very limited in this context, I know)}

Answer 1

Fix some object, and let $A$ be the set of its active dates. Also, let $R$ be some range we would want to check. The check itself is $R \cap A \neq \varnothing$, or in other words, there exists $d$ such that $d \in R$ and $d \in A$.

Now, we know, that $A$ and $R$ are not just any sets, but intervals, i.e. $A = [a_\min,a_\max]$ and $R = [r_\min,r_\max]$. Using this property we can simplify our query.

$(\Rightarrow)$ Suppose, there exists a date $d \in R \cap A$. Then,

\begin{align} a_\min \leq &d \leq a_\max & \text{ because } d \in A, \tag{1}\\ r_\min \leq &d \leq r_\max & \text{ because } d \in R, \tag{2}\\ \end{align} however, by mixing $(1)$ and $(2)$ we get \begin{align} a_\min \leq &d \leq r_\max \\ r_\min \leq &d \leq a_\max \end{align} which simplifies to exactly what we need. Therefore, this condition is necessary. Is it sufficient?

$(\Leftarrow)$ Let's assume that $$a_\min \leq r_\max \quad \land \quad r_\min \leq a_\max. \tag{3}$$ Set \begin{align} b_\min &= \max(a_\min,r_\min), \\ b_\max &= \min(a_\max,r_\max), \end{align} and observe, that by $3$ we have $$b_\min \leq b_\max.\tag{4}$$ Now, suppose that there exists $d \in [b_\min, b_\max]$, then $r_\min \leq d \leq r_\max$ so $d \in R$ and analogously $d \in A$. Hence, $d \in R \cap A$. The question is, whether range $[b_\min,b_\max]$ is non-empty, but this is implied by $(4)$, namely both $b_\min$ and $b_\max$ could substitute for $d$. This implies that the condition is sufficient.

I hope this helps $\ddot\smile$

Answer 2

Let's rephrase your problem:

• The starts_on and expires_on attributes form a closed time interval $[a,b]$.
• The object is active at time D, if $D \in [a,b]$.
• A range of dates is another interval, say $[c,d]$.
• The object is active in $[c,d]$ when any D of $[a,b]$ is also in $[c,d]$, in other words: the interval overlap: $[a,b]\cap [c,d] \neq \emptyset$.

Therefore some existing $D$ must fullfil the requirements

• $a \leq D \leq b$ and
• $c \leq D \leq d$.

Combined these requirements give $a \leq d$ and $c \leq b$.

P.S. There is nothing wrong with a case analysis given by drawing timelines ("one picture save 1k words"):

 a  b 
 ---- no                   ---- no 
 ------- yes --- yes  ------  yes  
      -------------------- yes     
       |----------------|       
       c                d

Answer 3

The solution comes from the definitions: You write

We say the object is active in the range of dates R(range_start, range_end) if it's active in at least one date D, range_start ≤ D ≤ range_end

But for the object to be active in at least one date D, it is necessary that starts_on ≤ D ≤ expires_on. This is because of the definition you gave:

We say the object is active at date D if starts_on ≤ D ≤ expires_on

So, you have two double inequalities that have to hold for D:

range_start ≤ D ≤ range_end

starts_on ≤ D ≤ expires_on

Now, if you "mix" them, you get range_start ≤ expires_on and starts_on ≤ range_end.