?

Log in

No account? Create an account

Вс, 23 мар, 2014, 03:00
В стиле SQL - 1 (умножение матриц)

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

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

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

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

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

Напомню, что произведением матрицы A(L×M) на матрицу B(M×N) является матрица С(L×N), элементы которой ci,j = Σk = 1...M  ai,k×bk,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;

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

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

Вс, 23 мар, 2014 15:51 (UTC)
hardsign

да вот за одно такое представление® матриц надо отлучать от компьютера на три года с конфискацией

Вс, 23 мар, 2014 19:44 (UTC)
egorius

Для разреженных матриц это не такое уж и представление®. А другие предложения?
(В любом случае, это простой красивый пример, а не задача, типичная для БД. Но на чем учиться, как не на простых красивых примерах?)

Пн, 24 мар, 2014 05:39 (UTC)
hardsign

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

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

Вт, 25 мар, 2014 20:32 (UTC)
egorius

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