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.

• Adam Pierce: 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!
• J. Polfer: This is heirarchical data. I've found Anthony Mollinaro's discussions on heirarchical data in SQL Cookbook (O'Reilly) to be really handy; he covers virtually all popular DBMSs, including PostrgreSQL.
• regilero: If you come here from google check @Chris KL response, since PostgreSQl 8.4 recursive queries are available on postgreSQL.

Answer 1

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.

• lucidbrot: If I understand your code correctly, it takes some (id, value) tuples matching on selectedid. Then joins those with a new instance of sumthis, which again contains those same tuples. So why would this query ever terminate? My understanding failure lies probably at how :selectedid is set. Or maybe where the values for the child sumthis tables come from

Answer 2

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

Answer 3

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.

• Kibbee: @Portman I've looked at nested sets. Seems like a good idea, but it seems like the insert/delete cost is terribly high.
• Portman: Yes, seems. But trust me - once you write the CRUD procedures, it performs very well.
• Sarah G: Every update in the nested-sets model requires you to update > 50% of the rows in the table. It's a clever mechanism, but it's totally contraindicated in any real-world situation. I'm generally a fan of Celko, but he's wrong on this point.
• bf2020: Intelligententerprise Link is dead now

Answer 4

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 5

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

• user330315: +1 for recursive CTE which is supported by all major DBMS nowadays - except for MySQL and SQLite
• poshest: Maybe I'm doing it wrong, but if I have any more than one field specified in the first SELECT clause, eg SELECT id, name, I get an each UNION query must have the same number of columns error at the SELECT fn_hierarchy line. I guess in the final SELECT I can re-join onto the example table to get the rest of the fields, but it's not so elegant any more.

Answer 6

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.

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

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 9

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;

Answer 10

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 11

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.