Материал: Using_MySql,_MS_SQL_Server_and_Oracle
Пример 47: формирование и анализ связанных структур
Впервом варианте реализуется следующий подход43:
•в оперативной памяти (ENGINE = HEAP) создаётся временная таблица для хранения найденных путей (строки 10-18);
•в созданную таблицу переносятся все данные из таблицы connections с учётом двунаправленности некоторых связей (строки 21-40; аналогичный подзапрос, учитывающий двунаправленные связи, используется в строках 6880 — фактически, он представляет собой ничто иное, как тело представления из решения{492} задачи 7.1.2.a{491});
•выполняется цикл поиска производных маршрутов (строки 45-92), в котором:
оусловием выхода является отсутствие новых маршрутов (функция
MySQL ROW_COUNT возвращает количество записей, затронутых последней операцией модификации данных);
оидея поиска новых маршрутов строится на том, чтобы к уже найденным маршрутам добавлять следующие шаги (конечная точка найденного маршрута совпадает с отправной точкой связи между городами, что проверяется в условии объединения в строке 81; условие в строках 8283 исключает порождение циклических маршрутов; условие в строках 88-89 исключает бесконечное повторное дублирующихся маршрутов между двумя любыми городами).
•после того, как все возможные производные маршруты построены, в качестве результата работы хранимой процедуры возвращаются только те маршруты, точки отправки и назначения которых совпадают с переданными в хранимую процедуру параметрами (строки 94-98).
Уэтого решения есть два недостатка:
•предварительное построение всех возможных маршрутов избыточно и приводит к бессмысленным затратам памяти и потере производительности;
•альтернативные маршруты могут быть обнаружены только в том случае, если у них одинаковая длина (т.е. они найдены на одном шаге цикла).
MySQL Решение 7.1.2.b (код процедуры, первый вариант)
1DELIMITER $$
2CREATE PROCEDURE FIND PATH(IN start node INT,
3 |
IN finish node INT) |
4BEGIN
5DECLARE rows_inserted INT DEFAULT 0;
7-- Пересоздание временной таблицы для хранения маршрутов
8-- (именно DROP/CREATE на случай, если такая таблица была):
9DROP TABLE IF EXISTS 'connections temp';
10CREATE TABLE IF NOT EXISTS 'connections temp'
11(
12'cn from' INT,
13'cn to' INT,
14'cn cost' DOUBLE,
15'cn bidir' CHAR 1 ,
16'cn steps' SMALLINT,
17'cn route' VARCHAR 1000)
18) ENGINE = MEMORY;
43 https://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016-2018 Стр: 525/545
Пример 47: формирование и анализ связанных структур
MySQL |
і |
Решение 7.1.2.b (код процедуры, первый вариант) (продолжение) |
| |
19-- Первичное наполнение временной таблицы
20-- существующими маршрутами:
21INSERT INTO 'connections temp'
22SELECT 'cn from',
23'cn to',
24'cn cost'
25'cn bidir',
261
27CONCAT('cn from', ',', 'cn to')
28 |
FROM |
(SELECT 'cn from', |
||
29 |
|
|
'cn to', |
|
30 |
|
|
'cn |
cost' |
31 |
|
|
'cn |
bidir' |
32 |
|
FROM |
'connections' |
|
33UNION DISTINCT
34SELECT 'cn to',
35 |
|
'cn from' , |
|
36 |
|
'cn |
cost' |
37 |
|
'cn |
bidir' |
38 |
FROM |
'connections' |
|
39WHERE 'cn bidir' = 'Y'
40) AS 'connections bidir';
41
42— Наполнение временной таблицы производными
43— маршрутами:
44SET rows inserted = ROW COUNT();
45WHILE (rows inserted > 0)
46DO
47INSERT INTO 'connections temp'
48SELECT 'connections next' 'cn from',
49 |
'connections next' 'cn to' |
|
50 |
'connections next' 'cn cost', |
|
51 |
'connections next' 'cn bidir', |
|
52 |
'connections next' 'cn steps', |
|
53 |
'connections next' 'cn route' |
|
54 |
FROM (SELECT 'connections temp' 'cn from' AS 'cn from', |
|
55 |
'connections' 'cn to' AS 'cn to' |
|
56 |
('connections temp' 'cn cost' + |
|
57 |
'connections' 'cn cost') AS 'cn cost', |
|
58 |
CASE |
|
59 |
WHEN ('connections temp' 'cn bidir' = 'Y') |
|
60 |
AND ('connections' 'cn bidir' = |
'Y') |
61 |
THEN 'Y' |
|
62 |
ELSE 'N' |
|
63 |
END AS 'cn bidir', |
|
64 |
('connections temp' 'cn steps' + 1 |
AS 'cn steps', |
65 |
CONCAT('connections temp' 'cn route', ',', |
|
66 |
'connections' 'cn to') AS 'cn route' |
|
67 |
FROM 'connections temp' |
|
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016-2018 Стр: 526/545
Пример 47: формирование и анализ связанных структур
MySQL I |
Решение 7.1.2.b (код процедуры, первый вариант) (продолжение) |
| |
||
68 |
|
JOIN (SELECT 'cn from', |
|
|
69 |
|
|
'cn to', |
|
70 |
|
|
'cn cost', |
|
71 |
|
|
'cn bidir' |
|
72 |
|
FROM |
'connections' |
|
73 |
|
|
UNION DISTINCT |
|
74 |
|
SELECT 'cn to', |
|
|
75 |
|
|
'cn from' , |
|
76 |
|
|
'cn cost', |
|
77 |
|
|
'cn bidir' |
|
78 |
|
FROM |
'connections' |
|
79 |
|
WHERE |
'cn bidir' = 'Y' |
|
80 |
|
) AS 'connections' |
|
|
81 |
|
ON 'connections temp' 'cn to' = 'connections' 'cn from' |
||
82 |
|
AND FIND IN SET('connections' 'cn to', |
|
|
83 |
|
|
'connections temp' 'cn route') = 0 |
|
84 |
|
) AS 'connections next' |
|
|
85 |
|
LEFT JOIN 'connections temp' |
|
|
86 |
|
ON 'connections next' 'cn from' = 'connections temp' 'cn from' |
||
87 |
|
AND 'connections next' 'cn to' = 'connections temp' 'cn to' |
||
88 |
|
WHERE 'connections temp' 'cn from' IS NULL |
|
|
89 |
|
AND 'connections_temp' 'cn_to' IS NULL; |
|
|
90 |
|
|
|
|
91 |
|
SET rows inserted = ROW COUNT(); |
|
|
92 |
|
END WHILE; |
|
|
93 |
|
— Извлечение маршрутов, соответствующих условию поиска: |
||
94 |
|
SELECT * |
|
|
95 |
|
FROM 'connections temp' |
|
|
96 |
|
WHERE 'cn from' = start node |
|
|
97 |
|
AND 'cn to' = finish node |
|
|
98 |
|
ORDER BY 'cn cost' ASC; |
|
|
99 |
|
DROP TABLE IF EXISTS 'connections temp'; |
|
|
100 |
END; |
|
|
|
101 |
$$ |
|
|
|
102 |
DELIMITER ; |
|
|
|
|
|
|
|
|
Альтернативное решение, построенное на основе классического алгоритма «поиска вглубь», требует предварительной подготовки: создания в оперативной памяти (ENGINE = MEMORY) двух таблиц и установки максимального уровня вложенности рекурсивных вызовов.
MySQL |
Решение 7.1.2.b (подготовка ко второму варианту решения) |
| |
1— Создание таблицы для хранения текущего пути:
2CREATE TABLE IF NOT EXISTS 'current_path'
3(
4'cp id' INT PRIMARY KEY AUTO INCREMENT
5'cp from' INT,
6'cp to' INT,
7'cp cost' DOUBLE,
8'cp bidir' CHAR 1
9) ENGINE = MEMORY;
10
11— Создание таблицы для хранения готовых путей:
12CREATE TABLE IF NOT EXISTS 'final_paths'
13(
14'fp id' DOUBLE,
15'fp from' INT,
16'fp to' INT,
17'fp cost' DOUBLE,
18'fp bidir' CHAR 1
19) ENGINE = MEMORY;
20
21— Установка максимального уровня вложенности рекурсивных вызовов:
22SET @@SESSION max sp recursion depth = 255
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016-2018 Стр: 527/545
Пример 47: формирование и анализ связанных структур
Теперь можно реализовывать алгоритм:
•если текущий путь пуст, отправной точкой является точка старта, иначе отправной точкой является точка прибытия последней связи в пути (строки 4054);
•открыть курсор для выбора всех связей между городами (строки 18-32, 56);
•для всех связей повторять цикл, в котором:
опроверить, совпадает ли отправная точка рассматриваемой связи с текущей отправной точкой (строки 69-72) и, если нет, перейти к следующей итерации цикла;
опроверить, не присутствует ли уже рассматриваемая связь в пути (строки 74-80) и не приводит ли переход по этой связи к циклическому маршруту (строки 83-88) — в случае выполнения любого из этих условий перейти к следующей итерации цикла;
опроверить (строка 91), не совпала ли конечная точка связи с точкой финиша:
■если совпала — мы нашли путь, для которого генерируем уникальный идентификатор (строка 93) и переносим в таблицу для хранения найденных путей (строки 95-118), не забыв добавить в конец саму связь, которую мы только что рассматривали (строки
108-118);
■если не совпала — путь ещё не найден, а потому: добавляем рассматриваемую связь к текущему пути (строки 121-131), выполняем рекурсивный вызов (строка 134), после которого убираем из текущего пути последнюю связь (строки 137-140: MySQL не позволяет одновременно читать и удалять данные из таблицы, потому идентификатор последней записи мы помещаем в переменную в строках 137-138, а затем используем в условии в строке 140).
По завершении работы в таблице final_paths будут находиться все найденные пути между двумя указанными городами.
MySQL |
Решение 7.1.2.b (код процедуры, второй вариант) | |
|
||
1 |
DELIMITER ..................... |
|
$$ ....... |
* |
2 |
CREATE PROCEDURE |
FIND_PATH |
(IN |
start_node INT, |
3 |
|
IN finish node INT) |
||
4BEGIN
5-- Признак выхода из цикла курсора: DECLARE done INT DEFAULT 0;
6 |
|
7 |
-- Переменные для извлечения данных из курсора: DECLARE DECLARE DECLARE |
8DECLARE cn_from_value INT DEFAULT 0;
9-- cn_to_value INT DEFAULT 0;
10Текущая cn_cost_value DOUBLE DEFAULT 0;
11cn_bidir_value CHAR(1) DEFAULT 0;
12"отправная точка"
13-- ВАЖНО! Эту переменную нельзя делать @глобальной ! DECLARE from node INT
14 DEFAULT 0;
15
16
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016-2018 Стр: 528/545
Пример 47: формирование и анализ связанных структур
MySQL |
і |
Решение 7.1.2.b (код процедуры, второй вариант) (продолжение) |
| |
17-- Курсор
18DECLARE nodes cursor CURSOR FOR
19SELECT *
20FROM (SELECT 'cn from',
21 |
|
'cn to', |
|
22 |
|
'cn |
cost' |
23 |
|
'cn |
bidir' |
24 |
FROM |
'connections' |
|
25UNION DISTINCT
26SELECT 'cn to',
27 |
|
'cn from', |
|
28 |
|
'cn |
cost' |
29 |
|
'cn |
bidir' |
30 |
FROM |
'connections' |
|
31 |
WHERE |
'cn bidir' = 'Y') |
|
32AS 'connections bidir';
33-- здесь можно дописать
34-- WHERE 'cn from' = from node
35-- и убрать далее
36-- IF (cn_from_value != from_node)
38DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1
39
40IF ((SELECT COUNT 1
41FROM 'current_path') = 0)
42THEN
43-- Если текущий путь пуст, отправной точкой
44-- является точка старта
45SET from node = start node
46ELSE
47-- Если текущий путь НЕ пуст, отправной точкой
48-- является точка прибытия последней связи в пути
49SET from node = (SELECT 'cp to'
50 |
FROM 'current_path' |
51 |
WHERE 'cp id' = (SELECT MAX('cp id') |
52 |
FROM 'current_path') |
53 |
); |
54 |
END IF; |
55 |
|
56 |
OPEN nodes_cursor; |
57 |
|
58nodes loop: LOOP
59FETCH nodes cursor INTO cn from value
60 |
cn to value |
|
61 |
cn |
cost value, |
62 |
cn |
bidir value; |
63IF done THEN
64LEAVE nodes loop;
65END IF;
66
67— Отправная точка связи не совпадает с текущей
68— отправной точкой, пропускаем
69IF (cn from value != from node
70THEN
71ITERATE nodes loop;
72END IF;
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016-2018 Стр: 529/545