pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedA path through a tree
6+ messages / 4 participants
[nested] [flat]
* A path through a tree
@ 1999-01-12 14:34 Neil Burrows <maillist@remo.demon.co.uk>
0 siblings, 2 replies; 6+ messages in thread
From: Neil Burrows @ 1999-01-12 14:34 UTC (permalink / raw)
To: pgsql-sql
Hi,
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).
The tree can be of arbitrary depth.
where i = id and p = parent
i = 1
p = NULL
|
|
+-----+-----+
| |
i = 2 i = 3
p = 1 p = 1
|
|
+-----+-----+
| |
i = 4 i = 5
p = 3 p = 3
So if I wanted to find all the parent ids from node with index 5 to root I'd
get (3,1)?
As I say, I doubt there is a simple select that can do this but thought I
may as well ask.
Thanks in advance,
Neil Burrows
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [SQL] A path through a tree
@ 1999-01-12 16:50 David Martinez Cuevas <david@estadistica.unam.mx>
parent: Neil Burrows <maillist@remo.demon.co.uk>
1 sibling, 0 replies; 6+ messages in thread
From: David Martinez Cuevas @ 1999-01-12 16:50 UTC (permalink / raw)
To: Neil Burrows <maillist@remo.demon.co.uk>; +Cc: pgsql-sql
Hi Neil.
On Tue, 12 Jan 1999, Neil Burrows wrote:
> Hi,
>
> OK, I have a feeling that this not something that can be done with SQL but I
> may as well give it a shot.
Actually, as you should know, postgresql doesn't have a procedural
language... in this problem it is necessary to use it... but you can use
libpq or any other interface to do it.
> Say you have a table with the following columns:
>
> id int4 NOT NULL UNIQUE
> parent int4
> value varchar(8)
>
Here a is a sample and bad written funtion that can help you.
As you will see I didn't compiled it, and there is a lot of code you
should still write to use it.... it's just an idea:
#include "whatever_you_need";
...
char * look_for_parent ( char *);
function look_for_parent ( char *leaf )
{ if (leaf == NULL) return "This is the root: $leaf";
parent = PQ_EXEC($YOUR_CONN,"select parent from table where values = $leaf")$
print ("\nFor the leaf %s the parent is %s",leaf,parent);
return ( look_for_parent (parent));
}
...
As you can see it pretends to be a C code contaminated with PHP ; )
Good luck
David Martinez Cuevas.mx
"Eat Linux, Drink Linux... SMOKE LINUX".
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [SQL] A path through a tree
@ 1999-01-12 19:09 Bruce Stephens <bruce@cenderis.demon.co.uk>
parent: Neil Burrows <maillist@remo.demon.co.uk>
1 sibling, 0 replies; 6+ messages in thread
From: Bruce Stephens @ 1999-01-12 19:09 UTC (permalink / raw)
To: pgsql-sql
"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.
^ permalink raw reply [nested|flat] 6+ messages in thread
* RE: [SQL] A path through a tree
@ 1999-01-13 23:20 Jackson, DeJuan <djackson@cpsgroup.com>
0 siblings, 0 replies; 6+ messages in thread
From: Jackson, DeJuan @ 1999-01-13 23:20 UTC (permalink / raw)
To: Bruce Stephens <bruce@cenderis.demon.co.uk>; pgsql-sql
> -----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
^ permalink raw reply [nested|flat] 6+ messages in thread
* RE: [SQL] A path through a tree
@ 1999-01-14 16:18 Jackson, DeJuan <djackson@cpsgroup.com>
0 siblings, 0 replies; 6+ messages in thread
From: Jackson, DeJuan @ 1999-01-14 16:18 UTC (permalink / raw)
To: Neil Burrows <neil@remo.demon.co.uk>; +Cc: pgsql-sql
> > 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.
>
> Eek! Caught! :)
>
> Thanks again,
>
> Regards,
>
> Neil Burrows
Well, last night I thought it over and a Good(tm) way to display
threading, hit me. If you don't ever delete a node, but just it's data
you can use the l and r information recursively to display.
function display(nodeList[][], currentNode, depth) {
printf("%s|_%s\n", spaces(depth*2), nodeList[currentNode]['title']);
numChildren = (nodeList[currentNode]['r'] -
nodeList[currentNode]['l'] - 1)/2;
for(numNodes=0;numNodes < numChildren;
numNodes += display(nodeList, currentNode+numNodes+1, depth+1)) ;
numNodes++;
return numNodes;
}
I hope my psudo-code is decipherable.
Looking at the tree from the previous message:
l| r|data
--+--+----
1|12|head
2| 7|c1
3| 4|c11
5| 6|c12
8| 9|c2
10|11|c3
(6 rows)
And using the information in the above function we get:
|_head
|_c1
|_c11
|_c12
|_c2
|_c3
Collapsing and expanding branches could simply be an array of booleans
that's checked at currentNode where true display current node with a
plus (link for html to expand) then return numChildren+1 otherwise do
the loop.
Just thought everybody might like to see this.
-DEJ
BTW if you want more examples of this data-layout of trees I can send in
the URL's where I found it.
^ permalink raw reply [nested|flat] 6+ messages in thread
* RE: [SQL] A path through a tree
@ 1999-01-20 16:20 Jackson, DeJuan <djackson@cpsgroup.com>
0 siblings, 0 replies; 6+ messages in thread
From: Jackson, DeJuan @ 1999-01-20 16:20 UTC (permalink / raw)
To: Michael J Schout <mschout@mail.gkg-com.com>; pgsql-sql
Oh well only one request for the URLS. But, hey that's enough of an
excuse for me, so here you go:
http://www.dbmsmag.com/9603d06.html
http://www.dbmsmag.com/9604d06.html
http://www.dbmsmag.com/9605d06.html
> Hi.
>
> Saw your message in the pgsql list. I would be interested in
> teh URL you
> mentioned where you found this information if you wouldnt
> mind. I have
> dones eomething similar toi this, but my solution is not as
> robust as this
> one. I basically just stored the node titles in one table, and made
> another table that tells which nodes are parents/children of
> other nodes.
> Works pretty well for what I need since I only need to show
> one "level" of
> the tree most of 'the time. There are some times I need to
> walk up the
> tree to get the path to the root, but my trees are very
> shallow, so this
> only takes 3-4 selects :). But I really like this solution
> and would liek
> to see the url where you round it.
>
> Thanks!
>
> Mike
> >
> > Well, last night I thought it over and a Good(tm) way to display
> > threading, hit me. If you don't ever delete a node, but
> just it's data
> > you can use the l and r information recursively to display.
> >
> > function display(nodeList[][], currentNode, depth) {
> > printf("%s|_%s\n", spaces(depth*2),
> nodeList[currentNode]['title']);
> > numChildren = (nodeList[currentNode]['r'] -
> > nodeList[currentNode]['l'] - 1)/2;
> > for(numNodes=0;numNodes < numChildren;
> > numNodes += display(nodeList,
> currentNode+numNodes+1, depth+1)) ;
> > numNodes++;
> > return numNodes;
> > }
> >
> > I hope my psudo-code is decipherable.
> > Looking at the tree from the previous message:
> > l| r|data
> > --+--+----
> > 1|12|head
> > 2| 7|c1
> > 3| 4|c11
> > 5| 6|c12
> > 8| 9|c2
> > 10|11|c3
> > (6 rows)
> >
> > And using the information in the above function we get:
> > |_head
> > |_c1
> > |_c11
> > |_c12
> > |_c2
> > |_c3
> >
> > Collapsing and expanding branches could simply be an array
> of booleans
> > that's checked at currentNode where true display current node with a
> > plus (link for html to expand) then return numChildren+1
> otherwise do
> > the loop.
> >
> > Just thought everybody might like to see this.
> > -DEJ
> > BTW if you want more examples of this data-layout of trees
> I can send in
> > the URL's where I found it.
> >
>
^ permalink raw reply [nested|flat] 6+ messages in thread
end of thread, other threads:[~1999-01-20 16:20 UTC | newest]
Thread overview: 6+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
1999-01-12 14:34 A path through a tree Neil Burrows <maillist@remo.demon.co.uk>
1999-01-12 16:50 ` David Martinez Cuevas <david@estadistica.unam.mx>
1999-01-12 19:09 ` Bruce Stephens <bruce@cenderis.demon.co.uk>
1999-01-13 23:20 RE: [SQL] A path through a tree Jackson, DeJuan <djackson@cpsgroup.com>
1999-01-14 16:18 RE: [SQL] A path through a tree Jackson, DeJuan <djackson@cpsgroup.com>
1999-01-20 16:20 RE: [SQL] A path through a tree Jackson, DeJuan <djackson@cpsgroup.com>
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