cloning hierarchical data

Question

let's assume i have a self referencing hierarchical table build the classical way like this one:

CREATE TABLE test
(name text,id serial primary key,parent_id integer
references test);

insert into test (name,id,parent_id) values
('root1',1,NULL),('root2',2,NULL),('root1sub1',3,1),('root1sub2',4,1),('root
2sub1',5,2),('root2sub2',6,2);

testdb=# select * from test;

   name    | id | parent_id
-----------+----+-----------
 root1     |  1 |  
 root2     |  2 |  
 root1sub1 |  3 |         1
 root1sub2 |  4 |         1
 root2sub1 |  5 |         2
 root2sub2 |  6 |         2

What i need now is a function (preferrably in plain sql) that would take the id of a test record and clone all attached records (including the given one). The cloned records need to have new ids of course. The desired result would like this for example:

Select * from cloningfunction(2);

   name    | id | parent_id    
-----------+----+-----------
 root2     |  7 |  
 root2sub1 |  8 |         7
 root2sub2 |  9 |         7

Any pointers? Im using PostgreSQL 8.3.

Answer 1

Pulling this result in recursively is tricky (although possible). However, it's typically not very efficient and there is a much better way to solve this problem.

Basically, you augment the table with an extra column which traces the tree to the top - I'll call it the "Upchain". It's just a long string that looks something like this:

name | id | parent_id | upchain
root1 | 1 | NULL | 1:
root2 | 2 | NULL | 2:
root1sub1 | 3 | 1 | 1:3:
root1sub2 | 4 | 1 | 1:4:
root2sub1 | 5 | 2 | 2:5:
root2sub2 | 6 | 2 | 2:6:
root1sub1sub1 | 7 | 3 | 1:3:7:

It's very easy to keep this field updated by using a trigger on the table. (Apologies for terminology but I have always done this with SQL Server). Every time you add or delete a record, or update the parent_id field, you just need to update the upchain field on that part of the tree. That's a trivial job because you just take the upchain of the parent record and append the id of the current record. All child records are easily identified using LIKE to check for records with the starting string in their upchain.

What you're doing effectively is trading a bit of extra write activity for a big saving when you come to read the data.

When you want to select a complete branch in the tree it's trivial. Suppose you want the branch under node 1. Node 1 has an upchain '1:' so you know that any node in the branch of the tree under that node must have an upchain starting '1:...'. So you just do this:

SELECT *
FROM table
WHERE upchain LIKE '1:%'

This is extremely fast (index the upchain field of course). As a bonus it also makes a lot of activities extremely simple, such as finding partial trees, level within the tree, etc.

I've used this in applications that track large employee reporting hierarchies but you can use it for pretty much any tree structure (parts breakdown, etc.)

Notes (for anyone who's interested):

• I haven't given a step-by-step of the SQL code but once you get the principle, it's pretty simple to implement. I'm not a great programmer so I'm speaking from experience.
• If you already have data in the table you need to do a one time update to get the upchains synchronised initially. Again, this isn't difficult as the code is very similar to the UPDATE code in the triggers.
• This technique is also a good way to identify circular references which can otherwise be tricky to spot.

Answer 2

The Joe Celko's method which is similar to the njreed's answer but is more generic can be found here:

• Nested-Set Model of Trees (at the middle of the article)
• Nested-Set Model of Trees, part 2
• Trees in SQL -- Part III