Getting list of all children from adjacency tree

From PostgreSQL wiki
Jump to navigationJump to search

Library Snippets

Getting list of all children from adjacency tree

Works with PostgreSQL

Any version

Written in

Pl/pgSQL

Depends on

Nothing


Description

Assuming you have Adjacency List based tree - i.e. table with structure similar to this:

                           Table "public.test"
  Column   |  Type   |                     Modifiers
-----------+---------+---------------------------------------------------
 id        | integer | not null default nextval('test_id_seq'::regclass)
 parent_id | integer |
 x         | text    |
Indexes:
    "test_pkey" PRIMARY KEY, btree (id)
Foreign-key constraints:
    "test_parent_id_fkey" FOREIGN KEY (parent_id) REFERENCES test(id)

you might want to get all children of given element.

To do it, you can use this function:

CREATE OR REPLACE FUNCTION get_all_children_array(use_parent INT4) RETURNS INT4[] as $$
DECLARE
    process_parents INT4[] := ARRAY[ use_parent ];
    children INT4[] := '{}';
    new_children INT4[];
BEGIN
    WHILE ( array_upper( process_parents, 1 ) IS NOT NULL ) LOOP
        new_children := ARRAY( SELECT id FROM test WHERE parent_id = ANY( process_parents ) AND id <> ALL( children ) );
        children := children || new_children;
        process_parents := new_children;
    END LOOP;
    RETURN children;
END;
$$ LANGUAGE plpgsql;

Usage

# select get_all_children_array(3);
 get_all_children_array
------------------------
 {5,6,9}
(1 row)


# select * from test where id = any( get_all_children_array(3) );
 id | parent_id | x
----+-----------+---
  5 |         3 | e
  6 |         3 | f
  9 |         5 | i
(3 rows)

PostgreSQL 8.4+

Common Table Expressions (CTE) make it much easier to write this as a query instead of as a procedure:

First, we write the CTE to return all ancestors of the item:

WITH RECURSIVE tree AS (
  SELECT id, ARRAY[]::integer[] AS ancestors
  FROM test WHERE parent_id IS NULL

  UNION ALL

  SELECT test.id, tree.ancestors || test.parent_id
  FROM test, tree
  WHERE test.parent_id = tree.id
) SELECT * FROM tree WHERE 0 = ANY(tree.ancestors);

This query could return something like this:

 id | ancestors
------------------------
  3 | {}
  5 | {3}
  6 | {3}
  9 | {3,5}
(4 rows)

Now that we have an array of ancestors for each item, retrieving the descendants is a simple WHERE clause:

WITH RECURSIVE tree AS (
  SELECT id, ARRAY[]::integer[] AS ancestors
  FROM test WHERE parent_id IS NULL

  UNION ALL

  SELECT test.id, tree.ancestors || test.parent_id
  FROM test, tree
  WHERE test.parent_id = tree.id
) SELECT * FROM tree WHERE 3 = ANY(tree.ancestors);

Given the result above, this query would return the following:

 id | ancestors
------------------------
  5 | {3}
  6 | {3}
  9 | {3,5}
(3 rows)