есть таблица хранящая вершины в виде списков смежностей
Keyword(id INT PRIMARY KEY, value TEXT, parent_id INT REFERENCES Keyword DEFAULT NULL);
нужно посчитать для каждой вершины размер ее поддерева
т.е. для данных
id parent_id
-------------
0 NULL
1 0
2 0
3 1
4 1
будет
id size
-------------
0 5
1 3
2 1
3 1
4 1
по идеи можно пройти по списку смежности, с использованием массива, который хранит путь потом используя операнды @> или <@ посчитать размер поддерева.
Т.е. есть пути 0-1-3, 1-3, 0-8, 0-1-4, 1-4
и для 0 размер будет 5
не пойму как для каждого узла хранить масив определяющий путь без использования функций
Ответ
WITH RECURSIVE q AS (
select id,id as idx
from Keyword
union all
select K.id,q.idx as idx
from Keyword K, q
where K.parent_id=q.id
)
select idx,count(1) from q
group by idx
order by idx
Вот так в postresql выглядят рекурсивные запросы. Внутри RECURSIVE всегда должен быть union. Первая часть union должна выбрать стартовые записи, с которых рекурсия начнется. Например, если бы нам надо было посчитать не количество потомков, а получить всех потомков записи с id=0 мы бы в первой части задали условие where id=0. Вторая часть union это основная рекурсивная часть. Она осуществляет спуск по дереву, выбирая записи из with и при этом поставляя собственные выбранные записи в этот же with, после чего она их там видит и использует уже их id. Что бы правильно посчитать записи нам надо знать изначальный id с которого начала выбираться ветвь, для этого приходится в первом подзапросе выбрать id второй раз и назвать его по другому, потому как просто q.id равен parent.id и у потомка это будет id его непосредственного родителя. А выбрав id под другим именем, не указанным в where мы получаем именно изначального родителя.
Комментариев нет:
Отправить комментарий