将范围列表展平为单个结果范围集

Question

我试图按定义的顺序（在提供的示例中按名称的字母顺序）将范围列表“展平”为单个合并结果。较新的范围覆盖较旧范围的值。从概念上讲，它看起来像这样，“e”是最新的范围：

0   1   2   3   4   5   6   7

|-------------a-------------|
        |---b---|            
    |---c---|                
                |---d---|    
            |---e---|        

|-a-|---c---|---e---|-d-|-a-|  <-- expected result

为了防止进一步混淆：这里的预期结果确实是正确的。值 0 - 7 只是范围的值，而不是时间上的进展。为简单起见，我在这里使用整数，但这些值可能不是离散的而是连续的。

请注意，这b完全被掩盖了，不再相关。

数据可以在 SQL 中像这样建模：

0   1   2   3   4   5   6   7

|-------------a-------------|
        |---b---|            
    |---c---|                
                |---d---|    
            |---e---|        

|-a-|---c---|---e---|-d-|-a-|  <-- expected result

如果有一种方法可以直接在 SQL 中查询结果，那将是完美的，例如：

create table ranges (
    name varchar(1),
    range_start integer,
    range_end integer
);

insert into ranges (name, range_start, range_end) values ('a', 0, 7);
insert into ranges (name, range_start, range_end) values ('b', 2, 4);
insert into ranges (name, range_start, range_end) values ('c', 1, 3);
insert into ranges (name, range_start, range_end) values ('d', 4, 6);
insert into ranges (name, range_start, range_end) values ('e', 3, 5);
-- assume alphabetical order by name

但我怀疑这在现实中是不可行的，因此我至少需要过滤掉所有被新的范围所掩盖的范围，就像b上面的例子一样。否则，随着数据库的增长和新范围覆盖旧范围，查询将需要传输越来越多的不相关数据。对于上面的示例，这样的查询可以返回除 之外的所有条目b，例如：

select *magic* from ranges;
-- result:
+------+-------------+-----------+
| a    |           0 |         1 |
| c    |           1 |         3 |
| e    |           3 |         5 |
| d    |           5 |         6 |
| a    |           6 |         7 |
+------+-------------+-----------+

我无法在 SQL 中构建这样的过滤器。我唯一能做的就是查询所有数据，然后在代码中计算结果，例如在 Java 中使用 Google Guava 库：

select *magic* from ranges;
-- result:
+------+-------------+-----------+
| a    |           0 |         7 |
| c    |           1 |         3 |
| d    |           4 |         6 |
| e    |           3 |         5 |
+------+-------------+-----------+

或者在 python 中手动：

final RangeMap<Integer, String> rangeMap = TreeRangeMap.create();
rangeMap.put(Range.closedOpen(0, 7), "a");
rangeMap.put(Range.closedOpen(2, 4), "b");
rangeMap.put(Range.closedOpen(1, 3), "c");
rangeMap.put(Range.closedOpen(4, 6), "d");
rangeMap.put(Range.closedOpen(3, 5), "e");
System.out.println(rangeMap);
// result: [[0..1)=a, [1..3)=c, [3..5)=e, [5..6)=d, [6..7)=a]

Answer 1

以下简单查询返回具有顶级名称的所有最小间隔：

with
 all_points(x) as (
   select range_start from ranges
   union 
   select range_end from ranges
 )
,all_ranges(range_start, range_end) as (
   select *
   from (select
           x as range_start, 
           lead(x) over(order by x) as range_end
         from all_points)
   where range_end is not null
)
select *
from all_ranges ar
     cross apply (
     select max(name) as range_name
     from ranges r
     where r.range_end   >= ar.range_end
       and r.range_start <= ar.range_start
     )
order by 1,2;

结果：

RANGE_START  RANGE_END RANGE_NAME
----------- ---------- ----------
          0          1 a
          1          2 c
          2          3 c
          3          4 e
          4          5 e
          5          6 d
          6          7 a

所以我们需要合并具有相同名称的连接区间：

最终查询没有新的 Oracle 特定功能

RANGE_START  RANGE_END RANGE_NAME
----------- ---------- ----------
          0          1 a
          1          2 c
          2          3 c
          3          4 e
          4          5 e
          5          6 d
          6          7 a

结果：

       GRP RANGE_NAME RANGE_START  RANGE_END
---------- ---------- ----------- ----------
         1 a                    0          1
         2 c                    1          3
         3 e                    3          5
         4 d                    5          6
         5 a                    6          7

或者使用实际的 Oracle 特定功能：

with
 all_ranges(range_start, range_end) as (
   select * from (
      select 
        x as range_start, 
        lead(x) over(order by x) as range_end
      from (
         select distinct x 
         from ranges 
         unpivot (x for r in (range_start,range_end))
      ))
   where range_end is not null
 )
select  *
from all_ranges ar
     cross apply (
     select max(name) as range_name
     from ranges r
     where r.range_end   >= ar.range_end
       and r.range_start <= ar.range_start
     )
match_recognize(
   order by range_start
   measures 
      first(range_start) as r_start,
      last(range_end) as r_end,
      last(range_name) as r_name
   pattern(STRT A*)
   define
     A as prev(range_name)=range_name and prev(range_end) = range_start
);