Joining parent rows to their children

I have a table consisting of parent to children mappings.

E.g

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

I would like to 'join' them so as to produce this output: (Rows marked with '<--' indicate that the row should not exist because of the stated reason)

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'}

The rows i开发者_如何学Cn this new table are to be repeatedly 'join' to my_table again so as to produce this output. (Rows marked with '<--' indicate that the row should not exist because of the stated reason)

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'}

... so on and so forth. Rows that can still be 'joined' will be joined until they have no more children. Rows that can no longer be joined will remain as is.

---

One problem of your example is, that you have an endless loop there (a,A1,b) -> (b,B3,a) -> (a,A1,b) which is a bit tricky to detect.

But this (and peufeu's link) should get you started:

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

It does not create the "visited_ids" column as you want it though

---

Your post corresponds perfectly to a WITH RECURSIVE query :

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