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


Пример Вычислений - часть 2


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

Рис. 2.5:

Трехмерный массив для измерений А, В и С, разбитый на 64 блока. Каждый блок можно полностью поместить в оперативную память.

Image multiway_chunks

В процессе вычисления подкуба BC мы были вынуждены прочитать все 64 блока. Однако в большинстве случаев существует возможность избежать повторного чтения этих блоков при вычислении прочих подкубов (таких как AC и AB). Для решения этой задачи и используются многопозиционное агрегирование и одновременное вычисление нескольких кубов. К примеру, при сканировании блока 1 (

$ a_0b_0c_0$

) для вычисления двухмерного блока

$ b_0 c_0$

, могут быть вычислены все остальные двухмерные блоки, относящиеся к

$ a_0b_0c_0$

. Во время пребывания

$ a_0b_0c_0$

в оперативной памяти вычисляются блоки

$ b_0 c_0$

,

$ a_0c_0$

и

$ a_0b_0$

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

Порядок, в котором читаются блоки и вычисляются подкубы, определяет общую эффективность вычислений. Рассмотрим тот же пример с учетом размерностей измерений (40, 400, 4000 для А, В и С соответственно). Тогда наибольшим двухмерным кубом является BC, его размер

$ 400 * 4000 = 1600000$

. Следующий по размеру подкуб AC, его размер

$ 40 * 4000 = 160000$

. AB — наименьший двухмерный куб размером

$ 40 * 400 = 16000$
.

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

$ b_0 c_0$

полностью агрегируется на основе участка, содержащего блоки 1-4;

$ b_1с_0$

полностью вычисляется на основе участка, содержащего блоки 5-8 и так далее. Для сравнения, полное вычисление одного блока второго по размеру двухмерного подкуба АС в том же порядке 1-64 требует просмотра 13 блоков. К примеру,

$ a_0c_0$

агрегируются после просмотра блоков 1, 5, 9 и 13. Наконец, для вычисление последнего двухмерного подкуба АВ потребуется 49 блоков.

$ a_0b_0$

полностью вычисляются после просмотра блоков 1, 17, 33 и 49. Таким образом, для вычисления АВ требуется самый длительный просмотр блоков.


Начало  Назад  Вперед