Check if two infinite intervals overlap

user_6443997 0
Viewed 85

I have a table where information about the execution-interval of tasks is stored. Every Task has a starting year and the interval for the execution. E.g. Start 2020, interval = 2 years would mean the task will be executed in 2020,2022,2024 and so on.

How can I check if there are overlapping intervals in the table?

ID  |   StartYear |    Interval
____|_____________|___________
1   |   2020      |    3
2   |   2019      |    4
3   |   2020      |    5
4   |   2019      |    2
5   |   2020      |    2

Result: Task 1 and two overlap (first time in 2023), Task 2 and 3 overlap (first time in2035), task 1 and 3 overlap (first time in 2020, then 2035), task 4 and 5 do not overlap each other (one is always on even years, the other on uneven years) and so on.

So mathematically, I want to know how to check if two infinite sets are disjoint. My problem is, I don't know how to even represent an infinite set by the data I have in MS-SQL.

The endresult would be a query (or function) that you can give a starting year and an interval as a parameter that returns all overlapping entries.

Example 1

Given a starting year of 2020 and an interval of 2, the set to compare against would be 2020,2022,2024,2026 etc. That's why in the result ID 2 and 4 are not selected, because they both start at an uneven year and the interval is an even number, meaning the execution year will always be an uneven year, which is not in the comparison set of 2020,2022,2024 etc.

Declare @CompareStart int = 2020;
Declare @CompareInterval int = 2;

SELECT * FROM MYTABLE WHERE OVERLAPPING(@CompareStart, @CompareInterval)

Result would be:

ID  |   StartYear |    Interval
____|_____________|___________
1   |   2020      |    3
3   |   2020      |    5
5   |   2020      |    2

Example 2

For a starting year of 2019 and an interval of 3, the resultset would be the rows with IDs 2 (first hit 2019), 3 (first hit 2025), 4 (first hit 2019) and 5 (first hit 2022).

Declare @CompareStart int = 2019;
Declare @CompareInterval int = 3;

SELECT * FROM MYTABLE WHERE OVERLAPPING(@CompareStart, @CompareInterval)

Result would be:

ID  |   StartYear |    Interval
____|_____________|___________
2   |   2019      |    4
3   |   2020      |    5
4   |   2019      |    2
5   |   2020      |    2
sql-server
2 Answers

Given this sample data:

CREATE TABLE #t(ID int PRIMARY KEY, StartYear int, Interval int);

INSERT #t(ID, StartYear, Interval) VALUES
(1,2020,3),
(2,2019,4),
(3,2020,5),
(4,2019,2),
(5,2020,2);

We can use two recursive CTEs, one for the full set of comparison dates based on the starting year and defined comparison interval, and another to get all the dates in the table, for each ID, based on its starting year and execution interval. Once we have these two sets, we can join them where they intersect. Play with the input params and uncomment the FirstHit_ForSanityCheck line to be sure that, for any given year/interval, the first "hit" is correctly identified.

-- input params
DECLARE @StartYear       int = 2019, 
        @CompareInterval int = 3;
        
-- local variables
DECLARE @LimitOfRange int = 100; -- to keep recursion <= 100!

-- recursive CTE to derive full set of comparison dates
;WITH CompareDates(Lvl, TheYear) AS
(
  SELECT Lvl = 0, @StartYear
  UNION ALL
  SELECT Lvl + 1, @StartYear + (Lvl + 1)*@CompareInterval
  FROM CompareDates
  WHERE Lvl < @LimitOfRange / @CompareInterval
),
-- to derive set of execution dates for each ID
TableDates AS
(
  SELECT ID, Lvl = 0, TheYear = StartYear, Interval
  FROM #t
  UNION ALL
  SELECT ID, Lvl + 1, TheYear + (Lvl + 1)*Interval, Interval
  FROM TableDates
  WHERE Lvl < @LimitOfRange / Interval
)
SELECT td.ID, 
       TheYear = MIN(td.TheYear), 
       td.Interval
       --, FirstHit_ForSanityCheck = MIN(cd.TheYear)
FROM CompareDates AS cd
INNER JOIN TableDates AS td
ON cd.TheYear = td.TheYear
GROUP BY td.ID, td.Interval
ORDER BY td.ID;

Output:

ID   StartYear   Interval
--   ---------   --------
2    2019        4
3    2020        5
4    2019        2
5    2020        2

Working fiddle.

user_613050

You could use the CTE to create the year list for each task and do the inner join later.

Examples for creating the year list for task #2 is provided below, you could insert the result into the table for each task, then the inner join between each result to find the overlapping year.

DECLARE @StartYear DATE = '2019-01-01' --Month and Day does not matter here
DECLARE @Interval INT = '4'
DECLARE @MAXDate DATE = '3000-01-01'  --change to 9999 if you want a 'Infinite' list

;WITH CTE_GenerateEachYear (Dates)
AS
(
   SELECT @StartYear 
   UNION ALL
   SELECT DATEADD(YEAR,@Interval,Dates)
   FROM CTE_GenerateEachYear
   WHERE Dates < @MAXDate
)
SELECT * FROM CTE_GenerateEachYear --could be replaced by an insert statment to be populated to a table
WHERE Dates<@MAXDate
OPTION (MAXRECURSION 0)
user_69017880
Related