Материал: Using_MySql,_MS_SQL_Server_and_Oracle(1)
Пример 47: формирование и анализ связанных структур
|
MS SQL |
Решение 7.1.2.b (код процедуры, второй вариант) |
||
|
1 |
|
CREATE PROCEDURE FIND_PATH |
|
|
2 |
|
|
@start_node INT, |
|
3 |
|
|
@finish_node INT |
4AS
5-- Переменные для извлечения данных из курсора:
6DECLARE @cn_from_value INT = 0;
7DECLARE @cn_to_value INT = 0;
8DECLARE @cn_cost_value DOUBLE PRECISION = 0;
9DECLARE @cn_bidir_value CHAR(1) = '0';
10
11-- Текущая "отправная точка"
12DECLARE @from_node INT = 0;
13
14-- Идентификатор найденного пути
15DECLARE @rand_value DOUBLE PRECISION = 0;
16
17-- Курсор для прохода по связям между городами
18DECLARE nodes_cursor CURSOR LOCAL FAST_FORWARD FOR
19SELECT *
20FROM (SELECT [cn_from],
21 |
|
|
[cn_to], |
22 |
|
|
[cn_cost], |
23 |
|
|
[cn_bidir] |
24 |
|
FROM |
[connections] |
25UNION
26SELECT [cn_to],
27 |
|
|
[cn_from], |
28 |
|
|
[cn_cost], |
29 |
|
|
[cn_bidir] |
30 |
|
FROM |
[connections] |
31WHERE [cn_bidir] = 'Y'
32) AS [connections_bidir];
33
34IF ((SELECT COUNT(1)
35FROM #current_path) = 0)
36-- Если текущий путь пуст, отправной точкой является точка старта
37SET @from_node = @start_node;
38ELSE
39-- Если текущий путь НЕ пуст, отправной точкой
40-- является точка прибытия последней связи в пути
41SET @from_node = (SELECT [cp_to]
42 |
|
FROM |
#current_path |
43 |
|
WHERE |
[cp_id] = (SELECT MAX([cp_id]) |
44 |
|
|
FROM #current_path) |
45 |
|
); |
|
46 |
|
|
|
47 |
|
OPEN nodes_cursor; |
|
48 |
|
|
|
|
|
|
|
49WHILE (1 = 1)
50BEGIN
51FETCH NEXT FROM nodes_cursor INTO @cn_from_value,
52 |
|
@cn_to_value, |
53 |
|
@cn_cost_value, |
54 |
|
@cn_bidir_value; |
|
|
|
55IF (@@FETCH_STATUS != 0)
56BREAK;
57
58-- Отправная точка связи не совпадает с текущей
59-- отправной точкой, пропускаем
60IF (@cn_from_value != @from_node)
61CONTINUE;
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 505/545
Пример 47: формирование и анализ связанных структур
MS SQL Решение 7.1.2.b (код процедуры, второй вариант) (продолжение)
62-- Такая связь уже есть в текущем пути, пропускаем
63IF EXISTS (SELECT 1
64 |
|
FROM #current_path |
||
65 |
|
WHERE |
[cp_from] |
= @cn_from_value |
66 |
|
AND |
[cp_to] = |
@cn_to_value) |
67 |
|
CONTINUE; |
|
|
68 |
|
|
|
|
69-- Такая связь приводит к циклу, пропускаем
70IF EXISTS (SELECT 1
71 |
|
FROM #current_path |
72 |
|
WHERE [cp_from] = @cn_to_value) |
73 |
|
CONTINUE; |
74 |
|
|
75-- Конечная точка связи совпала с точкой финиша, путь найден
76IF (@cn_to_value = @finish_node)
77BEGIN
78SET @rand_value = RAND();
79INSERT INTO #final_paths
80 |
|
|
([fp_id], |
81 |
|
|
[fp_from], |
82 |
|
|
[fp_to], |
83 |
|
|
[fp_cost], |
84 |
|
|
[fp_bidir]) |
85 |
|
SELECT @rand_value, |
|
86 |
|
|
[cp_from], |
87 |
|
|
[cp_to], |
88 |
|
|
[cp_cost], |
89 |
|
|
[cp_bidir] |
90 |
|
FROM |
#current_path; |
91 |
|
INSERT INTO #final_paths |
|
92 |
|
|
([fp_id], |
93 |
|
|
[fp_from], |
94 |
|
|
[fp_to], |
95 |
|
|
[fp_cost], |
96 |
|
|
[fp_bidir]) |
97 |
|
VALUES (@rand_value, |
|
98 |
|
|
@cn_from_value, |
99 |
|
|
@cn_to_value, |
100 |
|
|
@cn_cost_value, |
101 |
|
|
@cn_bidir_value); |
102END
103ELSE
104BEGIN
105-- Добавляем связь в текущий путь
106INSERT INTO #current_path
107 |
|
([cp_from], |
108 |
|
[cp_to], |
109 |
|
[cp_cost], |
110 |
|
[cp_bidir]) |
111 |
|
VALUES (@cn_from_value, |
112 |
|
@cn_to_value, |
113 |
|
@cn_cost_value, |
114 |
|
@cn_bidir_value); |
115 |
|
|
|
|
|
116-- Продолжаем рекурсивно искать следующие связи
117EXEC FIND_PATH @start_node, @finish_node;
118
119-- Удаляем последнюю связь из текущего пути
120DELETE FROM #current_path
121 |
|
WHERE [cp_id] = (SELECT MAX([cp_id]) FROM #current_path); |
122END;
123END;
124CLOSE nodes_cursor;
125DEALLOCATE nodes_cursor;
126GO
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 506/545
Пример 47: формирование и анализ связанных структур
Проверим, как работают полученные решения, выполнив такой код.
MS SQL |
Решение 7.1.2.b (код для проверки работоспособности) |
1-- Для первого варианта решения:
2EXEC FIND_PATH {начальная_точка}, {конечная_точка};
3
4-- Для второго варианта решения:
5TRUNCATE TABLE #current_path;
6TRUNCATE TABLE #final_paths;
7EXEC FIND_PATH {начальная_точка}, {конечная_точка};
8SELECT * FROM #final_paths;
Поведение MS SQL Server оказывается полностью эквивалентным поведе-
нию MySQL.
На представленном в начале данного примера наборе данных для поиска пути из города 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.159113517642648 |
1 |
|
7 |
20 |
|
N |
|
||||
0.159113517642648 |
7 |
|
2 |
15 |
|
Y |
|
||||
0.159113517642648 |
2 |
|
6 |
50 |
|
N |
|
||||
0.716279602109358 |
1 |
|
7 |
20 |
|
N |
|
||||
0.716279602109358 |
7 |
|
3 |
5 |
|
N |
|
||||
0.716279602109358 |
3 |
|
6 |
5 |
|
N |
|
||||
Но если в таблицу 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.948062188221448 |
|
1 |
|
3 |
100 |
|
N |
|
||||
0.948062188221448 |
|
3 |
|
5 |
20 |
|
N |
|
||||
0.562740117282937 |
|
1 |
|
5 |
100 |
|
N |
|
||||
Таким образом, как и было сказано выше, в MS SQL Server первый вариант решения тоже не находит альтернативные пути разной длины, в то время как второй вариант справляется с этим.
На этом решение для MS SQL Server завершено.
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 507/545
Пример 47: формирование и анализ связанных структур
Переходим к Oracle и реализуем решение, представленное выше для MySQL
иMS SQL Server.
Вотличие от двух других СУБД, Oracle не позволяет скомпилировать хранимую процедуру, внутри которой есть обращение к несуществующим объектам — даже если объекты создаются в этой же процедуре несколькими строками выше. Это ограничение можно обходить через EXECUTE IMMEDIATE и иными изощрёнными способами, но для простоты кода мы вынесем создание временной таблицы, с которой работает хранимая процедура, в отдельный код.
Oracle |
Решение 7.1.2.b (подготовка к первому варианту решения) |
1CREATE GLOBAL TEMPORARY TABLE "connections_temp"
2(
3"cn_from" NUMBER(10),
4"cn_to" NUMBER(10),
5"cn_cost" DOUBLE PRECISION,
6"cn_bidir" CHAR(1),
7"cn_steps" NUMBER(5),
8"cn_route" VARCHAR(1000)
9)
10ON COMMIT PRESERVE ROWS;
Алгоритм первого варианта решения:
•в созданную до компиляции хранимой процедуры временную таблицу переносятся все данные из таблицы connections с учётом двунаправленности некоторых связей (строки 10-28; аналогичный подзапрос, учитывающий двунаправленные связи, используется в строках 55-67 — фактически, он представляет собой ничто иное, как тело представления из решения{492} задачи
7.1.2.a{491});
•выполняется цикл поиска производных маршрутов (строки 32-79), в котором: o условием выхода является отсутствие новых маршрутов (переменная Oracle SQL%ROWCOUNT содержит количество записей, затронутых по-
следней операцией модификации данных);
oидея поиска новых маршрутов строится на том, чтобы к уже найденным маршрутам добавлять следующие шаги (конечная точка найденного маршрута совпадает с отправной точкой связи между городами, что проверяется в условии объединения в строке 68; условие в строках 69-70 исключает порождение циклических маршрутов; условие в строках 75-76 исключает бесконечное повторное дублирующихся маршрутов между двумя любыми городами).
•после того, как все возможные производные маршруты построены, в качестве результата работы хранимой процедуры возвращаются только те маршруты, точки отправки и назначения которых совпадают с переданными в хранимую процедуру параметрами (строки 82-87).
Обратите внимание на то, как формируется и анализируется маршрут, раз-
мещаемый в поле cn_route таблицы connections_temp: в Oracle (как и в MS SQL
Server) нет прямого аналога функции MySQL FIND_IN_SET, а при поиске вхожде-
ния подстроки в строку есть шанс, например, «найти» число 12 в числе 123 и т.д. Потому каждое значение идентификатора берётся в квадратные скобки
(маршрут примет вид наподобие «[1][7][3][6]»), и поиск тоже производится с предварительным заключением искомого идентификатора в квадратные скобки, что гарантирует отсутствие ложных срабатываний.
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 508/545
Пример 47: формирование и анализ связанных структур
|
Oracle |
|
Решение 7.1.2.b (код процедуры, первый вариант) |
|
|
1 |
|
CREATE OR REPLACE PROCEDURE FIND_PATH (start_node IN NUMBER, |
|
|
2 |
|
|
finish_node IN NUMBER, |
|
3 |
|
|
final_paths OUT SYS_REFCURSOR) |
4AS
5rows_inserted NUMBER := 0;
6BEGIN
7
8-- Первичное наполнение временной таблицы существующими маршрутами:
9INSERT INTO "connections_temp"
10SELECT "cn_from",
11"cn_to",
12"cn_cost",
13"cn_bidir",
141,
15('[' || "cn_from" || '][' || "cn_to" || ']')
16 |
|
FROM (SELECT |
"cn_from", |
17 |
|
|
"cn_to", |
18 |
|
|
"cn_cost", |
19 |
|
|
"cn_bidir" |
20 |
|
FROM |
"connections" |
21UNION
22SELECT "cn_to",
23 |
|
|
"cn_from", |
24 |
|
|
"cn_cost", |
25 |
|
|
"cn_bidir" |
26 |
|
FROM |
"connections" |
27WHERE "cn_bidir" = 'Y'
28) "connections_bidir";
29
30-- Наполнение временной таблицы производными маршрутами:
31rows_inserted := SQL%ROWCOUNT;
32WHILE (rows_inserted > 0)
33LOOP
34INSERT INTO "connections_temp"
35SELECT "connections_next"."cn_from",
36 |
|
"connections_next"."cn_to", |
37 |
|
"connections_next"."cn_cost", |
38 |
|
"connections_next"."cn_bidir", |
39 |
|
"connections_next"."cn_steps", |
40 |
|
"connections_next"."cn_route" |
41 |
|
FROM (SELECT "connections_temp"."cn_from" AS "cn_from", |
42 |
|
"connections"."cn_to" AS "cn_to", |
43 |
|
("connections_temp"."cn_cost" + |
44 |
|
"connections"."cn_cost") AS "cn_cost", |
45 |
|
CASE |
46 |
|
WHEN ("connections_temp"."cn_bidir" = 'Y') |
47 |
|
AND ("connections"."cn_bidir" = 'Y') |
48 |
|
THEN 'Y' |
49 |
|
ELSE 'N' |
50 |
|
END AS "cn_bidir", |
51 |
|
("connections_temp"."cn_steps" + 1) AS "cn_steps", |
52 |
|
("connections_temp"."cn_route" || '[' || |
53 |
|
"connections"."cn_to" || ']') AS "cn_route" |
54 |
|
FROM "connections_temp" |
|
|
|
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 509/545