Linked list with CTE

pg.ddx.io  pgsql-sql@postgresql.org mailing list archive  
help / color / mirror / Atom feed

Linked list with CTE
2+ messages / 2 participants
[nested] [flat]

* Linked list with CTE
@ 2010-03-14 23:51  Mark Lubratt <mark.lubratt@indeq.com>
  0 siblings, 1 reply; 2+ messages in thread

From: Mark Lubratt @ 2010-03-14 23:51 UTC (permalink / raw)
  To: pgsql-sql

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

^ permalink  raw  reply  [nested|flat] 2+ messages in thread

* Re: Linked list with CTE
@ 2010-03-20 03:34  Gurjeet Singh <singh.gurjeet@gmail.com>
  parent: Mark Lubratt <mark.lubratt@indeq.com>
  0 siblings, 0 replies; 2+ messages in thread

From: Gurjeet Singh @ 2010-03-20 03:34 UTC (permalink / raw)
  To: Mark Lubratt <mark.lubratt@indeq.com>; +Cc: pgsql-sql

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 <mark.lubratt@indeq.com>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

^ permalink  raw  reply  [nested|flat] 2+ messages in thread

end of thread, other threads:[~2010-03-20 03:34 UTC | newest]

Thread overview: 2+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2010-03-14 23:51 Linked list with CTE Mark Lubratt <mark.lubratt@indeq.com>
2010-03-20 03:34 ` Gurjeet Singh <singh.gurjeet@gmail.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