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

#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 |