Thread

1. A path through a tree

   maillist@remo.demon.co.uk — 1999-01-12T14:34:16Z

   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
   
   
   

2. Re: [SQL] A path through a tree

   David Martinez Cuevas <david@estadistica.unam.mx> — 1999-01-12T16:50:35Z

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

3. Re: [SQL] A path through a tree

   Bruce Stephens <bruce@cenderis.demon.co.uk> — 1999-01-12T19:09:55Z

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