Thread: A path through a tree

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

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".

"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.