Страницы

Поиск по вопросам

среда, 21 ноября 2018 г.

Рекурсивные запросы, списки смежности

есть таблица хранящая вершины в виде списков смежностей
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 мы получаем именно изначального родителя.

Комментариев нет:

Отправить комментарий