Обсуждение: WITH RECURSIVE clause -- all full and partial paths

Dear list,

In reference to the message below posted on the 'pgsql-hackers' list regarding 'iterative' queries,
could anyone help me write the queries that return all full and all partial paths from the root?

Sincerely,
Aryé.


--http://archives.postgresql.org/pgsql-hackers/2008-02/msg00642.php

CREATE TABLE department (
  id INT PRIMARY KEY,
  parent_department INT REFERENCES department,
  name TEXT
);

INSERT INTO department VALUES (0, NULL, 'ROOT');
INSERT INTO department VALUES (1, 0, 'A');
INSERT INTO department VALUES (2, 1, 'B');
INSERT INTO department VALUES (3, 2, 'C');
INSERT INTO department VALUES (4, 2, 'D');
INSERT INTO department VALUES (5, 0, 'E');
INSERT INTO department VALUES (6, 3, 'F');
INSERT INTO department VALUES (7, 5, 'G');

--select * from department
--delete from department

This will represent a tree structure of an organization:

  ROOT ---> A ---> B ---> C ---> F
    |              |
    |              +----> D
    |
    +-----> E ---> G




--If you want to extract all departments "under" A, you could use a recursive query:

WITH RECURSIVE subdepartment AS
(
  --
  SELECT * FROM department WHERE name = 'A'

  UNION ALL

  -- recursive term referring to "subdepartment"
  SELECT d.* FROM department AS d, subdepartment AS sd
    --WHERE d.id = sd.parent_department
    WHERE d.parent_department = sd.id
)
SELECT * FROM subdepartment;

This will return A, B, C, D and F.

In article <aaf543e90906120856r5219cf9cv7f13ba0d37494378@mail.gmail.com>,
aryoo <howaryoo@gmail.com> writes:

> Dear list,
> In reference to the message below posted on the 'pgsql-hackers' list regarding
> 'iterative' queries,
> could anyone help me write the queries that return all full and all partial
> paths from the root?

Probably you want to use the following query:

  WITH RECURSIVE subdepartment AS (
    SELECT id, parent_department, name AS path
    FROM department
    WHERE name = 'A'
  UNION ALL
    SELECT d.id, d.parent_department, sd.path || '.' || d.name
    FROM department d
    JOIN subdepartment sd ON sd.id = d.parent_department
  )
  SELECT id, path
  FROM subdepartment;

This returns:

 id |  path
----+---------
  1 | A
  2 | A.B
  3 | A.B.C
  4 | A.B.D
  6 | A.B.C.F
(5 rows)

On Fri, Jun 12, 2009 at 10:14:21PM +0200, Harald Fuchs wrote:
> In article <aaf543e90906120856r5219cf9cv7f13ba0d37494378@mail.gmail.com>,
> aryoo <howaryoo@gmail.com> writes:
>
> > Dear list,
> > In reference to the message below posted on the 'pgsql-hackers' list regarding
> > 'iterative' queries,
> > could anyone help me write the queries that return all full and all partial
> > paths from the root?
>
> Probably you want to use the following query:
>
>   WITH RECURSIVE subdepartment AS (
>     SELECT id, parent_department, name AS path
>     FROM department
>     WHERE name = 'A'
>   UNION ALL
>     SELECT d.id, d.parent_department, sd.path || '.' || d.name
>     FROM department d
>     JOIN subdepartment sd ON sd.id = d.parent_department
>   )
>   SELECT id, path
>   FROM subdepartment;

This is much easier as:

WITH RECURSIVE subdepartment AS (
  SELECT id, parent_department, ARRAY[name] AS "path"
  FROM department
  WHERE name = 'A'
UNION ALL
  SELECT d.id, d.parent_department, sd."path" || d.name
  FROM department d
  JOIN subdepartment sd ON (
    sd.id = d.parent_department
  AND
    d.name NOT IN(sd."path")  /* Make sure there are no cycles */
)
SELECT id, path
FROM subdepartment;

Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778  AIM: dfetter666  Yahoo!: dfetter
Skype: davidfetter      XMPP: david.fetter@gmail.com

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

Dear David and  Harald,

Thanks both for your help.
Good day.
Aryé.