Как найти сумму глубин поддеревьев с помощью SQL-запроса?

Question

[Ашот Такиев]

Добрый день.

Возникли проблемы с учебной задачей о PostgreSQL на определение размеров поддеревьев.
Есть таблица вида:

Keyword(id INT PRIMARY KEY, value TEXT, parent_id INT REFERENCES Keyword DEFAULT NULL);

И необходимо вывести для каждого узла размер поддерева (учитывая текущий элемент). Например, на данных:

Keyword                   
id  value  parent_id             
-------------------------
0   '1'       NULL      
1   '2'       0         
2   '3'       0         
3   '4'       1         
4   '5'       1

Запрос должен вернуть таблицу:

id  size
-------------
   0   5
   1   3
   2   1
   3   1
   4   1

И у меня возникла проблема с составлением рекурсивного запроса, так как я не понимаю, как можно собрать все данные, необходимые для выполнения задачи.
С помощью такого запроса:

WITH RECURSIVE tree AS (
    SELECT id, parent_id, array[id] AS path, 0 AS level FROM Keyword 

    UNION ALL

    SELECT Child.id, Parent.id, array_append(path, Child.id) AS parent_id, Parent.level + 1 AS level
    FROM Keyword Child JOIN tree Parent ON Child.parent_id = Parent.id
)
SELECT * FROM tree

Я получаю все пути, начиная от корня, до узла с идентификатором id на уровне level.

Наведите на мысль, пожалуйста.

Answer 1

[Ашот Такиев]

В итоге получился такой рекурсивный запрос, который выводит сумму глубин поддеревьев для каждого узла дерева.
На каждом проходе мы строим таблицу, содержащую id узла и путь от от родителя. После чего для каждой вершины считаем, какое количество путей, содержит id вершины в качестве родителя.

WITH RECURSIVE tree_depth as (
  SELECT id, array[id] AS parents, 0 AS level
  FROM Keyword

  UNION ALL

  SELECT C.id, P.parents || C.id, P.level + 1 as level FROM Keyword C
  JOIN tree_depth P ON P.id = C.parent_id
)
Select parents[1], COUNT(*) from tree_depth group by parents[1] order by parents[1];

Answer 2

[sim3x]

Пиши процедуру или храни глубину рядом з записью

Comments

[Ашот Такиев]

А как глубина может помочь? Для каждого id подсчитать сумму для всех дочерних узлов?

[sim3x]

Ашот Такиев: у тебя задача вообще странно поставлена
Стандартно, необходимо узнать на каком уровне от корня находится елемент. У тебя же нужно получить сумму глубин поддеревьев.

Потому тебе стоит уточни задание