Hi guys,I need to implement a multi-parented tree (or digraph) onto SQL Server 2005.I've read several articles, but most of them uses single-parented trees with a unique root like the following one.-My PC -Drive C -Documents and Settings -Program Files -Adobe -Microsoft -Folder X -Drive D -Folder Y -Folder Z
In this one, everything derives from a root element (My PC). In my case, a child could have more than 1 parent, like the following:G A \ / B / X C / \ D E \ / F
So I have the following code:create table #ObjectRelations( Id varchar(20), NextId varchar(20))insert into #ObjectRelations values ('G', 'B')insert into #ObjectRelations values ('A', 'B') insert into #ObjectRelations values ('B', 'C')insert into #ObjectRelations values ('B', 'X')insert into #ObjectRelations values ('C', 'E') insert into #ObjectRelations values ('C', 'D') insert into #ObjectRelations values ('E', 'F') insert into #ObjectRelations values ('D', 'F') declare @id varchar(20)set @id = 'A';WITH Objects (Id, NextId) AS( -- This is the 'Anchor' or starting point of the recursive query SELECT rel.Id, rel.NextId FROM #ObjectRelations rel WHERE rel.Id = @id UNION ALL -- This is the recursive portion of the query SELECT rel.Id, rel.NextId FROM #ObjectRelations rel INNER JOIN Objects -- Note the reference to CTE table name (Recursive Join) ON rel.Id = Objects.NextId)SELECT o.*FROM Objects odrop table #ObjectRelations----------------------------------------Which returns the following SET:Id NextId-------------------- --------------------A BB CB XC EC DD FE F
Expected result SET:Id NextId-------------------- --------------------G BA BB CB XC EC DD FE F
Note that the relation G->B is missing, because it asks for an starting object (which doesn't work for me also, because I don't know the root object from the start) and using A as the start point will ignore the G->B relationship.So, this code doesn't work in my case because it asks for a starting object, which is obvious in a SINGLE-parent tree (will always be the root object). But in multi-parent tree, you could have more than 1 "root" object (like in the example, G and A are the "root" objects, where root is an object which doesn't have a parent (ancestor)).So I'm kind of stucked in here... I need to modify the query to NOT ask for a starting object and recursively traverse the entire tree.I don't know if that's possible with the (Id, NextId) implementation... may be I need to store it like a graph using some kind of Incidence matrix, adjacency matrix or whatever (see http://willets.org/sqlgraphs.html).Any help? What do you think guys?Thank you very much for your time =)Cheers!Sources: http://www.sqlservercentral.com/articles/SQL+Server+2005+-+TSQL/recursivequeriesinsql1999andsqlserver2005/1846/http://www.rcs-solutions.com/blog/2008/09/27/RecursiveQueriesInSQLServer2005.aspxhttp://www.experts-exchange.com/Database/Miscellaneous/Q_23102605.html
Multiple parents tree (or digraph) implementation
Posted - 2009-05-12 : 22:51:45
