Hi.

Hi have this problem that will be a bit difficult to explain, but I will do my best:


I have a temp-table with following columns (all int):

TempId LogId AlternativeLogId

None of the fields are unique.
When the temp-table is filled, the AlternativeLogId is initially set to be equal to LogId. Initially the table could have these data in it:

TempId LogId AlternativeLogId

2 10 10
2 12 12
2 15 15
3 15 15
3 17 17
3 20 20
5 16 16
5 17 17
5 30 30
6 25 25
6 27 27

What I need, is to update the AlternativeLogId to be the lowest logid for all TempId's where a particular logid is present. So, for the above list, because TempId 2, 3 and 5 are overlapping ( via logid 15 and 17), they should all get the same AlternativeLogId. TempId 6 will get the lowest logid for all rows with TempId=6 as AlternativLogId, because it does not overlap any other TempId's. The updated temp-table should look like this:

TempId LogId AlternativeLogId

2 10 10
2 12 10
2 15 10
3 15 10
3 17 10
3 20 10
5 16 10
5 17 10
5 30 10
6 25 25
6 27 25


I have solved this problem using a cursor, but needless to say, it does take some time to do this with a cursor(the temp-table may contain over 200000 rows).

Please, can anyone lead me in a direction so that I won't have to use cursors? (Come on you oh so talentet people, give it a try :) )

Thanks in advance
Gert

How come this is true?

TempId LogId AlternativeLogId
-----------------------------------
2 10 10
2 12 10
2 15 10
3 15 10
3 17 10
3 20 10
5 16 10
5 17 10
5 30 10
6 25 25
6 27 25

TempID 5 that has log from 16-30 must be overlapping TempID 6 that has log from 25-27?

If you remove the 5 30 30 row, then your assumptions are right.

One way of solving it is like this! I do not know the speed of this algorithm, but please test and report back!
---------------------------------------
DECLARE @Ranges TABLE
        (
           tempid INT,
           minlogid INT,
           maxlogid INT
        )

INSERT INTO @Ranges
            (
               tempid,
               minlogid,
               maxlogid
            )
SELECT tempid,
            MIN(logid),
            MAX(logid)
FROM table1 -- THIS IS YOUR ORIGINAL TABLE
GROUP BY tempid

DECLARE @minlogid INT,
        @maxlogid INT

SELECT @minlogid = MIN(minlogid)
FROM @Ranges

SELECT @maxlogid = maxlogid
FROM @Ranges
WHERE minlogid = @minlogid

WHILE @minlogid IS NOT NULL
   BEGIN
      UPDATE @Ranges
      SET minlogid = @minlogid
      WHERE minlogid > @minlogid
             AND minlogid <= @maxlogid

      IF @@ROWCOUNT = 0
         SELECT @minlogid = MIN(minlogid)
         FROM @Ranges
         WHERE minlogid > @minlogid

      SELECT @maxlogid = MAX(maxlogid)
      FROM @Ranges
      WHERE minlogid = @minlogid
   END

UPDATE Table1 -- THIS IS YOUR ORIGINAL TABLE
SET AlternativeLogId = r.minlogid
FROM Table1, -- THIS IS YOUR ORIGINAL TABLE
       @Ranges r
WHERE Table1.tempid = r.tempid -- THIS IS YOUR ORIGINAL TABLE

--Try this:
/* Assumption: Overlap is defined by two or more tempid's having the same logID, not that the ranges of their log id's overlap
Overlap is communitive

For example:
TempID 2 has logids 6 and 9
TempID 3 has logids 7 and 8
TempID 4 has logids 6 and 12
TempID 5 has logids 12 and 15
TempID 6 has logids 8 and 18
TempId 7 has logids 20 and 21

Result
TempID 2 overlaps with 4 (share 6) and with 5 (since 4 and 5 share 12) but not with 3 even though 3's logids are inside of the range of temp2 id's
TempID 3 overlaps with 6 (share 8)
TempID 7 does not overlap with anything

*/
/* Algorithm
Find which TempID's overlap and Assign them a common ID. Example result set:
2 2
5 2
3 2
7 7
8 7
Find the lowest LogID of the overlaps
Update the AltLogID
*/

USE TEMPDB
GO
CREATE TABLE #tempIDs (TempID int, LogID int, AltLogID int)
GO
INSERT #tempIDs VALUES(2, 10, 10)
INSERT #tempIDs VALUES(2 , 12 , 12)
INSERT #tempIDs VALUES(2 , 15 , 15)
INSERT #tempIDs VALUES(3, 15 , 15)
INSERT #tempIDs VALUES(3 , 17 ,17)
INSERT #tempIDs VALUES(3 , 20, 20)
INSERT #tempIDs VALUES(5 , 16 , 16)
INSERT #tempIDs VALUES(5, 17 , 17)
INSERT #tempIDs VALUES(5 , 30 , 30)
INSERT #tempIDs VALUES(6 , 25 ,25)
INSERT #tempIDs VALUES(6 , 27 ,27)
INSERT #tempIDs VALUES(7 , 32 ,32)
INSERT #tempIDs VALUES(7 , 8 ,8)
INSERT #tempIDs VALUES(8 , 32 ,32)
INSERT #tempIDs VALUES(8 , 56 ,56)

GO
WITH TJ (T1TempID, T1LogID, T1AltLogID, T2TempID, T2LogID, T2AltLogID) -- Brings back the first level of matches
AS
(
    SELECT T1.TempID, T1.LogID, T1.AltLogID, T2.TempID, T2.LogID, T2.AltLogID
        FROM #tempIDs T1
        JOIN #tempIDs T2
            ON T1.LogID = T2.LogID
            AND T1.TempID < T2.TempID
)
, TIDS (T1TempID, T1LogID, T1AltLogID, TT1, TLevel) -- Recursive CTE -- Flushes out all of the possible matches
        -- so that if 2-3 and 3-5 then 2-5 and 5-2 will also show up
AS
( -- First Anchor Member -- will return rows that won't have any recursion
    SELECT T1.TempID, T1.LogID, T1.AltLogID, T1.TempID, 0 AS TLevel
    FROM #tempIDs T1
    WHERE T1.TempID NOT IN
        (SELECT T1TempID
        FROM TJ
        UNION
        SELECT T2TempID
        FROM TJ
        )
    UNION ALL--Second Anchor Member -- will return rows that will recurse
    SELECT T1TempID, T1LogID, T1AltLogID, T1TempID as TT1, 0 AS TLevel
    FROM TJ
    UNION ALL -- Recursive Member Query
    SELECT T2TempID, T2LogID, T2AltLogID, TIDS.TT1, TLevel + 1 AS TLevel
        FROM TJ
        JOIN TIDS
            ON TIDS.T1TempID = TJ.T1TempID
            AND TJ.T2TempID != TIDS.T1TempID

)
, MINTIDS (T1TempID, MINTT1) -- pares it down to use the lowest tempid as a common identifier among all of the overlapping
AS
(
    SELECT T1TempID, MIN(TT1) FROM TIDS
    GROUP BY T1TempID
)
, MINLOGIDS (MINTT1, MINLogID) -- Find out what is the lowest LogID
AS
(
    SELECT MT.MINTT1, MIN(T1.LogID)
    FROM MINTIDS MT
    JOIN #tempIDs T1
        ON T1.TempID = MT.T1TempID
    GROUP BY MT.MINTT1
)
--SELECT MT.T1TempID, ML.MINLogID -- Show the LowestLogID, next to each of the TempID's
--FROM MINLOGIDS ML
--JOIN MINTIDS MT
-- ON ML.MINTT1 = MT.MINTT1

UPDATE #tempIDs SET AltLogID = ML.MINLogID
FROM #tempIDs T
JOIN MINTIDS MT
    ON T.TempID = MT.T1TempID
JOIN MINLOGIDS ML
    ON ML.MINTT1 = MT.MINTT1

SELECT * FROM #tempIDs

David Lundell
Principal Consultant and Trainer
www.mutuallybeneficial.com

Hi, and thanks to both of you for your replies. I have been away since last friday, and have not seen your posts until today.

I apologize if my explanation of the problem was poor, but Davids assumption is correct. "Overlap is defined by two or more tempid's having the same logID, not that the ranges of their log id's overlap"

I have in the meantime found an other solution to the problem, but there I had to use a while-loop and add rows to a temp-table until there where no more rows to add (ROWCOUNT = 0) (This is a short version, there were a bit more to it). I tried first with recursive CTE, but couldn't find a proper anchor, so I will try out your suggestion David.

Thanks again to both of you for your effort.

Gert