Memorizzazione e query dell'albero degli intervalli in PostgreSQL

Puoi utilizzare i tipi di dati dell'intervallo e archiviare ogni tipo disgiunto in una riga.

Per il tuo campione:

-- 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]');

Per verificare se B è un sottoinsieme di A, puoi unirli a entrambi con tutte le tuple che l'intervallo di A contiene l'intervallo di B:

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

Con ciò, puoi verificare se tutti i valori dell'insieme B sono nel risultato precedente (il che significherà che tutti gli intervalli di B sono contenuti da almeno un intervallo di A):

 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'
     ));

Per ottenere l'intersezione, puoi incrociare entrambi ed escludere quelli vuoti:

 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);

Un problema su questo approccio è che devi mantenere solo intervalli disgiunti attraverso tuple diverse. Ad esempio, l'intervallo [1,5] e [4,7] da un insieme deve risiedere solo in una tupla con [1,7]. Per esserne sicuro, puoi inserirli in una tabella temporanea (durante l'inserimento o l'aggiornamento), si uniscono a croce alla tabella stessa con tuple che si sovrappongono e si uniscono a quelle e mantengono le altre così come sono.