确定范围是否完全被一组范​​围覆盖 [英] Determine if a range is completely covered by a set of ranges

问题描述

如何检查范围是否被一组范围 完全覆盖 。在下面的示例中：

How can I check if a range is completely covered by a set of ranges. In the following example:

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


• I want to select 10, 60 because all of it is covered by 0, 40 and 40, 60 (and 10, 30)
• I want to exclude 10, 90 because it is exposed between 60, 80

假定 a 是包含的，而 b 是唯一的，即值 40 属于 [40，60）而不是 [0，40）。范围可以包含空白和各种重叠。

Assume that a is inclusive and b is exclusive i.e. the value 40 belongs to [40, 60) and not [0, 40). The ranges can contain gaps and all kind of overlaps.

实际的问题涉及日期和时间数据，但日期只是数字。我正在使用SQL Server，但首选通用解决方案。

The actual problem involves date+time data but dates are just numbers. I am using SQL server but generic solution is preferred.

推荐答案

您希望使用递归查询来查找实际范围（0到60以及80至100）。我们将从给出的范围开始，然后寻找扩展这些范围的范围。最后，我们坚持使用最大范围的扩展（例如，可以将范围10到30扩展到0到40，然后扩展到0到60，因此我们将最宽的范围保持在0到60）。

You want a recursive query finding the real ranges (0 to 60 and 80 to 100 in your case). We'd start with the ranges given and look for ranges extending these. At last we stick with the most extended ranges (e.g. the range 10 to 30 can be extended to 0 to 40 and then to 0 to 60, so we keep the widest range 0 to 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
);

Rester演示： http://rextester.com/BDJA16583

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

根据要求，此方法在SQL Server中有效，但它是标准SQL，因此应在关于每个具有递归查询的DBMS。

As requested this works in SQL Server, but is standard SQL, so it should work in about every DBMS featuring recursive queries.

这篇关于确定范围是否完全被一组范​​围覆盖的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！