В стиле SQL - 1 (умножение матриц)

[egorius]

Часто приходится видеть, как разработчик, столкнувшись с задачей, первым делом берется за привычный процедурный инструмент, даже не вспомнив про мантру Кайта:

You should do it in a single SQL statement if at all possible.

Откуда такая мантра? Во-первых, процедурный подход оперирует циклами, а SQL — множествами. База данных может работать с множествами на порядок эффективнее, чем с помощью циклов; это лишь один способ из целого арсенала, которым располагает СУБД. Во-вторых, декларативный подход описывает желаемый результат, а процедурный — точный способ достижения этого результата. Поэтому декларативная программа зачастую оказывается короче и проще.

Почему же предпочтение отдается PL/SQL? Тут можно было бы порассуждать об эффективности, но, на мой взгляд, реальная причина проще: декларативный подход требует смены парадигмы программирования, а это дается нелегко.

Хочу начать эту серию заметок с простого примера, эффективно взрывающего процедурно настроенный мозг, а именно с умножения матриц.

Напомню, что произведением матрицы A(L×M) на матрицу B(M×N) является матрица С(L×N), элементы которой c_i,j = Σ_{k = 1...M}  a_i,k×b_k,j. Для иллюстрации процедурного подхода возьмем следующие определения (я использовал язык Си):

int a[L][M];
int b[M][N];
int c[L][N];

Алгоритм традиционен и хорошо иллюстрирует вышеизложенную мысль про циклы:

int i, j, k;
for (i=0; i<L; i++)
  for (j=0; j<N; j++)
    for (k=0; k<M; k++)
      c[i][j] += a[i][k] * b[k][j];

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

create table a(
  rw  number,
  cl  number,
  val number
);
create table b(
  rw  number,
  cl  number,
  val number
);

И вот как выглядит запрос, выдающий произведение в том же формате:

select   a.rw,
         b.cl,
         sum(a.val * b.val)
from     a,
         b
where    a.cl = b.rw
group by a.rw,
         b.cl;

Запрос стоит внимательно изучить и понять. С непривычки это совсем даже непросто. Здесь нет циклов: запрос оперирует множествами элементов и их соединением. Здесь нет размерности матрицы. Здесь не нужно хранить в таблице нулевые элементы.

Но после того, как мозг взорвался, код ставится очевидным и ничуть не более сложным, чем процедурный. Это важный момент.

Comments

[hardsign.livejournal.com]

Ну, это для очень-очень сильно разреженных матриц® (а также обширных матриц и кровавых матриц ЕВПОЧЯ).

А примеры, на мой взгляд, должны отражать реальную жызнь¤ Использовать для матриц реляционные СУБД - это как-то вообще не comme il fautъ.

[egorius.livejournal.com]

Ну как бы должны, но не совсем. Реальные задачи обычно большие и сложные, а примеры хочется ясные и короткие. Да и для расширения горизонтов полезно попробовать инструмент не по делу, побаловаться.