Как перемещаться иерархическая структура древовидной структуры назад с использованием рекурсивных запросов

Я использую PostgreSQL 9.1 для запроса иерархических древовидных данных, состоящих из ребер (или элементов) с подключениями к узлам. Фактически данные предназначены для сетей потоков, но я отвлек эту проблему на простые типы данных. Рассмотрим пример таблицы tree. Каждый ребро имеет атрибуты длины и площади, которые используются для определения некоторых полезных показателей из сети.

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.1, 0.9),
 ('B', 2, 4, 'start', 1.2, 1.3),
 ('C', 3, 5, 'start', 1.8, 2.4),
 ('D', 4, 5, NULL, 1.2, 1.3),
 ('E', 5, NULL, 'end', 1.1, 0.9);

Что можно проиллюстрировать ниже, где ребра, представленные A-E, связаны с узлами 1-5. NULL to_node (Ø) представляет собой конец node. from_node всегда уникален, поэтому он может действовать как ПК. Если эта сеть протекает подобно дренажному бассейну , это будет сверху вниз, где исходными ребрами притока являются A, B, C и окончание край отвода - E.

Документация для WITH служит хорошим примером того, как использовать поисковые графы в рекурсивных запросах. Итак, чтобы получить информацию "вперед", запрос начинается в конце и работает в обратном направлении:

WITH RECURSIVE search_graph AS (
  -- Begin at ending nodes
  SELECT E.from_node, 1 AS search_depth, E.length
    , ARRAY[E.edge] AS path -- optional
  FROM tree E WHERE E.to_node IS NULL

  UNION ALL
  -- Accumulate each edge, working backwards (upstream)
  SELECT o.from_node, sg.search_depth + 1, sg.length + o.length
    , o.edge|| sg.path -- optional
  FROM tree o, search_graph sg
  WHERE o.to_node = sg.from_node
)
UPDATE tree SET
  fwd_path = sg.path,
  fwd_search_depth = sg.search_depth,
  fwd_length = sg.length
FROM search_graph AS sg WHERE sg.from_node = tree.from_node;

SELECT edge, from_node, to_node, fwd_path, fwd_search_depth, fwd_length
FROM tree ORDER BY edge;

 edge | from_node | to_node | fwd_path | fwd_search_depth | fwd_length
------+-----------+---------+----------+------------------+------------
 A    |         1 |       4 | {A,D,E}  |                3 |        3.4
 B    |         2 |       4 | {B,D,E}  |                3 |        3.5
 C    |         3 |       5 | {C,E}    |                2 |        2.9
 D    |         4 |       5 | {D,E}    |                2 |        2.3
 E    |         5 |         | {E}      |                1 |        1.1

Вышеприведенное имеет смысл и хорошо масштабируется для крупных сетей. Например, я вижу, что край B - это 3 ребра с конца, а передний путь - {B,D,E} с общей длиной 3,5 от конца до конца.

Однако я не могу найти хороший способ создать обратный запрос. То есть, с каждого края, каковы накопленные "верхние" ребра, длины и области. Используя WITH RECURSIVE, лучшее, что у меня есть:

WITH RECURSIVE search_graph AS (
  -- Begin at starting nodes
  SELECT S.from_node, S.to_node, 1 AS search_depth, S.length, S.area
    , ARRAY[S.edge] AS path -- optional
  FROM tree S WHERE from_node IN (
    -- Starting nodes have a from_node without any to_node
    SELECT from_node FROM tree EXCEPT SELECT to_node FROM tree)

  UNION ALL
  -- Accumulate edges, working forwards
  SELECT c.from_node, c.to_node, sg.search_depth + 1, sg.length + c.length, sg.area + c.area
         , c.edge || sg.path -- optional
  FROM tree c, search_graph sg
  WHERE c.from_node = sg.to_node
)
UPDATE tree SET
  rev_path = sg.path,
  rev_search_depth = sg.search_depth,
  rev_length = sg.length,
  rev_area = sg.area
FROM search_graph AS sg WHERE sg.from_node = tree.from_node;

SELECT edge, from_node, to_node, rev_path, rev_search_depth, rev_length, rev_area
FROM tree ORDER BY edge;

 edge | from_node | to_node | rev_path | rev_search_depth | rev_length | rev_area
------+-----------+---------+----------+------------------+------------+----------
 A    |         1 |       4 | {A}      |                1 |        1.1 |      0.9
 B    |         2 |       4 | {B}      |                1 |        1.2 |      1.3
 C    |         3 |       5 | {C}      |                1 |        1.8 |      2.4
 D    |         4 |       5 | {D,A}    |                2 |        2.3 |      2.2
 E    |         5 |         | {E,C}    |                2 |        2.9 |      3.3

Я хотел бы построить агрегаты во второй член рекурсивного запроса, так как каждый нисходящий край соединяется с 1 или несколькими восходящими ребрами, но агрегаты не допускаются с рекурсивными запросами. Кроме того, я знаю, что объединение неаккуратно, поскольку результат WITH RECURSIVE имеет несколько условий соединения для edge.

Ожидаемый результат для обратного/обратного запроса:

 edge | from_node | to_node |  rev_path   | rev_search_depth | rev_length | rev_area
------+-----------+---------+-------------+------------------+------------+----------
 A    |         1 |       4 | {A}         |                1 |        1.1 |      0.9
 B    |         2 |       4 | {B}         |                1 |        1.2 |      1.3
 C    |         3 |       5 | {C}         |                1 |        1.8 |      2.4
 D    |         4 |       5 | {A,B,D}     |                3 |        3.5 |      3.5
 E    |         5 |         | {A,B,C,D,E} |                5 |        6.4 |      6.8

Как я могу написать этот запрос на обновление?

Обратите внимание, что в конечном итоге я больше беспокоюсь о аккумулировании точной длины и итоговых сумм и что атрибуты пути предназначены для отладки. В моем реальном случае, пути вперед до пары сотен, и я ожидаю обратных путей в десятки тысяч для больших и сложных водосборов.

Ответ 1