Я довольно на страничках своего сайта рассказываю начинающим программистам, как ПРАВИЛЬНО нормализовать различные данные в реляционную форму и как хранить в реляционной структуре самые различные (встречающиеся на практике) обьекты. Пример такого моего рассказа - Cекционирование графики при SQL-хранении. И я всегда стараюсь из каждого своего реального проекта описать на сайте хотя бы одну SQL-процедурку, хотя бы десяток строчек кода.

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

Но в контексте этой заметки термин "маршрутная топология" я буду применять как описание маршрутов движения транспорта по улицам, поездов по ЖД-сети, автокара по складу и подобным машрутам на плоскости. Как вы понимаете, на скрине слева могли бы быть указаны не только названия железнодорожных станций, но и названия улиц/перекрестков или улиц/перекрестков склада. Маршруты движения по трехмерному пространству в принципе строятся подобным образом, однако это слишком абстрактная задача и может встречаться только в системах управления воздушным движением и сложных многоуровневых складов, в то время как оптимальная прокладка маршрутов по "улицам" на плоскости - это одна из самых распространенных задач в программировании.

Собственно алгоритмы оптимальных маршрутов я в этой кратенькой заметке описывать не стану, я остановлюсь лишь на одном небольшом аспекте этой проблемы - ХРАНЕНИИ данных о сетевой топологии в реляционной СУБД MS SQL и ОТБОРАМ в базе сетевой топологии с помощью COMMON TABLE EXPRESSION (CTE).

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

• Куровская<->Люберцы 1,
• Куровская<->Ильинский погост,
• Куровская<->Кривандино,
• Куровская<->Орехово-Зуево.

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

При такой архитектуре вся Московская ЖД (из 10-ти областей) описывается в моей базе в 771 запись, состоящую из отдельных 72-х сегментов сети, соединенных узлами/перекрестками. Если бы передо мною стояла такая задача - я мог бы загрузить в базу и все улицы Москвы, например. Эта база была бы вероятно побольше.

Между Люберцами и Куровской есть промежуточные станции (или номера домов на некоторой конкретной улице). Поэтому записи в базе об этом сегменте сети выглядят вот так:

Как вы видите, каждый отдельный сегмент сетевой топологии я описываю в виде последовательности записей, где первая запись начинается в поле PrevID значением NULL (что означает что в этом месте есть узел/перекресток) и каждый сегмент заканчивается в поле NextID значением NULL - то есть сегмент сети завершился перекрестком.

Если вы поняли, как описать сеть в реляционной структуре, то вы можете легко понять как в нижелеследующем скрине я получил все начальные точки сетевой топололии Московкой ЖД.

А вот так в базе описана узловая станция Куровская, которая изображена на титульном рисунке выше. Избавиться от направления начальная->конечная точка сетевого сегмента просто, для этого достаточно в отборах указать условие PrevID is NULL or NextID is NULL.

Дочитав до этого места, вы достаточно подготовлены, чтобы понять изюминку - рекурсивный запрос CTE, которым можно вытащить все промежуточные станции от начальной точки сетевого сегмента до конечной:

   1:  ALTER procedure [dbo].[GetNetSegment]

   2:  @StartNetNode uniqueidentifier

   3:  as

   4:  with rzd_net (PrevID,ID,NextID,Code,Title)

   5:  as

   6:  (

   7:  select PrevID,ID,NextID,Code,Title from Net where ID=@StartNetNode

   8:  union all

   9:  select X.PrevID,X.ID,X.NextID,X.Code,X.Title from Net as X 

  10:  join rzd_net on rzd_net.NextID=X.ID

  11:  )

  12:  select * from rzd_net

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

И вот результат рекурсивных SQL-запросов этой процедурой к узлу, изображенному на титульном рисунке:

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

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

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

Если вас интересуют другие специфические технологии микрософтовского SQL-сервера, то вы можете почитать еще несколько моих заметок Реализация таймаута на динамически создаваемых SQL JOB, вызывающих SQL CLR сборку, Как парсить XML SOAP в MS SQL.

Если вас интересуют структуры данных РЖД и работа с расписанием Железной Дороги то вы можете почитать мой топик Скачка, раззиповка, перекодирование, парсинг и укладка в базу ЖД-расписания из АСУ Экспресс-3.

Comments ( )