Is it possible to make a recursive SQL query?

I have a table similar to this:

CREATE TABLE example (
  id integer primary key,
  name char(200),
  parentid integer,
  value integer);

I can use the parentid field to arrange data into a tree structure.

Now here's the bit I can't work out. Given a parentid, is it possible to write an SQL statement to add up all the value fields under that parentid and recurse down the branch of the tree ?

UPDATE: I'm using posgreSQL so the fancy MS-SQL features are not available to me. In any case, I'd like this to be treated as a generic SQL question.

BTW, I'm very impressed to have 6 answers within 15 minutes of asking the question! Go stack overflow!

Here is an example script using common table expression:

with recursive sumthis(id, val) as (
    select id, value
    from example
    where id = :selectedid
    union all
    select C.id, C.value
    from sumthis P
    inner join example C on P.id = C.parentid
)
select sum(val) from sumthis

The script above creates a 'virtual' table called sumthis that has columns id and val. It is defined as the result of two selects merged with union all.

First select gets the root (where id = :selectedid).

Second select follows the children of the previous results iteratively until there is nothing to return.

The end result can then be processed like a normal table. In this case the val column is summed.

Since version 8.4, PostgreSQL has recursive query support for common table expressions using the SQL standard WITH syntax.

If you want a portable solution that will work on any ANSI SQL-92 RDBMS, you will need to add a new column to your table.

Joe Celko is the original author of the Nested Sets approach to storing hierarchies in SQL. You can Google "nested sets" hierarchy to understand more about the background.

Or you can just rename parentid to leftid and add a rightid.

Here is my attempt to summarize Nested Sets, which will fall woefully short because I'm no Joe Celko: SQL is a set-based language, and the adjacency model (storing parent ID) is NOT a set-based representation of a hierarchy. Therefore there is no pure set-based method to query an adjacency schema.

However, most of the major platforms have introduced extensions in recent years to deal with this precise problem. So if someone replies with a Postgres-specific solution, use that by all means.

There are a few ways to do what you need in PostgreSQL.

• If you can install modules, look at the tablefunc contrib. It has a connectby() function that handles traversing trees. <http://www.postgresql.org/docs/8.3/interactive/tablefunc.html>

• Also check out the ltree contrib, which you could adapt your table to use: <http://www.postgresql.org/docs/8.3/interactive/ltree.html>

• Or you can traverse the tree yourself with a PL/PGSQL function.

Something like this:

create or replace function example_subtree (integer)
returns setof example as
'declare results record;
         child record;
 begin
  select into results * from example where parent_id = $1;
  if found then
    return next results;
    for child in select id from example
                  where parent_id = $1
      loop
        for temp in select * from example_subtree(child.id)
        loop
          return next temp;
        end loop;
      end loop;
  end if;
  return null;
end;' language 'plpgsql';

select sum(value) as value_sum
  from example_subtree(1234);

A standard way to make a recursive query in SQL are recursive CTE. PostgreSQL supports them since 8.4.

In earlier versions, you can write a recursive set-returning function:

CREATE FUNCTION fn_hierarchy (parent INT)
RETURNS SETOF example
AS
$$
        SELECT  example
        FROM    example
        WHERE   id = $1
        UNION ALL
        SELECT  fn_hierarchy(id)
        FROM    example
        WHERE   parentid = $1
$$
LANGUAGE 'sql';

SELECT  *
FROM    fn_hierarchy(1)

See this article:

• Hierarchical queries in PostgreSQL

use a common table expression.

>May want to indicate this is SQL Server 2005 or above only. Dale Ragan

here's an article on recursion by SqlTeam without common table expressions.

If your using SQL Server 2005, there is a really cool way to do this using Common Table Expressions.

It takes all of the gruntwork out of creating a temporary table, and basicly allows you to do it all with just a WITH and a UNION.

Here is a good tutorial:

http://searchwindevelopment.techtarget.com/tip/0,289483,sid8_gci1278207,00.html

The following code compiles and it's tested OK.

create or replace function subtree (bigint)
returns setof example as $$
declare
results record;
entry   record;
recs    record;
begin
select into results * from example where parent = $1;
if found then
for entry in select child from example where parent = $1 and child <> parent loop
for recs in select * from subtree(entry.child) loop
return next recs;
end loop;
end loop;
end if;
return next results;
end;
$$ language 'plpgsql';

The condition "child <> parent" is needed in my case because nodes point to themselves.

Have fun :)

Oracle has "START WITH" and "CONNECT BY"

select 
    lpad(' ',2*(level-1)) || to_char(child) s

from 
    test_connect_by 

start with parent is null
connect by prior child = parent;

http://www.adp-gmbh.ch/ora/sql/connect_by.html

Just as a brief aside although the question has been answered very well, it should be noted that if we treat this as a:

> generic SQL question

then the SQL implementation is fairly straight-forward, as SQL'99 allows linear recursion in the specification (although I believe no RDBMSs implement the standard fully) through the WITH RECURSIVE statement. So from a theoretical perspective we can do this right now.

None of the examples worked OK for me so I've fixed it like this:

declare
results record;
entry   record;
recs    record;
begin
for results in select * from project where pid = $1 loop
return next results;
for recs in select * from project_subtree(results.id) loop
return next recs;
end loop;
end loop;
return;
end;

is this SQL Server? Couldn't you write a TSQL stored procedure that loops through and unions the results together?

I am also interested if there is a SQL-only way of doing this though. From the bits I remember from my geographic databases class, there should be.

I think it is easier in SQL 2008 with HierarchyID

If you need to store arbitrary graphs, not just hierarchies, you could push Postgres to the side and try a graph database such as AllegroGraph:

Everything in the graph database is stored as a triple (source node, edge, target node) and it gives you first class support for manipulating the graph structure and querying it using a SQL like language.

It doesn't integrate well with something like Hibernate or Django ORM but if you are serious about graph structures (not just hierarchies like the Nested Set model gives you) check it out.

I also believe Oracle has finally added a support for real Graphs in their latest products, but I'm amazed it's taken so long, lots of problems could benefit from this model.