= --Apple-Mail-1-393221579-- From singh.gurjeet@gmail.com Sat Mar 20 03:35:56 2010 Received: from maia.hub.org (unknown [200.46.204.183]) by mail.postgresql.org (Postfix) with ESMTP id 49F22633E26 for ; Sat, 20 Mar 2010 00:35:56 -0300 (ADT) Received: from mail.postgresql.org ([200.46.204.86]) by maia.hub.org (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 97233-01-8 for ; Sat, 20 Mar 2010 03:35:45 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-vw0-f46.google.com (mail-vw0-f46.google.com [209.85.212.46]) by mail.postgresql.org (Postfix) with ESMTP id 15FBD634C5A for ; Sat, 20 Mar 2010 00:35:16 -0300 (ADT) Received: by vws11 with SMTP id 11so665266vws.19 for ; Fri, 19 Mar 2010 20:35:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :from:date:message-id:subject:to:cc:content-type; bh=o9lqRk9uAjxcqS8FASvQTUfDRjyAJJJUL91VvUpHbSI=; b=ImR+KgpSA6oXqK2ciTWSF1XqsVBw42xbAqkrMM6YPwvTMZmePQNIHj8RMcqBYRSYsR c5LGYw4pkOD7LUfUoOtFz7mlOQ9VbrsvaTqta+j1pbjjv0wOBVrmvd2KLP4Xv1jpy/1P cMNX4gNXmCdGogSO4Ooc5EToAnCGiFIZc4c8o= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; b=Wm0q6I69RxpZY8YzFqGJGYjDf60FzjFGsBBt8BRZvTmZDYf+WjMDd/pF7ePUEhgCfh pfXXfEuQsWcD0lVwGSrD/2lk4XC15rkIsRMBJYpMblVvtvaUg8/hRZdcfGMXQpg2rFSr v3KYZ60jv108MQgRRgqD9+vQ7iyzpxyTols5s= MIME-Version: 1.0 Received: by 10.220.122.15 with SMTP id j15mr1797367vcr.57.1269056114087; Fri, 19 Mar 2010 20:35:14 -0700 (PDT) In-Reply-To: References: From: Gurjeet Singh Date: Fri, 19 Mar 2010 23:34:54 -0400 Message-ID: <65937bea1003192034n461dbe33jd3528adb2f93aacc@mail.gmail.com> Subject: Re: Linked list with CTE To: Mark Lubratt Cc: pgsql-sql@postgresql.org Content-Type: multipart/alternative; boundary=005045015a50e158bb048233263e X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=-2.598 tagged_above=-10 required=5 tests=BAYES_00=-2.599, HTML_MESSAGE=0.001 X-Spam-Level: X-Archive-Number: 201003/157 X-Sequence-Number: 33864 --005045015a50e158bb048233263e Content-Type: text/plain; charset=ISO-8859-1 All you need is a function that traverses the tree upwards and returns the root's id. create or replace function get_root_name(dept text) returns text as $$ declare parent text := ''; prev_parent text; begin while( parent is not null ) loop prev_parent := parent; select p."name" into parent from department p join department c on( p.id = c.parent_department ) where c."name" = dept ; dept := parent; end loop; return prev_parent; $$ language plpgsql; This is untested code, and there are corner cases you should take care of. Also, you'd be better off using the ID column than the name column. Now you'd change the starting condition of your CTE as: -- non-recursive term SELECT * FROM department WHERE name = get_root_name( 'A' ) Best regards, On Sun, Mar 14, 2010 at 7:51 PM, Mark Lubratt wrote: > Hello, > > I have a table in my database with multiple, independent linked lists. I > would like to have a query that returns an entire linked list given a node > (the node could be anywhere within the list). > > I found on the web an example of how to use CTEs to do this: > > http://wiki.postgresql.org/wiki/CTEReadme > > I'll repeat the gist of it here: > > > CREATE TABLE department ( > id INTEGER PRIMARY KEY, -- department ID > parent_department INTEGER REFERENCES department, -- upper department ID > name TEXT -- department name > ); > > INSERT INTO department (id, parent_department, "name") > VALUES > (0, NULL, 'ROOT'), > (1, 0, 'A'), > (2, 1, 'B'), > (3, 2, 'C'), > (4, 2, 'D'), > (5, 0, 'E'), > (6, 4, 'F'), > (7, 5, 'G'); > > -- department structure represented here is as follows: > -- > -- ROOT-+->A-+->B-+->C > -- | | > -- | +->D-+->F > -- +->E-+->G > > To extract all departments under A, you can use the following recursive > query: > > > WITH RECURSIVE subdepartment AS > ( > -- non-recursive term > SELECT * FROM department WHERE name = 'A' > > UNION ALL > > -- recursive term > SELECT d.* > FROM > department AS d > JOIN > subdepartment AS sd > ON (d.parent_department = sd.id) > ) > SELECT * > FROM subdepartment > ORDER BY name; > > > My database contains multiple, independent structures like the one given > above. So, I can modify the above with: > > insert into department (id, parent_department, name) values (8, NULL, 'Z'), > (9, 8, 'Y'); > > I need a bidirectional query and since I'm quite new to CTE, I'm not sure > how to modify the query to get parent departments as well as > subdepartments... Thus, if I give the query any node in a linked list, I'd > like the entire tree returned. > > e.g. If I give the query 'A', I'd like it to return the ROOT, A, B, C, D, > E, F, G tree. If I give the query 'Y', I'd like it to return the Z, Y tree. > > I hope I made sense... > > Thanks! > Mark > > -- gurjeet.singh @ EnterpriseDB - The Enterprise Postgres Company http://www.enterprisedb.com singh.gurjeet@{ gmail | yahoo }.com Twitter/Skype: singh_gurjeet Mail sent from my BlackLaptop device --005045015a50e158bb048233263e Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

All you need is a function that traverses the tree upwards= and returns the root's id.


create or replace function get_root_name(dept text) returns text as $$
d=
eclare
=A0=A0=A0 parent text :=3D '';
=A0=A0=A0 prev_parent t=
ext;
begin
=A0=A0=A0 while( parent is not null ) loop
=A0=A0=A0=A0=
=A0=A0=A0 prev_parent :=3D parent;



=A0=A0=A0=A0=A0=A0=A0 select p."name"
        into parent<=
br>        from department p
          join department c 
           =
 on( p.id =3D c.parent_department )
        =
where c."name" =3D dept ;



=A0=A0=A0=A0=A0=A0=A0 dept :=3D parent;

=A0=A0=A0 end loop;
<=
br>=A0=A0=A0 return prev_parent;

$$ language plpgsql;

This is untested code, and there are corner cases you should tak= e care of. Also, you'd be better off using the ID column than the name = column.

Now you'd change the starting condition of your CTE as:


    -- non-recursive term
    SELECT * FROM department WHERE name =3D ge=
t_root_name( 'A' )

Best regards,

On Sun, Mar 14, 2010 at 7:51 PM, Mark Lubratt <mark.lubratt@indeq.c= om> wrote:

Hello,

I have a table in my databas= e with multiple, independent linked lists. =A0I would like to have a query = that returns an entire linked list given a node (the node could be anywhere= within the list).

I found on the web an example of how to use CTEs to do = this:
http://wiki.postgresql.org/wiki/CTEReadme

I'll repeat the gist of it here:
CREATE TABLE department ( id INTEGER PRIMARY KEY, -- department ID parent_department INTEGER REFERENCES department, -- upper department ID name TEXT -- department name ); INSERT INTO department (id, parent_department, "name") VALUES (0, NULL, 'ROOT'), (1, 0, 'A'), (2, 1, 'B'), (3, 2, 'C'), (4, 2, 'D'), (5, 0, 'E'), (6, 4, 'F'), (7, 5, 'G'); -- department structure represented here is as follows: -- -- ROOT-+->A-+->B-+->C -- | | -- | +->D-+->F -- +->E-+->G
To extrac= t all departments under A, you can use the following recursive query:
=
WITH RECURSIVE subdepartment AS ( -- non-recursive term SELECT * FROM department WHERE name =3D 'A' UNION ALL -- recursive term SELECT d.* FROM department AS d JOIN subdepartment AS sd ON (d.parent_department =3D sd.id) ) SELECT * FROM subdepartment ORDER BY name;
My database contains m= ultiple, independent structures like the one given above. =A0So, I can modi= fy the above with:

insert into department (id, par= ent_department, name) values (8, NULL, 'Z'), (9, 8, 'Y');

I need a bidirectional query and since I'm quite ne= w to CTE, I'm not sure how to modify the query to get parent department= s as well as subdepartments... =A0Thus, if I give the query any node in a l= inked list, I'd like the entire tree returned.

e.g. =A0If I give the query 'A', I'd like i= t to return the ROOT, A, B, C, D, E, F, G tree. =A0If I give the query '= ;Y', I'd like it to return the Z, Y tree.

I hope I made sense...

Thanks!
Mark

--
gurjeet.singh
@ EnterpriseDB - The Enterpr= ise Postgres Company
http://www.enterprisedb.com
=
singh.gurjeet@{ gmail | yahoo }.com
Twitter/Skype: singh_gurjeet
=
Mail sent from my BlackLaptop device

--005045015a50e158bb048233263e--