The following code extract is fully described as well has how recursion works in my blog article: http://sqlblogcasts.com/blogs/tonyrogerson/archive/2008/05/11/common-table-expressions-cte-s-how-it-works-how-recursion-works-using-with-adjacency-list.aspx

create table adjacency_list (
      parent_extractedword_id int   not null,
      child_extractedword_id  int not null,
            constraint pk_adjacency_list primary key clustered( parent_extractedword_id, child_extractedword_id )
      )
create table extractedword (
      id    int not null constraint pk_extractedword primary key clustered,
      word varchar(50) not null
      )
insert extractedword( id, word ) values( 11, 'demo' )
insert extractedword( id, word ) values( 12, 'on' )
insert extractedword( id, word ) values( 13, 'cte' )
insert extractedword( id, word ) values( 14, 'recursion' )
      
insert extractedword( id, word ) values( 21, 'does' )
insert extractedword( id, word ) values( 22, 'this' )
insert extractedword( id, word ) values( 23, 'rock' )
insert extractedword( id, word ) values( 24, 'ya' )
insert extractedword( id, word ) values( 25, 'boat?' )
insert adjacency_list ( parent_extractedword_id, child_extractedword_id ) values( 11, 12 )
insert adjacency_list ( parent_extractedword_id, child_extractedword_id ) values( 12, 13 )
insert adjacency_list ( parent_extractedword_id, child_extractedword_id ) values( 13, 14 )
insert adjacency_list ( parent_extractedword_id, child_extractedword_id ) values( 21, 22 )
insert adjacency_list ( parent_extractedword_id, child_extractedword_id ) values( 22, 23 )
insert adjacency_list ( parent_extractedword_id, child_extractedword_id ) values( 23, 24 )
insert adjacency_list ( parent_extractedword_id, child_extractedword_id ) values( 24, 25 )
; WITH WordStruct( org_parent_id, child_id, recurse_depth )
AS (
      --    The anchor is the starting point for possible recursion
      SELECT org_parent_id = parent_extractedword_id, 
             child_id      = child_extractedword_id,
             recurse_depth = CAST( 0 as tinyint )
      FROM adjacency_list l1
      WHERE NOT EXISTS ( SELECT *         --    The Anchor should only contain root PARENT's
                         FROM adjacency_list l2
                         WHERE l2.child_extractedword_id = l1.parent_extractedword_id )
      --    Recursive Member
      UNION ALL
      SELECT org_parent_id = l1.child_id, 
             child_id      = l2.child_extractedword_id,
             recurse_depth = recurse_depth + cast( 1 as tinyint )
      FROM WordStruct l1
            INNER JOIN adjacency_list l2 on l2.parent_extractedword_id = l1.child_id 
)
select e.id, e.word, ws.*, 
       case when org_parent_id=e.id then 'ROOT' else 'CHILD.DEPTH=' + CAST( recurse_depth + 1 as varchar(5) ) end
from WordStruct ws
      INNER JOIN extractedword e on e.id = ws.child_id
                                 or ( ws.recurse_depth = 0                 --      Do this to get the desc for the root parent
                                  and e.id = ws.org_parent_id )
order by ws.org_parent_id, ws.child_id 

Also note that more than one CTE can be used. They can be separated by commas.

Example:

with A (col1, col2)

as

(

select col1, col2 from table A

),

B (col3, col5)

as

(

select col3, col5 from table B

),

...

Select a.col1, a.col2, b.col3, b.col5

from A inner join B on

A.col1 = B.col5

I have found this to be extremely useful when converting for example an Access macros with several query steps into a stored procedure.

Cheers,

Mark

http://en.wikipedia.org/wiki/Trie

Try this.

Create Table Trie (
 ID int primary key,
 ParentID int,
 Data char(1),
 IsWord bit
)

Insert Trie Select 1, null, 't', 0
Insert Trie Select 2, null, 'i', 1
Insert Trie Select 3, 1, 'o', 1
Insert Trie Select 4, 1, 'e', 0
Insert Trie Select 5, 2, 'n', 1
Insert Trie Select 6, 4, 'a', 1
Insert Trie Select 7, 4, 'n', 1
Insert Trie Select 8, 5, 'n', 1
;

  
with dictionary(ID, ParentID,  Word, IsWord)  as
(
 Select ID, ParentID,  Cast(Data as varchar(256)), IsWord 
 From Trie Where ParentID is null
 Union ALL
 Select t.ID, t.ParentID, Cast(Word+t.Data as varchar(256)), t.IsWord
 From Trie t Join Dictionary d on d.ID = t.ParentID
 
)

select * from dictionary
where isWord = 1

Question:
Does anyone know if it is possible to use CTE to recursively return the set of record(s) NOT in the recursive CTE?

Background:
The versioning strategy is to have an initial set of records represent version #1. When a change is made to any of the records in version #1, a new version will be created by querying ONLY the modified records from version #1 and re-inserting them as version #2, thereby making this new version related to the old.

Criteria:
* there can be multilpe versions
* a version can "inherit" records from other versions

Heres a sample concept:
DECLARE @newVersionNumber DECIMAL(2,1)
DECLARE @baseVersionID INT
DECLARE @newVersionID INT

DECLARE @table TABLE (
TableID INT IDENTITY(1,1)
,[Name] VARCHAR(10)
,[Value] DECIMAL(18,2)
,VersionID INT)
DECLARE @version TABLE (
VersionID INT IDENTITY(1,1)
,VersionNumber DECIMAL(2, 1)
,ParentVersionID INT)

-- VERSION # 1: Initial state of the data with default version
SET @baseVersionID = 1
INSERT @version VALUES (1.0, Null)
INSERT @table ([Name], [Value], VersionID) VALUES ('A', 100, @baseVersionID) -- never change in all version
INSERT @table ([Name], [Value], VersionID) VALUES ('B', 200, @baseVersionID) -- changed in every version
INSERT @table ([Name], [Value], VersionID) VALUES ('C', 300, @baseVersionID); -- changed in every other version


-- VERSION # 2: Simulate a versioning of the data based on default version
SET @baseVersionID = 1
SELECT @newVersionNumber = IsNull(VersionNumber, 0) + 1 FROM @version WHERE VersionID = @baseVersionID
INSERT @version VALUES (@newVersionNumber, @baseVersionID)
SET @newVersionID = SCOPE_IDENTITY()
INSERT @table([Name], [Value], VersionID)
(
SELECT DISTINCT [Name], 400, @newVersionID FROM @table WHERE [Name] = 'B'
);

-- VERSION # 3: Simulate a versioning of the data
SET @baseVersionID = 2
SELECT @newVersionNumber = IsNull(VersionNumber, 0) + 1 FROM @version WHERE VersionID = @baseVersionID
INSERT @version VALUES (@newVersionNumber, @baseVersionID)
SET @newVersionID = SCOPE_IDENTITY()
INSERT @table([Name], [Value], VersionID)
(
SELECT DISTINCT [Name], 800, @newVersionID FROM @table WHERE [Name] = 'B'
UNION
SELECT DISTINCT [Name], 900, @newVersionID FROM @table WHERE [Name] = 'C'
);

-- VERSION # 4: Simulate a versioning of the data
SET @baseVersionID = 2
SELECT @newVersionNumber = IsNull(VersionNumber, 0) + 1 FROM @version WHERE VersionID = @baseVersionID
INSERT @version VALUES (@newVersionNumber, @baseVersionID)
SET @newVersionID = SCOPE_IDENTITY()
INSERT @table([Name], [Value], VersionID)
(
SELECT DISTINCT [Name], 200, @newVersionID FROM @table WHERE [Name] = 'A'
UNION
SELECT DISTINCT [Name], 1600, @newVersionID FROM @table WHERE [Name] = 'B'
UNION
SELECT DISTINCT [Name], 1800, @newVersionID FROM @table WHERE [Name] = 'C'
);

-- VERSION # 5: Simulate a versioning of the data
SET @baseVersionID = 2
SELECT @newVersionNumber = IsNull(VersionNumber, 0) + 1 FROM @version WHERE VersionID = @baseVersionID
INSERT @version VALUES (@newVersionNumber, @baseVersionID)
SET @newVersionID = SCOPE_IDENTITY()
INSERT @table([Name], [Value], VersionID)
(
SELECT DISTINCT [Name], 3600, @newVersionID FROM @table WHERE [Name] = 'C'
);

Refer to my blog for Recursive CTE help/tips.

Jeff Fischer