Friday, November 09, 2007

T-SQL Fibonacci and the power of 'With'

It's amazing how things can pass you by. I only found out about the recursive power of the T-SQL 'with' statement today. With it you can easily write a Fibonacci sequence generator:

with fib(a, b) as
(
 select 0, 1
 union all
 select b, a+b from fib where b < 100
)
select a from fib

Here's the output:

a
-----------
0
1
1
2
3
5
8
13
21
34
55
89

It really comes into its own when you've recursive structures such as a tree in your schema. Take this extremely typical example: a hierarchy of locations. Each record has a primary key 'id' and a foreign key 'parentId' that references another record in the same table.

locationTable

Here are some records:

locationRecords

Say I wanted to output all the locations with their level in the hierarchy. Easy:

with locationLevel(id, [name], [level]) as
(
 select id, [name], 0 from location where parentId is null
 union all
 select location.id, location.[name], locationLevel.[level]+1
 from location
 join locationLevel on location.parentId = locationLevel.id
)
select * from locationLevel

id          name                 level
----------- -------------------- -----------
0           World                0
1           UK                   1
2           France               1
5           Paris                2
6           Rouen                2
3           London               2
4           Brighton             2

Or when I search for a particular location, I want to find all its ancestors:

with locations(id, parentId, [name], targetName) as
(
 select id, parentId, [name], [name] from location
 union all
 select location.id, location.parentId, location.[name], locations.[targetName]
 from location
 join locations on location.id = locations.parentId
)
select id, [name] from locations where targetName = 'Rouen'

id          name
----------- --------------------
6           Rouen
2           France
0           World

1 comment:

Anonymous said...

Just lovely :) Thanks. I've been trying to get the WITH statement to accept UPDATE statements, seems that it doesn't like it:D

Cheers,
D
http://www.realityinfo.org