Материал: Using_MySql,_MS_SQL_Server_and_Oracle(1)
Пример 47: формирование и анализ связанных структур
Сохраним в таблице connections следующий набор данных.
cn_from |
cn_to |
cn_cost |
cn_bidir |
1 |
5 |
10 |
Y |
1 |
7 |
20 |
N |
7 |
1 |
25 |
N |
7 |
2 |
15 |
Y |
2 |
6 |
50 |
N |
6 |
8 |
40 |
Y |
8 |
4 |
30 |
N |
4 |
8 |
35 |
N |
8 |
9 |
15 |
Y |
9 |
1 |
20 |
N |
7 |
3 |
5 |
N |
3 |
6 |
5 |
N |
Теперь, когда все данные подготовлены, мы можем переходить к задачам.
Задача 7.1.2.a{492}: доработать модель базы данных таким образом, чтобы для прямых маршрутов (без пересадок), цена перемещения по которым «туда» и «обратно» одинакова, в запросе на поиск такого маршрута можно было произвольно менять местами точки отправки и назначения.
Задача 7.1.2.b{493}: написать хранимую процедуру, проверяющую существование маршрута (с возможными пересадками) между двумя указанными городами, и вычисляющую стоимость отправки книги по такому маршруту (при его наличии).
Ожидаемый результат 7.1.2.a.
Запрос вида
1 |
SELECT |
* |
2 |
FROM |
{источник_данных} |
3 |
WHERE |
{откуда} = 5 |
4 |
AND |
{куда} = 1 |
должен возвращать такой результат (обратите внимание: в представленных выше данные нет маршрута из города 5 в город 1, есть только из 1 в 5, но этот маршрут
— двунаправленный):
cn_from |
cn_to |
cn_cost |
cn_bidir |
5 |
1 |
10 |
Y |
Ожидаемый результат 7.1.2.b.
Например, для городов с идентификаторами 1 и 6 хранимая процедура должна возвратить такие данные.
cn_from |
cn_to |
cn_cost |
cn_bidir |
cn_steps |
cn_route |
1 |
6 |
31 |
N |
3 |
1,7,3,6 |
1 |
6 |
85 |
N |
3 |
1,7,2,6 |
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 491/545
Пример 47: формирование и анализ связанных структур
Решение 7.1.2.a{491}.
Для решения этой задачи нам необходимо обеспечить такое поведение СУБД, чтобы для двунаправленных маршрутов при указании условия поиска как cn_from=A ADN cn_to=B в выборку попадали также и маршруты, для которых выполняется условие cn_from=B AND cn_to=A. Проще всего такого эффекта можно добиться с использованием представлений.
В строке 8 представленного ниже кода для MySQL можно было не писать ключевое слово DISTINCT (т.к. по умолчанию (без ключевого слова ALL) оператор UNION работает в DISTINCT-режиме), но оно там есть для наглядности, чтобы подчеркнуть необходимость устранения дублирующихся записей.
MySQL Решение 7.1.2.a
1CREATE OR REPLACE VIEW `connections_bidir`
2AS
3SELECT `cn_from`,
4`cn_to`,
5`cn_cost`,
6`cn_bidir`
7 FROM `connections`
8UNION DISTINCT
9SELECT `cn_to`,
10`cn_from`,
11`cn_cost`,
12`cn_bidir`
13 |
|
FROM |
`connections` |
14 |
|
WHERE |
`cn_bidir` = 'Y' |
На примере решения для MySQL рассмотрим подробно, как работает такое представление. Если выбрать из него все данные, получится следующая картина. Серым фоном отмечены строки, появившиеся в результате выполнения UNION- части запроса: для всех двунаправленных маршрутов добавились записи с инвертированными пунктами отправки и назначения.
cn_from |
cn_to |
cn_cost |
cn_bidir |
1 |
5 |
10 |
Y |
1 |
7 |
20 |
N |
2 |
6 |
50 |
N |
3 |
6 |
6 |
N |
4 |
8 |
35 |
N |
6 |
8 |
40 |
Y |
7 |
1 |
25 |
N |
7 |
2 |
15 |
Y |
7 |
3 |
5 |
N |
8 |
4 |
30 |
N |
8 |
9 |
15 |
Y |
9 |
1 |
20 |
N |
5 |
1 |
10 |
Y |
8 |
6 |
40 |
Y |
2 |
7 |
15 |
Y |
9 |
8 |
15 |
Y |
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 492/545
Пример 47: формирование и анализ связанных структур
Теперь выполнение запроса
MySQL Решение 7.1.2.a (проверка работоспособности)
1 |
SELECT |
* |
2 |
FROM |
`connections_bidir` |
3 |
WHERE |
`cn_from` = 5 |
4 |
|
AND `cn_to` = 1 |
вернёт корректный ожидаемый результат.
cn_from |
cn_to |
cn_cost |
cn_bidir |
5 |
1 |
10 |
Y |
В MS SQL Server и Oracle синтаксис оператора UNOIN не допускает явного указания слова DISTINCT (строка 8 двух показанных ниже запросов), но это — не проблема, т.к. по умолчанию (без ключевого слова ALL) оператор UNION работает в DISTINCT-режиме.
MS SQL Решение 7.1.2.a
1CREATE VIEW [connections_bidir]
2AS
3SELECT [cn_from],
4[cn_to],
5[cn_cost],
6[cn_bidir]
7 FROM [connections]
8UNION
9SELECT [cn_to],
10[cn_from],
11[cn_cost],
12[cn_bidir]
13 |
|
FROM |
[connections] |
14 |
|
WHERE |
[cn_bidir] = 'Y' |
Oracle Решение 7.1.2.a
1CREATE OR REPLACE VIEW "connections_bidir"
2AS
3SELECT "cn_from",
4"cn_to",
5"cn_cost",
6"cn_bidir"
7 FROM "connections"
8UNION
9SELECT "cn_to",
10"cn_from",
11"cn_cost",
12"cn_bidir"
13 |
|
FROM |
"connections" |
14 |
|
WHERE |
"cn_bidir" = 'Y' |
На этом решение данной задачи завершено.
Решение 7.1.2.b{491}.
Решение данной задачи стоит начать с подчёркивания того факта, что реляционные СУБД не оптимизированы для хранения графовых структур и выполнения над ними подобных операций. Потому представленные ниже решения могут показаться излишне громоздкими (с использованием классических языков программирования можно создать гораздо более компактный и оптимальный код).
Традиционно начнём с MySQL и рассмотрим два варианта решения, первый из которых максимально использует возможности СУБД, а второй эмулирует классическое алгоритмическое решение.
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 493/545
Пример 47: формирование и анализ связанных структур
Впервом варианте реализуется следующий подход42:
•в оперативной памяти (ENGINE = HEAP) создаётся временная таблица для хранения найденных путей (строки 10-18);
•в созданную таблицу переносятся все данные из таблицы connections с учётом двунаправленности некоторых связей (строки 21-40; аналогичный подзапрос, учитывающий двунаправленные связи, используется в строках 68-80 — фактически, он представляет собой ничто иное, как тело представления из решения{492} задачи 7.1.2.a{491});
•выполняется цикл поиска производных маршрутов (строки 45-92), в котором: o условием выхода является отсутствие новых маршрутов (функция MySQL ROW_COUNT возвращает количество записей, затронутых по-
следней операцией модификации данных);
oидея поиска новых маршрутов строится на том, чтобы к уже найденным маршрутам добавлять следующие шаги (конечная точка найденного маршрута совпадает с отправной точкой связи между городами, что проверяется в условии объединения в строке 81; условие в строках 82-83 исключает порождение циклических маршрутов; условие в строках 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;
6
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;
42 https://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html
Работа с MySQL, MS SQL Server и Oracle в примерах © EPAM Systems, RD Dep, 2016–2018 Стр: 494/545