Хранение маршрутов (путей графа) в БД

Что-то без поллитры не соображу как хранить маршруты в базе данных. Маршрут -динамическая структура,
имеет переменное число промежуточных пунктов.
Можно конечно закодировать все пункты и представить маршрут как последовательность кодов пунктов
Вижу 2 альтернативы
1)Хранение маршрута каждый узел в своем поле БД
Недостатки - число полей БД фиксировано и можно лишь зарезервировать, например 30 или 50. Длину маршрута хранить в 1 поле. SQL запросы будут страшно длинными, неудобно, нужно каждый раз формировать в программном цикле.
Достоинства. Каждое поле-узел табл.reis можно связать каскадной связью с табл. узлов Node - т.е автоматич поддержка ссылочной целостности.

2)Хранение маршрута в строковом (или веществ)поле.
резервируется мах число узлов например N=100 Каждый узел кодируется тогда 2 символами
Недостатки - сложность раскодирования. Писать программу разбивающая строку на пары соседн символов и преобразующие их в NN узлов. Никакой поддержки ссылочной целостности.
Если тип поля вещественный - доп.проблема БД обрезает ведущие нули скажем цепочка узлов 0 -2 -10
представленная как 000110 обрежется в БД до 110
Единственное достоинство - удобное хранение в длинном текстовом поле (длина 200 и выше)

Добавлено через 38 минут
Отдельной проблемой является хранение сопутствующих маршруту данных. Например расписания и стоимости проезда Их уже так не закодируешь как в 1 случае. Если скажем стоимость проезда между 2 пунктами аддитивно зависит от стоимости проезда по каждому ребру, то можно скажем хранить атрибуты стоимости и
время движения в табл ребер . Но в жизни это не всегда так. Кроме того можно учитывать особенности расписания - например некоторые пункты проезжают без остановки, тогда сумм время будет меньше суммы времен

0

Как насчет таблицы
"Идентификатор маршрута" "Порядковый номер пункта в маршруте" "Идентификатор очередного пункта"?

Или такой
"Идентификатор маршрута" "Порядковый номер отрезка" "Идентификатор начального пункта отрезка" "Идентификатор конечного пункта отрезка"?

0

Да, именно такая структура табл удобна
Id_route -идентификатор маршрута
Nach - идентификатор узла начального пункта текущей ветви
Fin - идентификатор узла конечного пункта текущей ветви
При этом после SQL запроса выборки всех записей по данному маршруту, необходимо восстановить список
т.е найти Nach без входящих узлов и Fin без исходящих узлов и т.д. Правда такое не годится для кольцевых маршрутов, так как непонятно где будет начальная (она же и конечная)остановка
-------------------------------------------------------------
А дальше можно составить подчиненную к табл маршрутов табл расписаний с ключами
Id_route
Tstart - время выезда

0

Ага, только обратите внимание - я не зря указал дополнительное поле для порядкового номера отрезка - в общем случае порядок в котором СУБД будет возвращать отрезки для заданного маршрута не определен (может быть любым).

0

Сообщение от eugrita При этом после SQL запроса выборки всех записей по данному маршруту, необходимо восстановить список т.е найти Nach без входящих узлов и Fin без исходящих узлов и т.д. Правда такое не годится для кольцевых маршрутов, так как непонятно где будет начальная (она же и конечная)остановка

Это-то как раз не проблема: начало/конец можно и отдельными полями хранить.
В общем, имхо, в любом варианте будь готов много дописывать. Задача достаточно сложная, и в SQL красиво не укладывается.

0

А почему бы в таком случае не посмотреть на NoSQL базы данных? В частности на хранилища графов.

0

Вот в результате раздумий остановился на схеме

Какая-то ссылочная целостность (неполная)поддерживается. Так нельзя вставить
в маршрут не вершину графа. Но контроль на существование ребра возложен не на СУБД а на программиста.т.е. ребро между соседними остановками это поля Routes.N между каждыми соседними Routes.nost (nost - порядковы1 N остановки от начала маршрута)
Достоинства- минимум полей

0