В стиле SQL - 2 (перебор вариантов)

А вот попробуем решить на SQL какую-нибудь типично процедурную задачу. Скажем, поиск пути в лабиринте, чтобы было не скучно.

Для этого придумано много разных алгоритмов, один другого лучше. Для примера сошлюсь на волновой алгоритм; там и код программы приведен: циклы, циклы и еще раз циклы.

Как подойти к проблеме с реляционной стороны? Во-первых, лабиринт надо представить так, как мы делали в прошлый раз с матрицей: в виде отношения, содержащего номер строки, номер столбца и значение в ячейке.

create table maze_relation(
  linenum number,
  colnum  number,
  cell    varchar2(1)
    check(   cell = ' ' -- пусто
          or cell = '#' -- стена
          or cell = 's' -- начало
          or cell = 'e' -- конец
         )
);

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

Такого рода рекурсивные алгоритмы прекрасно соответствуют иерархическим запросам SQL. Условия первой итерации попадают во фразу start with, условия следующих итераций — в connect by (с указанием nocycle, чтобы алгоритм не ходил кругами). Отбор подходящих вариантов задается в where. Восстановление пути волнового алгоритма превращется в простой вызов функции sys_connect_by_path: если представить иерархический запрос как рекурсивный алгоритм, то эта функция возвращает не что иное, как стек возвратов.

with solutions as (
  select  sys_connect_by_path(m.linenum||','||m.colnum,' - ') path,
          level len
  from    maze_relation m
  where   m.cell = 'e'
  start with
          m.cell = 's'
  connect by nocycle
          m.cell != '#'
      and (
            (m.linenum = prior m.linenum + 1 and m.colnum = prior m.colnum) or
            (m.linenum = prior m.linenum - 1 and m.colnum = prior m.colnum) or
            (m.linenum = prior m.linenum     and m.colnum = prior m.colnum + 1) or
            (m.linenum = prior m.linenum     and m.colnum = prior m.colnum - 1)
          )
)
select  min (path) keep (dense_rank first order by len)
from    solutions;

Получив в подзапросе solutions все пути, мы отобраем из них самый короткий. Это можно сделать с подзапросом, а можно воспользоваться keep dense_rank. Смысл конструкции, изрядно затуманенный синтаксисом, прост: отобрать значение path, соответствующее минимальному значению len (если таких будет несколько, останется только одно благодаря min).

Собственно, все. По-моему, весьма поучительно сравнить объем кода с тем же волновым алгоритмом.

Естественно, простота решения не дается даром: в жертву приносится эффективность. За эффективность SQL, то есть за выбор конкретного алгоритма, отвечает оптимизатор. В свое время не верили в то, что оптимизатор может составить конкуренцию программе, написанной вручную (а еще раньше не верили в то, что языки програмирования высокого уровня смогут составить конкуренцию ассемблеру), но, охотно признаю: глупо рассчитывать на то, что оптимизатор найдет эффективное решение совершенно нетипичной для баз данных задачи.

Зато наше решение спокойно работает и в случае нескольких точек входа и выхода. Попробуйте-ка изменить волновой алгоритм, чтобы он позволял такое.

Но развлекаться — так развлекаться. Давайте сделаем решение этой задачи наглядным!

( продолжаем разговор )