0

I have a tree traversal method implemented in postgres to traverse a linking structure and return a list of nodes that are linked to the initial value-set.

The function:

if
    exists(
        select child_link_id
        from links
        where parent_link_id = any(source_link_ids)
    )
then
    return query 
    select child_link_id
    from links
    where parent_link_id = any(source_link_ids)
    union all select tree_traversal.child_link_id
    from public.tree_traversal(array(
        select distinct child_link_id
        from links 
        where parent_link_id = ANY(source_link_ids)
    )) as tree_traversal;
else
    return query 
    select child_link_id
    from links
    where parent_link_id = any(source_link_ids)
end if;

It's a pretty basic traversal method that provides a list of child_link_ids as the result set. Here's an example with data to illustrate.

child_link_id parent_link_id
1 2
2 3
6 7
7 8 
tree_traversal([1]) -> rows (2, 3, 4)
tree_traversal([6]) -> rows (7, 8, 9)
tree_traversal([1,6]) -> rows (2, 3, 4, 7, 8, 9)

I'd like to be able to preserve the relationship between initial value and subsequent links though and am struggling to find a good method for this. The idea would be that (for the above dataset), this is the return set:

tree_traversal([1]) ->
initial value | child_link_id
1, 2
1, 3
1, 4

tree_traversal([1,6]) ->
initial value | child_link_id
1, 2
1, 3
1, 4
6, 7
6, 8
6, 9

In the case of their being 1 initial value, it's an easy addition, but in the case of multiple initial values I'm struggling to see if that is possible.

Mcscrag
  • 55
  • 6
  • You can use a closure table, as explained [here](https://stackoverflow.com/a/38701519/5962802) - it allows you to get all descendants of a node no matter how deep in the hierarchy with a single SELECT. – IVO GELOV Aug 13 '21 at 16:48
  • Interesting solution, but to me it seems like on larger datasets (say millions of rows in the talbe), it would be very ill preformant? – Mcscrag Aug 13 '21 at 17:39
  • @IVOGELOV Looking into closure tables more it doesn't seem that this answers the question asked. A closure table is just another way to represent relationships in tree like data, but not how to traverse the tree with multiple start points and retain the initial association of start to finish. – Mcscrag Aug 13 '21 at 18:20
  • Closure table contains all possible pairs between all ascendants and descendants. So if you take a given ascendant - you can find all its descendants. And for any given descendant - you can find all its ascendants. You can limit the depth of search by using the column `depth` which depicts the number of edges between the given 2 nodes. – IVO GELOV Aug 15 '21 at 08:37

0 Answers0