How to Find Circular References in CTE between Parent/Child tables

Question

I have a CTE to show dependency tree over 2 tables (a parent and a child table). There is a data problem resulting in a circular dependency, resulting in a Max Recursion level error being thrown. i.e.

Table: Parent
Id
ItemId

Table: Child
Id
ParentId
ItemId

Example Circular Ref data
Table: Parent
Id   ItemId
1    A
2    B

Table: Child
Id   ParentId  ItemId
1    1         B
2    2         A

There are thousands of rows in these tables. How can I write a query identify the offending reference? Or is there a way to set the Max Recursion level that will then just stop the CTE once hit instead of throw an error...then I could view the results and identify the problem child.

WITH Recursive_CTE AS 
(
    SELECT        
        ItemId, 
        CAST(ItemDescription AS varchar(100)) AS ItemDescription, 
        Qty, 
        CAST(ParentItemId AS SmallInt) AS ParentItemId, 
        CAST(ItemId AS varchar(100)) AS ParentGroupItemId, 
        CAST('   -' AS varchar(100)) AS LVL, 
        CAST(ItemId AS varchar(100)) AS HierarchyItem, 
        CAST(SKU AS varchar(100)) AS HierarchySKU, 
        CAST(ItemDescription AS varchar(100)) AS HierarchyName, 
        0 AS RecursionLevel
    FROM dbo.vw_BOM AS child
    WHERE (ParentItemId = 0) 
    --and ItemId = @BOMHeaderItemId

    UNION ALL

    SELECT        
        child.ItemId, 
        CAST(parent.LVL + child.ItemDescription AS varchar(100)) AS ItemDescription, 
        child.Qty, 
        CAST(child.ParentItemId AS SmallInt) AS ParentItemId, 
        parent.ParentGroupItemId, 
        CAST('   -' + parent.LVL AS varchar(100)) AS LVL, 
        CAST(parent.HierarchyItem + ':' + CAST(child.ItemId AS varchar(100)) AS varchar(100)) AS HierarchyItem,
        CAST(parent.HierarchySKU + ':' + CAST(child.SKU AS varchar(100)) AS varchar(100)) AS HierarchySKU, 
        CAST(parent.HierarchyName + '/' + CAST(child.ItemDescription AS varchar(100)) AS varchar(100)) AS HierarchyName, 
        parent.RecursionLevel + 1 AS RecursionLevel
    FROM Recursive_CTE AS parent INNER JOIN
            dbo.vw_BOM AS child ON child.ParentItemId = parent.ItemId
)

SELECT        
    Recursive_CTE_1.RecursionLevel, 
    Recursive_CTE_1.ParentGroupItemId, 
    Recursive_CTE_1.ParentItemId, 
    Recursive_CTE_1.ItemId, 
    Recursive_CTE_1.Qty, 
    DATALENGTH(Recursive_CTE_1.LVL) AS LVLLength,
    Recursive_CTE_1.ItemDescription, 
    item.SKU, 
    item.OnHandQty, 
    item.AllocQty, 
    item.AvailableQty, 
    item.ToBeReceivedQty, 
    item.AvailableWFutureQty,   
    Recursive_CTE_1.HierarchyItem, 
    Recursive_CTE_1.HierarchySKU, 
    Recursive_CTE_1.HierarchyName
FROM Recursive_CTE AS Recursive_CTE_1 INNER JOIN
        dbo.vw_ItemInventorySummary AS item ON Recursive_CTE_1.ItemId = item.Id
ORDER BY Recursive_CTE_1.HierarchySKU
option (maxrecursion 200)

The View vw_BOM

SELECT        dbo.BillOfMaterialHeader.Id AS Id, dbo.BillOfMaterialHeader.ItemId AS ItemId, 0 AS ParentItemId, FGItems.SKU AS SKU, FGItems.SKU + N': ' + FGItems.ShortDescription AS ItemDescription, 
                         dbo.BillOfMaterialHeader.Quantity AS Qty
FROM            dbo.BillOfMaterialHeader INNER JOIN
                         dbo.Items AS FGItems ON dbo.BillOfMaterialHeader.ItemId = FGItems.Id
UNION ALL
SELECT        dbo.BillOfMaterialDetail.Id AS Id, dbo.BillOfMaterialDetail.ItemId AS ItemId, BOMHdr.ItemId AS ParentItemId, RMItems.SKU AS SKU, RMItems.SKU + N': ' + RMItems.ShortDescription AS ItemDescription, 
                         dbo.BillOfMaterialDetail.Quantity AS Qty
FROM            dbo.Items AS RMItems INNER JOIN
                         dbo.BillOfMaterialDetail ON RMItems.Id = dbo.BillOfMaterialDetail.ItemId INNER JOIN
                         dbo.BillOfMaterialHeader BOMHdr ON dbo.BillOfMaterialDetail.BillOfMaterialHeaderId = BOMHdr.Id

UPDATE

Tab's answer pointed me in the right direction. I used the flattened Parent Child table in vw_BOM and then joined it to itself per Tab's answer, which showed me where 6 Items had the same Item Id in the Parent Table and the Child Table. Like so:

SELECT        dbo.vw_BOM.SKU AS ParentSKU, vw_BOM_1.SKU AS ChildSKU
FROM            dbo.vw_BOM INNER JOIN
                         dbo.vw_BOM AS vw_BOM_1 ON dbo.vw_BOM.ItemId = vw_BOM_1.ParentItemId AND dbo.vw_BOM.ParentItemId = vw_BOM_1.ItemId

Answer 1

I have seen these issues before and have resorted to adding items one level at a time, ignoring those seen before.

Answer 2

Your CTE already has a hierarchy with the ItemID path concatenated. How about using that to determine if the item has already been seen?

Add a new column to the anchor portion of your CTE, HasCycle = Convert(bit, 0).

Then in the recursive portion of your CTE, add the column and a condition in the WHERE clause like so:

...
UNION ALL
SELECT
   ... other columns,
   HasCycle = Convert(bit,
      CASE
          WHEN ':' + parent.HierarchyItem + ':' LIKE
             '%:' + Convert(varchar(100), child.ItemID) + ':%'
          THEN 1
          ELSE 0
      END)
FROM
   ...
WHERE
   ...
   AND parent.HasCycle = 0 --terminate after cycle is found
;

Then you can select from the recursive CTE WHERE HasCycle = 1 and see all the rows that begin a cycle and their exact path upwards in the HierarchyItem.

Answer 3

Simple self-join should do it:

SELECT * FROM MyTable t1
INNER JOIN MyTable t2
  ON t1.Parent=t2.Child
  AND t1.Child=t2.Parent