Страницы

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

понедельник, 23 декабря 2019 г.

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

#sql #postgresql


есть таблица хранящая  вершины  в виде списков смежностей

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 

не пойму как для каждого узла хранить масив определяющий путь без использования функций 
    


Ответы

Ответ 1



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 мы получаем именно изначального родителя.

Ответ 2



Как я понимаю вы рекурсию собираетесь от корня вести, попробуйте наоборот. От листьев к корню: SQL Fiddle PostgreSQL 9.3 Schema Setup: CREATE TABLE tree ("id" int, "parent_id" int) ; INSERT INTO tree ("id", "parent_id") VALUES (0, NULL), (1, 0), (2, 0), (3, 1), (4, 1) ; Query 1: WITH RECURSIVE go_up(id, parent_id) as ( select id, parent_id from tree union all select tree.id, tree.parent_id from go_up join tree on tree.id=go_up.parent_id ) select id, count(*) from go_up group by id order by id Results: | id | count | |----|-------| | 0 | 5 | | 1 | 3 | | 2 | 1 | | 3 | 1 | | 4 | 1 |

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

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