PostgreSQL ltree find all ancestors of a given label (not path)

Question

I have a table with an ltree path column. In my hierarchy the path to a label is unique, meaning that every label has exactly one parent label. In other words, there are no two ltree paths in the table which would end with the same label.

I have an ltree label, let's say "C".

I can find all descendant rows of this label with the following query:

select * from myTree where path ~ '*.C.*';

This works fine and gives the correct subtree.

Now I need to implement the query to find all ancestor rows of this given label. I mean if there are for example 3 rows in the table with labels "A", "A.B", "A.B.C", I would like to get the rows with paths "A" and "A.B" (probably including "A.B.C" itself, does not matter for now).

If I know the full path of "C" ("A.B.C" in the above example) then the task is easy with the @> operator. However, now I know only "C", and still I would like to achieve the task with a single query. Is there any way to do this?

I haven't found any direct support for this within `ltree`, but you can select the child node with `path ~ '*.C'` & then you can do a self-join to get all ancestors. — pozs, Nov 26 '14 at 11:26
How do you know "C", but not the full path "A.B.C"? Aren't they on the same row of the table? — Kouber Saparev, Nov 26 '14 at 11:34
@KouberSaparev yes they are, but "C" is a kind of global identifier for that row, which I receive as a parameter in this case. — Zoltán Tamási, Nov 26 '14 at 11:40
Then with a subselect you can obtain the path corresponding to the identifier and search by it (as in the answer proposed below). — Kouber Saparev, Nov 26 '14 at 11:47

score 22 · Accepted Answer · answered Nov 26 '14 at 11:46

22

SELECT
  *
FROM
  myTree
WHERE
  path @> (
    SELECT
      path
    FROM
      myTree
    WHERE
      label = 'C'
  );

answered Nov 26 '14 at 11:46

Kouber Saparev

7,637
2
29
26

1

Jesus that was quite simple. It's far too many hours now whilte I'm sitting at the computer :) By the time I managed to implement it with a self-join, but the subquery in this case is much more readable. Thank you. – Zoltán Tamási Nov 26 '14 at 11:57
1

Thanks for good answer! But what if sub-select returns more than one row? It could happen if some node has more than one parent. Then Postgres shows error: "more than one row returned by a subquery used as an expression" Are there a way to handle this? – Johnner Feb 08 '16 at 12:46
How would you define a node with more than one parent at all with the materialized path pattern that ltree uses? – Kouber Saparev Feb 09 '16 at 19:56
2

Definitely possible for a node to have more than one parent in a DAG. In that case @Johnner, it's better to rewrite as a JOIN, not a subquery: SELECT * FROM myTree JOIN myTree AS mt ON myTree.path @> mt.path AND mt.label = 'C'; – Ricardo Villamil Feb 12 '19 at 15:36
In my opinion, the answer by @Kouber Saparev assumes that there is a "label" column in the table. I think the following can be used: select * from myTree where path ~ '*.C'; As per the documentation [here](https://www.postgresql.org/docs/current/ltree.html), `*.foo` matches any label path whose last label is foo. This seems trivial and I am thinking I might be misunderstanding something. Please correct me if I am wrong somewhere. Thank you, – Prabhatika Vij May 10 '22 at 02:32

vyegorov · Answer 2 · 2014-11-26T12:00:04.267

0

Something like this:

WITH r AS
(
    SELECT *, row_number() OVER (ORDER BY path) rn
      FROM myTree
)
SELECT *
  FROM r
 WHERE rn <= (SELECT rn FROM r WHERE path ~ '*.C');

SQL Fiddle

Maybe there's a better way using built-in stuff though.

edited Nov 26 '14 at 12:00

answered Nov 26 '14 at 11:30

vyegorov

21,787
7
59
73

Thank you, this looks quite tricky for my current knowledge, but will give it a try. What I'm afraid of is that (I think) I'm limited to simple query statements because I'm behind an ORM library. – Zoltán Tamási Nov 26 '14 at 11:33

PostgreSQL ltree find all ancestors of a given label (not path)

2 Answers2