egorius

А вот попробуем решить на 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, то есть за выбор конкретного алгоритма, отвечает оптимизатор. В свое время не верили в то, что оптимизатор может составить конкуренцию программе, написанной вручную (а еще раньше не верили в то, что языки програмирования высокого уровня смогут составить конкуренцию ассемблеру), но, охотно признаю: глупо рассчитывать на то, что оптимизатор найдет эффективное решение совершенно нетипичной для баз данных задачи.

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

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

Для этого, в первую очередь, надо задать лабиринт в виде матрицы. Например, так:

with maze_matrix(linenum, line) as (
  select 1, 's#   ' from dual union all
  select 2, '   # ' from dual union all
  select 3, ' #   ' from dual union all
  select 4, ' # # ' from dual union all
  select 5, '   #e' from dual
)
select    '|'||line||'|'
from      maze_matrix
order by  linenum;

|s#   |
|   # |
| #   |
| # # |
|   #e|

Теперь надо перевести это представление в наш реляционный вид:

with maze_matrix(linenum, line) as (
  ...
),
maze_relation(linenum, colnum, cell) as (
  select   m.linenum,
           t.column_value,
           substr(m.line, t.column_value, 1)
  from     maze_matrix m,
           table(cast(multiset(
             select level from dual connect by level <= length(m.line)
           ) as sys.odcinumberlist)) t
)
select    *
  from    maze_relation;

Хитрой конструкцией cast multiset я уже «восхищался», поэтому не буду подробно на ней останавливаться. Скажу только, что благодаря ей лабиринт может быть и не прямоугольным.

Теперь можно искать путь. В отличие от предыдущего варианта, где нас устраивало решение в виде простой строки, здесь мы хотим получить множество всех ячеек, составляющих путь. Это несколько сложнее: сначала (solutions) получим все ячейки, составляющие все возможные пути, а затем (solution) оставим только те, которые относятся к кротчайшему.

with maze_matrix(linenum, line) as (
  ...
),
maze_relation(linenum, colnum, cell) as (
  ...
),
solutions(linenum, colnum, cell, len, path) as (
  select   m.linenum,
           m.colnum,
           m.cell,
           level,
           sys_connect_by_path(m.linenum||','||m.colnum,' - ')
  from     maze_relation m
  start with
           m.cell = 's'
  connect by nocycle
           m.cell != '#'
       and prior m.cell != 'e'
       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)
           )
),
solution(linenum, colnum) as (
  select   s.linenum,
           s.colnum
  from     solutions s,
           (
             select   min(path) keep (dense_rank first order by len) path
             from     solutions
             where    cell = 'e'
           ) best
  where    instr(best.path, s.path) > 0
)
select   *
from     solution;

Дело за малым: осталось показать найденный путь в лабиринте и преобразовать наше реляционное представление обратно в матрицу. Для преобразования удобно использовать агрегатную функцию конкатенации listagg (опять же затуманенную синтаксисом).

with maze_matrix(linenum, line) as (
  ...
),
maze_relation(linenum, colnum, cell) as (
  ...
),
solutions(linenum, colnum, cell, len, path) as (
  ...
),
solution(linenum, colnum) as (
  ...
),
maze_relation_solved(linenum, colnum, cell) as (
  select   m.linenum,
           m.colnum,
           case when s.linenum is null then m.cell else '*' end
  from     maze_relation m
  left join
           solution s
        on s.linenum = m.linenum
       and s.colnum = m.colnum
       and m.cell = ' '
),
maze_matrix_solved(linenum, line) as (
  select   m.linenum,
           listagg(m.cell) within group (order by m.colnum)
  from     maze_relation_solved m
  group by m.linenum
)
select   '|'||line||'|'
from     maze_matrix_solved
order by linenum;

|s#   |
|***# |
| #***|
| # #*|
|   #e|

Обратите внимание, что это по-прежнему signle SQL statement. Хотя его размер существенно увеличился, благодаря активному использованию with код остался хорошо структурированным и понятным. К тому же всегда можно посмотреть, какие данные мы получаем на том или ином этапе, не прибегая к журналированию или, боже упаси, к отладчику.