Определить, полностью ли охвачен диапазон набором диапазонов

Question

Как я могу проверить, является ли диапазон полностью покрытым набором диапазонов.В следующем примере:

WITH ranges(id, a, b) AS (
    SELECT 1,  0, 40 UNION
    SELECT 2, 40, 60 UNION
    SELECT 3, 80, 100 UNION
    SELECT 4, 10, 30
), tests(id, a, b) AS (
    SELECT 1, 10, 90 UNION
    SELECT 2, 10, 60
)
SELECT *
FROM tests
WHERE -- ?

• Я хочу выбрать 10, 60, потому что все это покрыто 0, 40 и 40, 60 (и 10, 30)
• Я хочу исключить 10, 90, потому что он выставлен между 60, 80

Предположим, что a является включающим и b является эксклюзивным, т.е. значение 40 принадлежит [40, 60), а не[0, 40).Диапазоны могут содержать пробелы и всевозможные перекрытия.

Фактическая проблема связана с данными дата + время, но даты - это просто числа.Я использую сервер SQL, но предпочтительным является универсальное решение.

Answer 1

Как описано в принятом ответе, решение состоит в том, чтобы объединить перекрывающиеся диапазоны вместе, а затем определить, присутствует ли тестовый диапазон в одном из объединенных диапазонов.

Помимо объединения и / или рекурсии, вы можете использовать метод сортировки с оконными функциями для объединения перекрывающихся диапазонов:

WITH ranges(id, a, b) AS (
    SELECT 1,  0, 40 UNION
    SELECT 2, 40, 60 UNION
    SELECT 3, 80, 100 UNION
    SELECT 4, 10, 30
), tests(id, a, b) AS (
    SELECT 1, 10, 90 UNION
    SELECT 2, 10, 60
), ranges_chg AS (
    SELECT *, CASE WHEN MAX(b) OVER (ORDER BY a ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) >= a THEN 0 ELSE 1 END AS chg
    FROM ranges
), ranges_grp AS(
    SELECT *, SUM(chg) OVER (ORDER BY a) AS grp
    FROM ranges_chg
), merged_ranges AS (
    SELECT MIN(a) AS a, MAX(b) AS b
    FROM ranges_grp
    GROUP BY grp
)
SELECT *
FROM tests
WHERE EXISTS (
    SELECT 1
    FROM merged_ranges
    WHERE merged_ranges.a <= tests.a AND tests.b <= merged_ranges.b
)

Результат и Скрипка .

| id | a  | b  |
|----|----|----|
| 2  | 10 | 60 |

Данные внутри range_grpCTE даст вам представление о том, как это работает:

| id | a  | b   | max b over... | chg | grp |
|----|----|-----|---------------|-----|-----|
| 1  | 0  | 40  | NULL          | 1   | 1   |
| 4  | 10 | 30  | 40            | 0   | 1   |
| 2  | 40 | 60  | 40            | 0   | 1   |
| 3  | 80 | 100 | 60            | 1   | 2   |

Answer 2

Вам нужен рекурсивный запрос для нахождения реальных диапазонов (от 0 до 60 и от 80 до 100 в вашем случае). Мы начнем с заданных диапазонов и посмотрим на диапазоны, расширяющие их. Наконец, мы придерживаемся самых расширенных диапазонов (например, диапазон от 10 до 30 может быть расширен до 0–40, а затем до 0–60, поэтому мы сохраняем самый широкий диапазон от 0 до 60).

with wider_ranges(a, b, grp) as
(
  select a, b, id from ranges
  union all
  select
    case when r1.a < r2.a then r1.a else r2.a end,
    case when r1.b > r2.b then r1.b else r2.b end,
    r1.grp
  from wider_ranges r1
  join ranges r2 on (r2.a < r1.a and r2.b >= r1.a)
                 or (r2.b > r1.b and r2.a <= r1.b)
)
, real_ranges(a, b) as
(
  select distinct min(a), max(b)
  from wider_ranges
  group by grp
)
select * 
from tests
where exists
(
  select *
  from real_ranges
  where tests.a >= real_ranges.a and tests.b <= real_ranges.b
);

Rextester demo: http://rextester.com/BDJA16583

В соответствии с запросом это работает в SQL Server, но является стандартным SQL, поэтому он должен работать примерно на каждой СУБД с рекурсивными запросами.

Answer 3

Это рекурсивное решение, похожее на решение Торстена.Просто приведу еще один пример.

WITH ranges(id, a, b) AS (
    SELECT 1,  0, 40 UNION
    SELECT 2, 40, 60 UNION
    SELECT 3, 80, 100 UNION
    SELECT 4, 10, 30 
), tests(id, a, b) AS
(   
        SELECT 1 as id, 10 as a, 90 as b
        UNION
        SELECT 2, 10, 60
), rangeFinder(a, b, ra, rfb) AS
(
    SELECT a, b, 0 AS ra, 0 AS rfb 
    FROM ranges AS r
    UNION ALL
    SELECT rangeFinder.a, ranges.b, ranges.a, rangeFinder.b 
    FROM ranges 
    JOIN rangeFinder
        ON ranges.b > rangeFinder.b
        AND ranges.a <=rangeFinder.b
), islands(a, b) AS
(
    SELECT a, b 
    FROM rangeFinder
    WHERE a NOT IN (SELECT ra FROM rangeFinder)
        AND b NOT IN (SELECT rfb FROM rangeFinder)
)
SELECT t.id, t.a, t.b FROM 
tests t
JOIN islands i
ON t.a >= i.a
AND t.b <= i.b

Демо здесь: http://rextester.com/HDQ52126

Answer 4

Это общая форма решения.Идея состоит в том, чтобы сделать следующее:

• Получить список всех точек, которые не могут быть в диапазоне.Это все начало диапазона и конец диапазона.
• Проверьте, не входит ли какой-либо из них в диапазон.

Это основано на операции, при которой точка, находящаяся вне диапазона, будетодно из чисел, включенных в любую из таблиц:

with tc as (
      select t.test, r.candidate
      from tests t join
           (select r.a as candidate from ranges union all
            select r.b from ranges
           ) r
           on r.candiate >= t.a and r.candidate < t.b
      union all
      select t.test, t.a
      from tests t
      union all
      select t.test, t.b
      from tests t
     )
select distinct tc.test
from tc
where not exists (select 1
                  from ranges r
                  where tc.candidate >= r.a and tc.candidate < r.b
                 );

Поскольку диапазоны включают первый элемент, вам на самом деле не нужно это проверять.Таким образом, список кандидатов может быть сокращен:

with tc as (
      select t.test, r.candidate
      from tests t join
           (select r.b as candidate from ranges
           ) r
           on r.candidate >= t.a and r.r < t.b
      union all
      select t.test, t.a
      from tests t
      union all
      select t.test, t.b
      from tests t
     )