Агрегация подключенных наборов узлов/ребер

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 summed? Ожидаемый результат показан:

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; 

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