TSQL - Query all circular references

Question

Data setup (using letters in the comment to make it a bit more readable):

DECLARE @Data TABLE
    (
        [DeptId]   INT DEFAULT ( 1 )
      , [ParentId] UNIQUEIDENTIFIER
      , [ChildId]  UNIQUEIDENTIFIER
    ) ;

INSERT INTO @Data
VALUES
    ( DEFAULT, '4668E1DF-2200-4FF3-9091-ADE1016598B0', '4668E1DF-2200-4FF3-9091-ADE1016598B0' ) -- A > A
  , ( DEFAULT, '4668E1DF-2200-4FF3-9091-ADE1016598B0', '3DD4F212-30C9-43BB-B49D-ADE101659F1B' ) -- A > B
  , ( DEFAULT, '4668E1DF-2200-4FF3-9091-ADE1016598B0', 'F2A3C2A9-FEE6-4E79-8DCB-ADE10165E36E' ) -- A > C
  , ( DEFAULT, '4668E1DF-2200-4FF3-9091-ADE1016598B0', 'FCA427EA-C23F-45C6-82A6-ADE10165ED0F' ) -- A > D !! INVALID : A > D & A > E & E > D !!
  , ( DEFAULT, '4668E1DF-2200-4FF3-9091-ADE1016598B0', 'C6A2B1A9-0F97-40F2-9B54-ADE10165F7AD' ) -- A > E !! INVALID : A > D & A > E & E > D !!
  , ( DEFAULT, 'F2A3C2A9-FEE6-4E79-8DCB-ADE10165E36E', '421A5691-37CB-4EB6-A4F2-ADE101661C90' ) -- B > F
  , ( DEFAULT, 'F2A3C2A9-FEE6-4E79-8DCB-ADE10165E36E', '9450A83D-2A56-4A95-A2A0-ADE101662CAD' ) -- B > G
  , ( DEFAULT, 'C6A2B1A9-0F97-40F2-9B54-ADE10165F7AD', 'FCA427EA-C23F-45C6-82A6-ADE10165ED0F' ) -- E > D !! INVALID : A > D & A > E & E > D !!
  , ( DEFAULT, 'DF9C4FB5-ED7A-4864-9DAE-ADE10169B354', '7CE4DBF9-59FD-4499-BFAB-ADE10169BBD3' ) -- H > I !! INVALID : H > I & I > H !!
  , ( DEFAULT, '7CE4DBF9-59FD-4499-BFAB-ADE10169BBD3', 'DF9C4FB5-ED7A-4864-9DAE-ADE10169B354' ) -- I > H !! INVALID : H > I & I > H !!
  , ( DEFAULT, 'FD1B372D-123C-4702-B184-ADE1016BE094', '48FD8FAE-C42A-40EC-87C1-ADE1016BF328' ) -- J > K
  , ( DEFAULT, 'FD1B372D-123C-4702-B184-ADE1016BE094', '573C3B40-3031-4E52-96E6-ADE1016BFD5A' ) -- J > L
  , ( DEFAULT, '39FFAFB2-72CD-41BF-9A4B-ADE1016C1464', '7A1DB924-3976-4BEB-B03B-ADE1016C21D6' ) -- M > N
  , ( DEFAULT, '7A1DB924-3976-4BEB-B03B-ADE1016C21D6', '9C663E6A-7D9A-42FD-AE48-ADE1016C3AAB' ) -- N > O
  , ( DEFAULT, '9C663E6A-7D9A-42FD-AE48-ADE1016C3AAB', '573C3B40-3031-4E52-96E6-ADE1016BFD5A' ) -- O > L -- Note, this is valid
  , ( DEFAULT, '9C663E6A-7D9A-42FD-AE48-ADE1016C3AAB', '0D5B3809-8709-45C2-933D-ADE1016C4351' ) -- O > P
  , ( DEFAULT, '8488C4A6-A5A8-4DA1-84E0-ADE1016CBEEB', '6339E76D-53B5-4D6F-861B-ADE1016CC8B6' ) -- Q > R
  , ( DEFAULT, '6339E76D-53B5-4D6F-861B-ADE1016CC8B6', 'BCC90612-EEF3-411D-A44A-ADE1016CE0B1' ) -- R > S
  , ( DEFAULT, 'BCC90612-EEF3-411D-A44A-ADE1016CE0B1', '4D74231A-A232-45E8-9E9A-ADE1016DD1CF' ) -- S > T !! INVALID : S > T > U > S !!
  , ( DEFAULT, '4D74231A-A232-45E8-9E9A-ADE1016DD1CF', 'AE67AED1-B282-4447-9504-ADE1016DF570' ) -- T > U !! INVALID : S > T > U > S !!
  , ( DEFAULT, 'AE67AED1-B282-4447-9504-ADE1016DF570', 'BCC90612-EEF3-411D-A44A-ADE1016CE0B1' ) -- U > S !! INVALID : S > T > U > S !!
  , ( DEFAULT, 'D4063136-3A8F-4C20-9A16-ADE101730C45', 'D4063136-3A8F-4C20-9A16-ADE101730C45' ) -- V > V !! INVALID : V > V - Can't JUST self-split (ok, if it splits into itself + something else, e.g. A > A & A > B, C, and etc) !!
;

Goal:

To find invalid circular reference mappings.

Rules:

"Parent" cannot JUST split into itself. V > V for example. A > A is valid because A further splits into B, C, D, and so on.
Parent cannot split into a child that directly splits into the parent. H > I & I > H for example.
Parent cannot split into a child that indirectly splits into a parent from one of the above levels. S > T > U > V > S and A > D & A > E & E > D

Please see comments in the data setup for a bit clearer picture.

Ultimately, I would like to query those invalid mappings (ParentId, ChildId, and "Path" if possible - similar to how it's laid out next to "INVALID :" part of the comment).

Expected Output:

My (unsuccessful) try at just getting the parent/child id list:

;WITH [CTE] AS
    (
        SELECT  [ParentId]
              , [ChildId]
        FROM    @Data
        WHERE   [ParentId] <> [ChildId]
        UNION ALL
        SELECT  [C].[ParentId]
              , [T].[ChildId]
        FROM    [CTE] AS [C]
        JOIN    @Data AS [T]
        ON      [C].[ChildId] = [T].[ParentId]
                AND [T].[ParentId] <> [T].[ChildId]
    )
SELECT  *
FROM    [CTE]
WHERE   [CTE].[ChildId] = [CTE].[ParentId]
        AND [CTE].[ParentId] IS NOT NULL ;

Did you try to implement this solution: [Is there a way to detect a cycle in Hierarchical Queries in SQL Server?](https://stackoverflow.com/questions/40574229/is-there-a-way-to-detect-a-cycle-in-hierarchical-queries-in-sql-server) Anyway you need to build your hierarchy by "positive* predicate (do not use `<>`, obtain it as is) and add additional flag for cyclic branches (do not process them at the new step of recursion) — astentx, Nov 15 '21 at 22:58
Thank you @astentx. Interesting approach, though I'm not sure I fully grasp what's happening here. Just from the where clause in the main SELECT within the cte, is it integer-values only approach? How would it work with GUIDs? — 007, Nov 15 '21 at 23:08
`;`You can modify [this](https://stackoverflow.com/questions/15080922/infinite-loop-cte-with-option-maxrecursion-0/15081353#15081353) answer to cast GUIDs into strings, rather than `int` values, to assemble the `Path`. `;`Tip: `;`Providing the expected results to go with your sample data helps us help you. — HABO, Nov 15 '21 at 23:17
Thanks for the reference, will come handy after figuring out the main logic. Also updated OP with expected output. — 007, Nov 15 '21 at 23:52

score 3 · Answer 1 · answered Nov 16 '21 at 00:44

You can use SQL Graph to find arbitrary-length path closures. But in an acyclic graph it's unusual to allow A > A is valid so the solution below omits that. You can probably code it back in if there's a good reason for it:

DECLARE @Data TABLE
    (
        [DeptId]   INT DEFAULT ( 1 )
      , [ParentId] UNIQUEIDENTIFIER
      , [ChildId]  UNIQUEIDENTIFIER
    ) ;

INSERT INTO @Data
VALUES
    ( DEFAULT, '4668E1DF-2200-4FF3-9091-ADE1016598B0', '4668E1DF-2200-4FF3-9091-ADE1016598B0' ) -- A > A
  , ( DEFAULT, '4668E1DF-2200-4FF3-9091-ADE1016598B0', '3DD4F212-30C9-43BB-B49D-ADE101659F1B' ) -- A > B
  , ( DEFAULT, '4668E1DF-2200-4FF3-9091-ADE1016598B0', 'F2A3C2A9-FEE6-4E79-8DCB-ADE10165E36E' ) -- A > C
  , ( DEFAULT, '4668E1DF-2200-4FF3-9091-ADE1016598B0', 'FCA427EA-C23F-45C6-82A6-ADE10165ED0F' ) -- A > D !! INVALID : A > D & A > E & E > D !!
  , ( DEFAULT, '4668E1DF-2200-4FF3-9091-ADE1016598B0', 'C6A2B1A9-0F97-40F2-9B54-ADE10165F7AD' ) -- A > E !! INVALID : A > D & A > E & E > D !!
  , ( DEFAULT, 'F2A3C2A9-FEE6-4E79-8DCB-ADE10165E36E', '421A5691-37CB-4EB6-A4F2-ADE101661C90' ) -- B > F
  , ( DEFAULT, 'F2A3C2A9-FEE6-4E79-8DCB-ADE10165E36E', '9450A83D-2A56-4A95-A2A0-ADE101662CAD' ) -- B > G
  , ( DEFAULT, 'C6A2B1A9-0F97-40F2-9B54-ADE10165F7AD', 'FCA427EA-C23F-45C6-82A6-ADE10165ED0F' ) -- E > D !! INVALID : A > D & A > E & E > D !!
  , ( DEFAULT, 'DF9C4FB5-ED7A-4864-9DAE-ADE10169B354', '7CE4DBF9-59FD-4499-BFAB-ADE10169BBD3' ) -- H > I !! INVALID : H > I & I > H !!
  , ( DEFAULT, '7CE4DBF9-59FD-4499-BFAB-ADE10169BBD3', 'DF9C4FB5-ED7A-4864-9DAE-ADE10169B354' ) -- I > H !! INVALID : H > I & I > H !!
  , ( DEFAULT, 'FD1B372D-123C-4702-B184-ADE1016BE094', '48FD8FAE-C42A-40EC-87C1-ADE1016BF328' ) -- J > K
  , ( DEFAULT, 'FD1B372D-123C-4702-B184-ADE1016BE094', '573C3B40-3031-4E52-96E6-ADE1016BFD5A' ) -- J > L
  , ( DEFAULT, '39FFAFB2-72CD-41BF-9A4B-ADE1016C1464', '7A1DB924-3976-4BEB-B03B-ADE1016C21D6' ) -- M > N
  , ( DEFAULT, '7A1DB924-3976-4BEB-B03B-ADE1016C21D6', '9C663E6A-7D9A-42FD-AE48-ADE1016C3AAB' ) -- N > O
  , ( DEFAULT, '9C663E6A-7D9A-42FD-AE48-ADE1016C3AAB', '573C3B40-3031-4E52-96E6-ADE1016BFD5A' ) -- O > L -- Note, this is valid
  , ( DEFAULT, '9C663E6A-7D9A-42FD-AE48-ADE1016C3AAB', '0D5B3809-8709-45C2-933D-ADE1016C4351' ) -- O > P
  , ( DEFAULT, '8488C4A6-A5A8-4DA1-84E0-ADE1016CBEEB', '6339E76D-53B5-4D6F-861B-ADE1016CC8B6' ) -- Q > R
  , ( DEFAULT, '6339E76D-53B5-4D6F-861B-ADE1016CC8B6', 'BCC90612-EEF3-411D-A44A-ADE1016CE0B1' ) -- R > S
  , ( DEFAULT, 'BCC90612-EEF3-411D-A44A-ADE1016CE0B1', '4D74231A-A232-45E8-9E9A-ADE1016DD1CF' ) -- S > T !! INVALID : S > T > U > S !!
  , ( DEFAULT, '4D74231A-A232-45E8-9E9A-ADE1016DD1CF', 'AE67AED1-B282-4447-9504-ADE1016DF570' ) -- T > U !! INVALID : S > T > U > S !!
  , ( DEFAULT, 'AE67AED1-B282-4447-9504-ADE1016DF570', 'BCC90612-EEF3-411D-A44A-ADE1016CE0B1' ) -- U > S !! INVALID : S > T > U > S !!
  , ( DEFAULT, 'D4063136-3A8F-4C20-9A16-ADE101730C45', 'D4063136-3A8F-4C20-9A16-ADE101730C45' ) -- V > V !! INVALID : V > V - Can't JUST self-split (ok, if it splits into itself + something else, e.g. A > A & A > B, C, and etc) !!
;

drop table if exists n
drop table if exists e 

create table n(Id uniqueidentifier) as node
create table e as edge

insert into n(Id)
select parentid from @Data
union
select childid from @Data


INSERT INTO e 
select (SELECT $node_id FROM n WHERE id = ParentId),
       (SELECT $node_id FROM n WHERE id = ChildId)
from @Data;


with q as
(
    select 
            n1.id AS id1,
            STRING_AGG(cast(n2.id as varchar(100)), '->') WITHIN GROUP (GRAPH PATH) AS PathString,
            COUNT(n2.id) WITHIN GROUP (GRAPH PATH)  PathLength,
            LAST_VALUE(n2.id) WITHIN GROUP (GRAPH PATH) AS id2
    from 
      n as n1,
      e for path as e,
      n for path as n2
    WHERE MATCH(SHORTEST_PATH(n1(-(e)->n2)+))
)
select *
from q
where id1 = id2

outputs

id1                                  PathString                                                                                                                PathLength  id2
------------------------------------ ------------------------------------------------------------------------------------------------------------------------- ----------- ------------------------------------
4668E1DF-2200-4FF3-9091-ADE1016598B0 4668E1DF-2200-4FF3-9091-ADE1016598B0                                                                                      1           4668E1DF-2200-4FF3-9091-ADE1016598B0
D4063136-3A8F-4C20-9A16-ADE101730C45 D4063136-3A8F-4C20-9A16-ADE101730C45                                                                                      1           D4063136-3A8F-4C20-9A16-ADE101730C45
DF9C4FB5-ED7A-4864-9DAE-ADE10169B354 7CE4DBF9-59FD-4499-BFAB-ADE10169BBD3->DF9C4FB5-ED7A-4864-9DAE-ADE10169B354                                                2           DF9C4FB5-ED7A-4864-9DAE-ADE10169B354
7CE4DBF9-59FD-4499-BFAB-ADE10169BBD3 DF9C4FB5-ED7A-4864-9DAE-ADE10169B354->7CE4DBF9-59FD-4499-BFAB-ADE10169BBD3                                                2           7CE4DBF9-59FD-4499-BFAB-ADE10169BBD3
BCC90612-EEF3-411D-A44A-ADE1016CE0B1 4D74231A-A232-45E8-9E9A-ADE1016DD1CF->AE67AED1-B282-4447-9504-ADE1016DF570->BCC90612-EEF3-411D-A44A-ADE1016CE0B1          3           BCC90612-EEF3-411D-A44A-ADE1016CE0B1
4D74231A-A232-45E8-9E9A-ADE1016DD1CF AE67AED1-B282-4447-9504-ADE1016DF570->BCC90612-EEF3-411D-A44A-ADE1016CE0B1->4D74231A-A232-45E8-9E9A-ADE1016DD1CF          3           4D74231A-A232-45E8-9E9A-ADE1016DD1CF
AE67AED1-B282-4447-9504-ADE1016DF570 BCC90612-EEF3-411D-A44A-ADE1016CE0B1->4D74231A-A232-45E8-9E9A-ADE1016DD1CF->AE67AED1-B282-4447-9504-ADE1016DF570

David, this is... VERY interesting. I haven't come across this approach (or even seen some of the keywords) so just trying to wrap my head around the logic. I'll test out the code in my workstation tomorrow, but is there an alternative to STRING_AGG for SS '16 (suppose stuff/xml might work, but not sure how "WITHIN GROUP" works with it)? THANK YOU!! — 007, Nov 16 '21 at 06:00
Hmm looked into this further. Seems like Graph Processing might be available from SS '17 and onward. Is there an alternative approach for SS '16? — 007, Nov 16 '21 at 15:39
In TSQL you can use CTEs or JOINS if you limit the depth of the search. But you can't find arbitrarily long cycles, and perf degrades as you increase the depth of the search. So in the general case you would have to use some other language to implement the search for cycles. — David Browne - Microsoft, Nov 16 '21 at 16:44
Makes sense. When I try to use recursive CTE's, it gets errored out due to the depth. Will see if what other options we have. Thanks for your help. — 007, Nov 16 '21 at 16:58

TSQL - Query all circular references

1 Answers1