Соединение родительских строк со своими детьми

Question

У меня есть таблица, состоящая из отображений между родителями и детьми.

* 1003 например *

my_table
-----+------+---------
  id | name | child_id
-----+------+---------
  a  |  A1  | b
  b  |  B1  | c
  b  |  B2  | c
  b  |  B3  | a
  c  |  C1  | d
  d  |  D1  | a
  d  |  D2  | b

Я бы хотел присоединиться к ним, чтобы получить такой вывод: (Строки, отмеченные знаком «<-», указывают на то, что строка не должна существовать по указанной причине) </p>

desired_table
-----+--------+----------+-------------
  id |  name  | child_id | visited_ids
-----+--------+----------+-------------
  a  | A1, B1 |    c     | {'a', 'b'}
  a  | A1, B2 |    c     | {'a', 'b'}
  a  | A1, B3 |    a     | {'a', 'b'}  <-- 'a' was visited
  b  | B1, C1 |    d     | {'b', 'c'}
  b  | B2, C1 |    d     | {'b', 'c'}
  b  | B3, A1 |    b     | {'b', 'a'}  <-- 'b' was visited
  c  | C1, D1 |    a     | {'c', 'd'}
  c  | C1, D2 |    b     | {'c', 'd'}
  d  | D1, A1 |    b     | {'d', 'a'}
  d  | D2, B1 |    c     | {'d', 'b'}
  d  | D2, B2 |    c     | {'d', 'b'}
  d  | D2, B3 |    a     | {'d', 'b'}

Строки в этой новой таблице необходимо повторно объединить с my_table, чтобы получить этот вывод. (Строки, отмеченные знаком «<-», указывают на то, что строка не должна существовать по указанной причине) </p>

desired_table
-----+------------+----------+----------------
  id |    name    | child_id |   visited_ids
-----+------------+----------+----------------
  a  | A1, B1, C1 |    d     | {'a', 'b', 'c'}
  a  | A1, B2, C1 |    d     | {'a', 'b', 'c'}
  b  | B1, C1, D1 |    a     | {'b', 'c', 'd'}
  b  | B1, C1, D2 |    b     | {'b', 'c', 'd'}  <-- 'b' was visited
  b  | B2, C1, D1 |    a     | {'b', 'c', 'd'}
  b  | B2, C1, D2 |    b     | {'b', 'c', 'd'}  <-- 'b' was visited
  c  | C1, D1, D1 |    a     | {'c', 'd', 'd'}  <-- 'd' was visited
  c  | C1, D1, D2 |    b     | {'c', 'd', 'd'}  <-- 'd' was visited
  c  | C1, D2, B1 |    c     | {'c', 'd', 'b'}  <-- 'c' was visited
  c  | C1, D2, B2 |    c     | {'c', 'd', 'b'}  <-- 'c' was visited
  c  | C1, D2, B3 |    a     | {'c', 'd', 'b'}
  d  | D1, A1, B1 |    c     | {'d', 'a', 'b'}
  d  | D1, A1, B2 |    c     | {'d', 'a', 'b'}
  d  | D1, A1, B3 |    a     | {'d', 'a', 'b'}
  d  | D2, B1, C1 |    d     | {'d', 'b', 'c'}  <-- 'd' was visited
  d  | D2, B2, C1 |    d     | {'d', 'b', 'c'}  <-- 'd' was visited
  d  | D2, B3, A1 |    b     | {'d', 'b', 'a'}

... и так далее, и тому подобное. Ряды, которые еще можно «соединить», будут объединяться до тех пор, пока у них не останется детей. Строки, которые больше не могут быть объединены, останутся как есть.

Answer 1

Одной из проблем вашего примера является то, что у вас есть бесконечный цикл (a,A1,b) -> (b,B3,a) -> (a,A1,b), который немного сложно обнаружить.

Но это (и ссылка peufeu) должно помочь вам начать:

WITH RECURSIVE hierarchy (id, names, child_id, path)
AS
(
   SELECT id, array[name], child_id, array[id] as path
   FROM mapping
   WHERE id = 'a'

   UNION ALL

   SELECT c.id, p.names||c.name, c.child_id, p.path||c.id
   FROM mapping c
   JOIN hierarchy p ON p.child_id = c.id AND NOT (p.path @> (p.path||c.id))
)
SELECT *
FROM hierarchy
ORDER BY 1

Он не создает столбец "ited_ids ", как вы хотите, хотя

Answer 2

Ваше сообщение идеально соответствует запросу WITH RECURSIVE:

http://www.postgresql.org/docs/current/static/queries-with.html