How to group all linked objects in a undirected cyclic graph

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

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

--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
• Tried your solution but didnt get all linked customers. As for Maxrecursion it can be set for CTEs only – Arcturus Oct 25 '16 at 17:59
• @Arcturus I found the probable error (join conditions) and modified my code if you want to try again. I'm also testing recursive CTEs against this in my free time, but no promises there. – Forrest Oct 25 '16 at 18:44

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 "branch1", "branch2", ..., "branchn"; 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