PostgreSQLでの間隔ツリーの保存とクエリ

範囲データ型を使用して、互いに素な各型を1行に格納できます。

サンプルの場合：

-- The table
CREATE TABLE sets(id text, range int4range);
-- Values of set A
INSERT INTO sets VALUES('A', '[1,1]'),('A','[7,7]'),('A','[9,13]');
-- Values of set B
INSERT INTO sets VALUES('B','[1,1]'),('B','[7,7]'),('B','[10,10]');

BがAのサブセットであるかどうかを確認するには、Aの範囲にBの範囲が含まれているすべてのタプルと両方を結合できます。

 SELECT b.range
 FROM sets b JOIN sets a
     ON a.range @> b.range
 WHERE a.id='A' AND b.id='B'

これで、セットBのすべての値が上記の結果に含まれているかどうかを確認できます（つまり、Bのすべての範囲がAの少なくとも1つの範囲に含まれていることを意味します）：

 SELECT NOT EXISTS(
     SELECT 1 FROM sets q WHERE q.id='B' AND q.range NOT IN (
         SELECT b.range
         FROM sets b JOIN sets a
             ON a.range @> b.range
         WHERE a.id='A' AND b.id='B'
     ));

交差点を取得するには、両方を交差結合し、空のものを除外します。

 SELECT * FROM (
     SELECT a.range * b.range AS intersec
     FROM sets a CROSS JOIN sets b WHERE  a.id='A' AND b.id='B'
 ) i WHERE NOT isempty(i.intersec);

このアプローチに関する1つの問題は、異なるタプルを介して互いに素な範囲のみを保持する必要があることです。たとえば、セットの範囲[1,5]と[4,7]は、[1,7]のみのタプルに存在する必要があります。それを確認するために、それらを一時テーブルに挿入し（挿入または更新中に）、オーバーラップするタプルを使用してテーブル自体を相互結合し、それらを結合して他のタプルをそのまま維持します。