Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: 1 2 3 [Все]   Вниз
  Печать  
Автор Тема: Помогите собрать схему БД для расписания электричек.  (Прочитано 54292 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« : 12-08-2010 11:41 » 

Здравствуйте! Просьба помочь в составлении схемы БД для рассписания электричек.
Помощь нужна в правильной организации таблиц маршрутов и расстояний.
Расстояния нужны для информации пользователей системы (Например, человек подошел к системе, ввел заданный пункт, система ему вывела на экран все маршруты на сегодня до этого пункта + расстояние до него), а также от расстояния зависит стоимость проезда, и хочется сделать так, чтобы система не зависела от конкретного пункта отправления (Например, если система будет находиться в Минске, то можно сохранять расстояние от Минска до пунктов движения - это плохой вариант). Теперь давайте поподробнее.
У нас есть следующая схема движения электричек

в данном случае минимизированная схема - для простоты. Цифры - это расстояние между пунктами.
Составленная мною схема БД для маршрутов выглядит так:

т.е. маршруты будут вводиться руками, промежуточные станции, которые включаются в этот маршрут, тоже, а вот расстояние между станцией отправления и станцией куда следует пассажир должно каким-то образом подсчитываться автоматически (Вот я у Вас и прошу помочь разобраться каким таким образом?). Навреное нужно добавить еще одну таблицу с расстояниями между двумя соседними пунктами, но я не могу понять как это организовать, поэтому спрашиваю у Вас. (Возможно нужно даже 2 таблицы добавить, а потом воспользоваться декартовым произведением или чем-нибудь в этом роде). Принимаются все варианты, даже очень сложные.
Если что-то непонятное написал уточняйте... Заранее спасибо.
Записан
lapulya
Молодой специалист

ru
Offline Offline

« Ответ #1 : 12-08-2010 11:56 » 

Первые 2 секунды просмотра выявили, что таблица "Станции" имеет внешний ключ на таблицу "Маршруты", что не верно, должно быть наоборот.


Для вычисления расстояний в таблицы "станции" добавь:
1. добавь поле "направление" (название линии) причем линия это любая ветка из Минска (т.е. противоположные красные ветки от Минска это разные направления)
2. поле "расстояние" и заноси туда расстояние от этой станции до Минска (т.е. для Олехновичи это будет 47).

Тогда расстояние между ЛЮБЫМИ станциями будет мериться так:
ЕСЛИ начальная и конечная станции маршрута лежат на разных ветках, то просто складываем значения поля "расстояние" из таблицы "станции" для начала и конца маршрута
ЕСЛИ же начальная и конечная станции маршрута лежат на одной и той же ветке, то берем модуль разности значений поля "расстояние" из таблицы "станции" для начала и конца маршрута
Записан

С уважением Lapulya
lapulya
Молодой специалист

ru
Offline Offline

« Ответ #2 : 12-08-2010 12:12 » 

Ой, сорри не прочитал, что такой вариант (храним расстояния от Минска) не катит, но все равно станция не должна содержать внешних ключей на маршрут.

Хотя... боюсь что уж совсем общий вариант сделать не получится... или от просто будет хардкорным. Т.е. можно пронумеровать станции в разрезе каждой ветки и потом высчитывать путь. Или для каждой станции хранить предшественника и последователя и по ним выстраивать маршрут и высчитывать расстояний.

Подробней описать сейчас времени нет. Вечером может подробней распишу.
« Последнее редактирование: 12-08-2010 12:17 от lapulya » Записан

С уважением Lapulya
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 12-08-2010 12:41 » 

Нужно хранить несколько вещей.

1) Взвешенный граф дорожной сети. Это будет одна таблица - станции. Другая таблица - железная дорога между станциями.

Станция
Молодечно
Олехновичи
Радошковичи

Станция 1Станция 2Расстояние
МолодечноОлехновичи30
ОлехновичиРадошковичи13

Это базовая структура информации. На неё накладываются маршруты.

2) Маршрут представляет собой либо указание начальной и конечной остановки (тогда поиск промежуточных станций идёт вручную), либо полный перечень станций в порядке их прохода.

Если маршрут задаётся переменным числом станций, то опять две таблицы:
Маршрут
Электричка 1

МаршрутПорядковый пункт маршрутаСтанция
Электричка 11Молодечно
Электричка 12Олехновичи
Электричка 13Радошковичи
Электричка 14Олехновичи
Электричка 15Молодечно
Пример кольцевого маршрута.

Вычисление расстояния поездки по таблице маршрута и расстояний делается не очень сложным запросом.

3) Расписание лучше представить отдельной подсистемой данных и увязать её с маршрутами через вспомогательные таблицы.
« Последнее редактирование: 12-08-2010 12:47 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #4 : 12-08-2010 15:17 » 

Dimka, суть понял, только не могу понять для чего таблица Станция в 1?
Записан
Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #5 : 12-08-2010 15:18 » 

lapulya, буду очень признателен, если подробнее опишешь свой вариант.
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #6 : 12-08-2010 15:51 » 

Dimka, а хорошо ли повторять имя станции во всех таблицах, разве не делается так: станциям присвоен уникальный ID, а дальше используются ID станций, а не имена ?
Или так делается только для огромных по объёму баз?
Записан

Kivals
Команда клуба

ca
Offline Offline
Пол: Мужской

WWW
« Ответ #7 : 12-08-2010 15:54 » 

Man1BLR, Алексей1153++, именно для этого и есть таблица Станция - во всех остальных таблицах именно ID, а названия в посте - для наглядности
Записан
Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #8 : 12-08-2010 15:56 » 

Kivals, ха))), только что хотел написать, что наверное Dimka для этого и создал таблицу станции))))
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #9 : 12-08-2010 15:59 » 

Kivals, Man1BLR, ну я так и подумал )) Можно было бы для наглядности и поле ID показать в первой таблице

(да оптимизационный рефлекс сработал Отлично )
Записан

Kivals
Команда клуба

ca
Offline Offline
Пол: Мужской

WWW
« Ответ #10 : 12-08-2010 16:01 » 

Я бы наверное вторую таблицу делал зеркальную:
МолодечноОлехновичи30
ОлехновичиМолодечно30
И в таблице 4 хранил бы ссылки на таблицу 2
Записан
x77
Модератор

ro
Offline Offline
Пол: Мужской
меняю стакан шмали на обратный билет с Марса.


« Ответ #11 : 12-08-2010 16:02 » 

под маршрутом надо понимать две разные вещи:

1) это совокупность станций по пути следования из точки A в точку B по одной ветке, где A и B - конечные станции этой ветки. (т.е. маршрут электрички)
2) совокупность станций из точки A в точку B, где A и B - произвольные станции на схеме (т.е. машрут пассажира).

иными словами, конечный маршрут пассажира может состоять из отрезков маршрутов различных электричек. а задача о прокладке маршрута для пассажира - это задача о поиске наикратчайшего пути на графе. никаким запросом это не решается, это классическая комбинаторика.
Записан

x77
Модератор

ro
Offline Offline
Пол: Мужской
меняю стакан шмали на обратный билет с Марса.


« Ответ #12 : 12-08-2010 16:04 » 

хотя, если "маршруты будут вводиться руками, промежуточные станции, которые включаются в этот маршрут, тоже" - то это, наверное, несущественно. т.е. если пассажир вводит не первую и последнюю станции, а весь маршрут со всеми промежуточными станциями сам, руками.
Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #13 : 12-08-2010 16:06 » 

маршрут можно хранить в виде строки , перечислив ID станций через разделитель. А обработкой пущай программа занимается
Записан

Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #14 : 12-08-2010 16:06 » 

Цитата
это задача о поиске наикратчайшего пути на графе. никаким запросом это не решается, это классическая комбинаторика

Стоп. О поиске наикратчайшего пути на графе никто и не говорил. Задача системы достать из БД имеющиеся актуальные маршруты на данный момент и показать их пользователю, а пользователь уже сам решает какой маршрут он предпочтет. Ага
« Последнее редактирование: 12-08-2010 16:10 от Man1BLR » Записан
Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #15 : 12-08-2010 16:08 » 

Цитата
маршрут можно хранить в виде строки , перечислив ID станций через разделитель. А обработкой пущай программа занимается

Задача построить реляционную БД, а не плоский файл.
« Последнее редактирование: 12-08-2010 16:10 от Man1BLR » Записан
x77
Модератор

ro
Offline Offline
Пол: Мужской
меняю стакан шмали на обратный билет с Марса.


« Ответ #16 : 12-08-2010 16:11 » 

Man1BLR, да ну? у вас на упрощённой схеме 17 станций. на боевой, надо думать, поболее. если пассажир едет по одной ветке - нет вопросов, он просто выбирает ветку. а если ему надо попасть из Руденска в Борисов, например? у вас в базе такого маршрута нет. или вы собираетесь хранить все возможные маршруты между всеми станциями?

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

если это курсовая - сойдёт. если реальный проект - это не прокатит. слишком неудобно.
Записан

Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #17 : 12-08-2010 16:15 » 

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

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

Получается что да.
« Последнее редактирование: 12-08-2010 16:19 от Man1BLR » Записан
Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #18 : 12-08-2010 16:16 » 

У меня еще один небольшой вопрос по поводу решения Dimka. Получается что в таблице2 Станция1 и Станция2 - это внешние ключи ссылающиеся на таблицу1, так можно?  Здесь была моя ладья...
Записан
x77
Модератор

ro
Offline Offline
Пол: Мужской
меняю стакан шмали на обратный билет с Марса.


« Ответ #19 : 12-08-2010 16:19 » 

не можно, а нужно Улыбаюсь
Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #20 : 12-08-2010 16:23 » 

там как-то вот так будет )

СтанцияIDst (PK)
Молодечно1
Олехновичи2
Радошковичи3

IDst1IDst2Расстояние
1230
2313

Записан

Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #21 : 12-08-2010 17:19 » 

Теоритически, между теорией и практикой нет различий.
Но на практике они есть. (Jan L.A. van de Snepscheut)


Дело в том, что 2 внешних ключа ссылающихся на 1 таблицу не может быть! Для примера возьмем 2 таблицы, которые составил Алексей1153++ выше. Получается, что IDst1 - это FK, который ссылается на столбец IDst, но и IDst2 - это тоже FK, который ссылается на столбец IDst, а такого не может быть, такой связи нигде нет и в MS SQL такой фокус провернуть нельзя.

Не верите, проверьте сами, файл сценария прилагается.

* Пример.sql (1.01 Кб - загружено 777 раз.)
Записан
x77
Модератор

ro
Offline Offline
Пол: Мужской
меняю стакан шмали на обратный билет с Марса.


« Ответ #22 : 12-08-2010 17:28 » 

Цитата
IDst1 - это FK, который ссылается на столбец IDst, но и IDst2 - это тоже FK, который ссылается на столбец IDst, а такого не может быть

почему не может? всю жизнь так и было. какую ошибку M$ выдаёт, дословно?
Записан

Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #23 : 12-08-2010 17:30 » 

Ну если дословно то:

Сообщение 8148, уровень 16, состояние 0, строка 1
Более одного ограничения столбца FOREIGN KEY указано для столбца "Расстояние", таблица "ДорожнаяСеть".


Вот только причем тут столбец "Расстояние".  Здесь была моя ладья...
« Последнее редактирование: 12-08-2010 17:32 от Man1BLR » Записан
x77
Модератор

ro
Offline Offline
Пол: Мужской
меняю стакан шмали на обратный билет с Марса.


« Ответ #24 : 12-08-2010 17:44 » 

да при том, что вы все ключи определяете для него. смотрите синтаксис CREATE TABLE.

первичный ключ: job_id smallint PRIMARY KEY,
внешний ключ: job_id smallint NOT NULL DEFAULT 1 REFERENCES jobs(job_id),

и т.д. у вас просто синтаксис кривой Ага
Записан

Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #25 : 12-08-2010 18:25 » 

Действительно были ошибки - запятые не поставил, просто не думал, что они играют важную роль, такуюже как в С и С++ - ";".

А по поводу синтаксиса, то я считаю, что объявление ограничений PK и FK в таком стиле очень даже привлекательно, хотя бы по 3-м причинам:

  • упращается работа при создании первичного ключа, состаящего из нескольких столбцов (ведь первичный ключ с несколькими столбцами не может быть объявлен как ограничение столбца)
  • ты контролируешь название внешнего или первичного ограничения
  • проще понимать устройство оператора CREATE TABLE

Вот пример создания таблицы:
Код:
-- создание таблицы, которая задает расстояние между пунктами
CREATE TABLE ДорожнаяСеть
(
Станция1 int NOT NULL,
Станция2 int NOT NULL,
Расстояние int NOT NULL,

CONSTRAINT PK_ОтСтанции1ДоСтанции2
PRIMARY KEY (Станция1, Станция2),

CONSTRAINT FK_Станция1
FOREIGN KEY (Станция1)
REFERENCES Станции(КодСтанции),

CONSTRAINT FK_Станция2
FOREIGN KEY (Станция2)
REFERENCES Станции(КодСтанции)
)
GO

Очень даже симпотичный синтаксис. В прочем на вкус и цвет товарища нет.
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #26 : 12-08-2010 18:29 » 

ох, и увлечение ключами. А нужно ли

Код:

CONSTRAINT FK_Станция1
FOREIGN KEY (Станция1)
REFERENCES Станции(КодСтанции),

CONSTRAINT FK_Станция2
FOREIGN KEY (Станция2)
REFERENCES Станции(КодСтанции)

? Вроде нафик

Я не очень часто с базами воюю, но интуиция мне подсказала так ) Или я не прав?
Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #27 : 12-08-2010 18:32 » 

А, всё, понял. Целостность охота блюсти.

Только название таблице больше подойдёт не "ДорожнаяСеть", а "РасстояниеМеждуСтанциями" ))
« Последнее редактирование: 12-08-2010 18:35 от Алексей1153++ » Записан

Kivals
Команда клуба

ca
Offline Offline
Пол: Мужской

WWW
« Ответ #28 : 12-08-2010 18:34 » 

Алексей1153++, вообще-то для целосночти базы - желательно. Если такая связь есть - СУБД не даст удалить станцию из Станции, если на нее есть ссылки по FK в других таблицах. Иначе - останутся неразрешенные ссылки (при наличии FK легче обрабатывать exceptions).
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #29 : 12-08-2010 20:46 » 

Я бы наверное вторую таблицу делал зеркальную:
МолодечноОлехновичи30
ОлехновичиМолодечно30

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #30 : 12-08-2010 22:14 » 

Цитата: Алексей1153++
Можно было бы для наглядности и поле ID показать в первой таблице
Числовые ID в базах называются "фиктивные ключи", обладающие свойствами "первичных". В моих построениях используются настоящие первичные ключи. Затем, что так нагляднее показать концепцию. В реальной базе, конечно же, заводятся "фиктивные ключи".

Цитата: Kivals
Я бы наверное вторую таблицу делал зеркальную
Это избыточно. Достаточно по таблице построить view, который объединяет прямой и зеркальный порядок станций. Если же в таблице хранить все комбинационные варианты - это риск нарушить целостность данных, получив аномалии обновления и удаления.

Цитата: x77
1) это совокупность станций по пути следования из точки A в точку B по одной ветке, где A и B - конечные станции этой ветки. (т.е. маршрут электрички)
2) совокупность станций из точки A в точку B, где A и B - произвольные станции на схеме (т.е. машрут пассажира).

иными словами, конечный маршрут пассажира может состоять из отрезков маршрутов различных электричек. а задача о прокладке маршрута для пассажира - это задача о поиске наикратчайшего пути на графе. никаким запросом это не решается, это классическая комбинаторика.
Справедливо. У меня только пункт 1. Пункт 2 лучше реализовать (включая поиск маршрутов электричек и пересадок) с учётом расписания и затрат времени, а не с учётом расстояний (особенно без обсуждения цены). Если прямой поезд ходит редко, может быть выгоднее с пересадкой на двух непрямых, но более часто ходящих поездах.

Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Kivals
Команда клуба

ca
Offline Offline
Пол: Мужской

WWW
« Ответ #31 : 13-08-2010 02:47 » 

Dale, Dimka, целосность тривиально решается введением тригера, который за этим следит. Но тем не менее в реальности возможна ситуация когда расстояние от А до Б не равно расстоянию от Б до А (одноколейные пути). Хотя на цену билета это по идее не должно влиять.
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #32 : 13-08-2010 05:22 » 

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

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

У меня возникает аналогичная задача при поиске маршрута на графе, только вместо станций и путей у меня узлы коммутации и каналы связи. Если предположить, что упрощенная таблица маршрутов имеет вид RouteTable(P1, P2, Cost), где P1  и P2 - идентификаторы смежных узлов, а Cost - условная "цена" маршрута между ними, то ее легко симметрировать, введя представление:

Код:
SELECT P1, P2, Cost FROM RouteTable
UNION
SELECT P2, P1, Cost FROM RouteTable

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Kivals
Команда клуба

ca
Offline Offline
Пол: Мужской

WWW
« Ответ #33 : 13-08-2010 05:30 » 

Я прекрасно понимаю, что информация будет избыточной, но ИМХО это ускорит работу с таблицей для вычисления "стоимости" всего пути (хотя могу и ошибаться). Что касается триггеров - то абсолютно согласен что нужно учитывать все события, а не только добавление (я и не говорю что это просто). Не знаю как в M$, а в PostgreSQL и Oracle можно узнать какое поле менялось (при on update): в Oracle вообще можно триггер к изменению поля привязывать.
Цитата
Одноколейность в данном случае не является проблемой...
Я как раз имел в виду редкий случай когда одноколейная однонаправленная дорога, т.е. в разных направлениях едем по разному пути - тогда мы переходим к ориентированным графам
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #34 : 13-08-2010 05:39 » 

Многие СУБД поддерживают хранимые представления, которые по эффективности не уступают физическим таблицам (поскольку фактически и хранятся внутри БД в таких же таблицах). Так что остается выбирать вариант, обеспечивающий ту же степень дуракоустойчивости более наглядно и меньшими усилиями разработчиков. К тому же представления видны на традиционных схемах ERD, а триггеры - нет, нужно вникать в код.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #35 : 13-08-2010 05:40 » 

А если:
пусть триггер сравнит ID1 и ID2 и переставит их так, чтоб они были ID1<ID2 (а случай ID1==ID2 - вообще обломать) . Тогда пар не будет
Записан

Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #36 : 13-08-2010 05:47 » 

Пары реально нужны, поскольку мы хотим эффективно находить как путь из P1 в P2, так и путь из P2 в P1. Иначе клиенту, получившему отлуп при поиске маршрута по составному ключу (P1, P2), придется делать еще и попытку поиска по (P2, P1)
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #37 : 13-08-2010 05:49 » 

А может не морочить себе голову избыточным контролем целостности и оставить его на "совесть" ПО редактирования?
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #38 : 13-08-2010 05:54 » 

А может не морочить себе голову избыточным контролем целостности и оставить его на "совесть" ПО редактирования?
а вот я тоже за это ) Поэтому сначала и не понял, зачем два FK были созданы. А вот интересно - как лучше?
Записан

RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #39 : 13-08-2010 06:04 » 

Леш, я не про FK, а про возражения Dale на предложение Kivals держать в таблице перегонов по одной записи для каждого направления (по две записи на перегон).
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #40 : 13-08-2010 06:13 » 

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

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #41 : 13-08-2010 06:46 » 

Dale, "дружественный интерфейс" не будет сбоить, если  будет работать не напрямую с БД, а через прослойку сервера приложений, единого для все дружественных и недружественных интерфейсов.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #42 : 13-08-2010 06:58 » 

То есть удвоением строк в данном случае будет заниматься специально выделенный под эту задачу сервер приложений? IMHO дороговатая цена за то, чтобы избежать простенького представления, которое полностью снимает проблему.

К тому же, возможно, я неправильно интерпретировал фразу:
А может не морочить себе голову избыточным контролем целостности и оставить его на "совесть" ПО редактирования?
Под "ПО редактирования" подразумевается сервер приложений или же клиентский интерфейс?
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #43 : 13-08-2010 07:14 » 

Если речь идёт об ориентированном графе, некоторые рёбра которого двунаправленные, то, конечно, оба направления хранятся в таблице, они понимаются как два однонаправленных ребра. В данном случае такого нет и никогда не будет в будущем (направления описываются маршрутами, а не дорогой, в отличие от сети городских улиц с соответствующими знаками).

Дублирование данных в базе может быть оправдано только соображениями производительности. Таблицы станций и путей между ними - это фактически таблицы только для чтения. Изменения в них вносятся в лучшем случае один раз в несколько лет, и только одним пользователем. Поскольку правильно настроенный view по скорости работы не отличается от таблицы, этот вариант предпочтительнее. Однако из-за "только для чтения" характера данных по большому счёту в данном случае стратегия реализации двунаправленности ребёр не имеет решающего значения и может быть выбрана произвольно.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Kivals
Команда клуба

ca
Offline Offline
Пол: Мужской

WWW
« Ответ #44 : 13-08-2010 08:16 » 

Цитата
поэтому предпочитаю надежные решения, в которых логика обеспечения целостности сосредоточена в едином месте, по возможности как можно ближе к базе данных
Поддерживаю всеми руками - нельзя такое оставлять на откуп клиентских приложений. И со всеми доводами по этому вопросу тоже полностью согласен.
Записан
Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #45 : 13-08-2010 08:25 » 

Цитата: Dale
...поэтому предпочитаю надежные решения, в которых логика обеспечения целостности сосредоточена в едином месте, по возможности как можно ближе к базе данных
Тоже считаю, что должно быть именно так. И варинат с view тоже считаю самым оптимальным.
Записан
x77
Модератор

ro
Offline Offline
Пол: Мужской
меняю стакан шмали на обратный билет с Марса.


« Ответ #46 : 13-08-2010 08:26 » 

Пары реально нужны, поскольку мы хотим эффективно находить как путь из P1 в P2, так и путь из P2 в P1. Иначе клиенту, получившему отлуп при поиске маршрута по составному ключу (P1, P2), придется делать еще и попытку поиска по (P2, P1)

не придётся, так как это разные маршруты. в одном случае считаем расстояния по одному маршруту, в другом случае - по другому.

я вообще, если честно, не понимаю, о чём все эти разговоры: про тригера, вьюхи, зеркальные таблицы...  маршрут А=>B и В=>А - это два разных маршрута, которые задаются руками в некоем конфигураторе. ну или втупую прописываются в базе.

Димка об этом уже сказал, собственно - у нас однонаправленный граф, который двунаправленным никогда не будет. электричка не может проехать полдороги, вернуться, сделать круг, и поехать в Сочи.
Записан

x77
Модератор

ro
Offline Offline
Пол: Мужской
меняю стакан шмали на обратный билет с Марса.


« Ответ #47 : 13-08-2010 08:32 » 

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

а ты молодец, кстати Улыбаюсь не самую тривиальную задачку себе выбрал, интересную, из которой (при желании) вытекает ещё куча задач, и комбинаторику, и на оптимизацию. можно же не просто выдать все маршруты, можно выдать самый быстрый маршрут, самый дешёвый, оптимальный по соотношению время/деньги и т.д.

респект, в общем Ага
Записан

Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #48 : 13-08-2010 08:34 » 

Кстати, маршрут можно задавать и таким образом:

МаршрутЭтапСтанция отправленияСтанция прибытия
Электричка 11МолодечноОлехновичи
Электричка 12ОлехновичиРадошковичи

В физической базе пара станций в совокупности может являться внешним ключом на первичный ключ из такой же пары станций таблицы с расстояниями. В этом случае либо в таблице с расстояниями нужно хранить зеркальные записи, либо в таблицу маршрутов добавить поле - флажок направления. В обоих случаях вычислять зеркальные записи нет необходимости.

Поле "Этап" можно расширить на два поля "Этап в прямом направлении" и "Этап в обратном направлении", если один маршрут предполагает движение поезда в обоих направлениях по одной ветке железной дороги. Хотя это частный случай, так что такая структура данных скорее всего будет ненужным усложнением.
« Последнее редактирование: 13-08-2010 08:37 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #49 : 13-08-2010 08:37 » 

можно же не просто выдать все маршруты, можно выдать самый быстрый маршрут, самый дешёвый, оптимальный по соотношению время/деньги и т.д.

Интересная идея... Обязательно учту Да-да
Записан
Kivals
Команда клуба

ca
Offline Offline
Пол: Мужской

WWW
« Ответ #50 : 13-08-2010 08:59 » 

Кстати, маршрут можно задавать и таким образом...
Я об этом и писал вначале:
...И в таблице 4 хранил бы ссылки на таблицу 2
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #51 : 13-08-2010 09:42 » 

я вообще, если честно, не понимаю, о чём все эти разговоры: про тригера, вьюхи, зеркальные таблицы...  маршрут А=>B и В=>А - это два разных маршрута

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

Другое дело, что конкретный маршрут электрички может использовать данное звено для движения только в одном направлении. а возвращаться другим путем. Но это не запрещает использовать такое звено другому маршруту, поскольку в принципе оно существует.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #52 : 13-08-2010 10:05 » 

То есть удвоением строк в данном случае будет заниматься специально выделенный под эту задачу сервер приложений? IMHO дороговатая цена за то, чтобы избежать простенького представления, которое полностью снимает проблему.

И понижает универсальность. Я о том, что говорится в последних постах: обратный маршрут не обязан 100% совпадать с прямым, равно как и километраж, в случае, если колеи проложены по разным физическим маршрутам. Конечно, можно возразить, что Краснодарском крае и в пригороде Минска такого не бывает, но утверждать, что такого вообще не бывает, я бы не стал.

К тому же, возможно, я неправильно интерпретировал фразу:
А может не морочить себе голову избыточным контролем целостности и оставить его на "совесть" ПО редактирования?
Под "ПО редактирования" подразумевается сервер приложений или же клиентский интерфейс?

Я подразумевал административное ПО, через которое будет выполнятся занесение и изменение данных о перегонах, станциях, маршрутах и т.п. Это в противовес ПО для пользовательского доступа.
« Последнее редактирование: 13-08-2010 10:07 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #53 : 13-08-2010 11:29 » 

И понижает универсальность. Я о том, что говорится в последних постах: обратный маршрут не обязан 100% совпадать с прямым, равно как и километраж, в случае, если колеи проложены по разным физическим маршрутам.

Отнюдь не факт. Между станциями вполне может быть не одно звено пути, а несколько, возможно, даже разной длины. Никто не мешает прокладывать конкретный маршрут в одну сторону по одному звену, а в обратную - по другому. Как раз такой вариант наиболее универсален: если данное звено используется конкретным маршрутом лишь в одном направлении, это вовсе не мешает другому маршруту двигаться по нему же во встречном.

Я подразумевал административное ПО, через которое будет выполнятся занесение и изменение данных о перегонах, станциях, маршрутах и т.п. Это в противовес ПО для пользовательского доступа.

Это, конечно, дело вкуса, но лично я частенько корректирую данные напрямую с консоли сервера. Триггеры, которые предложил Kivals, в данном случае сработают. Вариант с view также сработает, поскольку он динамический. А вот сервер приложений будет не в курсе. Впрочем, это и неудивительно, поскольку серверы приложений в многоуровневых архитектурах обычно предназначаются для других задач.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #54 : 13-08-2010 12:46 » 

Таким образом у нас получается следующая схема для маршрутов и расстояний, если что-то не так или есть какие-то замечания поправляйте. КодРМС в таблице РасстояниеМеждуСтанциями был введен для упращения, возможно нужно было сделать первичным ключом - Станция1, Станция2, но мне кажется, что с ним (КодРМС) будет проще, кстати, хотелось бы узнать ваше мнение.
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #55 : 13-08-2010 13:01 » 

Ранее высказывалось справедливое замечание, что между двумя станциями в принципе может существовать несколько звеньев пути с разной длиной. Поэтому я бы переименовал таблицу РасстояниеМеждуСтанциями в ЗвеноПути (или, возможно, существует более точный железнодорожный термин для обозначения участка рельсового пути между соседними станциями). В этом случае составной ключ (Станция1, Станция2) не является уникальным, и нужно использовать суррогатный уникальный ключ для каждого Звена.

Тогда Маршрут описывается следующими атрибутами: КодМаршрута, НачальнаяСтанция, КонечнаяСтанция, а также связанный список звеньев пути. Для каждого звена Маршрута при необходимости можно добавить длительность стоянки после его прохождения (если 0, на станции не предусмотрена остановка).
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
McZim
Модератор

ru
Offline Offline
Пол: Мужской
Я странный


WWW
« Ответ #56 : 17-08-2010 06:36 » 

Промежуточные точки маршрута (код маршрута) - зачем два ключа на этом поле?
Записан

The CBO without stats is like a morning without coffee. (c) T.Kyte.
Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #57 : 17-08-2010 16:16 » 

Промежуточные точки маршрута (код маршрута) - зачем два ключа на этом поле?
Ну с учетом последнего замечания от Dale, я немного переделал и схема выглядит так:

Думаю теперь понятно, что составной первичный ключ (RouteID, SectionID) нужен, потому что ни RouteID, ни SectionID не обеспичивают по отдельности уникальности + не хочется вводить суррогатный.
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #58 : 17-08-2010 16:42 » 

Man1BLR, по-моему в Routes StartStation и FinishStation - лишние, а вот в RouteDescriptions явно не хватает порядкового номера "секции" маршрута.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Man1BLR
Участник

by
Offline Offline
Пол: Мужской

« Ответ #59 : 17-08-2010 18:10 » 

Вроде как справедливое замечание...
Dimka, хотелось бы уточнить по поводу ответа о создании зеркальной таблицы, в данном случае RailwaySections.
Это избыточно. Достаточно по таблице построить view, который объединяет прямой и зеркальный порядок станций...

Как видно из схемы таблица RouteDescriptions ссылается на таблицу RailwaySections, таким образом в RouteDescriptions присутствует ограничение внешнего ключа, а если мы построим представление, то
  • нужно установить с ним (представлением) связь
  • идентификатор (SectionID) не будет уникальным
Или я просто чего-то не знаю? Здесь была моя ладья...
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #60 : 17-08-2010 20:12 » 

Man1BLR, поскольку в RailwaySection указано, какая станция 1, а какая 2, то либо нужны зеркальные записи для встречных направлений, либо в RouteDescription дополнительное логическое поле, например, BackDirection, true в котором означает, что "по ходу следования" первой станцией является Station2, а второй Station1, иначе - прямой порядок.

Однако теоретически всё это избыточно, если в RouteDescription будет порядковый номер "секции". Ведь известно, что поезд не умеет телепортироваться, поэтому, если в маршруте указаны "1, X, Y", "2, Y, Z" или "1, X, Y", "2, Z, Y" - это не так важно, станции можно увязать в последовательность без разрывов. Этот теоретический случай не будет работать для коротких маршрутов из одной секции и для "хитрых" маршрутов с временными возвратами, кольцами, заездами в тупики и т.п. вещами.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Страниц: 1 2 3 [Все]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines