How to group all linked objects in a undirected cyclic graph

Question

I have a table that has customers and its joint customers. e.g Customer 1 has a joint customer 2. Customer 1 is also a joint customer to Customer 3.

I am trying to group all customers that are linked and assign same GroupCustNo to them. In below table 1-2 are linked, 3-1 are linked. So 2-3 are also linked. All customers from 1 to 8 in below table are thus linked to each other and will have same GroupCustNo.

 tbl_GroupCustomers:

CustNo   JtCustNo  GroupCustNo    
---      -------     ------   
1           2          null
2           null       null
3           1          null
4           1          null
4           5          null
5           6          null
5           7          null
6           null       null
7           null       null
8           5          null

The recursive stored procedure I wrote is below. I am calling this in a while loop for each CustNo:

exec usp_UpdateGroupCustomerNo 1, 1 The stored procedure ran successfully for most of the customers but threw up

Recursion Limit of 32 reached error for some customers. These are customers that have many joint customers and are also Joint Customers to other customers.

It seems recursion wont work here and I am at a loss on how to proceed. Please let me know if there are any alternate methods to address this problem.

CREATE PROCEDURE [dbo].[usp_UpdateGroupCustomerNo]
     @MainCustNo int, @GrpNo int
AS 
    declare @JtCustNo int; declare @MainCustNo2 int;

if exists(select 1 from tbl_GroupCustomer 
          where CustNo = @MainCustNo and groupcustomernumber is null)
begin    
    update tbl_GroupCustomer 
    set groupcustomernumber = @grpno 
    where CustNo = @MainCustNo 
      and groupcustomernumber is null

    DECLARE db_cursor CURSOR LOCAL FOR  
         select JtCustNo 
         from tbl_GroupCustomer 
         where CustNo = @MainCustNo and JtCustNo is not null

    OPEN db_cursor   

    FETCH NEXT FROM db_cursor INTO @JtCustNo   

    WHILE @@FETCH_STATUS = 0   
    BEGIN   
        select @JtCustNo as JtCustNo      

        exec usp_UpdateGroupCustomerNo @JtCustNo, @GrpNo

        DECLARE db_cursor2 CURSOR LOCAL FOR  
            select CustNo 
            from tbl_GroupCustomer 
            where JtCustNo = @JtCustNo 
              and groupcustomernumber is null

        OPEN db_cursor2

        FETCH NEXT FROM db_cursor2 INTO @MainCustNo2   

        WHILE @@FETCH_STATUS = 0   
        BEGIN   
            if exists(select 1 from tbl_GroupCustomer 
                      where CustNo = @MainCustNo2 
                        and groupcustomernumber is null)
            begin     
                exec usp_UpdateGroupCustomerNo @MainCustNo2, @GrpNo
            end

            FETCH NEXT FROM db_cursor INTO @MainCustNo2   
        END   

        CLOSE db_cursor2   
        DEALLOCATE db_cursor2

        FETCH NEXT FROM db_cursor INTO @JtCustNo   
END  

CLOSE db_cursor   
DEALLOCATE db_cursor

END

Answer 1

This answer assumes that you are unable to remove the recursion limit by using OPTION (MAXRECURSION 0) somewhere in your procedure.

I spent a while attempting recursive solutions, but no matter what I tried, I couldn't guarantee it would be less than the recursion limit - I could always build a chain requiring more iterations.

So, here's a simple looping solution, along with my DDL for testing:

/*
IF OBJECT_ID('tempdb..#tbl_GroupCustomers') IS NOT NULL
DROP TABLE #tbl_GroupCustomers

CREATE TABLE #tbl_GroupCustomers
(CustNo int,
JtCustNo int,
GroupCustNo int)

INSERT #tbl_GroupCustomers
(CustNo, JtCustNo)
VALUES
(1,2),
(2,NULL),
(3,1),
(4,1),
(4,5),
(5,3),
(6,7),
(7,8),
(8,6),
(9,null)

SELECT *
FROM #tbl_GroupCustomers
*/


DECLARE @GN int = 1
DECLARE @seedCust int
DECLARE @count1 int, @count2 int

--Outer loop: iterate group numbers
WHILE EXISTS(SELECT * FROM #tbl_GroupCustomers WHERE GroupCustNo IS NULL)
BEGIN
--Find next ungrouped customer
SET @seedCust = (SELECT TOP 1 CustNo FROM #tbl_GroupCustomers WHERE GroupCustNo IS NULL)
--reset counts
SET @count1 = 0
SET @count2 = 1

--Start with a customer
--Give that customer a Group number
UPDATE GC
SET GroupCustNo = @GN
FROM #tbl_GroupCustomers GC
WHERE CustNo = @seedCust

    --Inner loop
    WHILE @count1 <> @count2
    BEGIN

    --How many records?
    SELECT @count1 = COUNT(*) FROM #tbl_GroupCustomers WHERE GroupCustNo = @GN

    --Give all linked records the same GN
    UPDATE GC2
    SET GC2.GroupCustNo = @GN
    FROM (SELECT CustNo, JtCustNo
        FROM #tbl_GroupCustomers
        WHERE GroupCustNo = @GN
        ) GC1
    INNER JOIN #tbl_GroupCustomers GC2
    ON GC1.CustNo = GC2.JtCustNo
    OR GC1.JtCustNo = GC2.CustNo
    OR GC1.CustNo = GC2.CustNo
    OR GC1.JtCustNo = GC2.JtCustNo

    --How many records? If same, it ends loop
    SELECT @count2 = COUNT(*) FROM #tbl_GroupCustomers WHERE GroupCustNo = @GN
    END

SET @GN +=1
END

Beginning table:

CustNo      JtCustNo    GroupCustNo
----------- ----------- -----------
1           2           NULL
2           NULL        NULL
3           1           NULL
4           1           NULL
4           5           NULL
5           3           NULL
6           7           NULL
7           8           NULL
8           6           NULL
9           NULL        NULL

Result:

CustNo      JtCustNo    GroupCustNo
----------- ----------- -----------
1           2           1
2           NULL        1
3           1           1
4           1           1
4           5           1
5           3           1
6           7           2
7           8           2
8           6           2
9           NULL        3

Answer 2

The underlying difficulty with this problem is that a table with a self-referencing key, as a data structure, is an implementation of a vertex ( or node )-based digraph. One way of enabling bidirectional traversals in a relational database is to break out the self-referencing key as a separate table, so that the vertices of the graph can be represented by an entity table ( for instance, a Customer table, which you likely already have ) and the edges can be represented by the new relationship table ( your GroupCustomers table in this case, except the GroupCustomerNo would likely be moved to be an attribute of the Customer table ).

While the collection of edges can be leveraged in as many ways as you can imagine ( a linked list with "next" and "previous" attributes, an n-ary tree with "branch₁", "branch₂", ..., "branch_n"; whatever it is you need your data model to do at this point ), a simple directed edge is often sufficient, as a directed edge contains enough information to represent both directions without the need for storing an additional record for the representation of the other direction - you merely have to swap the vertices.

With that in mind, in order to perform a bidirectional traversal of your tbl_GroupCustomers, simple recursion will be sufficient, though there is some preparation of the data necessary for the traversal. For this scenario, simulating the graph from the digraph with a CTE seems reasonable, then a relatively run-of-the-mill recursive CTE to perform the traversal on the simulated graph.

USE tempdb;
GO

CREATE TABLE dbo.tbl_GroupCustomer 
( 
    CustNo                      INTEGER, 
    JtCustNo                    INTEGER, 
    GroupCustNo                 INTEGER
);

INSERT  INTO dbo.tbl_GroupCustomer ( CustNo, JtCustNo, GroupCustNo )
VALUES  ( 1, 2, NULL ), ( 2, NULL, NULL ), ( 3, 1, NULL ), ( 4, 1, NULL ), 
        ( 4, 5, NULL ), ( 5, 6, NULL ), ( 5, 7, NULL ), ( 6, NULL, NULL ), 
        ( 7, NULL, NULL ), ( 8, 5, NULL ), ( 9, NULL, NULL ), ( 10, 9, NULL );
GO

CREATE PROCEDURE dbo.usp_UpdateGroupCustomerNo
     @MainCustNo                INTEGER,
     @GrpNo                     INTEGER
AS BEGIN
    SET NOCOUNT ON;

    ;WITH
    cte_Graph AS (
        -- Simulate bidirectional relationships;
        SELECT  CustNo, JtCustNo
        FROM    dbo.tbl_GroupCustomer
        WHERE   JtCustNo IS NOT NULL
        UNION           
        SELECT  JtCustNo, CustNo
        FROM    dbo.tbl_GroupCustomer
        WHERE   JtCustNo IS NOT NULL ),
    cte_Traversal AS (
        -- Regular traversal;
        SELECT  DISTINCT CustNo = NULL, JtCustNo = CustNo
        FROM    cte_Graph
        WHERE   CustNo = @MainCustNo
        UNION ALL
        SELECT  g.CustNo, g.JtCustNo
        FROM    cte_Traversal t
        INNER JOIN cte_Graph g
            ON  g.CustNo = t.JtCustNo
        WHERE ( g.JtCustNo <> t.CustNo 
            OR  t.CustNo IS NULL ) )
    SELECT  *
    --UPDATE    gc
    --  SET GroupCustNo = @GrpNo
    FROM    cte_Traversal t
    INNER JOIN dbo.tbl_GroupCustomer gc
        ON  gc.CustNo = t.JtCustNo;

    SET NOCOUNT OFF;
END;
GO

EXECUTE dbo.usp_UpdateGroupCustomerNo @MainCustNo = 1, @GrpNo = 1;
EXECUTE dbo.usp_UpdateGroupCustomerNo @MainCustNo = 10, @GrpNo = 2;
GO

DROP PROCEDURE dbo.usp_UpdateGroupCustomerNo;
DROP TABLE dbo.tbl_GroupCustomer;
GO