Формирование многомерных данных с использованием промежуточных представлений

УДК 519.72

ФОРМИРОВАНИЕ МНОГОМЕРНЫХ ДАННЫХ С ИСПОЛЬЗОВАНИЕМ ПРОМЕЖУТОЧНЫХ ПРЕДСТАВЛЕНИЙ1

C.B. Зыкин, А.Н. Полуянов

Рассмотрена проблема автоматизации формирования многомерных таблиц данных из исходной реляционной базы данных с произвольной схемой. Для формирования размерностей таких таблиц предложено использовать ранее сформированные системой представления данных. Возможность повторного использования представлений определяется путем вычисления областей истинности логических выражений.

Ключевые слова: многомерная таблица, реляционная база данных, домен.

ВВЕДЕНИЕ

Технологии аналитической обработки данных (OLAP) сформировались как направление исследований в середине 1990-х г. [1] и в настоящее время служат основой информационной поддержки принятия решений. За прошедшие годы в этой области были получены значительные фундаментальные [2—4] и прикладные [5—8] результаты.

Основное внимание в данной работе уделяется проблеме динамического формирования многомерных таблиц из реляционных баз данных (РБД) с помощью зарезервированных представлений данных на компьютере пользователя, оснащенном графическим процессором (GPU). Эта проблема связана с детально исследованной и получившей широкое применение на практике области оптимизации запросов, поскольку нацелена на сокращение объема передаваемых данных с сервера БД. Зарезервированные данные достаточно активно используются на практике в системах управления базами данных (СУБД). Однако в большинстве случаев это относится к повторному использованию блоков данных, предварительно записанных в буферный пул, без какого-либо предварительного анализа содержимого блоков на предмет возможности частичного или комбинированного использования сохраненных в них данных. Работа СУБД ограничивается тем, что при выполнении очередного запроса блоки данных не запрашиваются с

1 Работа выполнена при финансовой поддержке РФФИ (проект № 12-07-00066-а).

внешних устройств, если они есть в буферном пуле, т. е. анализируются номера блоков, а не их содержимое. Наиболее продвинутое решение существует в СУБД Oracle благодаря применению повторно используемых SQL-операторов. Сервер Oracle предварительно просматривает разделяемый пул в поисках готового результата. К недостаткам такого подхода следует отнести необходимость создания вручную запросов с повторяющимися SQL-операторами и отсутствие возможности частичного и комбинированного использования сохраненных результатов в автоматическом режиме.

В области теоретических исследований ситуация складывается следующим образом. Огромное число публикаций посвящено проблеме построения оптимального плана запроса на основе формальных правил, в которых не используются области определения предикатов в SQL-операторах (логическая оптимизация) либо эти области учитываются при вычислении статистических оценок для оптимизации физического доступа к БД. Близкими по методам решения являются задачи выполнения запросов на потоках данных [9, 10], однако различные, по сравнению с настоящей работой, цели приводят к различным результатам. Наиболее близка к рассматриваемой проблеме работа [11]. В ней рассматриваются конъюнктивные запросы над доменами данных с предикатами в виде арифметических сравнений и представлены алгоритмы вычисления запросов с использованием существующих представлений. В настоящей работе рассматривается специальный вид универсального реляционного запроса над отношениями базы данных, а не над отдельными доменами. Хотя цели

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

1. ПОСТАНОВКА ЗАДАЧИ

В работе [12] для автоматизации формирования многомерной таблицы (гиперкуба) предлагается использовать последовательность преобразований

RDB ^ TJ ^ GC,

где RDB — реляционное представление данных, TJ — таблица соединений, GC — гиперкуб (далее соответствующие модели будут формально определены). В данном случае RDB — представление исходной модели данных, GC — целевой. Наличие промежуточного представления TJ позволяет динамически управлять содержимым гиперкуба благодаря определению контекстных ограничений и логическим ограничениям на данные.

Рассмотрим формализацию задачи. Пусть задана схема базы данных RDB: R = {Rp R2, ..., Rk}, полученная в результате нормализации отношений [13, 14]. Отношения R. определены на множестве атрибутов U = {А1, А2, ..., An}. Пусть (R;) — схема отношения, множество атрибутов, на которых определено отношение R. Предположим, что схема R является редуцированной [14], т. е. не существует двух отношений таких, что (R.) с (R;), i ^ j.

* J

Кортеж t[X — совокупность значений атрибутов А. е X с (R), заданных в кортеже t е R.. Неопре-

J I I

деленное значение NULL атрибута А. в кортеже t: t[Aj] = NULL не равно любому другому значению, в том числе другому неопределенному значению. Результат сравнения (арифметического, строкового и т. д.) с неопределенным значением дает значение UNKNOWN.

Определим размерности: {Dj, D2, ..., Dd}, d > 0, где Dl — упорядоченное, в соответствии с иерархией (сначала корневой атрибут, затем его потомок и т. д.), множество расширенных имен атрибутов: R.. А., А. е (R.). Каждая размерность считает* J J *

ся координатой в многомерном пространстве. Реализацией размерности служит некоторое отношение, упорядоченное в соответствии с иерархией (сначала по корневому атрибуту, затем по его потомку и т. д.) множество кортежей, определенное на множестве атрибутов D. Каждый кортеж реализации размерности является отсчетом на соответствующей координате. Для каждой размерности задается ограничение в виде логической формулы F, переменными в которой являются расширенные имена атрибутов. Атрибуты в выражении Fl могут

не принадлежать размерности Dl, а ограничение будет задаваться опосредованно, за счет контекстов. Пусть M — непустое множество мер, заданных в виде расширенных имен атрибутов. Реализацией мер служит некоторое отношение, т. е. множество кортежей, определенное на множестве атрибутов M.

Определение 1. Гиперкубом будем называть модель логического многомерного представления данных, где каждому кортежу реализации M соответствует ровно один кортеж каждой реализации D. ♦

Формальные определения гиперкубов в работах [2—4] представлены через определение операций над ними и явное ограничение в виде функциональной зависимости мер от размерностей:

D1D2"Dd ^ M

В настоящей работе не предполагается наличие этого ограничения, что позволит использовать содержательные, как правило, не ключевые атрибуты в размерностях [15]. В результате в одной ячейке гиперкуба будет несколько значений

атрибута R. .А. е M. Это не отвергает применения

* J

традиционных операций с гиперкубами, например, drill down и roll up, но потребует иной их реализации. Кроме того, все представление становится более компактным по причине меньшего числа ячеек в рабочей области гиперкуба.

Пример 1. Рассмотрим фрагмент схемы базы данных вуза:

Специальности (Номер специальности, Специальность),

Предметы (Номер предмета, Предмет),

Учебная нагрузка (Номер специальности, Номер предмета, Семестр, Вид занятия, Количество часов),

Контроль (Номер специальности, Номер предмета, Семестр, Контроль успеваемости),

где закурсивлены ключевые атрибуты отношений. Одно из возможных представлений гиперкуба приведено в таблице.

В таблице атрибуты размерностей представлены жирным шрифтом, атрибуты мер — курсивом, значения атрибутов — обычным шрифтом.

Схема гиперкуба в таблице может быть представлена в виде:

{Специальности.Специальность} s {Учебная_нагрузка.

Семестр {Предметы.Предмет {Учебная_нагрузка.

Вид_занятия (Учебная_нагрузка.Количество_часов)} (Контроль.Контроль_успеваемости)}},

где D1 = {Специальности.Специальность} и D2 = {Учеб-ная_нагрузка. Семестр {Предметы.Предмет {Учебная_ нагрузка. Вид_занятия}}} — размерности, M = {Учеб-ная_нагрузка.Количество_часов,Контроль.Контроль_ус-певаемости} — меры.

Логическое ограничение: F = (Контроль.Семестр = 2 л (Предметы.Предмет = 'Математика' v Предметы. Предмет = 'Физика')).

Фрагмент учебного плана в вузе

Семестр 2

Предмет Математика Физика

Вид занятия Лекции Практика Лабораторные работы Контроль успевае- Лекции Практика Лабораторные работы Контроль успевае-

Специальность Кол-во часов мости Кол-во часов мости

История 36 36 18 Зачет, экзамен 18 18 18 Зачет

Филология 18 18 18 Зачет 36 36 18 Зачет, экзамен.

Правоведение 48 48 24 Зачет, экзамен 48 48 24 Зачет, экзамен

В таблице размерность D2 имеет два терминальных уровня {Предметы.Предмет} и {Учебная_нагрузка.Вид_ занятия}, так как каждый из них имеет собственную сопоставленную меру, хотя между ними установлено иерархическое подчинение. ♦

При формировании представления в примере 1 использовались так называемые контексты и таблица соединения, определение и способ формирования которых рассматриваются далее. Предлагается не ограничивать пользователя в выборе структуры гиперкуба, а только подсказывать ему корректные решения по формированию гиперкуба при заданных мерах и размерностях.

2. ФОРМИРОВАНИЕ КОНТЕКСТОВ

Кратко рассмотрим понятие контекста, правила и причины его формирования [15]. Пусть DEP — множество зависимостей (функциональных, многозначных, соединения и включения) на отношениях из R, C = {R1, R2, ..., Rm} — произвольное подмножество отношений RDB.

Определение 2. Множество C при m > 0 будем называть контекстом, если оно удовлетворяет свойству соединения без потерь информации (СБПИ) [13, с. 165, 14, с. 125] на зависимостях DEP.

Замечание 1. В основе контекста лежит операция естественного соединения, которая собирает из различных отношений БД связанные друг с другом по значению данные. Затем эти данные (кортежи) участвуют в формировании новых структур, естественным образом дополняя и ограничивая друг друга, что делает уместным употребления термина «контекст» для совокупности таких значений.

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

* }

Яг — наименование отношения из исходной реляционной БД, и А. — наименование атрибута в этом отношении. Таким образом, будет задано началь-

" d0 Г D° D°

ное множество отношений R = {R1, R2,

R0

участвующее в обязательном порядке сначала в формировании таблицы соединения, а потом — гиперкуба. Совокупность отношений, по которым строится гиперкуб, должна удовлетворять свойству СБПИ [16], поскольку лишние кортежи в промежуточном представлении данных дают ошибочные значения в рабочей области гиперкуба. Следовательно, дальнейшая задача состоит в дополнении

множества R0 отношениями из R, чтобы результирующее множество удовлетворяло свойству СБПИ на множестве зависимостей DEP, т. е. являлось контекстом. В общем случае таких вариантов дополнения существует несколько. Каждый из вариантов (контекстов) имеет свою смысловую нагрузку, поэтому окончательный выбор контекста может выполнить только пользователь. В работе [14] предложен алгоритм последовательной генерации контекстов по сформулированным критериям, которые увеличивают вероятность более быстрого достижения результата.

Для решения проблемы дублирования значений в списках мер в работе [15] введено и обосновано понятие ключа KM. атрибута меры R..А. е M.

J I J

В существующих OLAP-системах, в том числе в «Microsoft Analysis Services» и «ORACLE Analytic Workspace Manager», свойство СБПИ не анализируется, что служит основной причиной ошибок

либо ограничений при формировании представлений гиперкубов.

В терминах реляционной алгебры выражение для контекста имеет вид:

77(C) = Ma/RM^M ...X RJ),

где С = {Лр Л2, ..., Лт}, пх — проекция по атрибутам X (вырезка по столбцам), ар — селекция (вырезка по строкам), XI — операция естественного соединения. Выражение (1) может быть преобразовано к оптимальному виду с учетом свойств операций реляционной алгебры [13, 14]. В данной работе предлагается использование единичных представлений Т/(С) для формирования размерностей, а не их комбинаций, поэтому преобразование выражения (1) будет дублировать функции СУБД по оптимизации запроса.

В работе [15] предложен алгоритм формирования гиперкуба БС из совокупности представлений ТДС^) с раздельным формированием размерностей. Это позволяет эффективно управлять содержимым БС, при этом гарантируется его корректность: в рабочей области присутствуют все значения, соответствующие текущему состоянию ЛОБ, и отсутствуют избыточные значения.

3. ИССЛЕДОВАНИЕ СВОЙСТВ ПРОМЕЖУТОЧНЫХ ПРЕДСТАВЛЕНИЙ ДАННЫХ

Промежуточные представления данных обозначим как Р = {Рр Р2, ..., Рт}, где Ру =

= лх>рД Л2>0-.К" )), ¿(V) — количество отношений в базе данных, использованных при формировании контекста Л = {Я\, Л2, ..., Л

V

и

затем использовавшихся для формирования представления данных Ру. В терминах отображений это есть инъекция пар индексов в конечное множество натуральных чисел: {(V, 1), (V, 2), ..., (V, ¿(V))} ^ {1, 2, ..., к}, где к — общее количество отношений в базе данных, V = 1...т. Целевое выражение, которое надо будет получить из представлений Р, запишем в виде:

P* = nX*(aF*(R* XR*X...XR*)),

что соответствует выражению в формуле (1). Пусть Dom(Fv) — область определения логического выражения F, т. е. область значений переменных величин в формуле, для которых она принимает значение TRUE. Формула Fv состоит из логических операций, в которых явным образом специфици-

рованы расширенные имена атрибутов R..А. (атри-

* J

бут А. в отношении R.): Ji

• операция сравнения Exprl 9 Expr2, 9 — операция сравнения (9 е {=, ф, >, <, >, <}), Expr. — согласованные по типам допустимые выражения, определенные на множестве расширенных имен атрибутов и констант;

• операция Exprl [NOT] BETWEEN Expr2 AND Expr3 (содержимое в прямоугольных скобках [•] для предиката не является обязательным при написании);

• операция Expr [NOT] IN S, где S — список значений либо подзапрос, результатом которого

является столбец атрибута А. в отношении R.;

Ji

• операция Strl [NOT] LIKE Str2, где Str. — строки;

• операция Expr 9 ALL/ANY S. Перечисленные варианты операций используют не все возможности языка SQL. Например, предикат EXISTS не используется, поскольку в нем явно не специфицированы расширенные имена атрибутов, предикат NULL используется в данной работе для другой цели. Сложность компонентов предикатов Expr, S и Str определяется возможностями программного обеспечения по вычислению областей определения Dom(Fv), что необходимо для вычисления TJ(CS) из промежуточных представлений Pv.

При вычислении логического выражения Fv может быть получено значение UNKNOWN, если на текущем кортеже t атрибут принимает значение NULL, поскольку результаты вычисления логических выражений в SQL-запросах соответствуют трехзначной логике. Это приводит к неоднозначной интерпретации результата не только обычными пользователями, но и опытными программистами. Для решения этой проблемы предлагается ограничение: каждому атрибуту, входящему в F *, явно присваивается признак «Использование неопределенного значения» с двумя взаимоисключающими значениями «Да» или «Нет». Семантика этого признака такова, что если ему присвоено значение «Да», то появление значения NULL для указанного атрибута в текущем кортеже t не служит основанием удаления этого кортежа из дальнейшего рассмотрения. В противном случае значение признака «Нет» гарантирует, что появление значения NULL для указанного атрибута в текущем кортеже t приведет к удалению этого кортежа из дальнейшего рассмотрения. Далее будем полагать, что все атрибуты формулы F* принадлежат множеству X*.

Пусть формула F* в выражении (2) имеет следующий вид: F*(..., Q, ...), где Q. — элемен-

тарные операции. Тогда после предложенного преобразования она примет следующий вид: F*(..., Ql, ...)aJRA* NULL), где aJR.A. * NULL) — конъюнкция по всем атрибутам формулы F *, для которых не допустимо значение NULL. Операция Q = (Q^JR.A = NULL)), где vjR.A.* NULL) — дизъюнкция по всем атрибутам предиката Q, для которых допустимо значение NULL. Внешние скобки для предиката Q'l определяют приоритет выполнения операций. Несложно убедиться, что в рамках трехзначной логики преобразованная формула принимает только значения TRUE и FALSE. Кроме того, несложно убедиться, что в рамках двузначной логики, когда в кортежах отсутствуют неопределенные значения, исходная формула F * будет эквивалентна преобразованной формуле, поэтому семантика представления P* практически не искажается. Для раскрытия термина «практически» рассмотрим наиболее неудобный пример: пусть F* = Rj.A2 > 3 v R3.A4 < 4 и на кортеже t атрибут Rj.A2 принимает допустимое значение NULL, а предикат R3.A4 < 4 принимает значение FALSE.

Тогда преобразование формулы F* на кортеже t будет иметь значение TRUE, что не совсем очевидно. Далее будем предполагать, что все формулы F * и Fv являются преобразованными.

Рассмотрим проблему вычисления представления данных P* из существующих промежуточных представлений Pv.

Теорема 1. P * с nz*(aF*(Pv)), если:

а) X* с X,

б) {R\, R2, ..., RV(v)} с {R*, R*, ..., R*},

в) Dom(F *) с Dom(Fv).

Доказательство. Пусть существует кортеж t* е Р*. По условию теоремы надо показать, что t* е nX»(aF »(Pv)). Из условия t* е Р* следует, что существует кортеж t' е RjXlRjM..^R* и t*[X*] = t'[X*]. Следовательно, существуют кортежи t* е R*:

t* [< R* >] = t' [< R* >], i = 1, ..., /,

и для любых пар г и у, для которых (Л*) п (Я*) * 0, выполнено:

г*[<Я*) п <Я*)] = г/[<Я*) п< Я*)], г,у = 1, ..., /.

Поскольку условия (3) и (4) выполнены для всего множества отношений {Я *, Я2*, ..., Я*}, то они выполнены для любого его подмножества, в том числе для

{Я1, Я2 , ..., Я^ }. Следовательно, кортежи г* из отношений Я1', при выполнении операции естественного со-

единения образуют кортеж t", для которого выполнено: t' [Xv] = t" [Xv]. Поэтому t" [X*] = t' [X*] = t *[X*].

Из условия t* е P* следует, что F*(t') = TRUE. Поскольку Dom(F *) с Dom(Fv), то формулы F * и Fv определены на атрибутах, общих для кортежей t" и t"", следовательно, Fv(t'') = TRUE. Это значит, что

t" е R1 МR^XI...XRsv(v) и t* = t"[X*] е nX„(aF„(Pv)). ♦

Замечание 2. Предложенные в теореме 1 условия гарантируют, что данные, необходимые для формирования представления P*, содержатся в промежуточном представлении Pv. Однако, в нем могут быть лишние кортежи, которые дают значение TRUE при подстановке в формулу F *. Дело в том, что эти кортежи будут удалены при выполнении операции естественного соединения с отношениями, которых не хватает в множестве {R\, R22, ..., Rvs(y)} для

совпадения с множеством {R*, R*, ..., R*}. Используя области определения атрибутов в Pv, по которым выполняется соединение, у СУБД можно запросить минимально необходимый набор данных для определения лишних кортежей.

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

Теорема 2. P* = nX*(aF*(Pv)) тогда и только тогда, когда:

а) X* с Xv,

б) {Ri, R2, ..., R(v)} = {R*, R2, ..., R*},

в) Dom(F*) с Dom(Fv).

Доказательство. Поскольку условия теоремы являются частным случаем теоремы 1, то включение Р* с nX»(ap,(Pv)) доказано. Необходимо показать, что nX»(aF»(Pv)) с Р*. Пусть кортеж tv е nX»(aF»(Pv)). Покажем, что tv е Р*. Из условия tv е nX»(aF»(Pv)) следует, что

существует кортеж t' е R^ XIR^ X...XRj(V) и tv = t'[X*]. По свойству операции естественного соединения R^X R^X ...X RV(v) = R*X R|X ...X R*, следовательно,

t' е R*X R^X...X R*. Из условий tv е nX»(aF»(Pv)) и Dom(F*) с Dom(Fv) следует, что F*(t) = TRUE, а значит tv е P*. ♦

Замечание 3. Выполнение условий теорем 1 и 2 не представляет собой исключительный случай, поскольку набор размерностей при формировании гиперкубов изменяется редко, что позволит формировать эти размерности из промежуточных представлений без обращения к СУБД. Кроме того, используя области определения атрибутов в Pv, у СУБД можно запросить минимально необходимый набор данных для определения значений мер в рабочей области гиперкуба.

ЗАКЛЮЧЕНИЕ

Основной результат данной работы состоит в обосновании условий использования зарезервированных представлений данных для формирования новых гиперкубов. Эти представления данных могут храниться на компьютере пользователя-аналитика и существенно сократить время на формирование данных, необходимых для принятия решений.

Традиционная проблема в системах, работающих не под управлением СУБД, заключается в актуализации данных, полученных из БД. В технологии МОЬДР она решается путем периодической актуализации содержимого гиперкуба службой сопровождения. Аналогичный способ может быть применен для актуализации представлений Р . Для сокращения времени актуализации возможно получить доступ к журналу изменений, который сопровождает СУБД, и актуализировать только те представления, для которых изменились исходные данные в БД. Однако еще раз отметим, что данные, используемые в размерностях гиперкуба, обычно редко модифицируются в БД.

Предлагаемый подход подразумевает в дальнейшем применение графических процессоров для выполнения промежуточных операций фильтрации и соединения различных представлений данных. Исследования в этой области [17, 18] показали, что операции на графическом процессоре выполняются существенно быстрее, чем на центральном процессоре, для небольших объемов данных. При увеличении объемов производитель -ность падает. Причина очевидна: пока данные помещаются в быструю память графического процессора, операции с ними выполняются быстро. При увеличении объемов данных появляется необходимость их многократного перемещения между различными видами памяти, что снижает производительность. С одной стороны, производители графических процессоров постоянно наращивают быструю память, с другой — повторное использование данных наиболее актуально для размерностей многомерных таблиц, для которых требуется сравнительно небольшой объем памяти, что в совокупности делает целесообразным применение графических процессоров при решении указанной проблемы.

ЛИТЕРАТУРА

1. Codd E.F., Codd S.B., Salley C.T. Providing OLAP (On-line Analytical Processing) to User-Analysts: An IT Mandate. — Sunnyvale (CA): Codd & Date Inc., 1993. — 31 p.

2. Lechtenborger J, Vossen G. Multidimensional normal forms for data warehouse design // Inf. Syst. — 2003. — Vol. 28, N 5. — P. 415—434.

3. Lehner W., Albrecht J, Wedekind H. Normal forms for multidimensional databases // Proc. of the Tenth Intern. Conf. on Scientific and Statistical Database Management. — Capri, 1998. — P. 63—72.

4. Mazon J.-N., Trujillo J., Lechtenborger J. Reconciling requirement-driven data warehouses with data sources via multidimensional normal forms // Data & Knowledge Engineering. — 2007. — Vol. 63, N 3. — P. 725—751.

5. Vassiliadis P., Sellis T. A survey of logical models for OLAP databases // SIGMOD Rec. — 1999. — Vol. 28, N 4. — P. 64—69.

6. Pedersen T.B., Jensen C.S., Dyreson C.E. A foundation for capturing and querying complex multidimensional data // Inf. Syst. — 2001. — Vol. 26, N 5. — P. 383—423.

7. Progressive ranking of range aggregates / H.-G. Li, et al. // Data & Knowledge Engineering. — 2007. — Vol. 63, N 1. — P. 4—25.

8. Giorgini P., Rizzi S., Garzetti M. Goal-oriented requirement analysis for data warehouse design // Proc. of the 8th ACM international Workshop on Data Warehousing and OLAP: DOLAP '05. — Bremen, 2005. — P. 47—56.

9. Olston C, Jiang J., Widom J. Adaptive filters for continuous queries over distributed data streams // Proc. of the 2003 ACM SIGMOD Intern. Conf. on Management of Data (SIGMOD '03). — San Diego, 2003. — P. 563—574.

10. Denny M., Franklin M.J. Predicate result range caching for continuous queries // Proc. of the 2005 ACM SIGMOD Intern. Conf. on Management of Data (SIGMOD '05). — N.-Y.,

2005. — P. 646—657.

11. Afrati F., Li C, Mitra P. Rewriting queries using views in the presence of arithmetic comparisons // Theoretical Computer Science. — 2006. — Vol. 368, N 1—2. — P. 88—123.

12. Зыкин С.В. Формирование гиперкубического представления реляционной базы данных // Программирование. —

2006. — № 6. — С. 71—80.

13. Ульман Дж. Основы систем баз данных. — М.: Финансы и статистика, 1983. — 334 с.

14. Мейер Д. Теория реляционных баз данных. — М.: Мир, 1987. — 608 с.

15. Зыкин С.В. Формирование гиперкубического представления данных со списочными компонентами // Информационные технологии и вычислительные системы. — 2010. — № 4. — С. 38—46.

16. Miller L., Nilakanta S. Data Warehouse Modeler: A CASE Tool for Warehouse Design // Thirty-First Annual Hawaii International Conference on System Sciences. — Kohala Coast, 1998. — Vol. 6. — P. 42—48.

17. Fast computation of database operations using graphics processors / N.K. Govindaraju, et al. // Proc. of the 2004 ACM SIGMOD Intern. Conf. on Management of Data (SIGMOD '04). — Paris, 2004. — P. 215—226.

18. Blas A.D., Kaldewey T. Why graphics processors will transform database processing // Spectrum, IEEE. — 2009. — Vol. 46, N 9. — P. 46—51.

Статья представлена к публикации руководителем РРС

А.К. Погодаевым.

Сергей Владимирович Зыкин — д-р техн. наук, зав. лабораторией,

И zykin@ofim.oscsbras.ru,

Андрей Николаевич Полуянов — канд. техн. наук,

науч. сотрудник, И Andrey.Poluyanov@gmail.com,

Институт математики им. С.Л. Соболева СО РАН, г. Омск,

(3812) 23-67-39.