sql - SQL でのアレンの区間代数演算

Question

私は、イベント間隔から資産の使用率を推測する必要がある SQL のいくつかのトリッキーな問題を解決するのに苦労しており、これらの問題を解決するための鍵と思われるAllen の間隔代数について学びました。

代数は区間間の 13 種類の関係を記述します。下の画像は最初の 7 つを示し、残りは逆です (つまり、x の前に y、y が x と出会うなど)。

しかし、関連する操作を実装する方法を見つけるのに苦労しています。

サンプル データが与えられた場合、SQL または PLSQL で次の 3 種類の操作から結果を取得するにはどうすればよいでしょうか。

1. 切り離す
2. 減らす
3. ギャップを見つける

---

私の SQLFiddle リンクを参照してください: http://sqlfiddle.com/#!4/cf0cc

---

元データ

   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

---

操作 1 - 切り離された結果

disjoint setオーバーラップが存在しないように、すべてのオーバーラップする間隔が行に分割されている上記のデータからクエリを返したいと思います。

この SQL はどうすればよいですか?

     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

---

操作 2 - 縮小結果

次のように、間隔を縮小/平坦化するにはどうすればよいですか。

• 空でない (つまり、幅が null でない)。
• 重複していません。
• 左から右に並べます。
• 隣接していません (つまり、2 つの連続した範囲の間に空でないギャップがなければなりません)

私の例では、これは次のようになります。

    start end width
[1]     1  29    29
[2]    34  35     2
[3]    40  46     7

---

操作 3 - ギャップ結果

また、ギャップを見つけるにはどうすればよいですか？

   start end width
[1]    30  33     4
[2]    36  39     4

Answer 1

ここにSQLFiddle のデモ があります。まず、一時テーブルを作成してクエリを簡素化しますが、これらの作成クエリを最終クエリに入れ、一時テーブルなしで実行できます。

create table t as select * from
(
select null s ,"start"-1 as e  from data
union all
select "start" s,null e  from data
union all
select "end"+1 s ,null e  from data
union all
select null s ,"end" e  from data
) d where exists (select "start" 
                  from data where d.s between data."start" and data."end"
                               or d.e between data."start" and data."end"
                                );
--Operation 1 - Disjoined Result   
create table t1 as select s,e,e-s+1 width from
(
select distinct s,(select min(e) from t where t.e>=t1.s) e from t t1
) t2 where t2.s is not null and t2.e is not null;

--Operation 2 - Reduced Result
create table t2 as 
select s,e,e-s+1 width from
(
select s,(select min(d2.e) from t1 d2 where d2.s>=d.s and not exists
          (select s from t1 where t1.s=d2.e+1) ) e
from
t1 d where not exists(select s from t1 where t1.e=d.s-1) 
) t2;

--Temp table for Operation 3 - Gaps
create table t3 as 
select null s, s-1 e from t2
union all
select e+1 s, null e from t2;

ここにクエリがあります：

--Operation 1 - Disjoined Result
select * from t1 order by s;

--Operation 2 - Reduced Result


select * from t2 order by s;

--Operation 3 - Gaps

select s,e,e-s+1 width 
from
(
select s,(select min(e) from t3 where t3.e>=d.s) e from t3 d
) t4 where s is not null and e is not null
order by s;