Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase ««123»»

Common table expressions and circular references Expand / Collapse
Author
Message
Posted Monday, January 31, 2011 8:50 AM
Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Yesterday @ 5:39 PM
Points: 1,382, Visits: 1,752
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.

Post #1056241
Posted Monday, January 31, 2011 9:12 AM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Wednesday, June 11, 2014 5:34 AM
Points: 146, 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
Post #1056250
Posted Monday, January 31, 2011 10:38 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Monday, November 17, 2014 6:00 AM
Points: 1,049, Visits: 3,012
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
Post #1056303
Posted Monday, January 31, 2011 11:48 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Wednesday, December 10, 2014 11:06 AM
Points: 1,113, Visits: 706
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
SQL Server MVP
SQLblog.com: THE SQL Server Blog Spot on the Web
Post #1056346
Posted Monday, January 31, 2011 11:55 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Wednesday, December 10, 2014 11:06 AM
Points: 1,113, Visits: 706
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


--
Adam Machanic
SQL Server MVP
SQLblog.com: THE SQL Server Blog Spot on the Web
Post #1056352
Posted Tuesday, February 1, 2011 2:06 AM
Old Hand

Old HandOld HandOld HandOld HandOld HandOld HandOld HandOld Hand

Group: General Forum Members
Last Login: Yesterday @ 7:54 AM
Points: 304, Visits: 645
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.
Post #1056664
Posted Tuesday, February 1, 2011 8:29 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Monday, November 17, 2014 6:00 AM
Points: 1,049, Visits: 3,012
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
Post #1056856
Posted Tuesday, February 1, 2011 8:36 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Wednesday, December 10, 2014 11:06 AM
Points: 1,113, Visits: 706
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


--
Adam Machanic
SQL Server MVP
SQLblog.com: THE SQL Server Blog Spot on the Web
Post #1056862
Posted Tuesday, February 1, 2011 10:42 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Monday, November 17, 2014 6:00 AM
Points: 1,049, Visits: 3,012
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

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
Post #1056981
Posted Tuesday, February 1, 2011 11:07 AM
Old Hand

Old HandOld HandOld HandOld HandOld HandOld HandOld HandOld Hand

Group: General Forum Members
Last Login: Monday, December 1, 2014 7:26 PM
Points: 368, Visits: 532
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

Post #1056994
« Prev Topic | Next Topic »

Add to briefcase ««123»»

Permissions Expand / Collapse