Глава 12. Рекурсивные запросы

В этой главе...

• Управление рекурсией
• Как определять рекурсивные запросы
• Способы применения рекурсивных запросов

SQL-92 и более ранние версии часто критиковали за отсутствие реализации рекурсивной обработки. Многие важные задачи, которые трудно решить другими средствами, легко решаются с помощью рекурсии. В SQL: 1999 появились расширения, позволяющие создавать рекурсивные запросы. Благодаря этим расширениям мощь языка SQL существенно возрастает. Если ваша реализация SQL включает в себя расширения для рекурсии, то вы можете эффективно решать новый большой класс задач. Впрочем, в основной части стандарта
SQL.-2OO3 поддержка рекурсии не предусмотрена. Поэтому во многих используемых реализациях этой поддержки может и не быть.

Что такое рекурсия

Это довольно старая возможность таких языков программирования, как Logo, LISP и C++. В этих языках можно определить функцию (совокупность одной или множества команд), которая выполняет заданную операцию. Главная программа вызывает функцию, выполняя для этого команду, которая называется вызовом функции. В процессе своей работы функция вызывает сама себя — это самая простая форма рекурсии.

Для иллюстрации достоинств и недостатков рекурсии приведем простую программу, в которой одна из функций использует рекурсивные вызовы. Эта программа, написанная на C++, чертит на экране компьютера спираль, начиная с единичного сегмента, направленного вверх.

В ее состав входят три функции.

• Функция line(n) чертит отрезок длины n.
• Функция Jeft_turn(d) поворачивает "чертежный инструмент" на d градусов против часовой стрелки.
• Функция spiral(segment), которая определяется следующим образом:

• void spiral(int segment)

  {

  line(segment);

  left_turn(90);

  spiral(seement + 1);

  }

Если из главной программы вызвать spiral(1), то будут выполняться такие действия:

• spiral(1) чертит единичный отрезок (т.е. единичной длины), направленный вверх;
• spiral(1) выполняет поворот на 90 градусов против часовой стрелки;
• spiral(1) вызывает spiral(2);
• spiral(2) чертит отрезок, равный по длине двум единичным и направленный влево;
• spiral(2) выполняет поворот на 90 градусов против часовой стрелки;
• spiral(2) вызывает spiral(3);
• и т.д.

Постепенно благодаря программе появляется спиральная кривая, изображенная на рис. 12.1.

Рис. 12.1 Результат вызова spiral(1)

Маленькие трудности

Ну ладно. Здесь ситуация не такая серьезная, как с Аполлоном-13, когда на пути к Луне прорвало его главный кислородный бак. Но и мы тоже испытываем трудности: наша маленькая программа от нас "убегает". Она все продолжает и продолжает вызывать сама себя и чертит все большие и большие отрезки. Программа будет делать это до тех пор, пока компьютер, пытающийся ее выполнить, не исчерпает свои ресурсы и не выведет на экран сообщение об ошибке. А если вам не повезет, то компьютер просто зависнет.

Сбой недопустим

Такой сценарий развития событий показывает одну из опасностей, связанных с использованием рекурсии. Программа, написанная для того, чтобы обращаться к себе самой, вызывает на выполнение свой новый экземпляр, а тот, в свою очередь, вызывает еще один, и так до бесконечности. Обычно это не то, что нужно. Чтобы решить проблему, программисты помешают в рекурсивную функцию условие завершения — предел того, насколько глубоко должна зайти рекурсия. В результате программа выполняет нужные действия, а затем красиво завершается. Условие завершения мы можем поместить и в нашу программу черчения спиралей, чтобы сберечь ресурсы компьютера и избежать головокружения у программистов:

void spiral2(int segment)

{

    if (segment <= 10)

    {

        line(segment);

        left_turn(90) ,

        spiral2(segment+ 1) ;

    }

}

При вызове программа spiral2(l) выполняется и затем рекурсивно вызывает сама себя до тех пор, пока значение segment не превысит 10. Как только значение segment станет равным 11, конструкция if (segment <= 10) возвратит значение False, и код, находящийся во внутренних скобках, будет пропущен. Управление снова передается предыдущему вызову spiral2(l), а оттуда постепенно возвращается к самому первому вызову, после которого программа завершается.

Каждый раз, когда функция вызывает саму себя, она еще на один уровень удаляется от главной программы — места начала операции. Чтобы эта главная программа продолжила работу, самая последняя итерация (т.е. повторение выполнения) должна вернуть управление предпоследней — той, которая ее вызвала. Предпоследняя итерация обязана поступить точно так же, и процесс продолжается, пока управление не вернется в главную программу, в которой был сделан первый вызов рекурсивной функции.

Рекурсия — это мощный инструмент для повторного выполнения кода. Она идеально подходит для поиска в древовидных структурах, например, в файловых системах, сложных электронных схемах или многоуровневых распределенных сетях.

Что такое рекурсивный запрос

Рекурсивным называется запрос, который функционально зависит от себя самого. Самой простой формой такой функциональной зависимости является случай, когда внутри оператора запроса Q1 находится вызов этого же запроса. Более сложный случай будет тогда, когда запрос Q1 зависит от запроса Q2, который, в свою очередь, зависит от Q1. И сколько бы запросов ни находилось между первым и вторым вызовом одного и того же запроса, главное, чтобы имела место функциональная зависимость.

Где можно использовать запрос

Во многих трудных ситуациях рекурсивные запросы помогают сэкономить и время, и нервы. Предположим, например, что у вас есть пропуск, который дает право бесплатно летать любым авиарейсом воображаемой компании Vannevar Airlines. Неплохо, правда? И тут встает вопрос: Куда же можно бесплатно попасть? Все авиарейсы Vannevar Airlines перечислены в таблице FLIGHT (авиарейс), и для каждого из них указан его номер, начальный пункт и место назначения (табл. 12.1).

Таблица 12.1. Авиарейсы компании Vannevar Airlines

Чтобы начать реализацию своего плана проведения отпуска, создайте с помощью SQL в базе данных таблицу FLIGHT:

Как только таблица будет создана, ее можно заполнить данными из табл. 12.1.

Предположим, вы хотите лететь из Портленда к своему другу в Монтгомери. Естественно, что вы зададите себе вопросы: "В какие города я попаду самолетами Vannevar Airlines, если начинать с Портленда? А куда я смогу долететь самолетами этой же авиакомпании, если садиться на самолет в Монтгомери?" В некоторые города долететь без промежуточных посадок можно, а в другие — нельзя. По пути в некоторые города придется делать не менее одной такой посадки. Конечно, можно найти все города, куда самолеты Vannevar Airlines могут вас доставить из любого выбранного вами города просто, что называется, "в лоб". Но если вы будете искать города, выполняя один запрос за другим, то тогда вами выбран...

Трудный способ

Найти то, что хотите узнать, — при условии, что у вас есть терпение и время, — можно с помощью последовательности запросов, в первом из которых начальным пунктом является Портленд:

SELECT Destination FROM FLIGHT WHERE Source = "Portland";

Этот первый запрос возвращает Orange County, Charlotte и Daytona Beach. Первый из них, если хотите, можно сделать начальным пунктом уже во втором запросе:

SELECT Destination FROM FLIGHT WHERE Source = "Orange County";

В результате второй запрос возвращает Montgomery. В третьем же запросе можете снова использовать результаты первого запроса, взяв на этот раз в качестве начального пункта второй город:

SELECT Destination FROM FLIGHT WHERE Source = "Charlotte";

Этот запрос возвращает Memphis. Результаты первого запроса можно использовать ив четвертом, взяв в качестве начального пункта последний из этих результатов:

SELECT Destination FROM FLIGHT WHERE Source = "Daytona Beach";

Прошу прощения, четвертый запрос возвращает неопределенное значение — у Vannevar Airlines нет авиарейсов из Дейтона-Бич. Но в качестве начального пункта можете также использовать город (Montgomery), который возвращен вторым запросом, что и делается в очередном, пятом, запросе:

SELECT Destination FROM FLIGHT WHERE Source = "Montgomery";

В результате его выполнения возвращается Memphis, но для вас это не имеет значения. Вы еще раньше узнали, что в этот город попасть можно через Шарлотт. Но Мемфис в качестве начального пункта можно использовать в следующем запросе:

SELECT Destination FROM FLIGHT WHERE Source = "Memphis";

Этот запрос возвращает Champaign. Им также можно пополнить список городов, куда вы можете попасть (пусть даже с промежуточной посадкой). А так как вас интересуют авиарейсы и с промежуточными посадками, то в запросе в качестве начального пункта можно использовать и этот город:

SELECT Destination FROM FLIGHT WHERE Source = "Champaign";

Обидно! Запрос возвращает неопределенное значение; оказывается у Vannevar Airlines нет авиарейсов и из Шампейн. (Пока что семь запросов. Они еще не действуют кому-то на нервы?)

Конечно, с помощью этой авиакомпании из Дейтона-Бич улететь нельзя. Так что если вы туда попадете, то там и застрянете. Впрочем, если это случится во время пасхальных каникул — а они, как известно, длятся целую неделю, то особой беды не будет. (Но если вы, чтобы узнать, куда еще можно долететь, будете неделю напролет запускать на выполнение один запрос за другим, то заработаете головную боль похуже, чем от недельного загула.) Или, возможно, застрянете в Шампейн. В этом случае вы можете, кроме всего прочего, поступить в Университет штата Иллинойс и прослушать в нем пару курсов по базам данных.

Конечно, когда-нибудь, со временем, этот метод даст исчерпывающий ответ на вопрос: В какие города можно попасть из Портленда? Но отправлять на выполнение один запрос за другим, при этом составляя каждый из них (кроме самого первого) на основе результатов предыдущего, — это работа сложная, требующая много времени, и, скажу прямо, нудная.

Экономия времени с помощью рекурсивного запроса

Получить нужную информацию будет проще, если создать единственный рекурсивный запрос, который сделает всю работу за одну операцию. Вот его синтаксис:

WITH RECURSIVE

    ReachableFrom (Source, Destination)

        AS (SELECT Source, Destination

                FROM FLIGHT

            UNION

            SELECT in.Source, out.Destination

                FROM ReachableFrom in, FLIGHT out

                WHERE in.Destination = out.Source

             )

    SELECT * FROM ReachableFrom

    WHERE Source = "Portland";

В начале первого прохода, выполняемого во время рекурсии, в таблице FLIGHT будет семь строк, а в ReachableFrom (означает "можно попасть из") — ни одной. Оператор UNION берет семь строк из FLIGHT и копирует их в таблицу ReachableFrom. Тогда в ReachableFrom появятся данные, показанные в табл. 12.2.

Таблица 12.2. Таблица ReachableFrom после одного прохода рекурсии

Интересное начнется уже при втором проходе. Предложение WHERE (WHERE in. Destination = out. Source)означает, что просматриваются только те строки в которых поле Destination таблицы ReachableFrom равно полю Source таблиш FLIGHT. Для каждой такой строки берутся значения поля Source из ReachableFrom и пол Destination из FLIGHT, а затем в качестве новой строки добавляются в ReachableFrom. Результат этого прохода показан в табл. 12.3.

Таблица 12.3. Таблица ReachableFrom после двух проходов рекурсии

Эти результаты выглядят намного более полезными. Теперь в таблице ReachableFrom поле Destination содержит все города, в которые можно попасть из любого города, находящегося в поле Source той же таблицы, делая при этом не более одной промежуточной посадки. Затем во время следующего прохода рекурсия обработает маршруты с двумя промежуточными посадками и будет так продолжать до тех пор, пока не будут найдены все города, куда только можно попасть.

После завершения рекурсии третий и последний оператор SELECT (который в рекурсии не участвует) выделяет из ReachableFrom только те города, в которые можно попасть из Портленда. В этом примере можно попасть во все остальные шесть городов, причем с достаточно малым числом промежуточных посадок. Так что вам не придется метаться, как будто вы скачете на ходуле с пружиной.

Если вы внимательно изучите код рекурсивного запроса, то увидите, что он не выглядит проще, чем семь отдельных запросов. Однако у этого запроса есть два преимущества:

• после его запуска постороннее вмешательство больше не требуется;
• он быстро работает.

Если можете, представьте себе настоящую авиакомпанию, у которой на карте ее маршрутов находится намного больше городов. И чем больше возможных мест назначения, тем больше пользы от рекурсивного метода.

Что же делает запрос рекурсивным? То, что мы определяем таблицу ReachableFrom на основе ее самой. Рекурсивной частью определения является второй оператор SELECT, который расположен сразу после UNION. ReachableFrom — это временная таблица, которая наполняется данными по мере выполнения рекурсии. И это наполнение продолжается до тех пор, пока все возможные пункты назначения не окажутся в ReachableFrom. Повторяющихся строк в этой таблице не будет, потому что туда их не пропустит оператор UNION. Когда рекурсия завершится, в таблице ReachableFrom окажутся все города, в которые можно попасть из любого города-начального пункта. Третий и последний оператор SELECT возвращает только те города, в которые вы можете попасть из Портленда. Так что желаем приятного путешествия.

Где еще можно использовать рекурсивный запрос

Любая задача, которую можно представить в виде древовидной структуры, поддается решению с помощью рекурсивного запроса. Классическим примером того, как такие запросы используются в промышленности, является обработка материалов (процесс превращения сырья в конечный продукт). Предположим, ваша компания выпускает новый гибридный бензи-ново-электрический автомобиль. Такую машину собирают из узлов (двигателя, батарей и т.п.), которые, в свою очередь, состоят из меньших подузлов (коленчатого вала, электродов и пр.), а те — из еще меньших компонентов. Данные обо всех этих компонентах компонентов сохранять в реляционной базе очень трудно — если, конечно, в ней не используется рекурсия. Рекурсия дает возможность, начав с целой машины, добраться любым путем к самой малой детали. Хотите найти данные о крепежном винте, который держит клемму отрицательного электрода вспомогательной батареи? Это можно — и причем без особых затрат времени. Справляться с такими задачами SQL может с помощью структуры WITH RECURSIVE (рекурсивный оператор).

Кроме того, рекурсия вполне естественна при анализе "что, если?". Например, что произойдет, если руководство авиакомпании Vannevar Airlines решит прекратить полеты ю Портленда в Шарлотт? Как это повлияет на полеты в те города, куда сейчас можно добраться кз Портленда? Рекурсивный запрос незамедлительно даст ответ на эти вопросы.