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 Saturday, January 29, 2011 12:41 PM


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
Comments posted to this topic are about the item Common table expressions and circular references

Semper in excretia, sumus solum profundum variat
Post #1055802
Posted Monday, January 31, 2011 1:24 AM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Tuesday, November 18, 2014 12:29 PM
Points: 1,945, Visits: 3,121
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.


Books in Celko Series for Morgan-Kaufmann Publishing
Analytics and OLAP in SQL
Data and Databases: Concepts in Practice
Data, Measurements and Standards in SQL
SQL for Smarties
SQL Programming Style
SQL Puzzles and Answers
Thinking in Sets
Trees and Hierarchies in SQL
Post #1056019
Posted Monday, January 31, 2011 2:34 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: 2 days ago @ 5:57 AM
Points: 1,095, Visits: 244
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!
Post #1056034
Posted Monday, January 31, 2011 2:41 AM
SSC Veteran

SSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC Veteran

Group: General Forum Members
Last Login: Today @ 2:07 AM
Points: 246, Visits: 524
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
where hierarchypath not like '%'+g.child +'->' + g.parent + '%'
)

select bottom, parentgroup, level, hierarchypath
from groupmembers
where hierarchypath like '%'+parentgroup + '->' + '%'
order by level desc
option(maxrecursion 100);

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

Post #1056038
Posted Monday, January 31, 2011 3:57 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
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.

Now, there's a question. The short answer is that I haven't. I know I've just written a technical article about CTEs, but I'm by no means an expert yet.

In fact, one of the biggest issues I have with hierarchal data is that most of the parent/child querying we do in my company is on data outside the control of the DBAs - most frequently group memberships in Active Directory. Indeed, in one or two cases, such a cyclic relationship has actually been valid. To my mind, no matter how difficult it may be to identify circular references in SQL, it pales into insignificance with the problem of "deciding" whether a particular instance should or should not be allowed.

I know it's a bit of a side-step answer, but I'd be tempted to throw this decision back towards the application. If it really had to be done at database level, I haven't yet come up with a better solution than what you've outlined.


Semper in excretia, sumus solum profundum variat
Post #1056060
Posted Monday, January 31, 2011 4:10 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
Peter.Frissen (1/31/2011)
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!

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


Semper in excretia, sumus solum profundum variat
Post #1056066
Posted Monday, January 31, 2011 4:13 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
gerg-520419 (1/31/2011)
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
where hierarchypath not like '%'+g.child +'->' + g.parent + '%'
)

select bottom, parentgroup, level, hierarchypath
from groupmembers
where hierarchypath like '%'+parentgroup + '->' + '%'
order by level desc
option(maxrecursion 100);

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


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


Semper in excretia, sumus solum profundum variat
Post #1056068
Posted Monday, January 31, 2011 7:18 AM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Friday, October 10, 2014 3:19 PM
Points: 28, Visits: 185
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
Post #1056180
Posted Monday, January 31, 2011 7:46 AM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: Administrators
Last Login: Yesterday @ 7:12 AM
Points: 31,284, Visits: 15,746
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.






Follow me on Twitter: @way0utwest

Forum Etiquette: How to post data/code on a forum to get the best help
Post #1056199
Posted Monday, January 31, 2011 7:56 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
Perhaps more pertinent in criticising AD is its accessibility. ADSI and LDAP are technically effective, but hardly user-friendly.

Semper in excretia, sumus solum profundum variat
Post #1056210
« Prev Topic | Next Topic »

Add to briefcase 123»»»

Permissions Expand / Collapse