Сохранение графа в бд и его обход

Общие вопросы по использованию второй версии фреймворка. Если не знаете как что-то сделать и это про Yii 2, вам сюда.
Ответить
KEFIR4UK
Сообщения: 97
Зарегистрирован: 2014.12.13, 16:24

Сохранение графа в бд и его обход

Сообщение KEFIR4UK »

Здравствуйте. Возникла весьма нетривиальная задача, по крайней мере для меня.
У меня есть совокупость узлов, к примеру: схема

Узел 7 ссылается на узел 1.
Насколько я понимаю это граф. У меня возникла проблема как его лутше сохранять в БД ? И потом обходить его.
Все что нашел ето для каждого узла отдельно хранить в список всех соседних узлов к примеру в json. Или вде таблици в первшой все узлы во второй все переходы.
Есть ли какие то готовые поведения для этого? Все что нарыл это nested set но он не подходит так как листя у меня могут ссылатся на верхнее уровни. вплоть до корня.
Есть какие то идеи по етому поводу?
someweb
Сообщения: 552
Зарегистрирован: 2017.03.09, 10:12

Re: Сохранение графа в бд и его обход

Сообщение someweb »

Чтобы правильно задать вопрос, нужно знать бо́льшую часть ответа. Роберт Шекли.
frid-karatel
Сообщения: 50
Зарегистрирован: 2017.03.06, 15:37
Откуда: Владивосток

Re: Сохранение графа в бд и его обход

Сообщение frid-karatel »

Есть графовые базы, как раз заточенные под хранение таких данных.
nested sets - это другой принцип, и тут не применим.

А вообще, тут и стандартным способом через "id | parent" решить можно.
Только в слове "обходить" кроется разный смысл, например, 7й элемент - он на каком уровне?
А когда получен 7й элемент, получить потом 1й? А потом какой?

Получать через MySQL/PostgreSQL можно рекурсивно, у каждой СУБД свой диалект (SQL команды) для этого.
KEFIR4UK
Сообщения: 97
Зарегистрирован: 2014.12.13, 16:24

Re: Сохранение графа в бд и его обход

Сообщение KEFIR4UK »

frid-karatel писал(а): 2019.02.26, 14:46 Есть графовые базы, как раз заточенные под хранение таких данных.
nested sets - это другой принцип, и тут не применим.

А вообще, тут и стандартным способом через "id | parent" решить можно.
Только в слове "обходить" кроется разный смысл, например, 7й элемент - он на каком уровне?
А когда получен 7й элемент, получить потом 1й? А потом какой?

Получать через MySQL/PostgreSQL можно рекурсивно, у каждой СУБД свой диалект (SQL команды) для этого.
Спасибо за ответ, но parent здесь не подойдет так как узел может ссылатся на узлы которые више него
Аватара пользователя
SiZE
Сообщения: 2813
Зарегистрирован: 2011.09.21, 12:39
Откуда: Perm
Контактная информация:

Re: Сохранение графа в бд и его обход

Сообщение SiZE »

Сделай таблицу вершин id, node_id, node_rel_id
KEFIR4UK
Сообщения: 97
Зарегистрирован: 2014.12.13, 16:24

Re: Сохранение графа в бд и его обход

Сообщение KEFIR4UK »

SiZE писал(а): 2019.02.27, 05:54 Сделай таблицу вершин id, node_id, node_rel_id
Была идея, но потом будет сложность в обходом такого графа. Мне нужно сохранить тот граф, а потом пройтись по всем его точкам.
Нашел redisgraph, попробую его заюзать
frid-karatel
Сообщения: 50
Зарегистрирован: 2017.03.06, 15:37
Откуда: Владивосток

Re: Сохранение графа в бд и его обход

Сообщение frid-karatel »

KEFIR4UK писал(а): 2019.02.26, 19:43Спасибо за ответ, но parent здесь не подойдет так как узел может ссылатся на узлы которые више него
Уровень не имеет значения, это же просто связь одного элемента с другим.
Если же имеется ввиду, что узел привязан к нескольким узлам, то тут можно через отдельную таблицу.
А принцип тот же - id => rel_id
Аватара пользователя
SiZE
Сообщения: 2813
Зарегистрирован: 2011.09.21, 12:39
Откуда: Perm
Контактная информация:

Re: Сохранение графа в бд и его обход

Сообщение SiZE »

KEFIR4UK писал(а): 2019.02.27, 11:09
SiZE писал(а): 2019.02.27, 05:54 Сделай таблицу вершин id, node_id, node_rel_id
Была идея, но потом будет сложность в обходом такого графа. Мне нужно сохранить тот граф, а потом пройтись по всем его точкам.
Нашел redisgraph, попробую его заюзать
А, я думал ты в mysql уперся. Просто так конечно не обойти граф, который не имеет четкого направления.
Ответить