Getting list of all children from adjacency tree
From PostgreSQL wiki
(Redirected from Snippets/Tree In 8.3)
Jump to navigationJump to searchGetting 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)