Is it possible to make a recursive SQL query ?

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

You could maybe use a subselect to do this:

Use SQL subselects to consolidate queries

Answer 4

I think it is easier in SQL 2008 with HierarchyID

Answer 5

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

Answer 6

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!

Answer 7

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

Answer 8

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.

Answer 9

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.

Answer 10

@Portman

I've looked at nested sets. Seems like a good idea, but it seems like the insert/delete cost is terribly high.

Answer 11

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);

Answer 12

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 :)

Answer 13

I will point out that PostgreSQL 8.4, when it's released, has recursive query support now:

http://developer.postgresql.org/pgdocs/postgres/queries-with.html

It uses the SQL standard WITH syntax.

Answer 14

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.

Answer 15

Jacob Rigby: If you really needed a directed graph so bad, PgSQL does support the SQL XML/XPath extensions. Though, didn't Ted Codd win this debate in 1974?

Answer 16

Is it possible to just use SQL to do recursive query?