In einer Reihe von überlappenden, versionsnummerierten Intervallen finden Sie die aktuellste Version zu jedem Zeitpunkt

Question

Ich arbeite mit einer Reihe von Datumsintervallen, wobei jedes Intervall eine Versionsnummer hat und neue Intervalle häufig alte überlappen. oder sogar Teilmengen von ihnen sein. Aus diesen Daten muss ich einen neuen Intervallsatz berechnen, der zu jedem Zeitpunkt die aktuellste Versionsnummer anzeigt. Gibt es eine Set-basierte Lösung für dieses Problem?

Hier ist eine Illustration:

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

Hier ist ein Beispiel der Daten mit Ich arbeite:

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 

... und die gewünschte Ausgabe:

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 

Ich habe keine anderen Beispiele für dieses Problem gefunden, mein googling zeigt nur Abfragen an, die gaps and islands oderidentifizieren.

Ich denke, ich habe eine iterative Lösung (SQL Server 2008). Es beginnt mit einer temporären Tabelle für Intervalle in der Ergebnismenge und definiert die Start- und Endpunkte für den Bereich, den wir abdecken möchten, indem Datensätze mit speziellen Versionsnummern eingefügt werden. Dann identifiziert sie immer wieder Lücken zwischen Ergebnis festgelegten Intervallen und versucht, sie mit den neuesten Datensätze aus dem ursprünglichen Datensatz zu füllen, bis es keine Lücken mehr oder nicht mehr Datensätze sind hinzuzufügen:

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 

Ein Set-basierte Lösung wäre viel nützlicher, aber ich hatte Mühe, einen zu finden. Irgendwelche Ideen?

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; 

Natürlich können Sie alles in „eine Abfrage“ tun, aber tun es auf eigene Gefahr, da die Leistung geht den Bach runter, große Zeit.

DO NOT USE - für akademische Interesse nur-

;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

Aktualisiert aufgrund einiger Feedback von den Kommentaren. Ich werde mir keine Sorgen über die Endfälle machen, auf die einige Leute hingewiesen haben, da sie sich in anderen Antworten als trivial erwiesen haben, aber ich wollte weitermachen und eine funktionierende Version herausbringen, die DDL nicht benötigt. .. Ich denke, es ist nur gut, Optionen zu haben. :-)

sollten Dieser Code funktioniert:

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 

ein paar kleine Einschränkungen gibt es ich tun musste, um es in eine einzelne SQL-Anweisung zu erhalten. Erstens ist das maximale Enddatum nicht dynamisch. Ich habe "2012-12-31" fest programmiert. Sie können es durch ein MAX (endDate) ersetzen, aber Sie können das nicht in die GROUP BY-Anweisung einfügen. Wenn Sie dies in einem Verfahren tun, können Sie tun:

select into @max_end_date MAX(endDate) from #Data 

und ersetzen ‚2012-12-31‘ mit @max_end_date.

Zweitens kann ich nicht garantieren, dass zwei benachbarte Segmente nicht den gleichen Wert haben! Dies kann für Sie wichtig sein oder auch nicht ...das heißt, wenn Sie hatte die folgenden:

Interval 1:  111111  
Interval 2: 22222222222222 

Die Ausgabe wäre:

Interval 1: 2222 
Interval 2:  2222222222 

Aber ich denke, es lohnt sich in einer einfachen und effizienten SQL-Abfrage schlägt. Es mag nicht schwierig sein, diese Vorbehalte zu korrigieren, aber es war mir egal, woran ich gerade arbeitete, also habe ich mich noch nicht darum gekümmert.

Answer 3

Wenn die Enddaten wichtig sind, sowie Lücken, hier ist ein Weg, wie Sie es tun können. Diese Lösung könnte auch angepasst werden, wenn Ihre Versionen datetimes statt nur Daten sind.

Zunächst wird eine Reihe von Funktionen

One die Version zu einem bestimmten Zeitpunkt zu bekommen

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 

Weiter, um den Mittelpunkt von zwei Datetimes (Minute Auflösung) zu erhalten:

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

Version in der Mitte:

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

Endlich ein Tisch, dass einige Punkte der Beginn einer Reihe und das Ende eines anderen sind, und es hilft, bewertet Funktion mit der Tatsache zu helfen, zwei Reihen von einem Eingang für diese zu bekommen:

-- 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 

Mit all diesen Maschinen an Ort und Stelle, müssen Sie schließlich eine rekursive CTE plust Tabellenvariable, MAXRECURSION entsprechend einzustellen:

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