Comments 7
Из текста осталось неясно:
1. Для чего нарезали ребра графа на половинки?
2. Чем не подошло типичное для такого сорта задач решение на рекурсивных CTE?
Я бы эту задачу решал как-то так: www.db-fiddle.com/f/urNknBbgKFJ6x8B5aJJC7p/4
Вроде проще получается.
1. Для чего нарезали ребра графа на половинки?
2. Чем не подошло типичное для такого сорта задач решение на рекурсивных CTE?
Я бы эту задачу решал как-то так: www.db-fiddle.com/f/urNknBbgKFJ6x8B5aJJC7p/4
Вроде проще получается.
Данная статья лишь этюд, описывающий один из методов реализации графа с использованием PL/pgSQL. Конечно, что метод хранения можно оптимизировать, но и используемый вполне удовлетворяет требованиям по простоте.
Спасибо за дополнения, они очень помогут тем, что будет искать методы реализации графов в PostgreSQL.
Спасибо за дополнения, они очень помогут тем, что будет искать методы реализации графов в PostgreSQL.
А что делать, если постановка задачи измениться и ребрам будут присвоены веса?
Получится найти оптимальный путь в графе используя CTE?
Получится найти оптимальный путь в графе используя CTE?
Если мы все еще говорим об оргструктуре, то это какая-то немыслимая для меня постановка. Можете привести пример из жизни, где такое может пригодиться?
Если же мы говорим о поиске кратчайшего пути в абстрактном (т.е. до приземления в некоторой предметной области) графе, то да, можно. Рекурсивный запрос — это обычный поиск вширь по графу, а уж что делать с найденными путями (какие характеристики путей собирать, что и в какой момент отбросить, как отсортировать и т.д.), зависит от конкретной задачи.
И хотя можно, не думаю, что стоит. Если вы хотите решать графовые задачи непременно в РСУБД общего назначения, то это значит, что у вас какая-то очень специфическая задача. Ну вот, например, в оргструктурах не бывает циклов, а это значит, не надо заморачиваться обнаружением этих самых циклов. А если соблюдается принцип единоначалия, то еще и путь между любой парой вершин единственен, а к его поиску можно применить существенные оптимизации.
Если же мы говорим о поиске кратчайшего пути в абстрактном (т.е. до приземления в некоторой предметной области) графе, то да, можно. Рекурсивный запрос — это обычный поиск вширь по графу, а уж что делать с найденными путями (какие характеристики путей собирать, что и в какой момент отбросить, как отсортировать и т.д.), зависит от конкретной задачи.
И хотя можно, не думаю, что стоит. Если вы хотите решать графовые задачи непременно в РСУБД общего назначения, то это значит, что у вас какая-то очень специфическая задача. Ну вот, например, в оргструктурах не бывает циклов, а это значит, не надо заморачиваться обнаружением этих самых циклов. А если соблюдается принцип единоначалия, то еще и путь между любой парой вершин единственен, а к его поиску можно применить существенные оптимизации.
Орг.структура это лишь пример из жизни для которого потребовался граф.В данном случае это ведь только этюд по реализации одного конкретного алгоритма — этюд, набросок.
Когда возникла необходимость я долго гуглил, никаких намеков на pgSQL не встретил, может кому пригодится.
А уж конкретную реализацию под конкретную предметную область каждый разработчик сам пусть выбирает и доводит до продакшн.
Примерно так.
Но в любом случае — спасибо за пример рекурсивного запроса.
Когда возникла необходимость я долго гуглил, никаких намеков на pgSQL не встретил, может кому пригодится.
А уж конкретную реализацию под конкретную предметную область каждый разработчик сам пусть выбирает и доводит до продакшн.
Примерно так.
Но в любом случае — спасибо за пример рекурсивного запроса.
Одной из удобных оптимизаций — это для каждого узла также хранить ссылку на корневой (top) уровень.
Sign up to leave a comment.
Этюд по реализации ориентированного графа с единичными ребрами, используя PL/pgSQL