From: Jackson, DeJuan <djackson@cpsgroup.com>
To: Bruce Stephens <bruce@cenderis.demon.co.uk>
To: pgsql-sql@postgreSQL.org
Subject: RE: [SQL] A path through a tree
Date: Wed, 13 Jan 1999 17:20:40 -0600
Message-ID: <F10BB1FAF801D111829B0060971D839F5DC744@cpsmail> (raw)
> -----Original Message-----
> "Neil Burrows" <maillist@remo.demon.co.uk> writes:
>
> > OK, I have a feeling that this not something that can be
> done with SQL but I
> > may as well give it a shot.
> >
> > Say you have a table with the following columns:
> >
> > id int4 NOT NULL UNIQUE
> > parent int4
> > value varchar(8)
> >
> > and each entry represents a node in a tree. So the top most node
> > will have no parent, and the next nodes will have the 1st node's id
> > as their parent etc etc etc.
> >
> > If I have a leaf node, is there a SELECT statement that will give me
> > all the parent ids on the way to the root? (See diagram below for a
> > different [probably not better] description).
>
> Alas, no. (I think, anyway. There wasn't the last time I looked!)
> What you want is proposed as RECURSIVE UNION, or RECURSIVE JOIN, or
> something. For reasonably static trees, you can set things up so that
> the answer is straightforward: encode leaves with suitable distinct
> values, and have "min" and "max" columns which encode the minimum and
> maximum values in the subtrees.
>
> There's an FAQ for one of the commercial databases which explains this
> (I forget which), and Joe Celko's "SQL for Smarties" also describes
> issues like this.
It can be done if you are willing to change your table layout (and your
way of thinking). If you think of your tree as a set. Then redesign
your table for that purpose. What this does is redesign your table to
where selecting is less costly, but insert is fairly expensive
CREATE TABLE mytree (l INT, r INT, data TEXT);
INSERT INTO mytree (l, r, data) VALUES (1, 2, 'head');
TREE: 1(head)2
Total count of elements: select count(*) from mytree;
Insert new element:
1. You need to know the elements parent.r (in this case 'head's r or
2);
2. BEGIN TRANSACTION;
UPDATE mytree SET r=r+2 WHERE r>=parent.r;
UPDATE mytree SET l=l+2 WHERE l>=parent.r;
INSERT INTO mytree (l, r, data) VALUES (parent.r, parent.r+1,
'c1');
END TRANSACTION;
TREE: 1(head)4
/
2(c1)3
Lets insert 2 more for 'head' and two under 'c1' (why because any more
and I'd refuse to type out the tree).
TREE: 1(head)12
/ | \
2(c1)7 8(c2)9 10(c3)11
/ \
3(c11)4 5(c12)6
(Here's the answer to the question you actually asked.)
Get all parents of 'c11' in order (to include row in question use
BETWEEN rather than '<' and '>' for all of the below):
SELECT t1.* FROM mytree t1, mytree t2
WHERE t2.l>t1.l AND t2.l<t1.r AND
t2.data = 'c11'
ORDER BY t1.l;
RESULT:
l|r |data
-+--+----
1|12|head
2| 7|c1
(2 rows)
Get all children of 'c1' in branch order:
SELECT t1.* FROM mytree t1, mytree t2
WHERE t2.l<t1.r AND t2.r>t1.r AND
t2.data = 'c1'
ORDER BY t1.l;
RESULTS;
l|r|data
-+-+----
3|4|c11
5|6|c12
(2 rows)
Get all leaves (And in Postgres you could index r-l):
SELECT * from mytree
WHERE r-l = 1
ORDER BY l;
RESULT:
l| r|data
--+--+----
3| 4|c11
5| 6|c12
8| 9|c2
10|11|c3
(4 rows)
Get all nodes in branch order:
SELECT * FROM mytree ORDER BY l;
RESULT:
l| r|data
--+--+----
1|12|head
2| 7|c1
3| 4|c11
5| 6|c12
8| 9|c2
10|11|c3
(6 rows)
Now this gave me fits for a long time (actually figured it out in this
message :^P ), How do you delete something? Answer: Just delete it and
the rest of the logic fills in the whole.
It becomes a un-name set but still contains the same elements.
Let's DELETE 'c1';
DELETE FROM mytree WHERE data = 'c1';
TREE: 1(head)12
/ | \
() 8(c2)9 10(c3)11
/ \
3(c11)4 5(c12)6
Now let's redo the parents of 'c11':
RESULT:
l| r|data
-+--+----
1|12|head
(1 row)
If you want to use this for a message board I'd suggest inserting a
dummy head that gets excluded from display in your app. instead of
trying to have multiple heads.
Let me know if you figure out an easy way to display treading, haven't
tried it myself.
Hope this helps,
-DEJ
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients from your mail client; the link fills in
the headers below: reply via email
Some clients, webmail especially, drop In-Reply-To and References from
a link, and the reply then starts a new thread: use the mbox below.
To: pgsql-sql@postgresql.org
Cc: djackson@cpsgroup.com, bruce@cenderis.demon.co.uk
Subject: Re: [SQL] A path through a tree
In-Reply-To: <F10BB1FAF801D111829B0060971D839F5DC744@cpsmail>
References: <F10BB1FAF801D111829B0060971D839F5DC744@cpsmail>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox