将范围列表展平为单个结果范围集
flatten list of ranges to single result range set
我正在尝试以定义的顺序（在提供的示例中按名称的字母顺序）将范围列表“展平”为单个合并结果。较新的范围会覆盖较旧范围的值。从概念上讲，它看起来像这样，“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 的情况一样] 在上面的例子中。否则，随着数据库的增长和新范围盖过旧范围，查询将需要传输越来越多不相关的数据。对于上面的示例，这样的查询可以 return 除 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)]
我不明白你的结果——正如我在评论中解释的那样。 “b”应该存在，因为它在时间 2 最近。
就是说，我们的想法是取消时间轴并找出每次最近的名字——包括开头和结尾。然后，使用 gaps-and-islands 个想法将它们结合起来。这是查询的样子：
with r as (
select name, range_start as t
from ranges
union all
select null, range_end as t
from ranges
),
r2 as (
select r.*,
(select r2.name
from ranges r2
where r2.range_start <= r.t and
r2.range_end >= r.t
order by r2.range_start desc
fetch first 1 row only
) as imputed_name
from (select distinct t
from r
) r
)
select imputed_name, t,
lead(t) over (order by t)
from (select r2.*,
lag(imputed_name) over ( order by t) as prev_imputed_name
from r2
) r2
where prev_imputed_name is null or prev_imputed_name <> imputed_name;
Here 是一个 db<>fiddle.
基本上相同的代码也应该 运行 在 Postgres 中。
这是一个分层查询，可以为您提供所需的输出：
WITH ranges(NAME, range_start, range_end) AS
(SELECT 'a', 0, 7 FROM dual UNION ALL
SELECT 'b', 2, 4 FROM dual UNION ALL
SELECT 'c', 1, 3 FROM dual UNION ALL
SELECT 'd', 4, 6 FROM dual UNION ALL
SELECT 'e', 3, 5 FROM dual UNION ALL
SELECT 'f', -3, -2 FROM dual UNION ALL
SELECT 'g', 8, 20 FROM dual UNION ALL
SELECT 'h', 12, 14 FROM dual)
, rm (NAME, range_start, range_end) AS
(SELECT r.*
FROM (SELECT r.NAME
, r.range_start
, NVL(r2.range_start, r.range_end) range_end
FROM ranges r
OUTER apply (SELECT *
FROM ranges
WHERE range_start BETWEEN r.range_start AND r.range_end
AND NAME > r.NAME
ORDER BY range_start, NAME DESC
FETCH FIRST 1 ROWS ONLY) r2
ORDER BY r.range_start, r.NAME desc
FETCH FIRST 1 ROWS ONLY) r
UNION ALL
SELECT r2.NAME
, r2.range_start
, r2.range_end
FROM rm
CROSS apply (SELECT r.NAME
, GREATEST(rm.range_end, r.range_start) range_start
, NVL(r2.range_start, r.range_end) range_end
FROM ranges r
OUTER apply (SELECT *
FROM ranges
WHERE range_start BETWEEN GREATEST(rm.range_end, r.range_start) AND r.range_end
AND NAME > r.NAME
ORDER BY range_start, NAME DESC
FETCH FIRST 1 ROWS ONLY) r2
WHERE r.range_end > rm.range_end
AND NOT EXISTS (SELECT 1 FROM ranges r3
WHERE r3.range_end > rm.range_end
AND (GREATEST(rm.range_end, r3.range_start) < GREATEST(rm.range_end, r.range_start)
OR (GREATEST(rm.range_end, r3.range_start) = GREATEST(rm.range_end, r.range_start)
AND r3.NAME > r.NAME)))
FETCH FIRST 1 ROWS ONLY) r2)
CYCLE NAME, range_start, range_end SET cycle TO 1 DEFAULT 0
SELECT * FROM rm
首先，您将获得按 range_start desc, name 排序的第一个条目，这将为您提供名称最小的最反感条目。
然后搜索与该范围相交的具有更高名称的范围。如果有的话，这个区间的range_start就是你最后一个区间的range_end。
从这个开始，您将或多或少地搜索具有相同条件的下一个条目。
下面的简单查询returns所有具有最高名称的最小区间：
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-specific 特征的最终查询
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
);
还有另一种不太有效但更简单、更短的方法：生成所有点并聚合它们。
例如，这个简单的查询将生成所有中间点：
select x,max(name)
from ranges,
xmltable('xs:integer($A) to xs:integer($B)'
passing range_start as a
,range_end as b
columns x int path '.'
)
group by x
结果：
X M
---------- -
0 a
1 c
2 c
3 e
4 e
5 e
6 d
7 a
然后我们可以合并它们：
select *
from (
select x,max(name) name
from ranges,
xmltable('xs:integer($A) to xs:integer($B)-1'
passing range_start as a
,range_end as b
columns x int path '.'
)
group by x
order by 1
)
match_recognize(
order by x
measures
first(x) as r_start,
last(x)+1 as r_end,
last(name) as r_name
pattern(STRT A*)
define
A as prev(name)=name and prev(x)+1 = x
);
结果：
R_START R_END R
---------- ---------- -
0 1 a
1 3 c
3 5 e
5 6 d
6 7 a
我正在尝试以定义的顺序（在提供的示例中按名称的字母顺序）将范围列表“展平”为单个合并结果。较新的范围会覆盖较旧范围的值。从概念上讲，它看起来像这样，“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 的情况一样] 在上面的例子中。否则，随着数据库的增长和新范围盖过旧范围，查询将需要传输越来越多不相关的数据。对于上面的示例，这样的查询可以 return 除 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)]
我不明白你的结果——正如我在评论中解释的那样。 “b”应该存在，因为它在时间 2 最近。
就是说，我们的想法是取消时间轴并找出每次最近的名字——包括开头和结尾。然后，使用 gaps-and-islands 个想法将它们结合起来。这是查询的样子：
with r as (
select name, range_start as t
from ranges
union all
select null, range_end as t
from ranges
),
r2 as (
select r.*,
(select r2.name
from ranges r2
where r2.range_start <= r.t and
r2.range_end >= r.t
order by r2.range_start desc
fetch first 1 row only
) as imputed_name
from (select distinct t
from r
) r
)
select imputed_name, t,
lead(t) over (order by t)
from (select r2.*,
lag(imputed_name) over ( order by t) as prev_imputed_name
from r2
) r2
where prev_imputed_name is null or prev_imputed_name <> imputed_name;
Here 是一个 db<>fiddle.
基本上相同的代码也应该 运行 在 Postgres 中。
这是一个分层查询，可以为您提供所需的输出：
WITH ranges(NAME, range_start, range_end) AS
(SELECT 'a', 0, 7 FROM dual UNION ALL
SELECT 'b', 2, 4 FROM dual UNION ALL
SELECT 'c', 1, 3 FROM dual UNION ALL
SELECT 'd', 4, 6 FROM dual UNION ALL
SELECT 'e', 3, 5 FROM dual UNION ALL
SELECT 'f', -3, -2 FROM dual UNION ALL
SELECT 'g', 8, 20 FROM dual UNION ALL
SELECT 'h', 12, 14 FROM dual)
, rm (NAME, range_start, range_end) AS
(SELECT r.*
FROM (SELECT r.NAME
, r.range_start
, NVL(r2.range_start, r.range_end) range_end
FROM ranges r
OUTER apply (SELECT *
FROM ranges
WHERE range_start BETWEEN r.range_start AND r.range_end
AND NAME > r.NAME
ORDER BY range_start, NAME DESC
FETCH FIRST 1 ROWS ONLY) r2
ORDER BY r.range_start, r.NAME desc
FETCH FIRST 1 ROWS ONLY) r
UNION ALL
SELECT r2.NAME
, r2.range_start
, r2.range_end
FROM rm
CROSS apply (SELECT r.NAME
, GREATEST(rm.range_end, r.range_start) range_start
, NVL(r2.range_start, r.range_end) range_end
FROM ranges r
OUTER apply (SELECT *
FROM ranges
WHERE range_start BETWEEN GREATEST(rm.range_end, r.range_start) AND r.range_end
AND NAME > r.NAME
ORDER BY range_start, NAME DESC
FETCH FIRST 1 ROWS ONLY) r2
WHERE r.range_end > rm.range_end
AND NOT EXISTS (SELECT 1 FROM ranges r3
WHERE r3.range_end > rm.range_end
AND (GREATEST(rm.range_end, r3.range_start) < GREATEST(rm.range_end, r.range_start)
OR (GREATEST(rm.range_end, r3.range_start) = GREATEST(rm.range_end, r.range_start)
AND r3.NAME > r.NAME)))
FETCH FIRST 1 ROWS ONLY) r2)
CYCLE NAME, range_start, range_end SET cycle TO 1 DEFAULT 0
SELECT * FROM rm
首先，您将获得按 range_start desc, name 排序的第一个条目，这将为您提供名称最小的最反感条目。 然后搜索与该范围相交的具有更高名称的范围。如果有的话，这个区间的range_start就是你最后一个区间的range_end。
从这个开始，您将或多或少地搜索具有相同条件的下一个条目。
下面的简单查询returns所有具有最高名称的最小区间：
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-specific 特征的最终查询
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
);
还有另一种不太有效但更简单、更短的方法：生成所有点并聚合它们。
例如，这个简单的查询将生成所有中间点：
select x,max(name)
from ranges,
xmltable('xs:integer($A) to xs:integer($B)'
passing range_start as a
,range_end as b
columns x int path '.'
)
group by x
结果：
X M
---------- -
0 a
1 c
2 c
3 e
4 e
5 e
6 d
7 a
然后我们可以合并它们：
select *
from (
select x,max(name) name
from ranges,
xmltable('xs:integer($A) to xs:integer($B)-1'
passing range_start as a
,range_end as b
columns x int path '.'
)
group by x
order by 1
)
match_recognize(
order by x
measures
first(x) as r_start,
last(x)+1 as r_end,
last(name) as r_name
pattern(STRT A*)
define
A as prev(name)=name and prev(x)+1 = x
);
结果：
R_START R_END R
---------- ---------- -
0 1 a
1 3 c
3 5 e
5 6 d
6 7 a