TSQL CTE and a Graph of Sorts

Question

With a table of the following structure and sample data:

TableActivity
-------------
Type                VARCHAR(8)
Activity            VARCHAR(8)
RelatedActivity     VARCHAR(8)

Type        Activity       RelatedActivity
------------------------------------------
Start       a              -
Transfer    a              b
Start       b              -
Transfer    b              c
Start       c              -
Stop        c              -
Transfer    c              b
Stop        b              -
Transfer    b              a
Stop        a              -

Would it be possible to write a CTE query to accomplish the following:

GetActivities('a')

Order    Activities
-------------------
0        a
1        b
2        c

I'm having a tough time writing one that stops returning rows in the recursive statement.

Any ideas?

Edit

To clarify GetActivities('a'). This function should find the 'Start' activity of 'a' and proceed to find any 'Transfer' activities on 'a'. At that the point the function can then recurse with 'b' and consequently 'c' with the sample data. The query should return all activities related to 'a' via 'Transfers'. This nesting of activities can go as deep as need be and is unknown (so no unions). The difficulty I'm having is that there is another 'Transfer' back down e.g. 'b' -> 'a'. You can see how this would create a loop in the recursive query.

One more clarification: the transfers in the activity table behave as a stack. Here is how the data is populated in the table (in C#):

 using (Activity.Start("a"))
 {
   // transfer to 'b' under covers
   using (Activity.Start("b"))
   {
     // transfer to 'c' under covers
     using (Activity.Start("c"))
     {
     }
     // transfer to 'b' under covers
   }
   // transfer to 'a' under covers
 }

Answer 1

I've given it a try, but can't tell you whether it will be any good. Just ignore if it isn't.

WITH TMP AS (
SELECT activity, relatedactivity
FROM tableactivity root
WHERE root.activity = 'a' and root.type='transfer'
UNION ALL
SELECT next.activity, next.relatedactivity
FROM tableactivity next, TMP prior
WHERE prior.relatedactivity = next.activity and next.type='transfer'
  AND not exists (SELECT * FROM TMP ttmp
                   WHERE ttmp.activity = next.relatedactivity
                     AND ttmp.relatedactivity = next.activity)
                 )
)
SELECT relatedactivity FROM TMP
UNION (ALL ???)
SELECT 'a' from <nonemptytable>

PS

as for your orderingnumber, that is a concept that doesn't fit very well with graphs and their closures. What do you want your number to be if there are multiple distinct paths of differing lengths from a to c ?

Answer 2

Based on Erwins input:

 declare @TableActivity table
 ([Type]              VARCHAR(8)
 ,Activity            VARCHAR(8)
 ,RelatedActivity     VARCHAR(8)
 )

 insert @TableActivity
       select 'Start','a','-'
 union select 'Transfer','a','b'
 union select 'Start','b','-'
 union select 'Transfer','b','c'
 union select 'Start','c','-'
 union select 'Transfer','c','d'
 union select 'Transfer','c','e'
 union select 'Start','d','-'
 union select 'Stop','d','-'
 union select 'Start','e','-'
 union select 'Stop','e','-'
 union select 'Transfer','d','c'
 union select 'Transfer','e','c'
 union select 'Stop','c','-'
 union select 'Transfer','c','b'
 union select 'Stop','b','-'
 union select 'Transfer','b','a'
 union select 'Stop','a','-'
 union select 'Start','1','-'
 union select 'Transfer','1','2'
 union select 'Start','2','-'
 union select 'Transfer','2','3'
 union select 'Start','3','-'
 union select 'Transfer','3','4'
 union select 'Start','4','-'
 union select 'Stop','4','-'
 union select 'Transfer','4','3'
 union select 'Stop','3','-'
 union select 'Transfer','3','2'
 union select 'Stop','2','-'
 union select 'Transfer','2','1'
 union select 'Stop','1','-'

 declare @activity varchar(8)
 set @activity = 'a' 

 ;WITH ActivitiesGraph(activity, relatedactivity) AS
 (
      SELECT activity,
             relatedactivity
      FROM   @TableActivity root
      WHERE  root.activity = @activity
      AND    root.type     = 'Transfer'

      UNION ALL

      SELECT next.activity,
             next.relatedactivity
      FROM   @TableActivity next
             INNER JOIN ActivitiesGraph prior
             ON     next.activity = prior.relatedactivity
      WHERE  next.type            = 'Transfer'
      AND    prior.activity != next.relatedactivity
      AND    prior.activity != next.activity
      )
 SELECT activity
 FROM   @TableActivity
 WHERE  activity = @activity

 UNION

 SELECT relatedactivity
 FROM   ActivitiesGraph

Answer 3

You failed to give any details about the intended semantics of your 'getactivities()' thing.

That makes the question hard to answer.

But anyway, since you mentioned 'recursion', I'll assume that you want the result set to include any activity that is at any level of indirection related to the given activity.

You cannot avoid recursion because of the 'at any level of indirection' part. It should roughly operate as follows :

Start with the given set of activities ('a') to find related activities ('b'). From the new activities found, remove the ones that you had found already (none). Add the remaining ones to the result set and repeat with this set : With the given set of activities ('b'), find related activities ('a' 'c'). From the new activities found, remove the ones that you had found already ('a'). Add the remaining ones ('c') to the result set and repeat with this set : With the given set of activities ('c'), find related activities ('b'). From the new activities found, remove the ones that you had found already ('b'). Add the remaining ones (none) to the result set and since there were none, you're done.

Sorry I can't turn this into SQL for you off the top of my hat.

Answer 4

Is a recursive query really required? Based on the sample data you have provided, all that is needed is to report the order that the Activities stop, in reverse:

declare @TableActivity table
([Type]              VARCHAR(8)
,Activity            VARCHAR(8)
,RelatedActivity     VARCHAR(8)
)


insert @TableActivity
      select 'Start','a','-'
union select 'Transfer','a','b'
union select 'Start','b','-'
union select 'Transfer','b','c'
union select 'Start','c','-'
union select 'Stop','c','-'
union select 'Transfer','c','b'
union select 'Stop','b','-'
union select 'Transfer','b','a'
union select 'Stop','a','-'


select activity
       ,ROW_NUMBER() OVER (ORDER BY activity) - 1 AS rn
from  @TableActivity
where [Type] = 'Stop'
order by 2