Postgres Pro
Downloads
Home   >   mailing lists

Thread: Linked list with CTE

Linked list with CTE

From
Mark Lubratt
Date:
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:


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

Re: Linked list with CTE

From
Gurjeet Singh
Date:
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:


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