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

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

71) "connections_next"

72LEFT JOIN "connections_temp"

75WHERE "connections_temp"."cn_from" IS NULL

76AND "connections_temp"."cn_to" IS NULL;

77

78rows_inserted := SQL%ROWCOUNT;

79END LOOP;

80

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

82OPEN final_paths FOR

83SELECT *

84FROM "connections_temp"

85WHERE "cn_from" = start_node

86AND "cn_to" = finish_node

87ORDER BY "cn_cost" ASC;

88END;

Для второго варианта решения, как и в случае с MySQL и MS SQL Server, нам понадобятся вспомогательные таблицы для хранения текущего и финальных путей.

1-- Создание таблицы для хранения текущего пути:

2CREATE GLOBAL TEMPORARY TABLE "current_path"

3(

4"cp_id" NUMBER(10),

5"cp_from" NUMBER(10),

6"cp_to" NUMBER(10),

7"cp_cost" NUMBER(15,4),

8"cp_bidir" CHAR(1)

9);

10

11-- Создание таблицы для хранения готовых путей:

12CREATE GLOBAL TEMPORARY TABLE "final_paths"

13(

14"fp_id" NUMBER(15,4),

15"fp_from" NUMBER(15,4),

16"fp_to" NUMBER(15,4),

17"fp_cost" NUMBER(15,4),

18"fp_bidir" CHAR(1)

19);

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

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

Алгоритм второго варианта решения:

•если текущий путь пуст, отправной точкой является точка старта, иначе отправной точкой является точка прибытия последней связи в пути (строки 2640; обратите внимание на то, как в Oracle проверяется на пустоту результат выполнения запроса — классическое выражение IF (NOT) EXISTS здесь не работает);

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

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

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

oпроверить, не присутствует ли уже рассматриваемая связь в пути (строки 52-60) и не приводит ли переход по этой связи к циклическому маршруту (строки 63-70) — в случае выполнения любого из этих условий перейти к следующей итерации цикла;

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

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

89-99);

если не совпала — путь ещё не найден, а потому: добавляем рассматриваемую связь к текущему пути (строки 102-113), выполняем рекурсивный вызов (строка 116), после которого убираем из текущего пути последнюю связь (строки 119-121).

По завершении работы в таблице final_paths будут находиться все

найденные пути между двумя указанными городами.

3AS

4from_node NUMBER(10) := 0;

5rows_count NUMBER(10) := 0;

6rand_value NUMBER(15,4) := 0;

7

8CURSOR nodes_cursor IS

9SELECT "cn_from",

10"cn_to",

11"cn_cost",

12"cn_bidir"

13FROM (SELECT "cn_from",

18UNION

19SELECT "cn_to",

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

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

Oracle Решение 7.1.2.b (код процедуры, второй вариант) (продолжение)

25BEGIN

26SELECT COUNT(1) INTO rows_count

27FROM "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")

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"

56AND "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,10);

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

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

100ELSE

101-- Добавляем связь в текущий путь

102INSERT INTO "current_path"

115-- Продолжаем рекурсивно искать следующие связи

116FIND_PATH (start_node, finish_node);

117

118-- Удаляем последнюю связь из текущего пути

119DELETE FROM "current_path"

120WHERE "cp_id" = (SELECT MAX("cp_id")

122END IF;

123END LOOP;

124END;

Проверим, как работают полученные решения, выполнив представленный ниже код. Поведение Oracle оказывается полностью эквивалентным поведению

MySQL и MS SQL Server.

На представленном в начале данного примера наборе данных для поиска пути из города 1 в город 6 оба решения возвращают одинаковые (хоть и по-разному представленные) результаты.

Результат первого варианта решения:

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

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

1-- Для первого варианта решения:

2TRUNCATE TABLE "connections_temp";

3DECLARE

4fp SYS_REFCURSOR;

5cn_from NUMBER(10);

6cn_to NUMBER(10);

7cn_cost DOUBLE PRECISION;

8cn_bidir CHAR(1);

9cn_steps NUMBER(5);

10cn_route VARCHAR(1000);

11BEGIN

12FIND_PATH({начальная_точка}, {конечная_точка}, fp);

13LOOP

14FETCH fp INTO cn_from,

20EXIT WHEN fp%NOTFOUND;

21DBMS_OUTPUT.PUT_LINE(cn_from || ' | ' ||

27END LOOP;

28CLOSE fp;

29END;

30

31-- Для второго варианта решения:

32TRUNCATE TABLE "current_path";

33TRUNCATE TABLE "final_paths";

34BEGIN

35FIND_PATH({начальная_точка}, {конечная_точка});

36END;

37SELECT * FROM "final_paths";

Но если в таблицу connections поместить следующие данные

и поискать путь между городами 1 и 5, результаты будут разными. Результат первого варианта решения:

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