Как пройти иерархическую древовидную структуру в обратном направлении с помощью рекурсивных запросов
Я использую 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);
Что можно проиллюстрировать ниже, где ребра, представленные AE, связаны с узлами 1-5. NULL to_node (Ø) представляет конечный узел. from_node всегда уникален, поэтому может выступать в роли PK. Если эта сеть протекает как дренажный бассейн, она будет сверху вниз, где начальные ребра притока - это 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 ответ
ОБНОВЛЕНИЕ 2: Я переписал исходный рекурсивный запрос, чтобы все накопление / агрегирование выполнялось за пределами рекурсивной части. Он должен работать лучше, чем предыдущая версия этого ответа. Это очень похоже на ответ @a_horse_with_no_name на аналогичный вопрос.
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
;
Результаты ожидаемые:
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