sql - 在 PostgreSQL 中存储和查询区间树

Question

我有一些数据集（假设它是示例的整数），我想在 Postgres 中存储和查询。
例如：
数据集 A: 1,7,9-13
数据集 B: 1, 7, 10
我想运行查询，例如：
1. B 是 A 的子集吗？（是）
2. A 和 B 的交集是什么？(B)
数据集可以包括数千个整数范围。
我想知道是否有一些扩展支持这种数据分析。
任何示例/链接将不胜感激。

Answer 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 的至少一个范围中）：

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

这种方法的一个问题是，您必须通过不同的元组只保留不相交的 rangeS。例如，集合中的范围 [1,5] 和 [4,7] 必须位于仅具有 [1,7] 的元组中。为了确保这一点，您可以将它们插入到一个临时表中（在插入或更新时），它们将表本身与重叠的元组交叉连接，然后将它们连接起来并保持其他的原样。

Answer 2

SQL小提琴

不需要数组或范围。这只是纯粹的关系。

拦截非常明显：

select v
from t
where set = 'A'
intersect
select v
from t
where set = 'B'
order by v

而子集并不难：

select count(*) = 0
from (
    select v
    from t
    where set = 'B'
    except
    select b.v
    from
        (select v from t where set = 'A') a
        inner join
        (select v from t where set = 'B') b on b.v = a.v
) s