Assign group_id to all linked records in many-to-many table

Question

There are 3 tables in my DB; Table 1 has 'Collateral', Table 2 has 'Loans', Table 3 is a multi-link table between 1 and 2; let's call it 'Loan_Collateral_link'.

A collateral can belong to 1 or more Loans, and a Loan can have multiple Collaterals.

What I want to achieve, is create a separate result set (or table) in which I group together all Loans and Collaterals which are in any way linked to eachother through different Loans and/or Collaterals.

Loans:

ID	name
Loan1	ABC
Loan2	DEF
Loan3	GHI
Loan4	JKL
Loan5	MNO

Collaterals:

ID	name
Coll1	Col1
Coll2	Col2
Coll3	Col3

Loan_Collateral_link:

Loan_ID	Collateral_ID
Loan1	Col1
Loan2	Col1
Loan2	Col3
Loan3	Col2
Loan4	Col2
Loan5	Col1
Loan5	Col3

So you see Loan1, Loan2 and Loan5 are sharing col1, so I want them to be grouped. Col3 should be in that same group, as it is linked through Loan2.

Loan4 and Loan3 are linked through Col2, so they should be a separate group.

The resultset would be something as per below:

Groups:

Group_ID	item_ID
Group1	Loan1
Group1	Loan2
Group1	Loan5
Group1	Col1
Group1	Col3
Group2	Loan3
Group2	Loan4
Group2	Col2

I'm trying to write a script, probably using a loop? to get this done. I was thinking to loop over each record in the Loan_Collateral_Link table, write every link that I find for the record into a temp_table. Then loop over this temp_table to find all linked records. However, I can't really seem to work it out conceptually, as the loop should somehow reference itself.

Something like;

--ForEach Loan_Collateral_Link Loan;
    --If not exists - Insert LOAN_ID into TempTable
    --If not exist - Insert COL_ID into TempTable
        --ForEach TempTable COL_ID;
            --Select * FROM Loan_Collateral_Link where Loan_ID or Col_ID matches
                --> If not exists - Insert LOAN_ID / COL_ID into TempTable

But this seems a bit like an infite loop perhaps?

Perhaps I should order all Loans, than go over Loan per Loan, add all the Col's, and in the loop per loan select all other loans with this loan. Than go over all the new Cols and select all matching Loans. However, than I have new Loans, so I need to go back and fetch their possible Cols. So again, how many times do I loop? Use a flag per collateral and keep looping until all flags are fulfilled?

Answer 1

A while ago I wrote an answer to the question How to find all connected subgraphs of an undirected graph. Your question here looks like the same problem.

Essentially, it treats the data as edges in a graph and traverses recursively all edges of the graph, stopping when the loop is detected. Then it puts all found loops in groups and gives each group a number.

For the detailed explanation of the query see that answer. I adapted that query to your schema here.

Also, this problem can be solved in linear time. Wikipedia has description of the algorithm. But, the T-SQL method shown here is far from optimal. If you still want to do it in T-SQL you can try the following. Instead of trying to find all groups at once, pick a single starting Identifier (add WHERE Ident='Loan1' to CTE_Idents and CTE_Pairs), then delete from the big table all identifiers that were appended to this group. Repeat until the big table is empty. At least you could see the progress. Proper indexes on Ident columns would not hurt as well.

Sample data

DECLARE @T TABLE (LoanID varchar(50), CollateralID varchar(50));
INSERT INTO @T (LoanID, CollateralID) VALUES
('Loan1', 'Col1'),
('Loan2', 'Col1'),
('Loan2', 'Col3'),
('Loan3', 'Col2'),
('Loan4', 'Col2'),
('Loan5', 'Col1'),
('Loan5', 'Col3'),

-- plus an extra group with some more interesting links
('Loan80', 'Col80'),
('Loan81', 'Col80'),
('Loan80', 'Col81'),
('Loan81', 'Col81'),
('Loan82', 'Col81')
;

Query

WITH
CTE_Idents
AS
(
    SELECT LoanID AS Ident
    FROM @T

    UNION

    SELECT CollateralID AS Ident
    FROM @T
)
,CTE_Pairs
AS
(
    SELECT LoanID AS Ident1, CollateralID AS Ident2
    FROM @T

    UNION

    SELECT CollateralID AS Ident1, LoanID AS Ident2
    FROM @T
)
,CTE_Recursive
AS
(
    SELECT
        CAST(CTE_Idents.Ident AS varchar(8000)) AS AnchorIdent 
        , Ident1
        , Ident2
        , CAST(',' + Ident1 + ',' + Ident2 + ',' AS varchar(8000)) AS IdentPath
        , 1 AS Lvl
    FROM 
        CTE_Pairs
        INNER JOIN CTE_Idents ON CTE_Idents.Ident = CTE_Pairs.Ident1

    UNION ALL

    SELECT 
        CTE_Recursive.AnchorIdent 
        , CTE_Pairs.Ident1
        , CTE_Pairs.Ident2
        , CAST(CTE_Recursive.IdentPath + CTE_Pairs.Ident2 + ',' AS varchar(8000)) AS IdentPath
        , CTE_Recursive.Lvl + 1 AS Lvl
    FROM
        CTE_Pairs
        INNER JOIN CTE_Recursive ON CTE_Recursive.Ident2 = CTE_Pairs.Ident1
    WHERE
        CTE_Recursive.IdentPath NOT LIKE CAST('%,' + CTE_Pairs.Ident2 + ',%' AS varchar(8000))
)
,CTE_RecursionResult
AS
(
    SELECT AnchorIdent, Ident1, Ident2
    FROM CTE_Recursive
)
,CTE_CleanResult
AS
(
    SELECT AnchorIdent, Ident1 AS Ident
    FROM CTE_RecursionResult

    UNION

    SELECT AnchorIdent, Ident2 AS Ident
    FROM CTE_RecursionResult
)
SELECT
    CTE_Idents.Ident
    ,CASE WHEN CA_Data.XML_Value IS NULL 
    THEN CTE_Idents.Ident ELSE CA_Data.XML_Value END AS GroupMembers
    ,DENSE_RANK() OVER(ORDER BY 
        CASE WHEN CA_Data.XML_Value IS NULL 
        THEN CTE_Idents.Ident ELSE CA_Data.XML_Value END
    ) AS GroupID
FROM
    CTE_Idents
    CROSS APPLY
    (
        SELECT CTE_CleanResult.Ident+','
        FROM CTE_CleanResult
        WHERE CTE_CleanResult.AnchorIdent = CTE_Idents.Ident
        ORDER BY CTE_CleanResult.Ident FOR XML PATH(''), TYPE
    ) AS CA_XML(XML_Value)
    CROSS APPLY
    (
        SELECT CA_XML.XML_Value.value('.', 'NVARCHAR(MAX)')
    ) AS CA_Data(XML_Value)
WHERE
    CTE_Idents.Ident IS NOT NULL
ORDER BY GroupID, Ident;

Result

+--------+-----------------------------------+---------+
| Ident  |           GroupMembers            | GroupID |
+--------+-----------------------------------+---------+
| Col1   | Col1,Col3,Loan1,Loan2,Loan5,      |       1 |
| Col3   | Col1,Col3,Loan1,Loan2,Loan5,      |       1 |
| Loan1  | Col1,Col3,Loan1,Loan2,Loan5,      |       1 |
| Loan2  | Col1,Col3,Loan1,Loan2,Loan5,      |       1 |
| Loan5  | Col1,Col3,Loan1,Loan2,Loan5,      |       1 |
| Col2   | Col2,Loan3,Loan4,                 |       2 |
| Loan3  | Col2,Loan3,Loan4,                 |       2 |
| Loan4  | Col2,Loan3,Loan4,                 |       2 |
| Col80  | Col80,Col81,Loan80,Loan81,Loan82, |       3 |
| Col81  | Col80,Col81,Loan80,Loan81,Loan82, |       3 |
| Loan80 | Col80,Col81,Loan80,Loan81,Loan82, |       3 |
| Loan81 | Col80,Col81,Loan80,Loan81,Loan82, |       3 |
| Loan82 | Col80,Col81,Loan80,Loan81,Loan82, |       3 |
+--------+-----------------------------------+---------+