Сериализация ацикличного направленного графа для сохранения в БД и десереализация с последующим разложением на деревья

[Ivan_32]

В общем задача у меня такая:
Есть направленный ацикличный граф (если точнее дерево, но некоторые элементы в нем могут иметь несколько родителей и не обязательно что эти родители будут на одном и то же уровне вложенности). Сохраняется он в БД в виде таблицы из кортежей edge_id, start_vertex, end_vertex. Собственно структуру таблицы взял отсюда, но предложенный там алгоритм использовать не могу так как там для полноценной работы нужна СУБД с поддержкой рекурсии в запросах, а я тотально ограничен MySQL, в котором никаких таких WITH нет. Во всяком случае в 5.5.

Сделать нужно следующее:
Из этих двух таблиц, которые я достаю в чистом виде, построить набор деревьев. Вернее преобразовать узлы (и поддеревья им принадлежащие) которые имеют несколько родителей в отдельные ветви для этих родителей, т.е. продублировать для каждого родителя.

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

Также будет интересно услышать каким еще методами можно сохранить это дерево (или вернее DAG) в базу, возможно есть и другие методы, которые более удобны для моей задачи?

[Utkin]

Как мне кажется удобней рекурсивных алгоритмов для работы с деревьями ничего еще не придумали. Единственно доказано, что любая хвостовая рекурсия может быть однозначно преобразована в цикл. Попробуйте копать в этом направлении.

[Виталий Желтяков]

Чертовски знакомый вопрос...

Года два назад пытался устроится в какую-то шарашкину контору. Мне задали подобный вопрос - как сохранить и работать с деревом в реляционной таблице.
Я их послал очень далеко со словами "только идиоты будут хранить яйца в коробке с гвоздями".

p.s. Ответа не знаю. Вообще вопрос крайне нелогичен.

[ReportCube]

А как же КЛАДР? Разве это не дерево?

[pu4koff]

Сообщение от Ivan_32

Сделать нужно следующее:
Из этих двух таблиц, которые я достаю в чистом виде, построить набор деревьев. Вернее преобразовать узлы (и поддеревья им принадлежащие) которые имеют несколько родителей в отдельные ветви для этих родителей, т.е. продублировать для каждого родителя.

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

Сообщение от Виталий Желтяков

Мне задали подобный вопрос - как сохранить и работать с деревом в реляционной таблице.
Я их послал очень далеко со словами "только идиоты будут хранить яйца в коробке с гвоздями".

Реляционные базы по сути все есть графы. Что не так с хранением иерархий в базе я не понимаю. Иерархии хранятся не обязательно на основе реляционной модели в таблицах, а вплоть до хранения строк по типу путей к файлам "1/2/1/5".

[Виталий Желтяков]

Реляционные базы по сути все есть графы. Что не так с хранением иерархий в базе я не понимаю. Иерархии хранятся не обязательно на основе реляционной модели в таблицах, а вплоть до хранения строк по типу путей к файлам "1/2/1/5".

Одно дело хранить, а совершенно другое работать с этими данными. Любой запрос будет строится из нескольких подзапросов или объединений.

[Kostia]

Мммм, может я не до конца понял, но как на счет декартова произведения?(самое простое и наглядное решение для MySQL, но не самое эффективное)
Есть таблица меню вида:
id parent title url

Нужно одним запросом получить, хм, набор данных который легко превращается в дерево.

SELECT * FROM `menu` as table1,`menu` as table2 WHERE table1.id = table2.parent OR (table1.parent = 0 AND table2.parent = 0 AND table1.id = table2.id)

Если родителей много, то добавляется еще одна таблица соответствий вида:
id id_menu id_menu_parent

Тогда можно выкрутиться декартовым произведением для 3х таблиц с соответствующими условиями