Как деревья из иерархического справочника сохранить в структуры вложенных словарей?

Question

[Иван Мельников]

В табличке лежит след. дерево (пока что только дерево – не произвольный граф):

source_id	target_id
10	15
10	20
15	30
15	35
35	40
40	45

with tree(source_id, target_id) as (
values (10, 15), (10, 20), (15, 30), (15, 35), (35, 40), (40, 45))
select * from tree

На выходе нужно полчить что-то вроде

{10: {15: {30: None, 35: {40: {45: None}}}, 20: None}}

для дальнейшей работы в python.
Можно ли это сделать средствами SQL? Хотелось бы вытащить все деревья из таблички одним запросом. Может как-то с помощью рекурсивного CTE?

Answer 1

[alexalexes]

Также как если вы бы решали задачу на любом процедурном языке, имея в распоряжении только массивы или списки.
SQL вам просто дает удобный интерфейс для извлечения из хранилища смежных узлов или хорд, но алгоритмы обхода графа вы уже сами пишите процедурно.
CTE вам поможет, если обход предельно простой и залезет по объему памяти или времени выполнения.
Если нужен какой-то специфичный обход, то лучше это делать процедурно.
Если хотите писать не отходя от Posgres, то вам дорога в хранимые функции и процедуры.