SQL Server 2005: Detecting cycles in hierarchical data

Question

I have a typical table of hierarchical data in id, parentId form.

CREATE TABLE Hierarchy (Id int, ParentId int NULL, Name varchar(128));
INSERT INTO Hierarchy VALUES (1, NULL, '1');
INSERT INTO Hierarchy VALUES (2, NULL, '2');
INSERT INTO Hierarchy VALUES (3, NULL, '3');
INSERT INTO Hierarchy VALUES (4, 1, '1.1');
INSERT INTO Hierarchy VALUES (5, 1, '1.2');
INSERT INTO Hierarchy VALUES (6, 4, '1.1.1');

I need to detect cycles like below in the existing data.

Id  ParentId  Name
27  8         'foo'
8   19        'bar'
19  27        'busted'

The Ids are from another table so I cannot use ordering of the Ids as part of the solution. There are about 1/2 million rows. The data is a large number of independent trees of height 1-5. The intent is to clean up the data to eliminate the cycles then add a trigger to the table to prevent cycles in the future.

I know the algorithms for cycle detection. It seems to me like it should be a common problem. So, I was wondering if there was a handy way in the SQL Server `box' to accomplish this with a minimum of code.

Answer 1

If you have Sql Server 2005, you can use the With clause to do a recursive query against your table. This will allow you to collapse the logic, as that seems to be your primary goal.

http://blogs.msdn.com/craigfr/archive/2007/10/25/recursive-ctes.aspx