SQL Clone
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


Common table expressions and circular references


Common table expressions and circular references

Author
Message
sknox
sknox
SSCertifiable
SSCertifiable (5.6K reputation)SSCertifiable (5.6K reputation)SSCertifiable (5.6K reputation)SSCertifiable (5.6K reputation)SSCertifiable (5.6K reputation)SSCertifiable (5.6K reputation)SSCertifiable (5.6K reputation)SSCertifiable (5.6K reputation)

Group: General Forum Members
Points: 5601 Visits: 3032
James Stephens (1/31/2011)
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


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.
andy.roberts
andy.roberts
SSC Veteran
SSC Veteran (254 reputation)SSC Veteran (254 reputation)SSC Veteran (254 reputation)SSC Veteran (254 reputation)SSC Veteran (254 reputation)SSC Veteran (254 reputation)SSC Veteran (254 reputation)SSC Veteran (254 reputation)

Group: General Forum Members
Points: 254 Visits: 124
gerg-520419 (1/31/2011)


code ...

will select just cycles. Needn't to calculate 'correct' max level beforehand.

e b 3 e->b->c->d->b
a b 3 a->b->c->d->b



This is another alternative that will show the required hierarchy and highlight where circular references begin -


WITH GroupMembers (Child, ParentGroup, Level, hierarchypath)
AS
(-- Anchor member definition
SELECT 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 g.child,
g.parent,
Level + 1,
hierarchypath + '->' + g.parent -- Add '-->...' to end when recursion found
+ Case When gm.hierarchypath like '%->'+g.parent+'->%' Then '-->...'
Else ''
End

FROM ChildrenAndParents as g
INNER JOIN GroupMembers AS gm
ON gm.parentgroup = g.child
--Exclude if the hierarchypath text contains a recursion
where gm.hierarchypath not like '%->...'

)




which gives -

child     parentgroup level       hierarchypath
--------- ----------- ----------- -----------------------
a b 0 a->b
a c 1 a->b->c
a d 2 a->b->c->d
a b 3 a->b->c->d->b-->...
e b 0 e->b
e c 1 e->b->c
e d 2 e->b->c->d
e b 3 e->b->c->d->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.

child     parentgroup level       hierarchypath
--------- ----------- ----------- -----------------------
b c 0 b->c
c d 0 c->d
etc


Can anyone explain why they were there/why they were removed?

Andy

--------------------------------------------------------------

“Doubt is not a pleasant condition, but certainty is absurd.” Voltaire
majorbloodnock
majorbloodnock
Hall of Fame
Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)

Group: General Forum Members
Points: 3611 Visits: 3064
andy.roberts (1/31/2011)

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.

child     parentgroup level       hierarchypath
--------- ----------- ----------- -----------------------
b c 0 b->c
c d 0 c->d
etc


Can anyone explain why they were there/why they were removed?

Andy

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


WHERE child not in (select parent from childrenandparents)


from the anchor definition. I don't suppose that could have happened whilst you were streamlining my CTE code, could it?

Semper in excretia, sumus solum profundum variat
Adam Machanic
Adam Machanic
SSCarpal Tunnel
SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)

Group: General Forum Members
Points: 4759 Visits: 735
CELKO (1/31/2011)
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.


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:


Mgr Emp
NULL A
A B
B C


And then do:


UPDATE tbl
SET Mgr = 'C'
WHERE Emp = 'B'



... 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:


CREATE TRIGGER tg_NoCycles
ON Employee_Temp
FOR UPDATE
AS
BEGIN
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
END
END
GO



--
Adam Machanic
whoisactive
Adam Machanic
Adam Machanic
SSCarpal Tunnel
SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)

Group: General Forum Members
Points: 4759 Visits: 735
James Stephens (1/31/2011)

It's 2011. Why the heck doesn't Microsoft store AD information in a true relational db to begin with?


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

--
Adam Machanic
whoisactive
serg-52
serg-52
SSCarpal Tunnel
SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)

Group: General Forum Members
Points: 4084 Visits: 1831
Adam Machanic (1/31/2011)
...Next, a unique constraint on the employee column, so that the same employee can't appear in the hierarchy twice under different managers...


This is correct for tree-like hierarchy only, which is not the case with AD adjacency model.
AD is rather network-like.
majorbloodnock
majorbloodnock
Hall of Fame
Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)

Group: General Forum Members
Points: 3611 Visits: 3064
Adam Machanic (1/31/2011)
....Next, a unique constraint on the employee column, so that the same employee can't appear in the hierarchy twice under different managers....

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.

Semper in excretia, sumus solum profundum variat
Adam Machanic
Adam Machanic
SSCarpal Tunnel
SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)SSCarpal Tunnel (4.8K reputation)

Group: General Forum Members
Points: 4759 Visits: 735
majorbloodnock (2/1/2011)
The technical logic is fine, but in practice, why shouldn't an employee have two managers?


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

--
Adam Machanic
whoisactive
majorbloodnock
majorbloodnock
Hall of Fame
Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)

Group: General Forum Members
Points: 3611 Visits: 3064
Adam Machanic (2/1/2011)
majorbloodnock (2/1/2011)
The technical logic is fine, but in practice, why shouldn't an employee have two managers?


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

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.

Semper in excretia, sumus solum profundum variat
NULLgarity
NULLgarity
Say Hey Kid
Say Hey Kid (672 reputation)Say Hey Kid (672 reputation)Say Hey Kid (672 reputation)Say Hey Kid (672 reputation)Say Hey Kid (672 reputation)Say Hey Kid (672 reputation)Say Hey Kid (672 reputation)Say Hey Kid (672 reputation)

Group: General Forum Members
Points: 672 Visits: 534
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.

Blog |
Twitter | LinkedIn


Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum







































































































































































SQLServerCentral


Search