title: Multiple parents tree (or digraph) implementation sql server 2005
body: <p>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.</p>
  
  <pre><code>-My PC
     -Drive C
        -Documents and Settings
        -Program Files
           -Adobe
           -Microsoft
        -Folder X
     -Drive D
        -Folder Y
        -Folder Z
  </code></pre>
  
  <p>In this one, everything derives from a root element (My PC). </p>
  
  <p>In my case, a child could have more than 1 parent, like the following:</p>
  
  <pre><code>G  A
   \ /
    B
   / \ 
  X   C
    /  \
    D   E
    \ /
     F
  </code></pre>
  
  <p>So I have the following code:</p>
  
  <pre><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 o
  
  drop table #ObjectRelations
  </code></pre>
  
  <hr>
  
  <p>Which returns the following SET:</p>
  
  <pre><code>Id                   NextId
  -------------------- --------------------
  A                    B
  B                    C
  B                    X
  C                    E
  C                    D
  D                    F
  E                    F
  </code></pre>
  
  <p>Expected result SET:</p>
  
  <pre><code>Id                   NextId
  -------------------- --------------------
  G                    B
  A                    B
  B                    C
  B                    X
  C                    E
  C                    D
  D                    F
  E                    F
  </code></pre>
  
  <p>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.</p>
  
  <p>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)).</p>
  
  <p>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 <a href="http://willets.org/sqlgraphs.html" rel="nofollow noreferrer">http://willets.org/sqlgraphs.html</a>).</p>
  
  <p>Any help? What do you think guys?
  Thank you very much for your time =)</p>
  
  <p>Cheers!</p>
  
  <p>Sources: 
  <a href="http://www.sqlservercentral.com/articles/SQL+Server+2005+-+TSQL/recursivequeriesinsql1999andsqlserver2005/1846/" rel="nofollow noreferrer">Source 1</a>
  <a href="http://www.rcs-solutions.com/blog/2008/09/27/RecursiveQueriesInSQLServer2005.aspx" rel="nofollow noreferrer">Source 2</a>
  <a href="http://www.experts-exchange.com/Database/Miscellaneous/Q_23102605.html" rel="nofollow noreferrer">Source 3</a></p>