# How did I solve this problem?

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)

• well SQL is fundamentally based on set theory. hopefully you'll get an answer here, but there are also plenty of textbooks on relational databases which go into the set theory side of it. Feb 26, 2014 at 11:22
• @TooTone my main problem is I don't know how these things are called, so cannot start a search by myself :) Hope someone can point me in the right direction. SQL is based on set theory (that's how I tagged my question), but I think the problem here is combining predicates, so maybe more a differential calculus one - really don't know where to start Feb 26, 2014 at 11:28
• ok are you happy with an answer that focusses on pointing you in the right direction on the relationship between SQL and set theory? Feb 26, 2014 at 11:30
• @TooTone Hope so! Don't want others to do my job for me for free, just a help to jump the wall I hit, so I'll be able to keep running on my own. Of course, an answer like SQL is based on set theory and this is a dozen of good books... isn't going to help that much - something like Short explanation is [...] This subject is called X and I found R to be a really helpful resource when learning would do Feb 26, 2014 at 11:36
• I guess ends_on means expires_on? Because you don't explain what ends_on means. Feb 26, 2014 at 11:47

• 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

• +1, loved the wording at the beginning. I accepted @dtldarek's because my main point was explaining the combination of the requirements part without depicting it Feb 26, 2014 at 12:27
• @Raffaele: I have to admit, I'm a physicist and programmer, so I'm more interested in a solid, but quick problem solution. I'm completely satisfied with your decision, there is beauty in dtldarek's answer. Feb 26, 2014 at 16:04

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$

• The beauty of this answer is that it's so exact, yet so simple, that I read it and then thought "Why didn't I think of it before?". Beside, you have been the only one to prove what others called "mixing" or "combination of predicates", so I think you deserved your +25 :) Feb 26, 2014 at 12:33

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.

• Upvoted. Accepted @dtldarek's answer because my main concern was explaining what you call the "mixing" Feb 26, 2014 at 12:28
• @Raffaele Fair enough :) Feb 26, 2014 at 12:29