Recursive query loops

Question

Recursive query loops

majorbloodnock

SSCrazy Eights

Points: 9389
More actions
January 2, 2008 at 2:02 am

#182269

This isn't a problem per se, but more a bit of angling for suggestions.
I currently have a vb script that queries our Active Directory, to show the group membership for a given user account, including the inherited group memberships with respect to nested groups. Given I'm going to need to use this functionality for historical reporting purposes (J-SOX), I'm currently intending to do approximately the same within a SQL database, so I can store the results.
Now most of this isn't a problem. However, the one thing that has been an issue to date (that I'd obviously like to avoid in SQL Server) is the area of cyclic membership i.e. group a is a member of group b, group b is a member of group c and group c is a member of group a. In that scenario, the current piece of recursive script (based on the article here)unsurprisingly gets itself into a loop.
So, without suggesting a slavish adherence to that particular query method, I'd like to ask if anyone has any bright ideas about how to query AD for group memberships, including those inherited from nested groups, whilst being able to recognise (and therefore trap) cyclic group memberships.
Any ideas?
Semper in excretia, suus solum profundum variat

Viewing 10 posts - 1 through 9 (of 9 total)

You must be logged in to reply to this topic. Login to reply

Jeff Moden SSC Guru Points: 1003863 More actions · Answer 1

Well, kind'a... haven't taken the time to CTE this puppy, yet... if you do, would you mind sharing it, please? Thanks...

The "key" is that at least one of the groups must have a double parent... one in the cyclic group and one a level up. You can see in the code below what the difference will be if you have one or all having double parent's. You can also see that if a cyclic group has no double parents, then that group won't show in the hierarcy table (nor would any "orphan")... very useful for finding orphans including cyclic groups which the code also contains....

--=======================================================================================

-- Setup some test data... note that nothing in this section is part of the actual

-- solution except for the fact that some of the children in cyclic groups have

-- double parents to relate the cyclic group to the next level up.

----=======================================================================================

--===== Setup a "quiet" environment

SET NOCOUNT ON

--===== Create a table to hold some test data.

-- This is NOT part of the solution

CREATE TABLE #yourtable

(

Child VARCHAR(10),

Parent VARCHAR(10)

)

--===== Populate the test table with the "cyclic and other data

INSERT INTO #yourtable

(Child,Parent)

SELECT 'GroupA1','GroupB1' UNION ALL --All groups in the cyclic have double parents

SELECT 'GroupB1','GroupC1' UNION ALL

SELECT 'GroupC1','GroupA1' UNION ALL

SELECT 'GroupA1','Company1' UNION ALL

SELECT 'GroupB1','Company1' UNION ALL

SELECT 'GroupC1','Company1' UNION ALL

SELECT 'Company1',NULL

UNION ALL ----------------------------------------

SELECT 'GroupA2','GroupB2' UNION ALL --only one group in the cyclic has double parents

SELECT 'GroupB2','GroupC2' UNION ALL

SELECT 'GroupC2','GroupA2' UNION ALL

SELECT 'GroupA2','Company2' UNION ALL

SELECT 'Company2',NULL

UNION ALL ----------------------------------------

SELECT 'GroupA3','GroupB3' UNION ALL --no groups in the cyclic have double parents

SELECT 'GroupB3','GroupC3' UNION ALL

SELECT 'GroupC3','GroupA3' UNION ALL

-- SELECT 'GroupA3','Company3' UNION ALL

SELECT 'Company3',NULL

UNION ALL ----------------------------------------

SELECT 'GroupB4','GroupC4' --demo an "orphan"

--=======================================================================================

-- The following code makes a Hierarchy "sister" table with strings that are used

-- to traverse various hierarchies.

--=======================================================================================

--===== Create and seed the "Hierarchy" table on the fly

SELECT Child,

Parent,

Level = 0, --Top Level

HierarchyString = CAST(' '+CAST(Child AS CHAR(10))+' ' AS VARCHAR(8000))

INTO #Hierarchy

FROM #yourtable

WHERE Parent IS NULL

--===== Declare a local variable to keep track of the current level

DECLARE @Level INT

SET @Level = 0

--===== Create the hierarchy in the HierarchyString

WHILE @@ROWCOUNT > 0

BEGIN

SET @Level = @Level + 1

INSERT INTO #Hierarchy

(Child, Parent, Level, HierarchyString)

SELECT y.Child,y.Parent, @Level, h.HierarchyString + CAST(y.Child AS CHAR(10))+' '

FROM #yourtable y

INNER JOIN #Hierarchy h

ON y.Parent = h.Child --Looks for parents only

AND h.Level = @Level - 1 --Looks for parents only

WHERE NOT EXISTS (SELECT 1 FROM #Hierarchy h1 WHERE h1.Child = y.Child AND h1.Parent = y.Parent)

--WHERE clause above keeps runaway cyclic groups from occuring

END

--=======================================================================================

-- Now, demo the use of the sister table

--=======================================================================================

--===== Display the entire tree with indented descriptions according to the Level

SELECT Child,

Parent,

Level,

HierarchyString

FROM #Hierarchy

ORDER BY HierarchyString

--===== Display all the orphans

SELECT y.Child,y.Parent

FROM #yourtable y

WHERE NOT EXISTS (SELECT 1

FROM #Hierarchy h1

WHERE h1.Child = y.Child

AND h1.Parent = y.Parent)

AND y.Parent > '' --A bit faster than IS NOT NULL

drop table #Hierarchy

drop table #yourtable

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

majorbloodnock SSCrazy Eights Points: 9389 More actions · Answer 2

Hi, Jeff

That's quite a bit for me to read through and get my head round, so I probably won't post an update for a little while. I did want to post a "thank you" quickly, though; much appreciated.

Semper in excretia, suus solum profundum variat

Jeff Moden SSC Guru Points: 1003863 More actions · Answer 3

You bet... easiest thing to see what I'm talking about is to simply run the code and compare to what's in the #yourtable to the results...

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

majorbloodnock SSCrazy Eights Points: 9389 More actions · Answer 4

OK, I think I understand it now. In your While loop, you're basically wandering up the hierarchy, writing each parent/child combination to the Hierarchy table, checking first to see if you've visited that parent/child combination before. It's not trying to determine where in the chain the duplication has occurred; it's just an "I'm getting a sense of deja vu" check.

You're probably right. As long as I keep track of that combination, I can always check against a historical "record" of what's already been processed, and escape the routine if I get a match.

I'll have a tinker. Thanks a lot for your help.

P.S. the code worked fine first time.

Semper in excretia, suus solum profundum variat

Jeff Moden SSC Guru Points: 1003863 More actions · Answer 5

Correct... and thanks for the feedback!

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

majorbloodnock SSCrazy Eights Points: 9389 More actions · Answer 6

Just an update.

Unfortunately, the logic for spotting a group membership loop has a minor flaw. What I've found in practice is that there are a couple of instances in our group structure where someone can inherit membership from one group via two or more different routes, and that introduces an interesting problem.

Let me explain. Let's say top level group A contains two members; B and C. C is also a member of B, and a user is a member of group C. That means user inherits group A membership via A > B > C and A > C, so meaning that the where clause in the inner join sees two entries with the same child/parent string, so fails to include one of them.

I'm working on an answer, and I think the key is still the recurrence of a child/parent pattern - just within a single hierarchy string. If I get any inspiration, I'll provide an update.

Thanks for your help

Semper in excretia, suus solum profundum variat

alen teplitsky SSC-Dedicated Points: 30014 More actions · Answer 7

why not a multi-step approach

grab the data out of AD and display the first level of group membership. then run several queries to display the second and third levels and so on. you might need to add extra columns for this.

Jeff Moden SSC Guru Points: 1003863 More actions · Answer 8

Good idea... in fact, that's exactly what my code does... but there's nothing in the data to determine what level a node is at... just the parent ID, etc... and that is the cause of "hierarchical loops". I've avoided some of them in the code but it's at the expense of being able to expand multi-parent groups unless everyone in the group has a row for each group they belong to... that would actually be the best way to resolve it because then it almost becomes the "Nirvana" of a true positional hierarchy.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

majorbloodnock SSCrazy Eights Points: 9389 More actions · Answer 9

SQL Noob (1/9/2008)
why not a multi-step approach
grab the data out of AD and display the first level of group membership. then run several queries to display the second and third levels and so on. you might need to add extra columns for this.

Agreed. That's actually exactly what my real process is doing. And you're absolutely right that it's just fine tuning; it's just that recognising a loop is more difficult than it seems when you've got membership chains that are legitimately very similar but for a minor difference here and there, typically somewhere in the middle of the chain. And, although I don't have any at the moment, I'm not sure how I'd identify a loop that takes perhaps 5 or 6 group to group memberships to come full circle.

I'll get there, though.

Semper in excretia, suus solum profundum variat