W zestawie nakładających się, numerowanych w odstępach, numeracji, znajdź najnowszą wersję w każdym punkcie czasowym

Question

Pracuję z zestawem przedziałów daty, w których każdy interwał ma numer wersji, a nowe interwały często nakładają się na stare, lub nawet być ich podzbiorami. Na podstawie tych danych muszę obliczyć nowy zestaw interwałów, który pokazuje najnowszy numer wersji w każdym momencie. Czy istnieje rozwiązanie tego problemu oparte na zestawie?

Oto ilustracja:

Interval 1: 11111111111111111111111  
Interval 2:  2222222222    
Interval 3: 33333333333333    
Interval 4:      444444444 
Interval 5:     555555555 
Result : 11333333333333331155555555544 

Oto próbka danych pracuję z:

groupId startDate endDate  version 
-------- --------- ---------- ------ 
1   1/1/2010 1/1/2011 1 
1   10/1/2010 7/5/2011 2 
1   7/5/2011 8/13/2012 3 
1   8/13/2012 12/31/2012 6 
1   10/1/2012 11/1/2012 8 

... a sygnał wyjściowy:

groupId startDate endDate  version 
-------- --------- ---------- ------ 
1   1/1/2010 10/1/2010 1 
1   10/1/2010 7/5/2011 2 
1   7/5/2011 8/13/2012 3 
1   8/13/2011 10/1/2012 6 
1   10/1/2012 11/1/2012 8 << note how version 8 supersedes version 6 
1   11/1/2012 12/31/2012 6 << version 6 is split into two records 

Nie znalazłem żadnych innych przykładów tego problemu, moje googlowanie wyświetla tylko zapytania identyfikujące gaps and islands lub covering sets.

Myślę, że mam rozwiązanie iteracyjne (SQL Server 2008). Zaczyna się od tabeli temp dla przedziałów w zestawie wyników i definiuje punkt początkowy i końcowy zakresu, który chcemy pokryć, wstawiając rekordy o specjalnych numerach wersji. Wtedy to wielokrotnie identyfikuje luki między ustalonych odstępach wynikowych i próbuje wypełnić je z najnowszych płyt z oryginalnego zbioru danych, dopóki nie ma więcej luk lub nie więcej rekordów dodać:

GO 
-- Create data set and results table 
CREATE TABLE #Data (
    groupId INT 
    ,startDate DATE 
    ,endDate DATE 
    ,versionId INT 
) 

INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (1, '2007-12-22', '2008-12-22', 8) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (1, '2008-12-22', '2009-12-22', 9) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (1, '2009-12-22', '2010-12-22', 10) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (1, '2010-12-22', '2011-12-22', 11) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (1, '2011-01-01', '2011-11-30', 500) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (1, '2011-12-22', '2012-12-22', 12) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (1, '2012-01-22', '2012-12-22', 13) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (1, '2012-01-22', '2012-12-22', 14) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (1, '2012-04-22', '2012-12-22', 17) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (1, '2012-04-22', '2012-12-22', 19) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (2, '2010-01-01', '2011-01-01', 1) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (2, '2010-10-01', '2011-07-05', 2) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (2, '2011-07-05', '2012-08-13', 3) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (2, '2012-08-13', '2012-12-31', 6) 
INSERT INTO #Data (groupId, startDate, endDate, versionId) VALUES (2, '2012-10-01', '2012-11-01', 8) 


CREATE TABLE #Results (
    groupId  VARCHAR(10) 
    ,startDate DATE 
    ,endDate DATE 
    ,versionId  BIGINT 
) 

DECLARE @startDate  DATE 
DECLARE @endDate  DATE 
DECLARE @placeholderId BIGINT 

SET @startDate = '20030101' 
SET @endDate = '20121231' 
SET @placeholderId = 999999999999999 

INSERT #Results 
SELECT DISTINCT 
    groupId 
    ,CASE WHEN MIN(startDate) < @startDate THEN MIN(startDate) ELSE @startDate END 
    ,CASE WHEN MIN(startDate) < @startDate THEN @startDate ELSE MIN(startDate) END 
    ,@placeholderId 
FROM #data 
GROUP BY groupId 
UNION ALL 
SELECT DISTINCT 
    groupId 
    ,CASE WHEN MAX(endDate) < @endDate THEN MAX(endDate) ELSE @endDate END 
    ,CASE WHEN MAX(endDate) < @endDate THEN @endDate ELSE MAX(endDate) END 
    ,@placeholderId 
FROM #data 
GROUP BY groupId 
GO 

-- Fill gaps in results table 
DECLARE @startDate  DATE 
DECLARE @endDate  DATE 
DECLARE @placeholderId BIGINT 

SET @startDate = '20030101' 
SET @endDate = '20111231' 
SET @placeholderId = 999999999999999 

DECLARE @counter INT 
SET @counter = 0 

WHILE @counter < 10 
BEGIN 
    SET @counter = @counter + 1; 
    WITH Gaps AS (
     SELECT 
      gs.groupId 
      ,gs.startDate 
      ,MIN(ge.endDate) as endDate 
      ,ROW_NUMBER() OVER (ORDER BY gs.groupId, gs.startDate) as gapId 
     FROM (
      SELECT groupId, endDate as startDate 
      FROM #Results r1 
      WHERE NOT EXISTS (
        SELECT * 
        FROM #Results r2 
        WHERE r2.groupId = r1.groupId 
         AND r2.versionId <> r1.versionId 
         AND r2.startDate <= r1.endDate 
         AND r2.endDate > r1.endDate 
       ) 
       AND NOT (endDate >= @endDate AND versionId = @placeholderId) 
     ) gs 
     INNER JOIN (
      SELECT groupId, startDate as endDate 
      FROM #Results r1 
      WHERE NOT EXISTS (
        SELECT * 
        FROM #Results r2 
        WHERE r2.groupId = r1.groupId 
         AND r2.versionId <> r1.versionId 
         AND r2.endDate >= r1.startDate 
         AND r2.startDate < r1.startDate 
       ) 
       AND NOT (startDate <= @startDate AND versionId = @placeholderId) 
     ) ge 
      ON ge.groupId = gs.groupId 
      AND ge.endDate >= gs.startDate 
     GROUP BY gs.groupId, gs.startDate 
    ) 
    INSERT #Results (
     groupId 
     ,startDate 
     ,endDate 
     ,versionId 
    ) 
    SELECT 
     d.groupId 
     ,CASE WHEN d.startDate < g.startDate THEN g.startDate ELSE d.startDate END 
     ,CASE WHEN d.endDate > g.endDate THEN g.endDate ELSE d.endDate END 
     ,d.versionId 
    FROM #Data d 
    INNER JOIN Gaps g 
     ON g.groupId = d.groupId 
     AND g.startDate <= d.endDate 
     AND g.endDate >= d.startDate 
    INNER JOIN (
     SELECT 
      d.groupId 
      ,gapId 
      ,MAX(d.versionId) as versionId 
     FROM #Data d 
     INNER JOIN Gaps g 
      ON g.groupId = d.groupId 
      AND g.startDate <= d.endDate 
      AND g.endDate >= d.startDate 
     WHERE d.versionId < (
       SELECT MIN(versionId) 
       FROM #Results r 
       WHERE r.groupId = d.groupId 
        AND (r.startDate = g.endDate OR r.endDate = g.startDate) 
      ) 
      AND NOT EXISTS (
       SELECT * 
       FROM #Data dsup 
       WHERE dsup.groupId = d.groupId 
        AND dsup.versionId > d.versionId 
        AND dsup.startDate <= d.startDate 
        AND dsup.endDate >= d.endDate 
      ) 
     GROUP BY 
      d.groupId 
      ,g.gapId 
    ) mg 
     ON mg.groupId = g.groupId 
     AND mg.gapId = g.gapId 
     AND mg.versionId = d.versionId 
END 

SELECT * 
FROM #Results 
WHERE versionId <> @placeholderId 
order by groupId, startDate 

Zestaw opartej rozwiązanie byłoby o wiele bardziej użyteczne, ale ja z trudem je znalazłem. Jakieś pomysły?

Answer 1

-- create a dates table 
create table dates (thedate date primary key clustered); 
;with dates(thedate) as (
    select dateadd(yy,years.number,0)+days.number 
    from master..spt_values years 
    join master..spt_values days 
     on days.type='p' and days.number < datepart(dy,dateadd(yy,years.number+1,0)-1) 
    where years.type='p' and years.number between 100 and 150 
     -- note: 100-150 creates dates in the year range 2000-2050 
     --  adjust as required 
) 
insert dbo.dates select * from dates; 

-- for each date, determine the prevailing version 
    select t.groupId, d.thedate, max(t.versionId) versionId 
    into #tmp1 
    from dates d 
    join #Data t on t.startDate <= d.thedate and d.thedate <= t.endDate 
group by t.groupId, d.thedate; 

-- create index to help 
create clustered index cix_tmp1 on #tmp1(groupId, thedate, versionId); 

-- find the start dates 
;with t as (
    select a.*, rn=row_number() over (partition by a.groupId order by a.thedate) 
    from #tmp1 a 
left join #tmp1 b on b.thedate = dateadd(d,-1,a.thedate) and a.groupId = b.groupId and a.versionId = b.versionId 
    where b.versionId is null 
) 
    select c.groupId, c.thedate startdate, dateadd(d,-1,d.thedate) enddate, c.versionId 
    from t c 
left join t d on d.rn=c.rn+1 and c.groupId = d.groupId 
order by groupId, startdate; 

Oczywiście, można zrobić wszystko, co w „jednego zapytania” ale zrób to na własne ryzyko, ponieważ wydajność idzie w błoto, wielki czas.

NIE UŻYWAĆ - odsetek akademickiego Wydawany

;with dates(thedate) as (
    select dateadd(yy,years.number,0)+days.number 
    from master..spt_values years 
    join master..spt_values days 
     on days.type='p' and days.number < datepart(dy,dateadd(yy,years.number+1,0)-1) 
    where years.type='p' and years.number between 100 and 150 
     -- note: 100-150 creates dates in the year range 2000-2050 
     --  adjust as required 
), tmp1 as (
    select t.groupId, d.thedate, max(t.versionId) versionId 
    from dates d 
    join #Data t on t.startDate <= d.thedate and d.thedate <= t.endDate 
group by t.groupId, d.thedate 
), t as (
    select a.*, rn=row_number() over (partition by a.groupId order by a.thedate) 
    from tmp1 a 
left join tmp1 b on b.thedate = dateadd(d,-1,a.thedate) and a.groupId = b.groupId and a.versionId = b.versionId 
    where b.versionId is null 
) 
    select c.groupId, c.thedate startdate, dateadd(d,-1,d.thedate) enddate, c.versionId 
    from t c 
left join t d on d.rn=c.rn+1 and c.groupId = d.groupId 
order by groupId, startdate; 

Answer 2

zaktualizowany ze względu na pewne informacje zwrotne od komentarzach. Nie będę się martwił końcowymi przypadkami, które zostały wskazane przez kilka osób, ponieważ okazały się banalne do rozwiązania w innych odpowiedziach, ale chciałem iść dalej i uzyskać działającą wersję, która nie wymagała DDL. .. Myślę, że po prostu dobrze jest mieć opcje. :-)

Kod ten powinien działać:

select nesty.groupId, nesty.startDate, nesty.segment_end_date, Max(bob.versionId) 
from(
select starter.groupId, starter.startDate, 
coalesce(DATEADD(DAY,-1,ender.startDate),('2012-12-31')) AS segment_end_date 
from 
(select groupId, startDate, ROW_NUMBER() over (partition by groupID order by startDate) as rownumber from 
    (select groupID, startDate from #Data union select groupID, DATEADD(DAY, 1,endDate) as startDate from #Data) xx) starter 
left outer join 
(select groupId, startDate, ROW_NUMBER() over (partition by groupID order by startDate) as rownumber from 
    (select groupID, startDate from #Data union select groupID, DATEADD(DAY, 1,endDate) as startDate from #Data) xy) ender on 
    starter.groupId = ender.groupId and 
    starter.rownumber = ender.rownumber - 1 
where 
starter.startDate<= coalesce(DATEADD(DAY,-1,ender.startDate),('2012-12-31')) 
) nesty 
left outer join #Data bob on 
bob.groupId = nesty.groupId and 
nesty.segment_end_date between bob.startDate and bob.endDate 
group by nesty.groupId, nesty.startDate, nesty.segment_end_date 
order by nesty.groupId, nesty.startDate 

Istnieje kilka drobnych zastrzeżeń, co musiałem zrobić, aby dostać go w pojedynczej instrukcji SQL. Po pierwsze, maksymalna data zakończenia nie jest dynamiczna; Ciężko zakodowałem "2012-12-31". Możesz go zastąpić MAX (endDate), ale nie możesz tego umieścić w instrukcji GROUP BY. Jeśli można to zrobić w procedurze, można zrobić:

select into @max_end_date MAX(endDate) from #Data 

i zastąpić „2012-12-31” z @max_end_date.

Po drugie, nie gwarantuję, że dwa sąsiednie segmenty nie będą miały tej samej wartości! To może lub nie może być dla ciebie ważne ...to znaczy, jeśli trzeba było następujące:

Interval 1:  111111  
Interval 2: 22222222222222 

Twój wynik byłby:

Interval 1: 2222 
Interval 2:  2222222222 

Mimo to, myślę, że warto się ukryć, że w prosty i efektywny zapytania SQL. Naprawienie tych zastrzeżeń może nie być trudne, ale nie ma znaczenia, nad czym pracowałem, więc nie zawracałem sobie tym głowy.

Answer 3

Jeśli daty zakończenia są ważne, podobnie jak luki, oto sposób, w jaki można to zrobić. To rozwiązanie może również zostać dostosowane do pracy, jeśli twoje wersje są datetimes zamiast dat.

pierwsze grono funkcji

Jednym aby uzyskać wersji na dany dzień

Create Function dbo.VersionAtDate(@GroupID int, @Date datetime) Returns int as 
Begin 
    Declare @Ret int = Null 
    Select 
    @Ret = Max(VersionID) 
    From 
    VersionedIntervals iv 
    Where 
    iv.GroupID = @GroupID And 
    iv.StartDate <= @Date And 
    iv.EndDate + 1 > @Date -- if dates were half open intervals this would just be iv.EndDate > @Date 
    Return @Ret 
End 

Następny uzyskać środkowy dwóch datetimes (rozdzielczości minut):

Create Function dbo.Midpoint(@Start datetime, @End datetime) Returns datetime as 
Begin 
    Return DateAdd(Minute, DateDiff(Minute, @Start, @End)/2, @Start) 
End 

wersja w punkcie środkowym:

Create Function dbo.VersionAtMidpoint(@GroupID int, @Start datetime, @End datetime) returns int as 
Begin 
    Return dbo.VersionAtDate(@GroupID, dbo.Midpoint(@Start, @End)) 
End; 

Wreszcie tabela funkcji, aby pomóc w tym, że niektóre punkty są początkiem jednego zakresu i koniec drugiego, a to pomaga uzyskać dwa wiersze z jednego wejścia na ten ceniony:

-- returns two rows if a point is the end of one interval and the 
-- start of another 
Create Function dbo.EndPoints(@GroupID int, @RN bigint, @Start datetime, @End datetime, @Next datetime, @Version int) 
Returns @EndPoints Table (
    GroupID int, 
    RN bigint, 
    Version int, 
    StartDate datetime, 
    EndDate datetime 
) As 
Begin 
    Declare @NextVersion int, @VersionAtMidpoint int 
    Set @NextVersion = dbo.VersionAtDate(@GroupID, @Next) 
    If @NextVersion = @Version 
    -- interval carries on 
    Insert Into @EndPoints Select @GroupID, @RN, @Version, @Start, @Next 
    Else 
    Begin 
    -- interval has ended 
    Set @VersionAtMidpoint = dbo.VersionAtMidPoint(@GroupID, @End, @Next) 
    If @VersionAtMidpoint != @Version 
     -- we have something like this, start a run of 3s (run of 4s is already ended by previous call) 
     -- 3333333 
     -- 44  
     Insert Into @EndPoints Select @GroupID, @RN, @VersionAtMidpoint, @End, @Next 
    Else 
    Begin 
     -- We have something like this, end the run of 3s and start the run of fours 
     -- 33333 
     -- 444 
     Insert Into @EndPoints Select @GroupID, -1, @Version, @Start, @Next 
     Insert Into @EndPoints Select @GroupID, @RN, @NextVersion, @Next, @Next 
    End 
    End 
    Return 
End 

Mając to wszystko maszyny w miejscu, wreszcie rekurencyjny zmienna stół plust CTE, musisz ustawić maxrecursion odpowiednio:

Declare @Bounds Table (GroupID int, RN bigint, BoundDate datetime, Primary Key (GroupID, RN)) 

Insert Into 
    @Bounds 
Select 
    GroupID, 
    Row_Number() Over (Partition By GroupID Order By BoundDate), 
    BoundDate 
From (
    Select 
     GroupID, 
     StartDate As BoundDate 
    From 
     dbo.VersionedIntervals 
    Union 
    Select 
     GroupID, 
     EndDate 
    From 
     dbo.VersionedIntervals 
    ) a 

;With VersionedBounds (GroupID, RN, StartDate, EndDate, Version) as (
    Select 
     GroupID, 
     RN, 
     BoundDate, 
     BoundDate, 
     dbo.VersionAtDate(GroupID, BoundDate) 
    From 
     @Bounds 
    Where 
     RN = 1 
    Union All 
    Select 
     e.GroupID, 
     e.RN, 
     e.StartDate, 
     e.EndDate, 
     e.Version 
    From 
     @Bounds b 
      Inner Join 
     VersionedBounds v 
      On v.GroupID = b.GroupID And b.RN = v.RN + 1 
      Cross Apply 
     dbo.EndPoints(v.GroupID, b.RN, v.StartDate, v.EndDate, b.BoundDate, v.Version) e 
) 
Select 
    GroupID, 
    StartDate, 
    Max(EndDate) As EndDate, 
    Max(Version) As Version 
From 
    VersionedBounds 
Group By 
    GroupID, 
    StartDate 
Order By 
    GroupID, 
    StartDate 

http://sqlfiddle.com/#!6/b95bd/2