007
Reputation: 2186
TSQL - Query all circular references
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 ;
Upvotes: 0
Views: 131
Answers (1)
David Browne - Microsoft
Reputation: 89091
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
Upvotes: 3
Related Questions
- Find only self referencing values using recursive query
- How to Find Circular References in CTE between Parent/Child tables
- Recurcive cte to identify circular reference in data
- Recursive SQL query only returning single reference instead of recursive references
- SQL Server: Recursive Query
- Recursive CTE in presence of circular references
- Table Recursion Query In SQL Server 2008 R2
- T-SQL Recursive Select Circular dependency
- TSQL version 2008-R2 - Recursive Select
- Recursive Query on a self referential table (not hierarchical)