I need to convert data between two systems.
First system stores schedules as a plain list of dates. Each date that is included in the schedule is one row.
There can be various gaps in the sequence of dates (weekends, public holidays and longer pauses, some days of the week may be excluded from the schedule). There can be no gaps at all, even weekends can be included. The schedule can be up to 2 years long. Usually it is few weeks long.
Here is a simple example of a schedule that spans two weeks excluding weekends (there are more complicated examples in the script below):
+----+------------+------------+---------+--------+
| ID | ContractID | dt | dowChar | dowInt |
+----+------------+------------+---------+--------+
| 10 | 1 | 2016-05-02 | Mon | 2 |
| 11 | 1 | 2016-05-03 | Tue | 3 |
| 12 | 1 | 2016-05-04 | Wed | 4 |
| 13 | 1 | 2016-05-05 | Thu | 5 |
| 14 | 1 | 2016-05-06 | Fri | 6 |
| 15 | 1 | 2016-05-09 | Mon | 2 |
| 16 | 1 | 2016-05-10 | Tue | 3 |
| 17 | 1 | 2016-05-11 | Wed | 4 |
| 18 | 1 | 2016-05-12 | Thu | 5 |
| 19 | 1 | 2016-05-13 | Fri | 6 |
+----+------------+------------+---------+--------+
ID
is unique, but it is not necessarily sequential (it is primary key).
Dates are unique within each Contract (there is unique index on (ContractID, dt)
).
Second system stores schedules as intervals with the list of week days that are part of the schedule. Each interval is defined by its start and end dates (inclusive) and a list of week days that are included in the schedule. In this format you can efficiently define repetitive weekly patterns, such as Mon-Wed, but it becomes a pain when a pattern is disrupted, for example by public holiday.
Here is how the simple example above will look like:
+------------+------------+------------+----------+----------------------+
| ContractID | StartDT | EndDT | DayCount | WeekDays |
+------------+------------+------------+----------+----------------------+
| 1 | 2016-05-02 | 2016-05-13 | 10 | Mon,Tue,Wed,Thu,Fri, |
+------------+------------+------------+----------+----------------------+
[StartDT;EndDT]
intervals that belong to the same Contract should not overlap.
I need to convert data from the first system into the format used by the second system.
At the moment I'm solving this on the client side in C# for the single given Contract,
but I'd like to do it in T-SQL on the server side for bulk processing and export/import between servers.
Most likely, it could be done using CLR UDF, but at this stage I can't use SQLCLR.
The challenge here is to make the list of intervals as short and human-friendly as possible.
For example, this schedule:
+-----+------------+------------+---------+--------+
| ID | ContractID | dt | dowChar | dowInt |
+-----+------------+------------+---------+--------+
| 223 | 2 | 2016-05-05 | Thu | 5 |
| 224 | 2 | 2016-05-06 | Fri | 6 |
| 225 | 2 | 2016-05-09 | Mon | 2 |
| 226 | 2 | 2016-05-10 | Tue | 3 |
| 227 | 2 | 2016-05-11 | Wed | 4 |
| 228 | 2 | 2016-05-12 | Thu | 5 |
| 229 | 2 | 2016-05-13 | Fri | 6 |
| 230 | 2 | 2016-05-16 | Mon | 2 |
| 231 | 2 | 2016-05-17 | Tue | 3 |
+-----+------------+------------+---------+--------+
should become this:
+------------+------------+------------+----------+----------------------+
| ContractID | StartDT | EndDT | DayCount | WeekDays |
+------------+------------+------------+----------+----------------------+
| 2 | 2016-05-05 | 2016-05-17 | 9 | Mon,Tue,Wed,Thu,Fri, |
+------------+------------+------------+----------+----------------------+
,not this:
+------------+------------+------------+----------+----------------------+
| ContractID | StartDT | EndDT | DayCount | WeekDays |
+------------+------------+------------+----------+----------------------+
| 2 | 2016-05-05 | 2016-05-06 | 2 | Thu,Fri, |
| 2 | 2016-05-09 | 2016-05-13 | 5 | Mon,Tue,Wed,Thu,Fri, |
| 2 | 2016-05-16 | 2016-05-17 | 2 | Mon,Tue, |
+------------+------------+------------+----------+----------------------+
I tried to apply a gaps-and-islands
approach to this problem. I tried to do it in two passes. In the first pass I find islands of simple consecutive days, i.e. the end of the island is any gap in the sequence of days, be it weekend, public holiday or something else. For each such found island I build a comma-separated list of distinct WeekDays
. In the second pass I group found islands further by looking at the gap in the sequence of week numbers or a change in the WeekDays
.
With this approach each partial week ends up as an extra interval as shown above, because even though week numbers are consecutive, the WeekDays
change. Besides, there can be regular gaps within a week (see ContractID=3
in sample data, which has data only for Mon,Wed,Fri,
) and this approach would generate separate intervals for each day in such schedule. On the bright side, it generates one interval if the schedule doesn't have any gaps at all (see ContractID=7
in the sample data that includes weekends) and in that case it doesn't matter if the start or end week is partial.
Please see other examples in the script below to get a better idea of what I'm after. You can see that quite often weekends are excluded, but any other days of the week could also be excluded. In example 3 only Mon
, Wed
and Fri
are part of the schedule. Besides, weekends can be included, as in example 7. The solution should treat all days of the week equally. Any day of the week can be included or excluded from the schedule.
To verify that the generated list of intervals describes the given schedule correctly you can use the following pseudo-code:
- loop through all intervals
- for each interval loop through all calendar dates between Start and End dates (inclusive).
- for each date check if its day of the week is listed in the
WeekDays
. If yes, then this date is included in the schedule.
Hopefully, this clarifies in what cases a new interval should be created. In examples 4 and 5 one Monday (2016-05-09
) is removed from the middle of the schedule and such schedule can't be represented by a single interval. In example 6 there is a long gap in the schedule, so two intervals are needed.
Intervals represent weekly patterns in the schedule and when a pattern is disrupted/changed the new interval has to be added. In example 11 first three weeks have a pattern Tue
, then this pattern changes to Thu
. As a result we need two intervals to describe such schedule.
I'm using SQL Server 2008 at the moment, so solution should work in this version.
If a solution for SQL Server 2008 can be simplified/improved using features from later versions, that's a bonus, please show it as well.
I have a Calendar
table (list of dates) and Numbers
table (list of integer numbers starting from 1), so it is OK to use them, if needed. It is also OK to create temporary tables and have several queries that process data in several stages. The number of stages in an algorithm has to be fixed though, cursors and explicit WHILE
loops are not OK.
Script for sample data and expected results
-- @Src is sample data
-- @Dst is expected result
DECLARE @Src TABLE (ID int PRIMARY KEY, ContractID int, dt date, dowChar char(3), dowInt int);
INSERT INTO @Src (ID, ContractID, dt, dowChar, dowInt) VALUES
-- simple two weeks (without weekend)
(110, 1, '2016-05-02', 'Mon', 2),
(111, 1, '2016-05-03', 'Tue', 3),
(112, 1, '2016-05-04', 'Wed', 4),
(113, 1, '2016-05-05', 'Thu', 5),
(114, 1, '2016-05-06', 'Fri', 6),
(115, 1, '2016-05-09', 'Mon', 2),
(116, 1, '2016-05-10', 'Tue', 3),
(117, 1, '2016-05-11', 'Wed', 4),
(118, 1, '2016-05-12', 'Thu', 5),
(119, 1, '2016-05-13', 'Fri', 6),
-- a partial end of the week, the whole week, partial start of the week (without weekends)
(223, 2, '2016-05-05', 'Thu', 5),
(224, 2, '2016-05-06', 'Fri', 6),
(225, 2, '2016-05-09', 'Mon', 2),
(226, 2, '2016-05-10', 'Tue', 3),
(227, 2, '2016-05-11', 'Wed', 4),
(228, 2, '2016-05-12', 'Thu', 5),
(229, 2, '2016-05-13', 'Fri', 6),
(230, 2, '2016-05-16', 'Mon', 2),
(231, 2, '2016-05-17', 'Tue', 3),
-- only Mon, Wed, Fri are included across two weeks plus partial third week
(310, 3, '2016-05-02', 'Mon', 2),
(311, 3, '2016-05-04', 'Wed', 4),
(314, 3, '2016-05-06', 'Fri', 6),
(315, 3, '2016-05-09', 'Mon', 2),
(317, 3, '2016-05-11', 'Wed', 4),
(319, 3, '2016-05-13', 'Fri', 6),
(330, 3, '2016-05-16', 'Mon', 2),
-- a whole week (without weekend), in the second week Mon is not included
(410, 4, '2016-05-02', 'Mon', 2),
(411, 4, '2016-05-03', 'Tue', 3),
(412, 4, '2016-05-04', 'Wed', 4),
(413, 4, '2016-05-05', 'Thu', 5),
(414, 4, '2016-05-06', 'Fri', 6),
(416, 4, '2016-05-10', 'Tue', 3),
(417, 4, '2016-05-11', 'Wed', 4),
(418, 4, '2016-05-12', 'Thu', 5),
(419, 4, '2016-05-13', 'Fri', 6),
-- three weeks, but without Mon in the second week (no weekends)
(510, 5, '2016-05-02', 'Mon', 2),
(511, 5, '2016-05-03', 'Tue', 3),
(512, 5, '2016-05-04', 'Wed', 4),
(513, 5, '2016-05-05', 'Thu', 5),
(514, 5, '2016-05-06', 'Fri', 6),
(516, 5, '2016-05-10', 'Tue', 3),
(517, 5, '2016-05-11', 'Wed', 4),
(518, 5, '2016-05-12', 'Thu', 5),
(519, 5, '2016-05-13', 'Fri', 6),
(520, 5, '2016-05-16', 'Mon', 2),
(521, 5, '2016-05-17', 'Tue', 3),
(522, 5, '2016-05-18', 'Wed', 4),
(523, 5, '2016-05-19', 'Thu', 5),
(524, 5, '2016-05-20', 'Fri', 6),
-- long gap between two intervals
(623, 6, '2016-05-05', 'Thu', 5),
(624, 6, '2016-05-06', 'Fri', 6),
(625, 6, '2016-05-09', 'Mon', 2),
(626, 6, '2016-05-10', 'Tue', 3),
(627, 6, '2016-05-11', 'Wed', 4),
(628, 6, '2016-05-12', 'Thu', 5),
(629, 6, '2016-05-13', 'Fri', 6),
(630, 6, '2016-05-16', 'Mon', 2),
(631, 6, '2016-05-17', 'Tue', 3),
(645, 6, '2016-06-06', 'Mon', 2),
(646, 6, '2016-06-07', 'Tue', 3),
(647, 6, '2016-06-08', 'Wed', 4),
(648, 6, '2016-06-09', 'Thu', 5),
(649, 6, '2016-06-10', 'Fri', 6),
(655, 6, '2016-06-13', 'Mon', 2),
(656, 6, '2016-06-14', 'Tue', 3),
(657, 6, '2016-06-15', 'Wed', 4),
(658, 6, '2016-06-16', 'Thu', 5),
(659, 6, '2016-06-17', 'Fri', 6),
-- two weeks, no gaps between days at all, even weekends are included
(710, 7, '2016-05-02', 'Mon', 2),
(711, 7, '2016-05-03', 'Tue', 3),
(712, 7, '2016-05-04', 'Wed', 4),
(713, 7, '2016-05-05', 'Thu', 5),
(714, 7, '2016-05-06', 'Fri', 6),
(715, 7, '2016-05-07', 'Sat', 7),
(716, 7, '2016-05-08', 'Sun', 1),
(725, 7, '2016-05-09', 'Mon', 2),
(726, 7, '2016-05-10', 'Tue', 3),
(727, 7, '2016-05-11', 'Wed', 4),
(728, 7, '2016-05-12', 'Thu', 5),
(729, 7, '2016-05-13', 'Fri', 6),
-- no gaps between days at all, even weekends are included, with partial weeks
(805, 8, '2016-04-30', 'Sat', 7),
(806, 8, '2016-05-01', 'Sun', 1),
(810, 8, '2016-05-02', 'Mon', 2),
(811, 8, '2016-05-03', 'Tue', 3),
(812, 8, '2016-05-04', 'Wed', 4),
(813, 8, '2016-05-05', 'Thu', 5),
(814, 8, '2016-05-06', 'Fri', 6),
(815, 8, '2016-05-07', 'Sat', 7),
(816, 8, '2016-05-08', 'Sun', 1),
(825, 8, '2016-05-09', 'Mon', 2),
(826, 8, '2016-05-10', 'Tue', 3),
(827, 8, '2016-05-11', 'Wed', 4),
(828, 8, '2016-05-12', 'Thu', 5),
(829, 8, '2016-05-13', 'Fri', 6),
(830, 8, '2016-05-14', 'Sat', 7),
-- only Mon-Wed included, two weeks plus partial third week
(910, 9, '2016-05-02', 'Mon', 2),
(911, 9, '2016-05-03', 'Tue', 3),
(912, 9, '2016-05-04', 'Wed', 4),
(915, 9, '2016-05-09', 'Mon', 2),
(916, 9, '2016-05-10', 'Tue', 3),
(917, 9, '2016-05-11', 'Wed', 4),
(930, 9, '2016-05-16', 'Mon', 2),
(931, 9, '2016-05-17', 'Tue', 3),
-- only Thu-Sun included, three weeks
(1013,10,'2016-05-05', 'Thu', 5),
(1014,10,'2016-05-06', 'Fri', 6),
(1015,10,'2016-05-07', 'Sat', 7),
(1016,10,'2016-05-08', 'Sun', 1),
(1018,10,'2016-05-12', 'Thu', 5),
(1019,10,'2016-05-13', 'Fri', 6),
(1020,10,'2016-05-14', 'Sat', 7),
(1021,10,'2016-05-15', 'Sun', 1),
(1023,10,'2016-05-19', 'Thu', 5),
(1024,10,'2016-05-20', 'Fri', 6),
(1025,10,'2016-05-21', 'Sat', 7),
(1026,10,'2016-05-22', 'Sun', 1),
-- only Tue for first three weeks, then only Thu for the next three weeks
(1111,11,'2016-05-03', 'Tue', 3),
(1116,11,'2016-05-10', 'Tue', 3),
(1131,11,'2016-05-17', 'Tue', 3),
(1123,11,'2016-05-19', 'Thu', 5),
(1124,11,'2016-05-26', 'Thu', 5),
(1125,11,'2016-06-02', 'Thu', 5),
-- one week, then one week gap, then one week
(1210,12,'2016-05-02', 'Mon', 2),
(1211,12,'2016-05-03', 'Tue', 3),
(1212,12,'2016-05-04', 'Wed', 4),
(1213,12,'2016-05-05', 'Thu', 5),
(1214,12,'2016-05-06', 'Fri', 6),
(1215,12,'2016-05-16', 'Mon', 2),
(1216,12,'2016-05-17', 'Tue', 3),
(1217,12,'2016-05-18', 'Wed', 4),
(1218,12,'2016-05-19', 'Thu', 5),
(1219,12,'2016-05-20', 'Fri', 6);
SELECT ID, ContractID, dt, dowChar, dowInt
FROM @Src
ORDER BY ContractID, dt;
DECLARE @Dst TABLE (ContractID int, StartDT date, EndDT date, DayCount int, WeekDays varchar(255));
INSERT INTO @Dst (ContractID, StartDT, EndDT, DayCount, WeekDays) VALUES
(1, '2016-05-02', '2016-05-13', 10, 'Mon,Tue,Wed,Thu,Fri,'),
(2, '2016-05-05', '2016-05-17', 9, 'Mon,Tue,Wed,Thu,Fri,'),
(3, '2016-05-02', '2016-05-16', 7, 'Mon,Wed,Fri,'),
(4, '2016-05-02', '2016-05-06', 5, 'Mon,Tue,Wed,Thu,Fri,'),
(4, '2016-05-10', '2016-05-13', 4, 'Tue,Wed,Thu,Fri,'),
(5, '2016-05-02', '2016-05-06', 5, 'Mon,Tue,Wed,Thu,Fri,'),
(5, '2016-05-10', '2016-05-20', 9, 'Mon,Tue,Wed,Thu,Fri,'),
(6, '2016-05-05', '2016-05-17', 9, 'Mon,Tue,Wed,Thu,Fri,'),
(6, '2016-06-06', '2016-06-17', 10, 'Mon,Tue,Wed,Thu,Fri,'),
(7, '2016-05-02', '2016-05-13', 12, 'Sun,Mon,Tue,Wed,Thu,Fri,Sat,'),
(8, '2016-04-30', '2016-05-14', 15, 'Sun,Mon,Tue,Wed,Thu,Fri,Sat,'),
(9, '2016-05-02', '2016-05-17', 8, 'Mon,Tue,Wed,'),
(10,'2016-05-05', '2016-05-22', 12, 'Sun,Thu,Fri,Sat,'),
(11,'2016-05-03', '2016-05-17', 3, 'Tue,'),
(11,'2016-05-19', '2016-06-02', 3, 'Thu,'),
(12,'2016-05-02', '2016-05-06', 5, 'Mon,Tue,Wed,Thu,Fri,'),
(12,'2016-05-16', '2016-05-20', 5, 'Mon,Tue,Wed,Thu,Fri,');
SELECT ContractID, StartDT, EndDT, DayCount, WeekDays
FROM @Dst
ORDER BY ContractID, StartDT;
Comparison of answers
The real table @Src
has 403,555
rows with 15,857
distinct ContractIDs
.
All answers produce correct results (at least for my data) and all of them are reasonably fast, but they differ in optimality. The less intervals generated, the better. I included run times just for curiosity. The main focus is the correct and optimal result, not the speed (unless it takes too long – I stopped the non-recursive query by Ziggy Crueltyfree Zeitgeister after 10 minutes).
+--------------------------------------------------------+-----------+---------+
| Answer | Intervals | Seconds |
+--------------------------------------------------------+-----------+---------+
| Ziggy Crueltyfree Zeitgeister | 25751 | 7.88 |
| While loop | | |
| | | |
| Ziggy Crueltyfree Zeitgeister | 25751 | 8.27 |
| Recursive | | |
| | | |
| Michael Green | 25751 | 22.63 |
| Recursive | | |
| | | |
| Geoff Patterson | 26670 | 4.79 |
| Weekly gaps-and-islands with merging of partial weeks | | |
| | | |
| Vladimir Baranov | 34560 | 4.03 |
| Daily, then weekly gaps-and-islands | | |
| | | |
| Mikael Eriksson | 35840 | 0.65 |
| Weekly gaps-and-islands | | |
+--------------------------------------------------------+-----------+---------+
| Vladimir Baranov | 25751 | 121.51 |
| Cursor | | |
+--------------------------------------------------------+-----------+---------+
Best Answer
This one uses a recursive CTE. Its result is identical to the example in the question. It was a nightmare to come up with... The code includes comments to ease through its convoluted logic.
Another strategy
This one should be significantly faster than the previous one because it doesn't rely on the slow limited recursive CTE in SQL Server 2008, although it implements more or less the same strategy.
There is a
WHILE
loop (I couldn't devise a way to avoid it), but goes for a reduced number of iterations (the highest number of sequences (minus one) on any given contract).It's a simple strategy, and could be used for sequences either shorter or longer than a week (replacing any occurrence of the constant 7 for any other number, and the
dowBit
calculated from MODULUS x ofDayNo
rather thanDATEPART(wk)
) and up to 32.