SQLServerCentral / Article Discussions / Article Discussions by Author / Discuss content posted by Geoff Norman / Common table expressions and circular references / Latest Posts

RE: Common table expressions and circular references

Lowell — Sun, 18 Mar 2012 10:01:18 GMT

For those of you who followed this thread, did anyone use this method to handle foreign keys with circular references?I adapted a couple of the posted examples, and against one of my databases which i know has circular references, I'm thinking this is not really going to give results in a hierarchy correctly; it seems that the hierarchy is more of the count of FK levels between the objects, and not necessarily the hiarchy order.i was fiddling around with this trying to get all objects in a hierarchy, butIt seems to me to be pretty inefficient; 20 plus minutes on a machine with no resources in use at all, along with 60,000 rows;[code];WITH ChildrenAndParentsAS(SELECTparent_object_id AS object_id,convert(varchar(255),OBJECT_NAME(parent_object_id)) AS child,referenced_object_id AS referenced_major_id,convert(varchar(255),OBJECT_NAME(referenced_object_id)) AS parentFROM sys.foreign_keys),GroupMembers (Child, ParentGroup, Level, hierarchypath)AS(-- Anchor member definitionSELECT g.child, g.parent, 0 AS Level, convert(varchar(max), g.child + '->' + g.parent) AS hierarchypathFROM ChildrenAndParents AS gWHERE child not in (select parent from ChildrenAndParents)UNION ALL-- Recursive member definitionSELECT g.child, g.parent, Level + 1, hierarchypath + '->' + g.parent -- Add '-->...' to end when recursion found + Case When gm.hierarchypath like '%->'+g.parent+'->%' Then '-->...' Else '' EndFROM ChildrenAndParents as gINNER JOIN GroupMembers AS gmON gm.parentgroup = g.child--Exclude if the hierarchypath text contains a recursionwhere gm.hierarchypath not like '%->...')select left(hierarchypath, charindex('->', hierarchypath) - 1) as child, parentgroup, level, hierarchypathfrom groupmembersoption(maxrecursion 20);[/code]

RE: Common table expressions and circular references

majorbloodnock — Wed, 02 Feb 2011 05:25:26 GMT

Well, now you're getting my poor old brain smoking. I had to think long and hard before realising the problem here.I agree that in a true tree structure each node except the root will have one and only one parent. However, there are in practice many perfectly acceptable hierarchal situations where relationships mesh together so that a node can have more than one parent, and that's where I think this trigger would have an issue. However, I have to admit I'm by no means certain I haven't missed something in my understanding here.

RE: Common table expressions and circular references

CELKO — Tue, 01 Feb 2011 13:34:45 GMT

Let me propose higher level constraints to do the job. Trees have certain properties:1) The tree has one and only one root node 2) The root node has in-degree = 0 (i.e. no parent node)3) All non-root nodes have in-degree = 1 (i.e. exactly one parent)node4) The number of edges is one less than the number of nodes in the treeLet's declare the table with CREATE TABLE AdjacencyListModel(parent_node CHAR(2), -- null means root child_node CHAR(2) NOT NULL UNIQUE, -- one parent CHECK (parent_node <> child_node)); -- shortest cycle checkThe shortest cycle is more for the optimizer than data integrity, but it prevents graphs like this which meet rule #4, but are not trees. {a,b,c} is a cycle and {d} is an orphan. A / \ DB - CNow let's enforce the rules with aggregate functions instead of procedure code and BIT flags: CREATE TRIGGER Valid_Tree_CheckON AdjacencyListModelFOR UPDATE, INSERT, DELETE ASBEGINIF NOT EXISTS (SELECT * FROM AdjacencyListModel HAVING COUNT(*) = COUNT(parent_node) +1)BEGIN RAISERROR('invalid root', 16, 1); ROLLBACK;END;IF NOT EXISTS (SELECT * FROM (SELECT parent_node FROM AdjacencyListModel UNION SELECT child_node FROM AdjacencyListModel) AS X(i) HAVING COUNT(i) = (SELECT COUNT(*) FROM AdjacencyListModel))BEGIN RAISERROR('invalid edge and node counts', 16, 1); ROLLBACK;END;END; --Valid_Tree_CheckWe could do this with a CREATE ASSERTION or full ANSI Standard CHECK(),

RE: Common table expressions and circular references

NULLgarity — Tue, 01 Feb 2011 11:07:42 GMT

I chuckled when I saw the title of this article as I was working on a recursive CTE just last Friday and ran into circular references. I laughed out loud when I started to read the article as I, too, was working with Active Directory group memberships as well. FWIW, I came up with essentially the same techniques for dealing with it. I also plan to bring the circular relationships to the attention of our AD administrators and see if we can remove them somehow.Thanks for the timely article.

RE: Common table expressions and circular references

majorbloodnock — Tue, 01 Feb 2011 10:42:36 GMT

[quote][b]Adam Machanic (2/1/2011)[/b][hr][quote][b]majorbloodnock (2/1/2011)[/b][hr]The technical logic is fine, but in practice, why shouldn't an employee have two managers? [/quote]Having actually had two managers (and then, later, three) at one point in my career, I can tell you firsthand that it's a nightmare. Manager A: "Drop everything and fix widget #123."[later]Manager B: "Why haven't you finished fixing widget #456?"Me: "Manager A told me to stop working on that!"Manager B: "Forget what he said! Work on #456!"[later]Manager A: "Why the **** haven't you fixed #123?!?!"... etc. Oh, the two managers should have talked to one another and synchronized? Sure, they should have, but human nature works in different ways and people tend to disagree, especially when they're put into positions of what is supposed to be equal power. I don't, personally, believe that any form of matrix management can work in any organization where something is actually supposed to get accomplished.But, YMMV. And apologies for the aside to the conversation :-D[/quote]To be frank, I've seen that rather more from managers who can't let go. The ones who have managers reporting to them, but who still insist on micromanaging the whole team. Not pretty....And no problem with wandering off at a tangent; I'm regularly guilty of doing it to other people's threads.

RE: Common table expressions and circular references

Adam Machanic — Tue, 01 Feb 2011 08:36:53 GMT

[quote][b]majorbloodnock (2/1/2011)[/b][hr]The technical logic is fine, but in practice, why shouldn't an employee have two managers? [/quote]Having actually had two managers (and then, later, three) at one point in my career, I can tell you firsthand that it's a nightmare. Manager A: "Drop everything and fix widget #123."[later]Manager B: "Why haven't you finished fixing widget #456?"Me: "Manager A told me to stop working on that!"Manager B: "Forget what he said! Work on #456!"[later]Manager A: "Why the **** haven't you fixed #123?!?!"... etc. Oh, the two managers should have talked to one another and synchronized? Sure, they should have, but human nature works in different ways and people tend to disagree, especially when they're put into positions of what is supposed to be equal power. I don't, personally, believe that any form of matrix management can work in any organization where something is actually supposed to get accomplished.But, YMMV. And apologies for the aside to the conversation :-D

RE: Common table expressions and circular references

majorbloodnock — Tue, 01 Feb 2011 08:29:23 GMT

[quote][b]Adam Machanic (1/31/2011)[/b][hr]....Next, a unique constraint on the employee column, so that the same employee can't appear in the hierarchy twice under different managers....[/quote]Thereby, of course, hangs a fairly fundamental problem. The technical logic is fine, but in practice, why shouldn't an employee have two managers? I'll admit it's not that usual, but if a managerial position is a job-share, you've got two part time employees who're both legitimate managers to the whole of the subordinate team. It might be difficult to map hierarchally, but we can't force a change on the business process just because our software can't cope with the business's needs.

RE: Common table expressions and circular references

serg-52 — Tue, 01 Feb 2011 02:06:52 GMT

[quote][b]Adam Machanic (1/31/2011)[/b]...Next, a unique constraint on the employee column, so that the same employee can't appear in the hierarchy twice under different managers...[/quote]This is correct for tree-like hierarchy only, which is not the case with AD adjacency model.AD is rather network-like.

RE: Common table expressions and circular references

Adam Machanic — Mon, 31 Jan 2011 11:55:52 GMT

[quote][b]James Stephens (1/31/2011)[/b][hr]It's 2011. Why the heck doesn't Microsoft store AD information in a true relational db to begin with?[/quote]The newest versions of AD use SQL Server (or at least some variation on SQL Server -- perhaps not a normal build) as the internal data store.As to whether that's a "true relational DB," that's an entirely different question :-D

RE: Common table expressions and circular references

Adam Machanic — Mon, 31 Jan 2011 11:48:03 GMT

[quote][b]CELKO (1/31/2011)[/b][hr]Nice piece! Now let's go one step further. How do you write constraints to prevent cycles (and orphans) in an adjacency list model? The best I have done for the adjacency list in a TRIGGER with a loop which is what your recursive CTE is, under the covers. But the loop does not have a built-in limit of 32.[/quote]Orphans? No problem--that's what foreign key constraints are there for.Cycles? A bit trickier, but easy enough. First step, a check constraint so that an employee can't be his or her own manager. (We'll say that the manager for the root node is NULL.) Next, a unique constraint on the employee column, so that the same employee can't appear in the hierarchy twice under different managers. That eliminates most cycles, but we still have a potential issue where we can insert the following data:[code="plain"]Mgr EmpNULL AA BB C[/code]And then do:[code="sql"]UPDATE tblSET Mgr = 'C'WHERE Emp = 'B'[/code]... getting rid of that requires a trigger; below is one I came up with when working on my book, "Expert SQL Server 2005 Development." The idea is to start at the updated node(s) and walk up the hierarchy toward the root. If, during that walk, we find a case where the parent "manager" is the same as the child "employee," we know that something is amiss:[code="sql"]CREATE TRIGGER tg_NoCyclesON Employee_TempFOR UPDATEASBEGIN SET NOCOUNT ON --Only check if the ManagerId column was updated IF NOT UPDATE(ManagerId) RETURN --Avoid cycles DECLARE @CycleExists BIT SET @CycleExists = 0 --Traverse up the hierarchy toward the --root node ;WITH e AS ( SELECT EmployeeId, ManagerId FROM inserted UNION ALL SELECT e.EmployeeId, et.ManagerId FROM Employee_Temp et JOIN e ON e.ManagerId = et.EmployeeId WHERE et.ManagerId IS NOT NULL AND e.ManagerId <> e.EmployeeId ) SELECT @CycleExists = 1 FROM e WHERE e.ManagerId = e.EmployeeId IF @CycleExists = 1 BEGIN RAISERROR('The update introduced a cycle', 16, 1) ROLLBACK ENDENDGO[/code]

RE: Common table expressions and circular references

majorbloodnock — Mon, 31 Jan 2011 10:38:40 GMT

[quote][b]andy.roberts (1/31/2011)[/b]Something I can't get my head round - can anyone explain ... The result of running the first CTE before the circular relationship was added had extra rows reported that aren't there when the circular check is added. E.g. [code="plain"]child parentgroup level hierarchypath--------- ----------- ----------- -----------------------b c 0 b->cc d 0 c->detc[/code]Can anyone explain why they were there/why they were removed?Andy[/quote]Since b and c both exist in the parent column of the underlying table, they shouldn't appear in the first pass. The only way I can get the extra rows you've mentioned into the CTE results is if I comment out the line[code="plain"]WHERE child not in (select parent from childrenandparents)[/code]from the anchor definition. I don't suppose that could have happened whilst you were streamlining my CTE code, could it?

RE: Common table expressions and circular references

andy.roberts — Mon, 31 Jan 2011 09:12:27 GMT

[quote][b]gerg-520419 (1/31/2011)[/b][hr]code ...will select just cycles. Needn't to calculate 'correct' max level beforehand.e b 3 e->b->c->d->ba b 3 a->b->c->d->b[/quote]This is another alternative that will show the required hierarchy and highlight where circular references begin -[code="sql"]WITH GroupMembers (Child, ParentGroup, Level, hierarchypath)AS(-- Anchor member definitionSELECT g.child, g.parent, 0 AS Level, convert(varchar(max), g.child + '->' + g.parent) AS hierarchypathFROM ChildrenAndParents AS gWHERE child not in (select parent from ChildrenAndParents)UNION ALL-- Recursive member definitionSELECT g.child, g.parent, Level + 1, hierarchypath + '->' + g.parent -- Add '-->...' to end when recursion found[b] + Case When gm.hierarchypath like '%->'+g.parent+'->%' Then '-->...' Else '' End[/b]FROM ChildrenAndParents as gINNER JOIN GroupMembers AS gmON gm.parentgroup = g.child[b]--Exclude if the hierarchypath text contains a recursionwhere gm.hierarchypath not like '%->...'[/b])[/code]which gives -[code="plain"]child parentgroup level hierarchypath--------- ----------- ----------- -----------------------a b 0 a->ba c 1 a->b->ca d 2 a->b->c->da b 3 a->b->c->d->b-->...e b 0 e->be c 1 e->b->ce d 2 e->b->c->de b 3 e->b->c->d->b-->...[/code]-------Something I can't get my head round - can anyone explain ... The result of running the first CTE before the circular relationship was added had extra rows reported that aren't there when the circular check is added. E.g. [code="plain"]child parentgroup level hierarchypath--------- ----------- ----------- -----------------------b c 0 b->cc d 0 c->detc[/code]Can anyone explain why they were there/why they were removed?Andy

RE: Common table expressions and circular references

sknox — Mon, 31 Jan 2011 08:50:46 GMT

[quote][b]James Stephens (1/31/2011)[/b][hr]Hi,Great article. On the same general topic but stepping back to the part about getting the AD data into tables:It's 2011. Why the heck doesn't Microsoft store AD information in a true relational db to begin with?--Jim[/quote]Because AD is a hierarchical data store. Based on LDAP, it's very much like XML. Parent-child relationships, extensible object types, and the variety of attribute types mean that a relational data store is a poor fit -- especially since the primary use case is individual item transactional processing.

RE: Common table expressions and circular references

majorbloodnock — Mon, 31 Jan 2011 07:56:20 GMT

Perhaps more pertinent in criticising AD is its accessibility. ADSI and LDAP are technically effective, but hardly user-friendly.

RE: Common table expressions and circular references

Steve Jones - SSC Editor — Mon, 31 Jan 2011 07:46:39 GMT

AD is a distributed database of sorts. I think it was built by a separate team, and optimized for a different purpose. Just like I'm not sure mail belongs in a RDBMS, not sure that directories should be.

RE: Common table expressions and circular references

James Stephens — Mon, 31 Jan 2011 07:18:03 GMT

Hi,Great article. On the same general topic but stepping back to the part about getting the AD data into tables:It's 2011. Why the heck doesn't Microsoft store AD information in a true relational db to begin with?--Jim

RE: Common table expressions and circular references

majorbloodnock — Mon, 31 Jan 2011 04:13:33 GMT

[quote][b]gerg-520419 (1/31/2011)[/b][hr][code="sql"]WITH GroupMembers (Bottom, Child, ParentGroup, Level, hierarchypath) AS ( -- Anchor member definition SELECT g.child as Bottom, g.child, g.parent, 0 AS Level, convert(varchar(max), g.child + '->' + g.parent) AS hierarchypath FROM childrenandparents AS g WHERE child not in (select parent from childrenandparents) UNION ALL -- Recursive member definition SELECT gm.bottom, g.child, g.parent, Level + 1, hierarchypath + '->' + g.parent FROM childrenandparents as g INNER JOIN GroupMembers AS gm ON gm.parentgroup = g.child [b]where hierarchypath not like '%'+g.child +'->' + g.parent + '%'[/b]) select bottom, parentgroup, level, hierarchypath from groupmembers [b]where hierarchypath like '%'+parentgroup + '->' + '%'[/b]order by level desc option(maxrecursion 100);[/code]will select just cycles. Needn't to calculate 'correct' max level beforehand.e b 3 e->b->c->d->ba b 3 a->b->c->d->b[/quote]Agreed.I expect there are several other areas too where my CTEs could be tidied up; indeed, I'd be rather surprised if there weren't....

RE: Common table expressions and circular references

majorbloodnock — Mon, 31 Jan 2011 04:10:16 GMT

[quote][b]Peter.Frissen (1/31/2011)[/b][hr]Hi, Cool stuff this CTE, but I have a question about the example.Suppose I want to return not only the leaf-to-parent relation, but also any subparent-to-parent? For example, b -> c (level 0), b -> d (level 1) and c -> d (level 0)?Thanks in advance![/quote]I think I understand your question, but apologies if not.My example CTE starts off with ultimate children (records existing in the "child" column, but not in the "parent" column) and then wanders up the hierarchal tree. You could just as easily work the other way around (select all "parent" records which don't exist in the "child" column) and wander down the tree. In your case, it might even be worth starting off with all "parent" records irrespective of whether they're children or not. It'll increase the size of your CTE, but will allow you to see inherited relationships between parents and children within the middle of the hierarchal tree.Hope that helps

RE: Common table expressions and circular references

majorbloodnock — Mon, 31 Jan 2011 03:57:37 GMT

RE: Common table expressions and circular references

serg-52 — Mon, 31 Jan 2011 02:41:38 GMT

[code="sql"]WITH GroupMembers (Bottom, Child, ParentGroup, Level, hierarchypath) AS ( -- Anchor member definition SELECT g.child as Bottom, g.child, g.parent, 0 AS Level, convert(varchar(max), g.child + '->' + g.parent) AS hierarchypath FROM childrenandparents AS g WHERE child not in (select parent from childrenandparents) UNION ALL -- Recursive member definition SELECT gm.bottom, g.child, g.parent, Level + 1, hierarchypath + '->' + g.parent FROM childrenandparents as g INNER JOIN GroupMembers AS gm ON gm.parentgroup = g.child [b]where hierarchypath not like '%'+g.child +'->' + g.parent + '%'[/b]) select bottom, parentgroup, level, hierarchypath from groupmembers [b]where hierarchypath like '%'+parentgroup + '->' + '%'[/b]order by level desc option(maxrecursion 100);[/code]will select just cycles. Needn't to calculate 'correct' max level beforehand.e b 3 e->b->c->d->ba b 3 a->b->c->d->b

RE: Common table expressions and circular references

Peter.Frissen — Mon, 31 Jan 2011 02:34:29 GMT

Hi, Cool stuff this CTE, but I have a question about the example.Suppose I want to return not only the leaf-to-parent relation, but also any subparent-to-parent? For example, b -> c (level 0), b -> d (level 1) and c -> d (level 0)?Thanks in advance!

RE: Common table expressions and circular references

CELKO — Mon, 31 Jan 2011 01:24:14 GMT

Nice piece! Now let's go one step further. How do you write constraints to prevent cycles (and orphans) in an adjacency list model? The best I have done for the adjacency list in a TRIGGER with a loop which is what your recursive CTE is, under the covers. But the loop does not have a built-in limit of 32.

Common table expressions and circular references

majorbloodnock — Sat, 29 Jan 2011 12:41:47 GMT

Comments posted to this topic are about the item [B]Common table expressions and circular references[/B]