SQL 挑战/谜题 : How to merge nested ranges?

Question

• 此挑战基于涉及 IP 范围的现实用例。
• 我提供的解决方案基于 stack trace我之前提出过的挑战。每个范围开始都被视为PUSH操作，每个范围结束+1被视为POP操作。

<小时/>

挑战

我们有一个范围数据集，其中每个范围都有起点、终点和值。

create table ranges
(
    range_start     int         not null
   ,range_end       int         not null
   ,range_val       char(1)     not null
)
;

一个范围可以包含另一个范围或跟随另一个范围，但不能等于另一个范围或与另一个范围相交。

这些是范围之间的有效关系:

(1)           (2)           (3)           (4)
---------     ---------     ---------     -------- -----------
---                 ---        ---

这些关系无效:

(5)                (6)
-------        --------       
-------              --------

我们的初始范围，当以图形方式呈现时，可能看起来像这样(字母代表range_val):

AAAAAAAA  BBCCCCCCC
 DDE   F   GGGGG
   H       IIII
             J

目标是采用初始范围集并根据以下规则创建新集:

包含范围将覆盖包含范围的相应子范围。

请求的结果以图形方式呈现时可能如下所示

ADDHAAAF  BIIJIGCCC

要求

• 解决方案应该是单个 SQL 查询(子查询也可以)。
• 不允许使用 T-SQL、PL/SQL 等。
• 不允许使用 UDF(用户定义函数)。

数据样本

AAAAAAAAAAAAAAAAAAAAAAAAAAAA  BBBB    CCCCCCCCCCCCCCCCCCCCCCCCC
DDDE  FFFFFFFF    GGGGGGGGG               HHHHHHHH    IIIIIII
JJ      KKKLLL       MM NN                              OOOOO
            P                                              QQ

insert into ranges (range_start,range_end,range_val) values (1  ,28 ,'A');
insert into ranges (range_start,range_end,range_val) values (31 ,34 ,'B');
insert into ranges (range_start,range_end,range_val) values (39 ,63 ,'C');
insert into ranges (range_start,range_end,range_val) values (1  ,3  ,'D');
insert into ranges (range_start,range_end,range_val) values (4  ,4  ,'E');
insert into ranges (range_start,range_end,range_val) values (7  ,14 ,'F');
insert into ranges (range_start,range_end,range_val) values (19 ,27 ,'G');
insert into ranges (range_start,range_end,range_val) values (43 ,50 ,'H');
insert into ranges (range_start,range_end,range_val) values (55 ,61 ,'I');
insert into ranges (range_start,range_end,range_val) values (1  ,2  ,'J');
insert into ranges (range_start,range_end,range_val) values (9  ,11 ,'K');
insert into ranges (range_start,range_end,range_val) values (12 ,14 ,'L');
insert into ranges (range_start,range_end,range_val) values (22 ,23 ,'M');
insert into ranges (range_start,range_end,range_val) values (25 ,26 ,'N');
insert into ranges (range_start,range_end,range_val) values (57 ,61 ,'O');
insert into ranges (range_start,range_end,range_val) values (13 ,13 ,'P');
insert into ranges (range_start,range_end,range_val) values (60 ,61 ,'Q');

请求的结果

(Null 在这里显示为空格)

JJDEAAFFKKKLPLAAAAGGGMMGNNGA  BBBB    CCCCHHHHHHHHCCCCIIOOOQQCC

range_start range_end range_val
----------- --------- ---------
1           2          J
3           3          D
4           4          E
5           6          A
7           8          F
9           11         K
12          12         L
13          13         P
14          14         L
15          18         A
19          21         G
22          23         M
24          24         G
25          26         N
27          27         G
28          28         A
29          30         
31          34         B
35          38         
39          42         C
43          50         H
51          54         C
55          56         I
57          59         O
60          61         Q
62          63         C

可选添加最后一行:

64

Answer 1

Oracle 解决方案:

with l as ( select level lvl from dual connect by level < 66 ),
     r as ( select range_start r1, range_end r2, range_val v, 
                    range_end - range_start + 1 cnt 
              from ranges ),
     t1 as (select distinct lvl, 
                   nvl(max(v) keep (dense_rank first order by cnt) 
                              over (partition by lvl), '*' ) m
              from l left join r on lvl between r1 and r2 ),
     t2 as (select lvl, m, case when lag(m) over (order by lvl) <> m then 0 else 1 end mrk 
              from t1),
     t3 as (select lvl, m, lvl - sum(mrk) over (order by lvl) grp from t2)
select min(lvl) r1, max(lvl) r2, nullif(min(m), '*') val
  from t3 group by grp order by r1

输出按要求。我的英语很差，所以很难解释，但让我们尝试一下:

• l - 数字生成器，
• r - 来自范围的数据以及计算的距离，
• t1 - 查找每个级别的最小距离值，
• t2 - 添加标记来告诉范围是否开始，
• t3 - 添加我们接下来将使用的列对数据进行分组。