Skip to content
Advertisement

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

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;

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?

Advertisement

Answer

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

Query

Result

User contributions licensed under: CC BY-SA
8 People found this is helpful
Advertisement