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!

Solution 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.

Solution 2

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

Solution 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.

Solution 4

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

Solution 5

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.

View more solutions

Comments

[Dale Ragan]

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

[Darren Kopp]

agreed. database bound menus are going to be soooo much nicer.

[Abhishek]

Don't feel like looking it up now, but I know oracle 10g has With clauses, I wonder if this is possible there too.

[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.

[Jeffrey Kemp]

Oracle 11gR2 introduced support for recursive WITH clauses; prior to that a WITH clause could not refer to itself. For prior versions, Oracle has had its own hierarchical query syntax (START WITH+CONNECT BY) since at least version 7 or 8, probably earlier.

[a_horse_with_no_name]

+1 for recursive CTE which is supported by all major DBMS nowadays - except for MySQL and SQLite

[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

[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.

[dat]

Curious why the downvote -- an issue specific to AllegroGraph? a concern regarding graph databases in general? not explicitly touching on how to execute a recursive query?

[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