Я использую 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. NULLto_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
<,/pre>

How can I write this update query?

Note that I'm ultimately more concerned about accumulating accurate length and area totals, and that the path attributes are for debugging. In my real-world case, forwards paths are up to a couple hundred, and I expect reverse paths in the tens of thousands for large and complex catchments.