Материал: Using_MySql,_MS_SQL_Server_and_Oracle
Пример 47: формирование и анализ связанных структур
MySQL |
Решение 7.1.2.b (код процедуры, второй вариант) (продолжение) |
75 |
|
FROM |
'current_path' |
||
|
WHERE |
'cp_from' = |
cn_from_value |
||
76 |
|
||||
|
AND 'cp_to' = cn_to_value |
||||
77 |
|
||||
THEN |
|
|
|
||
78 |
|
|
|
||
ITERATE nodes_loop; |
|
||||
79 |
|
||||
END IF; |
|
|
|
||
80 |
|
|
|
||
|
|
|
|
||
81 |
— |
Такая связь приводит к циклу, пропускаем |
|||
82 |
|||||
IF EXISTS (SELECT 1 |
|
||||
83 |
|
||||
|
FROM |
'current_path' |
|||
84 |
|
||||
|
WHERE |
'cp_from' = |
cn_to_value |
||
85 |
|
||||
THEN |
|
|
|
||
86 |
|
|
|
||
ITERATE nodes_loop; |
|
||||
87 |
|
||||
END IF; |
|
|
|
||
88 |
|
|
|
||
|
|
|
|
||
89 |
— |
Конечная точка связи совпала с точкой финиша, путь найден |
|||
90 |
|||||
IF |
|
cn_to_value |
= finish_node |
||
91 |
|
||||
THEN |
|
|
|
||
73 |
- Такая связь уже есть в текущем пути, пропускаем |
||||
74 |
IF EXISTS (SELECT 1 |
|
|||
|
|
|
|
||
92 |
SET @rand_value = RAND(); |
|
93 |
||
|
||
94 |
INSERT INTO 'final_paths' |
|
95 |
||
('fp_id', |
||
96 |
||
'fp_from' , |
||
97 |
||
'fp_to', |
||
98 |
||
'fp_cost', |
||
99 |
||
'fp_bidir') |
||
|
100SELECT @rand_value,
101'cp_from',
102'cp_to',
103'cp_cost',
104'cp_bidir'
105FROM 'current_path';
107 |
INSERT INTO 'final_paths' |
|
|
108 |
('fp_id', |
|
|
109 |
'fp_from' , |
|
|
110 |
'fp_to', |
|
|
111 |
'fp_cost', |
|
|
112 |
'fp_bidir') |
|
|
113 |
VALUE S (@ rand_value, |
|
|
114 |
cn_from_value, cn_to_value cn_cos t_value, cn_bidir_value); |
|
|
115 |
ELSE |
|
|
116 |
|
117 |
|
118 |
|
119 |
|
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016-2018 Стр: 530/545
Пример 47: формирование и анализ связанных структур
MySQL I |
Решение 7.1.2.b (код процедуры, второй вариант) (продолжение) |
| |
120-- Добавляем связь в текущий путь
121INSERT INTO 'current_path'
122 |
('cp id', |
|
123 |
'cp from' , |
|
124 |
'cp to', |
|
125 |
'cp |
cost', |
126 |
'cp |
bidir') |
127 |
VALUES (NULL, |
128 |
cn from value |
129 |
cn to value, |
130 |
cn cost value |
131 |
cn_bidir_value ; |
132 |
|
133-- Продолжаем рекурсивно искать следующие связи
134CALL FIND_PATH start_node, finish_nodei;
135
136-- Удаляем последнюю связь из текущего пути
137SET @max cp id = (SELECT MAX('cp id')
138 |
FROM 'current_path'); |
139 |
DELETE FROM 'current_path' |
140 |
WHERE 'cp id' = @max cp id |
141END IF;
142END LOOP nodes loop;
143CLOSE nodes cursor;
144END;
145$$
146DELIMITER ;
Проверим, как работают полученные решения, выполнив такой код.
MySQL |
Решение 7.1.2.b (код для проверки работоспособности) |
1-- Для первого варианта решения:
2CALL FIND_PATH({начальная_точка}, {конечная_точка});
4 -- Для второго варианта решения:
5TRUNCATE TABLE'current_path';
6TRUNCATE TABLE 'final_paths';
CALL FIND_PATH({начальная_точка}, {конечная_точка}); 8 SELECT * FROM 'final paths';
На представленном в начале данного примера наборе данных для поиска пути из города 1 в город 6 оба решения возвращают одинаковые (хоть и по-разному представленные) результаты.
Результат первого варианта решения:
cn_from |
cn_to |
cn_cost |
cn_bidir |
cn_steps |
cn_route |
1 |
6 |
30 |
N |
3 |
1,7,3,6 |
1 |
6 |
85 |
N |
3 |
1,7,2,6 |
Результат второго варианта решения:
fp_id |
fp_from |
fp_to |
fp_cost |
fp_bidir |
0.42358866466543516 |
1 |
7 |
20 |
N |
0.42358866466543516 |
7 |
2 |
15 |
Y |
0.42358866466543516 |
2 |
6 |
50 |
N |
0.34713028031134074 |
1 |
7 |
20 |
N |
0.34713028031134074 |
7 |
3 |
5 |
N |
0.34713028031134074 |
3 |
6 |
5 |
N |
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016-2018 Стр: 531/545
Пример 47: формирование и анализ связанных структур
Но если в таблицу connections поместить следующие данные
cn_from |
cn_to |
cn_cost |
cn_bidir |
1 |
3 |
100 |
N |
1 |
5 |
100 |
N |
3 |
5 |
20 |
N |
5 |
3 |
200 |
N |
и поискать путь между городами 1 и 5, результаты будут разными. Результат первого варианта решения:
cn_from |
|
cn_to |
cn_cost |
cn_bidir |
cn_steps |
cn_route |
||||
1 |
|
5 |
100 |
|
N |
1 |
|
1,5 |
|
|
Результат второго варианта решения: |
|
|
||||||||
|
fp_id |
|
fp_from |
fp_to |
|
fp_cost |
fp_bidir |
|
||
0.6203666074391143 |
1 |
|
3 |
|
100 |
N |
|
|||
0.6203666074391143 |
3 |
|
5 |
|
20 |
N |
|
|||
0.2569376912498266 |
1 |
|
5 |
|
100 |
N |
|
|||
Как и было сказано выше, первый вариант решения не находит альтернативные пути разной длины, в то время как второй вариант справляется с этим.
На этом решение для MySQL завершено.
Переходим к MS SQL Server и реализуем один-в-один решение, представленное выше для MySQL.
Алгоритм первого варианта решения:
•удаляется (если существует) и создаётся временная таблица для хранения найденных путей (строки 7-19);
•в созданную таблицу переносятся все данные из таблицы connections с учётом двунаправленности некоторых связей (строки 23-42; аналогичный подзапрос, учитывающий двунаправленные связи, используется в строках 69-81 — фактически, он представляет собой ничто иное, как тело представления из решения{492} задачи 7.1.2.a{491});
•выполняется цикл поиска производных маршрутов (строки 46-93), в котором:
оусловием выхода является отсутствие новых маршрутов (переменная
MS SQL Server @@ROWCOUNT содержит количество записей, затронутых последней операцией модификации данных);
оидея поиска новых маршрутов строится на том, чтобы к уже найденным маршрутам добавлять следующие шаги (конечная точка найденного маршрута совпадает с отправной точкой связи между городами, что проверяется в условии объединения в строке 82; условие в строках 8384 исключает порождение циклических маршрутов; условие в строках 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 Стр: 532/545
Пример 47: формирование и анализ связанных структур
в строку есть шанс, например, «найти» число 12 в числе 123 и т.д.
Потому каждое значение идентификатора берётся в квадратные скобки (маршрут примет вид наподобие «[1][7][3][6]»), и поиск тоже производится с предварительным заключением искомого идентификатора в квадратные скобки, что гарантирует отсутствие ложных срабатываний.
MS SQL I Решение 7.1.2.b (код процедуры, первый вариант) |
1 |
CREATE PROCEDURE FIND PATH |
2 |
@start node INT, |
3 |
@finish node INT |
4AS
5DECLARE @rows_inserted INT = 0;
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] , ']')
30 |
FROM |
(SELECT [cn from] , |
||
31 |
|
|
[cn to], |
|
32 |
|
|
[cn |
cost], |
33 |
|
|
[cn |
bidir] |
34 |
|
FROM |
[connections] |
|
35UNION
36SELECT [cn to],
37 |
|
[cn from] , |
|
38 |
|
[cn |
cost], |
39 |
|
[cn |
bidir] |
40 |
FROM |
[connections] |
|
41WHERE [cn bidir] = 'Y'
42) AS [connections bidir];
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016-2018 Стр: 533/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],
50 |
[connections next] [cn to], |
|
|
|
51 |
[connections next] [cn cost], |
|
|
|
52 |
[connections next] [cn bidir], |
|
|
|
53 |
[connections next] [cn steps], |
|
|
|
54 |
[connections next] [cn route] |
|
|
|
55 |
FROM (SELECT #connections temp [cn from] AS [cn from] |
|
||
56 |
[connections] [cn to] AS [cn to], |
|
||
57 |
#connections temp [cn cost] + |
|
|
|
58 |
[connections] [cn cost] AS [cn cost], |
|
||
59 |
CASE |
|
|
|
60 |
WHEN |
#connections temp [cn bidir] = 'Y') |
|
|
61 |
AND ([connections] [cn bidir] = |
'Y') |
|
|
62 |
THEN 'Y' |
|
|
|
63 |
ELSE 'N' |
|
|
|
64 |
END AS |
[cn bidir], |
|
|
65 |
#connections temp [cn steps] + 1 |
AS [cn steps] |
|
|
66 |
CONCAT #connections temp [cn route], '[', |
|
||
67 |
|
[connections] [cn to], ']') AS [cn route] |
|
|
68 |
FROM #connections temp |
|
|
|
69 |
JOIN (SELECT [cn from] , |
|
|
|
70 |
[cn to] |
|
|
|
71 |
[cn cost], |
|
|
|
72 |
[cn bidir] |
|
|
|
73 |
FROM |
[connections] |
|
|
74 |
UNION |
|
|
|
75 |
SELECT [cn to] |
|
|
|
76 |
[cn from] , |
|
|
|
77 |
[cn cost], |
|
|
|
78 |
[cn bidir] |
|
|
|
79 |
FROM |
[connections] |
|
|
80 |
WHERE |
[cn bidir] = 'Y' |
|
|
81 |
) AS [connections] |
|
|
|
82 |
ON #connections temp [cn to] = [connections] [cn from] |
|
||
83 |
AND CHARINDEX(CONCAT('[', [connections] [cn to], ']'), |
|
||
84 |
|
#connections temp [cn route] ) |
= 0 |
|
85) AS [connections next]
86LEFT JOIN #connections temp
87 |
ON [connections next] [cn |
from] = |
#connections temp [cn from] |
88 |
AND [connections next] |
[cn to] |
= #connections temp [cn to] |
89WHERE #connections temp [cn from] IS NULL
90AND #connections_temp [cn_to] IS NULL;
92SET @rows inserted = @@ROWCOUNT;
93 END; — 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 Стр: 534/545