Материал: Using_MySql,_MS_SQL_Server_and_Oracle(1)

Пример 47: формирование и анализ связанных структур

120-- Добавляем связь в текущий путь

121INSERT INTO `current_path`

133-- Продолжаем рекурсивно искать следующие связи

134CALL FIND_PATH (start_node, finish_node);

135

136-- Удаляем последнюю связь из текущего пути

137SET @max_cp_id = (SELECT MAX(`cp_id`)

139DELETE FROM `current_path`

140WHERE `cp_id` = @max_cp_id;

141END IF;

142END LOOP nodes_loop;

143CLOSE nodes_cursor;

144END;

145$$

146DELIMITER ;

Проверим, как работают полученные решения, выполнив такой код.

1-- Для первого варианта решения:

2CALL FIND_PATH({начальная_точка}, {конечная_точка});

3

4-- Для второго варианта решения:

5TRUNCATE TABLE `current_path`;

6TRUNCATE TABLE `final_paths`;

7CALL FIND_PATH({начальная_точка}, {конечная_точка});

8SELECT * FROM `final_paths`;

На представленном в начале данного примера наборе данных для поиска пути из города 1 в город 6 оба решения возвращают одинаковые (хоть и по-разному представленные) результаты.

Результат первого варианта решения:

Результат второго варианта решения:

Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 500/545

Пример 47: формирование и анализ связанных структур

Но если в таблицу connections поместить следующие данные

и поискать путь между городами 1 и 5, результаты будут разными. Результат первого варианта решения:

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

На этом решение для MySQL завершено.

Переходим к MS SQL Server и реализуем один-в-один решение, представленное выше для MySQL.

Алгоритм первого варианта решения:

•удаляется (если существует) и создаётся временная таблица для хранения найденных путей (строки 7-19);

•в созданную таблицу переносятся все данные из таблицы connections с учётом двунаправленности некоторых связей (строки 23-42; аналогичный подзапрос, учитывающий двунаправленные связи, используется в строках 69-81 — фактически, он представляет собой ничто иное, как тело представления из решения{492} задачи 7.1.2.a{491});

•выполняется цикл поиска производных маршрутов (строки 46-93), в котором: o условием выхода является отсутствие новых маршрутов (переменная MS SQL Server @@ROWCOUNT содержит количество записей, затронутых

последней операцией модификации данных);

oидея поиска новых маршрутов строится на том, чтобы к уже найденным маршрутам добавлять следующие шаги (конечная точка найденного маршрута совпадает с отправной точкой связи между городами, что проверяется в условии объединения в строке 82; условие в строках 83-84 исключает порождение циклических маршрутов; условие в строках 89-90 исключает бесконечное повторное дублирующихся маршрутов между двумя любыми городами).

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

Обратите внимание на то, как формируется и анализируется маршрут, раз-

мещаемый в поле cn_route таблицы connections_temp: в MS SQL Server нет прямого аналога функции MySQL FIND_IN_SET, а при поиске вхождения подстроки

Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 501/545

Пример 47: формирование и анализ связанных структур

в строку есть шанс, например, «найти» число 12 в числе 123 и т.д.

Потому каждое значение идентификатора берётся в квадратные скобки (маршрут примет вид наподобие «[1][7][3][6]»), и поиск тоже производится с предварительным заключением искомого идентификатора в квадратные скобки, что гарантирует отсутствие ложных срабатываний.

4AS

5DECLARE @rows_inserted INT = 0;

6

7-- Создание временной таблицы для хранения маршрутов:

8IF OBJECT_ID('tempdb.dbo.#connections_temp', 'U') IS NOT NULL

9DROP TABLE #connections_temp;

10

11CREATE TABLE #connections_temp

12(

13[cn_from] INT,

14[cn_to] INT,

15[cn_cost] DOUBLE PRECISION,

16[cn_bidir] CHAR(1),

17[cn_steps] SMALLINT,

18[cn_route] VARCHAR(1000)

19);

20

21-- Первичное наполнение временной таблицы

22-- существующими маршрутами:

23INSERT INTO #connections_temp

24SELECT [cn_from],

25[cn_to],

26[cn_cost],

27[cn_bidir],

281,

29CONCAT('[', [cn_from], '][', [cn_to], ']')

35UNION

36SELECT [cn_to],

41WHERE [cn_bidir] = 'Y'

42) AS [connections_bidir];

Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 502/545

Пример 47: формирование и анализ связанных структур

MS SQL Решение 7.1.2.b (код процедуры, первый вариант) (продолжение)

43-- Наполнение временной таблицы производными

44-- маршрутами:

45SET @rows_inserted = @@ROWCOUNT;

46WHILE (@rows_inserted > 0)

47BEGIN

48INSERT INTO #connections_temp

49SELECT [connections_next].[cn_from],

68FROM #connections_temp

69JOIN (SELECT [cn_from],

85) AS [connections_next]

86LEFT JOIN #connections_temp

89WHERE #connections_temp.[cn_from] IS NULL

90AND #connections_temp.[cn_to] IS NULL;

91

92SET @rows_inserted = @@ROWCOUNT;

93END; -- WHILE

94

95-- Извлечение маршрутов, соответствующих условию поиска:

96SELECT *

97FROM #connections_temp

98WHERE [cn_from] = @start_node

99AND [cn_to] = @finish_node

100ORDER BY [cn_cost] ASC;

101GO

Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 503/545

Пример 47: формирование и анализ связанных структур

Для второго варианта решения, как и в случае с MySQL, нам понадобятся вспомогательные таблицы для хранения текущего и финальных путей.

MS SQL Решение 7.1.2.b (подготовка ко второму варианту решения)

1-- Создание таблицы для хранения текущего пути:

2IF OBJECT_ID('tempdb.dbo.#current_path', 'U') IS NOT NULL

3DROP TABLE #current_path;

4CREATE TABLE #current_path

5(

6[cp_id] INT NOT NULL IDENTITY (1, 1),

7[cp_from] INT,

8[cp_to] INT,

9[cp_cost] DOUBLE PRECISION,

10[cp_bidir] CHAR(1)

11);

12

13-- Создание таблицы для хранения готовых путей:

14IF OBJECT_ID('tempdb.dbo.#final_paths', 'U') IS NOT NULL

15DROP TABLE #final_paths;

16CREATE TABLE #final_paths

17(

18[fp_id] DOUBLE PRECISION,

19[fp_from] INT,

20[fp_to] INT,

21[fp_cost] DOUBLE PRECISION,

22[fp_bidir] CHAR(1)

23);

Алгоритм второго варианта решения:

•если текущий путь пуст, отправной точкой является точка старта, иначе отправной точкой является точка прибытия последней связи в пути (строки 3445);

•открыть курсор для выбора всех связей между городами (строки 18-32, 47);

•для всех связей повторять цикл, в котором:

oпроверить, совпадает ли отправная точка рассматриваемой связи с текущей отправной точкой (строки 60-61 и, если нет, перейти к следую-

щей итерации цикла;

oпроверить, не присутствует ли уже рассматриваемая связь в пути (строки 63-67) и не приводит ли переход по этой связи к циклическому

маршруту (строки 70-73) — в случае выполнения любого из этих условий перейти к следующей итерации цикла;

oпроверить (строка 76), не совпала ли конечная точка связи с точкой финиша:

если совпала — мы нашли путь, для которого генерируем уникальный идентификатор (строка 78) и переносим в таблицу для хранения найденных путей (строки 79-90), не забыв добавить в конец саму связь, которую мы только что рассматривали (строки

91-101);

если не совпала — путь ещё не найден, а потому: добавляем рассматриваемую связь к текущему пути (строки 106-114), выполняем рекурсивный вызов (строка 117), после которого убираем из текущего пути последнюю связь (строки 120-121).

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

Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 504/545