DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com;
	h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
	b=kUJNAyOlEsg8Q+sPrn5LvyUEESXGbPxskbwLxq9oQhXxmmWb6Qyks6hEmHVGwhPXPunK9E38boW02YrJ2Lzr+vVl86iNrWuIfUc6p/3Mz8j1TbbSbHBoRgePlaROcKJc0M52eekbWmeBgmy7wJ4JFdB3mMDoPSlOnPVLKTEr/cc=
Message-ID: <ddcd549e0604270131x45fcfc02j27f76aa447702371@mail.gmail.com>
Date: Thu, 27 Apr 2006 09:31:22 +0100
From: "Neil Saunders" <n.j.saunders@gmail.com>
To: "Ray Madigan" <ray@madigans.org>
Subject: Re: LinkedList
Cc: Pgsql-Sql <pgsql-sql@postgresql.org>
In-Reply-To: <20060427054631.GB97354@pervasive.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
References: <1146067158.23538.264.camel@state.g2switchworks.com>
	<IEELLOAPJFACBDBGELGHAELAEDAA.ray@madigans.org>
	<20060427054631.GB97354@pervasive.com>

Ray,

There's a good introductory article on Sitepoint for doing this kind of thi=
ng:

http://www.sitepoint.com/article/hierarchical-data-database

The "Modified Preorder Tree Traversal" is quite a nice method that I
would expect  to be a magnitude faster than recursive joins, although
does have some drawbacks.

Kind Regards,

Neil.


On 4/27/06, Jim C. Nasby <jnasby@pervasive.com> wrote:
> decibel=3D# select * from t;
>  a | b
> ---+---
>  1 | 0
>  3 | 1
>  5 | 3
>  7 | 5
>  2 | 0
>  4 | 2
>  6 | 4
>  8 | 6
> (8 rows)
>
> decibel=3D# select * from t x join t y on(x.a=3Dy.b) where y.a=3D7;
>  a | b | a | b
> ---+---+---+---
>  5 | 3 | 7 | 5
> (1 row)
>
> decibel=3D# select * from t x join t y on(x.a=3Dy.b) where y.a=3D8;
>  a | b | a | b
> ---+---+---+---
>  6 | 4 | 8 | 6
> (1 row)
>
> decibel=3D#
>
> As you can see, it selects the right data, but you'll need to step
> through it somehow. You might be able to do it with a generate_series(),
> or you can use a function. If we get WITH support/recursion in 8.2 you'd
> use that.
>
> I think that "SQL For Smarties" by Joe Celko might have an example of
> how to do this without using a function. Even if it doesn't it's a book
> any serious database developer should own.
>
> On Wed, Apr 26, 2006 at 10:35:15AM -0700, Ray Madigan wrote:
> > Scott,
> >
> > Thanks for your reply,  I tried what you said, worked around a few thin=
gs
> > but I am still stuck.  The main reason is I didn't do an adequate job o=
f
> > explaining the situation.  The table implements many linked lists and I=
 want
> > to traverse one of them given the end of the list.
> >
> > Say the table contains
> >
> > h | v | j
> > 1   0   100
> > 3   1   300
> > 5   3   500
> > 7   5   700
> >
> > 2   0   200
> > 4   2   400
> > 6   4   600
> > 8   6   800
> >
> > If I specify t.h =3D 8 I want to traverse the even part of the table
> > If I specify t.h =3D 7 I want to traverse the odd part of the table
> >
> > If you can send me to a book to read I am willing
> >
> > Thanks
> >
> > -----Original Message-----
> > From: pgsql-sql-owner@postgresql.org
> > [mailto:pgsql-sql-owner@postgresql.org]On Behalf Of Scott Marlowe
> > Sent: Wednesday, April 26, 2006 8:59 AM
> > To: Ray Madigan
> > Cc: pgsql-sql@postgresql.org
> > Subject: Re: [SQL] LinkedList
> >
> >
> > On Wed, 2006-04-26 at 11:09, Ray Madigan wrote:
> > > I have a table that I created that implements a linked list.  I am no=
t an
> > > expert SQL developer and was wondering if there are known ways to tra=
verse
> > > the linked lists.  Any information that can point me in the direction=
 to
> > > figure this out would be appreciated.  The table contains many linked
> > lists
> > > based upon the head of the list and I need to extract all of the node=
s
> > that
> > > make up a list.  The lists are simple with a item and a link to the
> > history
> > > item so it goes kind of like:
> > >
> > > 1, 0
> > > 3, 1
> > > 7, 3
> > > 9, 7
> > > ...
> > >
> > > Any suggestions would be helpful, or I will have to implement the tab=
le
> > > differently.
> >
> > You should be able to do this with a fairly simple self-join...
> >
> > select a.id, b.aid, a.field1, b.field1
> > from mytable a
> > join mytable b
> > on (a.id=3Db.aid)
> >
> > Or something like that.
> >
> > ---------------------------(end of broadcast)--------------------------=
-
> > TIP 2: Don't 'kill -9' the postmaster
> >
> >
> > ---------------------------(end of broadcast)--------------------------=
-
> > TIP 6: explain analyze is your friend
> >
>
> --
> Jim C. Nasby, Sr. Engineering Consultant      jnasby@pervasive.com
> Pervasive Software      http://pervasive.com    work: 512-231-6117
> vcard: http://jim.nasby.net/pervasive.vcf       cell: 512-569-9461
>
> ---------------------------(end of broadcast)---------------------------
> TIP 2: Don't 'kill -9' the postmaster
>