How to traverse a hierarchical tree-structure structure backwards using recursive queries

Question

I'm using PostgreSQL 9.1 to query hierarchical tree-structured data, consisting of edges (or elements) with connections to nodes. The data are actually for stream networks, but I've abstracted the problem to simple data types. Consider the example `tree` table. Each edge has length and area attributes, which are used to determine some useful metrics from the network. ``` CREATE TEMP TABLE tree ( edge text PRIMARY KEY, from_node integer UNIQUE NOT NULL, -- can also act as PK to_node integer REFERENCES tree (from_node), mode character varying(5), -- redundant, but illustrative length numeric NOT NULL, area numeric NOT NULL, fwd_path text[], -- optional ordered sequence, useful for debugging fwd_search_depth integer, fwd_length numeric, rev_path text[], -- optional unordered set, useful for debugging rev_search_depth integer, rev_length numeric, rev_area numeric ); CREATE INDEX ON tree (to_node); INSERT INTO tree(edge, from_node, to_node, mode, length, area) VALUES ('A', 1, 4, 'start', 1…

Accepted Answer

UPDATE 2: I rewrote the original recursive query so that all accumulation/aggregation is done outside the recursive part. It should perform better than the previous version of this answer. This is very much alike the answer from @a_horse_with_no_name for a similar question.

```
  WITH 
    RECURSIVE search_graph(edge, from_node, to_node, length, area, start_node) AS
    (
        SELECT edge, from_node, to_node, length, area, from_node AS "start_node"
        FROM tree
        UNION ALL
        SELECT o.edge, o.from_node, o.to_node, o.length, o.area, p.start_node
        FROM tree o
    JOIN search_graph p ON p.from_node = o.to_node
    )
    SELECT array_agg(edge) AS "edges"
       -- ,array_agg(from_node) AS "nodes"
          ,count(edge) AS "edge_count"
          ,sum(length) AS "length_sum"
          ,sum(area) AS "area_sum"
    FROM search_graph
    GROUP BY start_node
    ORDER BY start_node
;
```

Results are as expected:

```
 start_node | edges       | edge_count | length_sum |  area_sum
------------+-------------+------------+------------+------------
  1         | {A}         |          1 |        1.1 |       0.9
  2         | {B}         |          1 |        1.2 |       1.3
  3         | {C}         |          1 |        1.8 |       2.4
  4         | {D,B,A}     |          3 |        3.5 |       3.5
  5         | {E,D,C,B,A} |          5 |        6.4 |       6.8
```

How to traverse a hierarchical tree-structure structure backwards using recursive queries

Solution

Problem

Related problems