Материал: Using_MySql,_MS_SQL_Server_and_Oracle
Пример 47: формирование и анализ связанных структур
Для второго варианта решения, как и в случае с MySQL, нам понадобятся вспомогательные таблицы для хранения текущего и финальных путей.
MS S |
QL I |
Решение 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);
•для всех связей повторять цикл, в котором:
опроверить, совпадает ли отправная точка рассматриваемой связи с текущей отправной точкой (строки 60-61 и, если нет, перейти к следующей итерации цикла;
опроверить, не присутствует ли уже рассматриваемая связь в пути (строки 63-67) и не приводит ли переход по этой связи к циклическому маршруту (строки 70-73) — в случае выполнения любого из этих условий перейти к следующей итерации цикла;
опроверить (строка 76), не совпала ли конечная точка связи с точкой финиша:
■если совпала — мы нашли путь, для которого генерируем уникальный идентификатор (строка 78) и переносим в таблицу для хранения найденных путей (строки 79-90), не забыв добавить в конец саму связь, которую мы только что рассматривали (строки
91-101);
■если не совпала — путь ещё не найден, а потому: добавляем рассматриваемую связь к текущему пути (строки 106-114), выполняем рекурсивный вызов (строка 117), после которого убираем из текущего пути последнюю связь (строки 120-121).
По завершении работы в таблице final_paths будут находиться все найденные пути между двумя указанными городами.
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016-2018 Стр: 535/545
Пример 47: формирование и анализ связанных структур
MS SQL I Решение 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;
14-- Идентификатор найденного пути
15DECLARE @rand_value DOUBLE PRECISION = 0 ;
17-- Курсор для прохода по связям между городами
18DECLARE nodes cursor CURSOR LOCAL FAST FORWARD FOR
19SELECT *
20 |
FROM (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];
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 Стр: 536/545
Пример 47: формирование и анализ связанных структур
MS SQL |
Решение 7.1.2.b (код процедуры, второй вариант) (продолжение) |
і |
62- Такая связь уже есть в текущем пути, пропускаем
63IF EXISTS (SELECT 1
64 |
FROM #current_path |
|
||
WHERE |
[cp_from] = |
@cn_from_value |
||
65 |
||||
AND |
[cp_to] = @cn_to_value |
|||
66 |
||||
CONTINUE; |
|
|
||
67 |
|
|
||
|
|
|
||
68 |
— Такая связь приводит к циклу, пропускаем |
|||
69 |
||||
IF EXISTS (SELECT 1 |
|
|||
70 |
|
|||
FROM #current_path |
|
|||
71 |
|
|||
WHERE |
[cp_from] = |
@cn_to_value) |
||
72 |
||||
CONTINUE; |
|
|
||
73 |
|
|
||
|
|
|
||
74 |
— Конечная точка связи совпала с точкой финиша, путь найден |
|
75 |
||
IF (@cn_to_value = @finish_node |
||
76 |
||
BEGIN |
||
77 |
||
SET @rand_value = RAND(); |
||
78 |
||
INSERT INTO #final_paths |
||
79 |
||
([fp_id], |
||
80 |
||
[fp_from], |
||
81 |
||
[fp_to], |
||
82 |
||
[fp_cost], |
||
83 |
||
[fp_bidir]) |
||
84 |
||
SELECT @rand_value, |
||
85 |
||
[cp_from], |
||
86 |
||
[cp_to], |
||
87 |
||
[cp_cost], |
||
88 |
||
[cp_bidir] |
||
|
89FROM #current_path;
90INSERT INTO #final_paths
92 |
([fp_id], |
|
[fp_from], |
||
93 |
||
[fp_to], |
||
94 |
||
[fp_cost], |
||
95 |
||
[fp_bidir]) |
||
96 |
||
VALUES (@rand_value, |
||
97 |
||
@ cn_f rom_value |
||
98 |
||
@cn_to_value, |
||
99 |
||
@ cn_cost_value |
||
100 |
||
@cn_bidir_value); |
||
101 |
||
END ELSE |
||
102 |
||
BEGIN |
||
103 |
||
— Добавляем связь в текущий путь |
||
104 |
||
INSERT INTO #current_path |
||
105 |
||
[cp_from], |
||
106 |
||
[cp_to], |
||
107 |
||
[cp_cost], |
||
108 |
||
[cp_bidir]) |
||
109 |
||
VALUES @cn_from_value, |
||
110 |
||
@ cn_to_value |
||
111 |
||
@ cn_cos t_value, @cn_bidir_value); |
||
112 |
||
|
||
113 |
-- Продолжаем рекурсивно искать следующие связи EXEC FIND_PATH |
|
114 |
||
@start_node @finish_node; |
||
115 |
||
|
116-- Удаляем последнюю связь из текущего пути
117DELETE FROM #current_path
118 |
WHERE [cp_id] = (SELECT MAX([cp_id]) FROM #current_path); |
119END;
120END;
121CLOSE nodes_cursor
122DEALLOCATE nodes_cursor;
123GO
124
125
126
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016-2018 Стр: 537/545
Пример 47: формирование и анализ связанных структур
Проверим, как работают полученные решения, выполнив такой код.
MS SQL і |
Решение 7.1.2.b (код для проверки работоспособности) |
[ |
1-- Для первого варианта решения:
2EXEC FIND_PATH {начальная_точка}, {конечная_точка};
4-- Для второго варианта решения:
5TRUNCATE TABLE#current_path
6TRUNCATE TABLE#final_paths 1
EXEC 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 Стр: 538/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), в котором:
оусловием выхода является отсутствие новых маршрутов (переменная
Oracle SQL%ROWCOUNT содержит количество записей, затронутых последней операцией модификации данных);
оидея поиска новых маршрутов строится на том, чтобы к уже найденным маршрутам добавлять следующие шаги (конечная точка найденного маршрута совпадает с отправной точкой связи между городами, что проверяется в условии объединения в строке 68; условие в строках 6970 исключает порождение циклических маршрутов; условие в строках 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 Стр: 539/545