Обзор алгоритмов MOLAP


Разбиение на классы ячеек


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

$ a,b \in C $

и

$ \exists c: a<c<b \rightarrow c\in C$

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

Однако разбиение только по значению агрегирующей функции разрушает семантику куба (и тем более не выпукло). Покажем это.

Например, рассмотрим еще раз таблицу Продажи из введения (). Получившиеся разбиение изображено на рис. .

Таблица 5.1:

Копия таблицы

$\displaystyle \begin{tabular}{\vert c\vert c\vert c\vert c\vert} \hline Регион ... ...e R1 & Еда & Осень & 3\\ \hline R2 & книги & Осень & 6\\ \hline \end{tabular}$


Рис. 5.1:

Разбиение только по значению агрегирующей функции

У нас получается следующая схема (рисунок ).

Рис. 5.2:

Классы при разбиении только по значению агрегирующей функции

Image quotient_wrong_part_classes

Выбор агрегирующей функции в данном случае не важен, т.к. у нас есть возможность двигаться в обе стороны по отношениям roll-up/drill-down. Например, можно пойти вверх от ячейки (ALL, ALL, ALL) в С2 в ячейку (ALL, книги, ALL) в C5, а потом в (R2, книги, ALL) в С2. Тем самым, нарушается семантика отношений roll-up/drill-down.

Таким образом, мы показали, что разбиение только по значению агрегирующей функции не порождает связанной решетки классов эквивалентности. Необходимы какие-то ограничения.

В первых работах по данному алгоритму в качестве разбиения предлагалось так называемое связанное разбиение, однако оно верно только для монотонных функций (Sum (слагаемые одного знака), Count и пр). Впоследствии было предложено разбиение по покрытию. Поэтому здесь в примерах используется AVG — немонотонная функция.

Будем рассматривать кортежи куба как решетку (CL(r), Cube Lattice над отношением r) с введенным порядком, определенным иерархиями измерений (т.е.

$ \forall x in D x \le ALL$

). Введем определение покрытия для решетки (см [1],[2])

$ T_l=(\{0,a,b,1\},\le): 0\le a \le 1, 0\le b\le 1$

.

Определение 5.2 Будем говорить, что в частично упорядоченном множестве

$ (A,\le)$

элемент а покрывает элемент b, или b покрывается элементом a (обозначение:

$ a\succ b$

или

$ b\prec a$

), если: