title: Prevent recursive CTE visiting nodes multiple times
body: <p>Consider the following simple DAG:</p>
  
  <pre><code>  1-&gt;2-&gt;3-&gt;4
  </code></pre>
  
  <p>And a table, #bar, describing this (I'm using SQL Server 2005):</p>
  
  <pre><code>parent_id   child_id
  1           2
  2           3
  3           4
  //... other edges, not connected to the subgraph above
  </code></pre>
  
  <p>Now imagine that I have some other arbitrary criteria that select the first and last edges, i.e. 1->2 and 3->4. I want to use these to find the rest of my graph.</p>
  
  <p>I can write a recursive CTE as follows (I'm using terminology from <a href="http://msdn.microsoft.com/en-us/library/ms186243.aspx" rel="noreferrer">MSDN</a>):</p>
  
  <pre><code>with foo(parent_id,child_id) as (
  // anchor member that happens to select first and last edges:
  select parent_id,child_id from #bar where parent_id in (1,3)
  union all
  // recursive member:
  select #bar.* from #bar
  join foo on #bar.parent_id = foo.child_id
  )
  select parent_id,child_id from foo
  </code></pre>
  
  <p>However, this results in edge 3->4 being selected twice:</p>
  
  <pre><code>parent_id  child_id
  1          2
  3          4
  2          3
  3          4    // 2nd appearance!
  </code></pre>
  
  <p>How can I prevent the query from recursing into subgraphs that have already been described? I could achieve this if, in my "recursive member" part of the query, I could reference <em>all data that has been retrieved by the recursive CTE so far</em> (and supply a predicate indicating in the recursive member excluding nodes already visited). However, I think I can access data that was returned by <em>the last iteration</em> of the recursive member only.</p>
  
  <p>This will not scale well when there is a lot of such repetition. Is there a way of preventing this unnecessary additional recursion?</p>
  
  <p>Note that I could use "select distinct" in the last line of my statement to achieve the desired results, but this seems to be applied <em>after</em> all the (repeated) recursion is done, so I don't think this is an ideal solution.</p>
  
  <p><em>Edit</em> - hainstech suggests stopping recursion by adding a predicate to exclude recursing down paths that were explicitly in the starting set, i.e. recurse only <code>where foo.child_id not in (1,3)</code>. That works for the case above only because it simple - all the repeated sections begin within the anchor set of nodes. It doesn't solve the general case where they may not be. e.g., consider adding edges 1->4 and 4->5 to the above set. Edge 4->5 will be captured twice, even with the suggested predicate. :(</p>