title: Allen's Interval Algebra operations in SQL
body: <p>I've been struggling to solve a few tricky problems in SQL where I need to infer asset utilisation from event intervals, and have just learned about <a href="https://i.stack.imgur.com/holbD.png" rel="nofollow noreferrer">Allen's Interval Algebra</a>, which seems to be the key to solving these problems.</p>
  
  <p>The algebra describes 13 kinds of relationships between intervals, and the image below shows the first seven, with the rest being the inverse (i.e. y before x, y meets x, etc)</p>
  
  <p><img src="https://i.stack.imgur.com/DIDOW.png" alt="enter image description here"></p>
  
  <p>But I'm having trouble finding out how to implement the relevant operations. </p>
  
  <p>Given my sample data, how can I go about getting results from the following three types of operations in SQL or PLSQL?</p>
  
  <ol>
  <li><strong>Disjoin</strong></li>
  <li><strong>Reduce</strong></li>
  <li><strong>Find Gaps</strong></li>
  </ol>
  
  <hr>
  
  <p>Please see my SQLFiddle link:  <a href="http://sqlfiddle.com/#!4/cf0cc" rel="nofollow noreferrer">http://sqlfiddle.com/#!4/cf0cc</a></p>
  
  <hr>
  
  <h2>Original Data</h2>
  
  <pre><code>   start end width
  [1]     1  12    12
  [2]     8  13     6
  [3]    14  19     6
  [4]    15  29    15
  [5]    19  24     6
  [6]    34  35     2
  [7]    40  46     7
  </code></pre>
  
  <p><img src="https://i.stack.imgur.com/holbD.png" alt="enter image description here"></p>
  
  <hr>
  
  <h2>Operation 1 - Disjoined Result</h2>
  
  <p>I'd like a query to return the <code>disjoint set</code> from the data above, where all overlapping intervals have been broken into rows such that no overlaps exist.</p>
  
  <p>How do I go about this SQL?</p>
  
  <pre><code>     start end width
  [1]      1   7     7
  [2]      8  12     5
  [3]     13  13     1
  [4]     14  14     1
  [5]     15  18     4
  [6]     19  19     1
  [7]     20  24     5
  [8]     25  29     5
  [9]     34  35     2
  [10]    40  46     7
  </code></pre>
  
  <p><img src="https://i.stack.imgur.com/holbD.png" alt="enter image description here">
  <img src="https://i.stack.imgur.com/Raqzb.png" alt="enter image description here"></p>
  
  <hr>
  
  <h2>Operation 2 - Reduced Result</h2>
  
  <p>How do I go about reducing/flattening the intervals, such that they are:</p>
  
  <ul>
  <li>not empty (i.e. they have a non-null width);   </li>
  <li>not overlapping; </li>
  <li>ordered from left to right; </li>
  <li>not even adjacent (i.e. there must be a non empty gap between 2 consecutive ranges)</li>
  </ul>
  
  <p>For my example, this would look like:</p>
  
  <pre><code>    start end width
  [1]     1  29    29
  [2]    34  35     2
  [3]    40  46     7
  </code></pre>
  
  <p><img src="https://i.stack.imgur.com/holbD.png" alt="enter image description here">
  <img src="https://i.stack.imgur.com/RIVx4.png" alt="enter image description here"></p>
  
  <hr>
  
  <h2>Operation 3 - Gap Result</h2>
  
  <p>Also, how would I find the gaps?</p>
  
  <pre><code>   start end width
  [1]    30  33     4
  [2]    36  39     4
  </code></pre>
  
  <p><img src="https://i.stack.imgur.com/holbD.png" alt="enter image description here">
  <img src="https://i.stack.imgur.com/uQ4wL.png" alt="enter image description here"></p>