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

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

[Everything_is_bad]

для дальнейшей работы в python.

ну да обычно такое и делается через "рекурсивный CTE", решение можно погуглить, там стандартный шаблон, если для тебя это сложно, есть еще часто используемое решение на уровня ЯП, который это обрабатывает, у тебя питон, выгружаешь одним запросом свое "дерево" в плоском виде, а на питоне уже собираешь в нужную структуру.

Comments

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

А если теперь задачку усложнить и представить, что в табличке могут ещё лежать произвольные ориентированные графы? В этом случае системы вложенных словарей будет недостаточно. Можно ли SQL-скриптом получить матрицу смежности или списки связности?

[Everything_is_bad]

Иван Мельников,

В этом случае системы вложенных словарей будет недостаточно.

ну тогда надо использовать соответствующую структуру данных, а не словарь

Answer 2

[alexalexes]

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