Агрегирование связанных наборов узлов / ребер

Question

У меня есть связанный набор ребер с уникальными узлами. Они связаны с использованием родительского узла. Рассмотрим следующий пример кода и иллюстрации:

CREATE TABLE network (
  node integer PRIMARY KEY,
  parent integer REFERENCES network(node),
  length numeric NOT NULL
);
CREATE INDEX ON network (parent);
INSERT INTO network (node, parent, length) VALUES
  (1, NULL, 1.3),
  (2, 1, 1.2),
  (3, 2, 0.9),
  (4, 3, 1.4),
  (5, 4, 1.6),
  (6, 2, 1.5),
  (7, NULL, 1.0);

Визуально можно выделить две группы ребер. Как идентифицировать две группы с помощью PostgreSQL 9.1, и length суммируется? Ожидаемый результат показан:

 edges_in_group | total_edges | total_length
----------------+-------------+--------------
 {1,2,3,4,5,6}  |           6 |          7.9
 {7}            |           1 |          1.0
(2 rows)

Я даже не знаю с чего начать. Нужна ли пользовательская агрегатная или оконная функция? Могу ли я использовать WITH RECURSIVE итеративно собирать ребра, которые соединяются? Мой пример из реальной жизни - это потоковая сеть из 245 000 ребер. Я ожидаю, что максимальное количество edges_in_group быть менее 200, и пара сотен агрегированных групп (строк).

Answer 1

Рекурсивный запрос - это путь:

with recursive tree as (
  select node, parent, length, node as root_id
  from network
  where parent is null
  union all
  select c.node, c.parent, c.length, p.root_id
  from network c
    join tree p on p.node = c.parent
)
select root_id, array_agg(node) as edges_in_group, sum(length) as total_length
from tree
group by root_id;

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