Using Recursive Common table expressions to represent Tree structures

Sunday, August 16. 2009

Using Recursive Common table expressions to represent Tree structures

A very long time ago, we wrote an article on how to use PostgreSQL to show the fully qualified name of an item in an inventory tree. Basically we were modeling a paper products tree. The original article can be found here Using PostgreSQL User-Defined Functions to solve the Tree Problem and was based on PostgreSQL 7.4 technology.

We'll repeat the text here for completeness and demonstrate the PostgreSQL 8.4 that solves this and more efficiently.

The Problem

Suppose you are tracking supplies and have a field called si_item and another called si_parentid. The parent keeps track of what subclass a supply item belongs to. E.g. you have paper parent that has subclasses such as recycled, non-recycled. When someone takes supplies, you want to return the fully qualified name e.g. Paper->Recycled->20 Lb

Below is what the structure of your table looks like.

si_id int, si_parentid int, si_item. In your table are the following entries


si_id   si_parentid si_item
1   Paper
2 1 Recycled

3 2 20 lb
4 2 40 lb
5 1 Non-Recycled
6 5 20 lb
7 5 40 lb

8 5 Scraps

Solution

CREATE TABLE supplyitem(si_id integer PRIMARY KEY, si_parentid integer, si_item varchar(100));

--load up the table (multirow constructor introduced in 8.2)
INSERT INTO supplyitem(si_id,si_parentid, si_item)
VALUES (1, NULL, 'Paper'),
(2,1, 'Recycled'),
(3,2, '20 lb'),
(4,2, '40 lb'),
(5,1, 'Non-Recycled'),
(6,5, '20 lb'),
(7,5, '40 lb'),
(8,5, 'Scraps');

--Recursive query (introduced in 8.4 returns fully qualified name)
WITH RECURSIVE supplytree AS
(SELECT si_id, si_item, si_parentid, CAST(si_item As varchar(1000)) As si_item_fullname
FROM supplyitem
WHERE si_parentid IS NULL
UNION ALL
SELECT si.si_id,si.si_item,
	si.si_parentid,
	CAST(sp.si_item_fullname || '->' || si.si_item As varchar(1000)) As si_item_fullname
FROM supplyitem As si
	INNER JOIN supplytree AS sp
	ON (si.si_parentid = sp.si_id)
)
SELECT si_id, si_item_fullname
FROM supplytree
ORDER BY si_item_fullname;

Result looks like

si_id |      si_item_fullname
------+-----------------------------
 1    | Paper
 5    | Paper->Non-Recycled
 6    | Paper->Non-Recycled->20 lb
 7    | Paper->Non-Recycled->40 lb
 8    | Paper->Non-Recycled->Scraps
 2    | Paper->Recycled
 3    | Paper->Recycled->20 lb
 4    | Paper->Recycled->40 lb

Posted by Leo Hsu and Regina Obe in 8.4, basics, cte, intermediate at 13:44 | Comments (5) | Trackback (1)

Trackbacks

Trackback specific URI for this entry

Social comments and analytics for this post
This post was mentioned on Twitter by roblb: Using Recursive Common table expressions to represent Tree structures: A very long time ago, we wrote .. http://bit.ly/Flne3 #postgres

Weblog: uberVU - social comments
Tracked: Jan 04, 21:19

Freee Open source GIS Conference in Barcelona 2010

Comments

Display comments as (Linear | Threaded)

Great topic!

A couple of observations:

* Unless the length 1000 has some significance, use TEXT instead of
VARCHAR(1000).

* It might well be both faster and more correct to push items into an array
and use array_to_string() in the outer SELECT, and it won't be subject to
sorting anomalies.

WITH RECURSIVE supplytree AS
(
SELECT
si_id,
si_item,
si_parentid,
ARRAY[si_item] AS si_item_array
FROM supplyitem
WHERE si_parentid IS NULL
UNION ALL
SELECT
si.si_id,si.si_item,
si.si_parentid,
sp.si_item_array || si.si_item As si_item_array
FROM
supplyitem As si
JOIN
supplytree AS sp
ON (si.si_parentid = sp.si_id)
)
SELECT
si_id,
array_to_string(si_item_array, '->') AS si_item_fullname
FROM supplytree
ORDER BY si_item_array;

#1 David Fetter (Homepage) on 2009-08-16 19:10 (Reply)

Have thought about using ltree ?

http://www.postgresql.org/docs/current/static/ltree.html

I'am not saying than WITH RECURSIVE is bad .. just that, there are simpler solution sometimes

#2 Arek on 2009-09-19 18:16 (Reply)

Good point. We haven't explored the use of ltree so will have to give it a test drive sometime. I think the only thing against it is that its a PostgreSQL specific feature where as the CTE is more ANSI portable (except for possiblyt the word RECURSIVE)

#2.1 Leo on 2009-09-28 02:58 (Reply)

How do you use it to find the parent path for just a single item?

#3 sabra on 2009-09-26 18:35 (Reply)

Sabra,

Couple of ways -- you could write a function as we demonstrated in linked article, but that is not as suitable for multiple sets since it would probably do a subquery for each record.

You coulde also take our example and limit with a WHERE clause but that is much slower than it could be.

The other way would be to recurse backward from the child to the parent. So instead of starting at parent nodes -- you start at the child node and keep on unioning until you hit a parent with no parent. Will have to write that up sometime.

#3.1 Leo on 2009-09-28 03:05 (Reply)

Add Comment

Name
Email
Homepage
In reply to
Comment	Standard emoticons like :-) and ;-) are converted to images. E-Mail addresses will not be displayed and will only be used for E-Mail notifications To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly. Enter the string from the spam-prevention image above:
	Remember Information? Subscribe to this entry