Climbing a Parent/Child Database Relationship in Postgres

Question

We have the following example table (actually taken from another example here on stackoverflow...)

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

And given a specific child we want to get the top Parent.

I know of the tablefunc connectby function but that is for getting a parents children.

But, I'm interested in the other direction, given a child what is its top parent? What type of query would I try and use?

Any friendly advice is appreciated.

Answer 1

In my experience, SQL isn't very good at this kind of query (recursion). I would suggest creating an additional table with id and top parent id. As you add more children, you simply look up it's parent's top parent id and insert the appropriate row in the additional table.

You could also store the top parent id in your original table.

Answer 2

You could write a PL/PgSQL function to perform the recursion:

CREATE LANGUAGE plpgsql;
CREATE OR REPLACE FUNCTION get_top_parent(
        child integer
) RETURNS integer as $$
DECLARE
        parent integer;
        last_parent integer;
BEGIN
        last_parent := child;
        SELECT INTO parent parentid
        FROM example
        WHERE id = child;

        IF parent is NOT NULL THEN
                parent := get_top_parent(parent);
        ELSE
                parent := last_parent;
        END IF;
        RETURN parent;
END
$$ LANGUAGE plpgsql;

This function can definitely be optimized. It will likely be slow if depth is very high and the tables are large, so like Jegern mentioned it might be worth caching the hierarchy, possibly using triggers and such.

Answer 3

Look into Joe Celko's books, SQL for Smarties and his book on Trees and Hierarchies. He has a section or two in SQL for Smarties on trees and hierarchies, or if you want to really get into it then you can get the other book. SQL for Smarties will also touch on a lot of other database design and querying info. Some really good stuff in there. He presents alternative ways of modeling trees which can work much better than the adjacency list model that you're using.

In one of his models the question of "who is the top most parent" becomes very trivial.

Answer 4

You may consider using the "ltree" contrib module.

Answer 5

WITH RECURSIVE from PostgreSQL 8.4 onwards?

Answer 6

I found this post very helpful. It just uses a pl/sql function which is called recursively:

http://gustavostraube.wordpress.com/2009/11/17/retrieving-an-hierarchical-tree-recursively-with-plpgsql/