I am trying to "flatten" a list of ranges in a defined order (alphabetically by name in the examples provided) to a single merged result. Newer Ranges overwrite values of older ranges. Conceptually it looks like this, with "e" being the newest range:
0 1 2 3 4 5 6 7
|-------------a-------------|
|---b---|
|---c---|
|---d---|
|---e---|
|-a-|---c---|---e---|-d-|-a-| <-- expected result
To prevent further confusion: The expected result here is indeed correct. The values 0 - 7 are just the ranges' values, not a progression in time. I use integers for simplicity here, but the values might not be discrete but continuous.
Note that b is completely overshadowed and not relevant anymore.
the data may be modeled like this in 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
It would be perfect if there was a way to directly query the result in SQL, e.g. like this:
select *magic* from ranges;
-- result:
+------+-------------+-----------+
| a | 0 | 1 |
| c | 1 | 3 |
| e | 3 | 5 |
| d | 5 | 6 |
| a | 6 | 7 |
+------+-------------+-----------+
But I suspect that is not realistically feasible, therefore I need to at least filter out all ranges that are overshadowed by newer ones, as is the case for b in the example above. Otherwise the query would need to transfer more and more irrelevant data as the database grows and new ranges overshadow older ones. For the example above, such a query could return all entries except for b, e.g.:
select *magic* from ranges;
-- result:
+------+-------------+-----------+
| a | 0 | 7 |
| c | 1 | 3 |
| d | 4 | 6 |
| e | 3 | 5 |
+------+-------------+-----------+
I was unable to construct such a filter in SQL. The only thing I managed to do is query all data and then calculate the result in code, for example in Java using the Google Guava library:
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]
Or by hand in 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)]
The following simple query returns all smallest intervals with top name:
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;
Results:
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
So we need to merge connected intervals with the same names:
Final query without new oracle-specific features
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;
Results:
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
Or using actual oracle specific features:
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
);