Ich verwende PostgreSQL 9.1, um hierarchisch strukturierte Daten abzufragen, die aus Kanten (oder Elementen) mit Verbindungen zu Knoten bestehen. Die Daten sind eigentlich für Stream-Netzwerke, aber ich habe das Problem auf einfache Datentypen abstrahiert. Betrachten Sie das Beispieltree Tabelle. Jede Kante verfügt über Längen- und Bereichsattribute, anhand derer einige nützliche Metriken aus dem Netzwerk ermittelt werden.

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);

Was unten dargestellt werden kann, wobei die durch A-E dargestellten Kanten mit den Knoten 1-5 verbunden sind. Das NULLto_node (Ø) steht für den Endknoten. Dasfrom_node ist immer eindeutig und kann daher als PK fungieren. Wenn dieses Netzwerk wie ein @ flieDrainage Becken, es wäre von oben nach unten, wo die anfänglichen Nebenkanten A, B, C sind und die abschließende Abflusskante E ist.

DasDokumentation fürWITH bietet ein schönes Beispiel für die Verwendung von Suchdiagrammen in rekursiven Abfragen. Um die "Vorwärts" -Informationen zu erhalten, beginnt die Abfrage am Ende und funktioniert rückwärts:

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

Das oben Gesagte ist sinnvoll und eignet sich gut für große Netzwerke. Zum Beispiel kann ich edge @ sehB ist 3 Kanten vom Ende entfernt und der Vorwärtspfad ist{B,D,E} mit einer Gesamtlänge von 3,5 von der Spitze bis zum Ende.

Ich kann jedoch keine gute Methode zum Erstellen einer umgekehrten Abfrage finden. Das heißt, von jeder Kante aus, was sind die akkumulierten "stromaufwärtigen" Kanten, Längen und Flächen. @ VerwendWITH RECURSIVE, das beste was ich habe ist:

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

Ich möchte Aggregate in den zweiten Term der rekursiven Abfrage einbauen, da jede Downstream-Kante mit einer oder mehreren Upstream-Kanten verbunden ist, aberaggregate sind bei rekursiven Abfragen nicht zulässig. Ich bin mir auch bewusst, dass der Join schlampig ist, da daswith recursive result hat mehrere Join-Bedingungen füredge.

Das erwartete Ergebnis für die Rückwärts- / Rückwärtsabfrage ist:

 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.