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

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 中像这样建模:

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

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

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

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

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

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

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]

或者在 python 中手动:

import re
from collections import namedtuple
from typing import Optional, List

Range = namedtuple("Range", ["name", "start", "end"])


def overlap(lhs: Range, rhs: Range) -> Optional[Range]:
    if lhs.end <= rhs.start or rhs.end <= lhs.start:
        return None
    return Range(None, min(lhs.start, rhs.start), max(lhs.end, rhs.end))


def range_from_str(str_repr: str) -> Range:
    name = re.search(r"[a-z]+", str_repr).group(0)
    start = str_repr.index("|") // 4
    end = str_repr.rindex("|") // 4
    return Range(name, start, end)


if __name__ == '__main__':
    ranges: List[Range] = [
        #               0   1   2   3   4   5   6   7
        range_from_str("|-------------a-------------|"),
        range_from_str("        |---b---|            "),
        range_from_str("    |---c---|                "),
        range_from_str("                |---d---|    "),
        range_from_str("            |---e---|        "),
        # result:       |-a-|---c---|---e---|-d-|-a-|
    ]

    result: List[Range] = []
    for range in ranges:
        for i, res in enumerate(result[:]):
            o = overlap(range, res)
            if o:
                result.append(Range(res.name, o.start, range.start))
                result.append(Range(res.name, range.end, o.end))
                result[i] = Range(res.name, 0, 0)
        result.append(range)
    result = sorted(filter(lambda r: r.start < r.end, result), key=lambda r: r.start)
    print(result)
    # result: [Range(name='a', start=0, end=1), Range(name='c', start=1, end=3), Range(name='e', start=3, end=5), Range(name='d', start=5, end=6), Range(name='a', start=6, end=7)]

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 特定功能的最终查询

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 
   grp,range_name,min(range_start) as range_start,max(range_end) as range_end
from (
   select
      sum(start_grp_flag) over(order by range_start) grp
     ,range_start,range_end,range_name
   from (
      select 
        range_start,range_end,range_name,
        case when range_name = lag(range_name)over(order by range_start) then 0 else 1 end start_grp_flag
      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
           )
   )
)
group by grp,range_name
order by 1;

结果:

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