Материал: Using_MySql,_MS_SQL_Server_and_Oracle(1)

Пример 47: формирование и анализ связанных структур

19-- Первичное наполнение временной таблицы

20-- существующими маршрутами:

21INSERT INTO `connections_temp`

22SELECT `cn_from`,

23`cn_to`,

24`cn_cost`,

25`cn_bidir`,

261,

27CONCAT(`cn_from`, ',', `cn_to`)

33UNION DISTINCT

34SELECT `cn_to`,

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`,

Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 495/545

Пример 47: формирование и анализ связанных структур

84) AS `connections_next`

85LEFT JOIN `connections_temp`

88WHERE `connections_temp`.`cn_from` IS NULL

89AND `connections_temp`.`cn_to` IS NULL;

90

91SET rows_inserted = ROW_COUNT();

92END WHILE;

93-- Извлечение маршрутов, соответствующих условию поиска:

94SELECT *

95FROM `connections_temp`

96WHERE `cn_from` = start_node

97AND `cn_to` = finish_node

98ORDER BY `cn_cost` ASC;

99DROP TABLE IF EXISTS `connections_temp`;

100END;

101$$

102DELIMITER ;

Альтернативное решение, построенное на основе классического алгоритма «поиска вглубь», требует предварительной подготовки: создания в оперативной памяти (ENGINE = MEMORY) двух таблиц и установки максимального уровня вложенности рекурсивных вызовов.

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 Стр: 496/545

Пример 47: формирование и анализ связанных структур

Теперь можно реализовывать алгоритм:

•если текущий путь пуст, отправной точкой является точка старта, иначе отправной точкой является точка прибытия последней связи в пути (строки 4054);

•открыть курсор для выбора всех связей между городами (строки 18-32, 56);

•для всех связей повторять цикл, в котором:

oпроверить, совпадает ли отправная точка рассматриваемой связи с текущей отправной точкой (строки 69-72) и, если нет, перейти к следующей итерации цикла;

oпроверить, не присутствует ли уже рассматриваемая связь в пути (строки 74-80) и не приводит ли переход по этой связи к циклическому

маршруту (строки 83-88) — в случае выполнения любого из этих условий перейти к следующей итерации цикла;

oпроверить (строка 91), не совпала ли конечная точка связи с точкой финиша:

если совпала — мы нашли путь, для которого генерируем уникальный идентификатор (строка 93) и переносим в таблицу для хранения найденных путей (строки 95-118), не забыв добавить в конец саму связь, которую мы только что рассматривали (строки

108-118);

если не совпала — путь ещё не найден, а потому: добавляем рассматриваемую связь к текущему пути (строки 121-131), выполняем рекурсивный вызов (строка 134), после которого убираем из текущего пути последнюю связь (строки 137-140: MySQL не позволяет одновременно читать и удалять данные из таблицы, потому идентификатор последней записи мы помещаем в переменную в строках 137-138, а затем используем в условии в строке 140).

По завершении работы в таблице final_paths будут находиться все найденные пути между двумя указанными городами.

1DELIMITER $$

2CREATE PROCEDURE FIND_PATH (IN start_node INT,

4BEGIN

5-- Признак выхода из цикла курсора:

6DECLARE done INT DEFAULT 0;

7

8-- Переменные для извлечения данных из курсора:

9DECLARE cn_from_value INT DEFAULT 0;

10DECLARE cn_to_value INT DEFAULT 0;

11DECLARE cn_cost_value DOUBLE DEFAULT 0;

12DECLARE cn_bidir_value CHAR(1) DEFAULT 0;

13

14-- Текущая "отправная точка"

15-- ВАЖНО! Эту переменную нельзя делать @глобальной !

16DECLARE from_node INT DEFAULT 0;

Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 497/545

Пример 47: формирование и анализ связанных структур

17-- Курсор

18DECLARE nodes_cursor CURSOR FOR

19SELECT *

20FROM (SELECT `cn_from`,

25UNION DISTINCT

26SELECT `cn_to`,

31WHERE `cn_bidir` = 'Y')

32AS `connections_bidir`;

33-- здесь можно дописать

34-- WHERE `cn_from` = from_node

35-- и убрать далее

36-- IF (cn_from_value != from_node)

37

38 DECLARE 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`

58nodes_loop: LOOP

59FETCH nodes_cursor INTO cn_from_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 Стр: 498/545

Пример 47: формирование и анализ связанных структур

73-- Такая связь уже есть в текущем пути, пропускаем

74IF EXISTS (SELECT 1

78THEN

79ITERATE nodes_loop;

80END IF;

81

82-- Такая связь приводит к циклу, пропускаем

83IF EXISTS (SELECT 1

86THEN

87ITERATE nodes_loop;

88END IF;

89

90-- Конечная точка связи совпала с точкой финиша, путь найден

91IF (cn_to_value = finish_node)

92THEN

93SET @rand_value = RAND();

101SELECT @rand_value,

102`cp_from`,

103`cp_to`,

104`cp_cost`,

105`cp_bidir`

106FROM `current_path`;

Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 499/545