Материал: Using_MySql,_MS_SQL_Server_and_Oracle
Пример 47: формирование и анализ связанных структур
Алгоритм второго варианта решения:
•если текущий путь пуст, отправной точкой является точка старта, иначе отправной точкой является точка прибытия последней связи в пути (строки 2640; обратите внимание на то, как в Oracle проверяется на пустоту результат выполнения запроса — классическое выражение IF (NOT) EXISTS здесь не работает);
•открыть курсор для выбора всех связей между городами (строки 8-24, 42);
•для всех связей повторять цикл, в котором:
опроверить, совпадает ли отправная точка рассматриваемой связи с текущей отправной точкой (строки 46-49 и, если нет, перейти к следующей итерации цикла;
опроверить, не присутствует ли уже рассматриваемая связь в пути (строки 52-60) и не приводит ли переход по этой связи к циклическому маршруту (строки 63-70) — в случае выполнения любого из этих условий перейти к следующей итерации цикла;
опроверить (строка 73), не совпала ли конечная точка связи с точкой финиша:
■если совпала — мы нашли путь, для которого генерируем уникальный идентификатор (строка 75) и переносим в таблицу для хранения найденных путей (строки 77-88), не забыв добавить в конец саму связь, которую мы только что рассматривали (строки
89-99);
■если не совпала — путь ещё не найден, а потому: добавляем рассматриваемую связь к текущему пути (строки 102-113), выполняем рекурсивный вызов (строка 116), после которого убираем из текущего пути последнюю связь (строки 119-121).
По завершении работы в таблице final_paths будут находиться все найденные пути между двумя указанными городами.
Обратите внимание, как в строках 108-109 реализована эмуляция автоинкрементируемого первичного ключа без использования триггера.
Oracl |
і Решение 7.1.2.b (код процедуры, второй вариант) |
| |
||||
e |
||||||
|
|
|
|
|
||
1 |
CREATE OR REPLACE PROCEDURE FIND PATH (start node IN NUMBER, |
|||||
2 |
|
|
|
|
finish node IN NUMBER) |
|
3 |
AS |
|
|
|
|
|
4 |
from node NUMBER 10) := 0 |
|
|
|||
5 |
rows count NUMBER(10| := 0; |
|
|
|||
6 |
rand value NUMBER(154 |
:= 0; |
|
|||
7 |
|
|
|
|
|
|
8 |
CURSOR nodes cursor IS |
|
|
|
||
9 |
SELECT "cn from", |
|
|
|
||
10 |
"cn to", |
|
|
|
||
11 |
"cn cost", |
|
|
|
||
12 |
"cn bidir" |
|
|
|
||
13 |
FROM (SELECT "cn from", |
|
|
|||
14 |
|
"cn to" |
|
|
|
|
15 |
|
"cn cost", |
|
|
||
16 |
|
"cn bidir" |
|
|
||
17 |
FROM |
"connections" |
|
|
||
18 |
UNION |
|
|
|
|
|
19 |
SELECT "cn to" |
|
|
|
||
20 |
|
"cn from" , |
|
|
||
21 |
|
"cn cost", |
|
|
||
22 |
|
"cn bidir" |
|
|
||
23 |
FROM |
"connections" |
|
|
||
24 |
WHERE |
"cnbidir" = |
'Y'); |
|
||
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016-2018 Стр: 542/545
Пример 47: формирование и анализ связанных структур
Oracl |
і Решение 7.1.2.b (код процедуры, второй вариант) (продолжение) |
| |
||
e |
||||
|
|
|
||
25 |
BEGIN |
|
|
|
26 |
SELECT COUNT 1 |
INTO rows count |
|
|
27 |
FROM "current_path"; |
|
||
28 |
|
|
|
|
29IF rows count = 0)
30THEN
31-- Если текущий путь пуст, отправной точкой является точка старта
32from node := start node
33ELSE
34-- Если текущий путь НЕ пуст, отправной точкой
35-- является точка прибытия последней связи в пути
36SELECT "cp to" INTO from node
37FROM "current_path"
38WHERE "cp id" = (SELECT MAX("cp id"
39 |
FROM "current_path"); |
40 |
END IF; |
41 |
|
42FOR one link IN nodes cursor
43LOOP
44-- Отправная точка связи не совпадает с текущей
45-- отправной точкой, пропускаем
46IF (one link "cn from" != from node
47THEN
48CONTINUE;
49END IF;
50
51— Такая связь уже есть в текущем пути, пропускаем
52SELECT COUNT(1) INTO rows count
53FROM (SELECT 1
54FROM "current_path"
55WHERE "cp from" = one link "cn from"
56 |
AND "cp to" = one link "cn to"); |
57IF rows count > 0)
58THEN
59CONTINUE;
60END IF;
61
62— Такая связь приводит к циклу, пропускаем
63SELECT COUNT(1) INTO rows count
64FROM (SELECT 1
65FROM "current_path"
66WHERE "cp from" = one link "cn to" ;
67IF rows count > 0)
68THEN
69CONTINUE;
70END IF;
71
72— Конечная точка связи совпала с точкой финиша, путь найден
73IF one link "cn to" = finish node)
74THEN
75rand_value := DBMS_RANDOM.VALUE 1 101;
76 |
|
|
77 |
INSERT INTO "final_paths" |
|
78 |
|
("fp id", |
79 |
|
"fp from" , |
80 |
|
"fp to", |
81 |
|
"fp cost", |
82 |
|
"fp bidir" |
83 |
SELECT rand value, |
|
84 |
|
"cp from" , |
85 |
|
"cp to" |
86 |
|
"cp cost", |
87 |
|
"cp bidir" |
88 |
FROM |
"current path": |
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016-2018 Стр: 543/545
Пример 47: формирование и анализ связанных структур
Oracl |
і |
Решение 7.1.2.b (код процедуры, второй вариант) (продолжение) |
| |
||
e |
|||||
|
|
|
|
||
89 |
|
INSERT INTO "final_paths" |
|
||
90 |
|
("fp id", |
|
||
91 |
|
|
"fp from" , |
|
|
92 |
|
|
"fp to", |
|
|
93 |
|
|
"fp cost", |
|
|
94 |
|
|
"fp bidir" |
|
|
95 |
|
VALUES (rand value |
|
||
96 |
|
one link "cn from" |
|
||
97 |
|
one link "cn to", |
|
||
98 |
|
one link "cn cost" |
|
||
99 |
|
one link "cn bidir"); |
|
||
100 |
|
ELSE |
|
|
|
101 |
|
-- Добавляем связь в текущий путь |
|
||
102 |
|
INSERT INTO "current_path" |
|
||
103 |
|
("cp id", |
|
||
104 |
|
|
"cp from" , |
|
|
105 |
|
|
"cp to", |
|
|
106 |
|
|
"cp cost", |
|
|
107 |
|
|
"cp bidir" |
|
|
108 |
|
VALUES (NVL((SELECT MAX "cp id") + 1 |
|
||
109 |
|
FROM "current_path"), 1), |
|
||
110 |
|
one link "cn from" |
|
||
111 |
|
one link "cn to", |
|
||
112 |
|
one link "cn cost" |
|
||
113 |
|
one link "cn bidir"); |
|
||
114 |
|
|
|
|
|
115 |
|
-- Продолжаем рекурсивно искать следующие связи |
|||
116 |
|
FIND PATH (start node, finish node ; |
|
||
117 |
|
|
|
|
|
118 |
|
-- Удаляем последнюю связь из текущего пути |
|
||
119 |
|
DELETE FROM |
"current_path" |
|
|
120 |
|
WHERE "cp id" = (SELECT MAX("cp id" |
|
||
121 |
|
|
FROM "current_path"); |
|
|
122 |
|
END IF; |
|
|
|
123 |
|
END LOOP; |
|
|
|
124 |
END; |
|
|
||
Проверим, как работают полученные решения, выполнив представленный ниже код. Поведение Oracle оказывается полностью эквивалентным поведению
MySQL и MS SQL Server.
На представленном в начале данного примера наборе данных для поиска пути из города 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 |
|
|
|||
4.5847 |
1 |
|
|
7 |
20 |
|
N |
|
|
|
4.5847 |
7 |
|
|
2 |
15 |
|
Y |
|
|
|
4.5847 |
2 |
|
|
6 |
50 |
|
N |
|
|
|
8.5731 |
1 |
|
|
7 |
20 |
|
N |
|
|
|
8.5731 |
7 |
|
|
3 |
5 |
|
N |
|
|
|
8.5731 |
3 |
|
|
6 |
5 |
|
N |
|
|
|
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016-2018 Стр: 544/545