1

the title may not be very clear so let's consider this example (this is not my code, just taking this example to model my request)

I have a table that references itself (like a filesystem)

 id |  parent  | name
----+----------+-------
 1  |   null   |   /
 2  |    1     |  home
 3  |    2     |  user
 4  |    3     |  bin
 5  |    1     |  usr
 6  |    5     |  local

Is it possible to make a sql request so if I choose :

1 I will get a table containing 2,3,4,5,6 (because this is the root) so matching :

  • /home
  • /home/user
  • /home/user/bin
  • /usr
  • etc...

2 I will get a table containing 3,4 so matching :

  • /home/user
  • /home/user/bin

and so on

vdegenne
  • 12,272
  • 14
  • 80
  • 106

1 Answers1

1

Use recursive common table expression. Always starting from the root, use an array of ids to get paths for a given id in the WHERE clause.

For id = 1:

with recursive cte(id, parent, name, ids) as (
    select id, parent, name, array[id]
    from my_table
    where parent is null
union all
    select t.id, t.parent, concat(c.name, t.name, '/'), ids || t.id
    from cte c
    join my_table t on c.id = t.parent
)
select id, name 
from cte
where 1 = any(ids) and id <> 1

 id |         name          
----+-----------------------
  2 | /home/
  5 | /usr/
  6 | /usr/local/
  3 | /home/user/
  4 | /home/user/bin/
(5 rows)

For id = 2:

with recursive cte(id, parent, name, ids) as (
    select id, parent, name, array[id]
    from my_table
    where parent is null
union all
    select t.id, t.parent, concat(c.name, t.name, '/'), ids || t.id
    from cte c
    join my_table t on c.id = t.parent
)
select id, name 
from cte
where 2 = any(ids) and id <> 2

 id |         name          
----+-----------------------
  3 | /home/user/
  4 | /home/user/bin/
(2 rows)

Bidirectional query

The question is really interesting. The above query works well but is inefficient as it parses all tree nodes even when we're asking for a leaf. The more powerful solution is a bidirectional recursive query. The inner query walks from a given node to top, while the outer one goes from the node to bottom.

with recursive outer_query(id, parent, name) as (
    with recursive inner_query(qid, id, parent, name) as (
        select id, id, parent, name
        from my_table
        where id = 2        -- parameter
    union all
        select qid, t.id, t.parent, concat(t.name, '/', q.name)
        from inner_query q
        join my_table t on q.parent = t.id
    )
    select qid, null::int, right(name, -1)
    from inner_query
    where parent is null
union all
    select t.id, t.parent, concat(q.name, '/', t.name)
    from outer_query q
    join my_table t on q.id = t.parent
)
select id, name
from outer_query
where id <> 2;          -- parameter
klin
  • 112,967
  • 15
  • 204
  • 232
  • thanks, but I only want the id's of all the directories and subdirectories from a given directory returned in a new table – vdegenne Jul 02 '17 at 19:34
  • argh.. that is really not what I mean. It's more like I need to use `where id=1` and i will get 2,3,4,5,6 (a table with this 5 values) or if I use `where id=2` I will get 3,4 (a table with this 2 values). do you understand ? – vdegenne Jul 02 '17 at 19:47
  • Ok, you have to use an additional array like in the updated answer. – klin Jul 02 '17 at 21:07
  • Why not just to put `where id = 2` to the topmost query instead of `where parent is null`? @ballangddang – Abelisto Jul 02 '17 at 21:58
  • @Abelisto - because the OP wants to get full paths. Starting from e.g. `id=3` he'll get partial paths. – klin Jul 02 '17 at 22:11
  • @Abelisto you were actually right, writing the condition directly in the recursive query resolved my problem. thanks – vdegenne Sep 11 '17 at 15:07
  • @klin well, editing my question again, you were right, I needed the full paths and the bidirectional query is a real charm to implement. thanks again – vdegenne Sep 13 '17 at 03:09