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


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


Чтобы избежать загрузки трехмерного блока в оперативную память несколько раз, требуется оперативнвя память следующего объема:

\begin{displaymath} \begin{array}{l} 40 * 400 \mbox{ (для плоскости AB) } + 40 *... ...ек памяти (каждая ячейка памяти хранит набор мер).} \end{array}\end{displaymath}

Предположим что блоки считываются в порядке 1, 17, 33, 49, 5, 21, 27, 53 и так далее. Тогда сначала вычисляется плоскость AB, затем АС и в конце ВС. Минимальный размер памяти, необходимой для двухмерных блоков, в таком случае составит:

\begin{displaymath} \begin{array}{l} 400 * 4000 \mbox{ (полностью плоскость ВС)}... ...0000 + 40000 + 1000 = 1641000 \mbox{ ячеек памяти}. \end{array}\end{displaymath}

На порядок больше, чем в предыдущем примере.

Аналогично можно вычислить минимальные требования к памяти для вычисления одномерных и нульмерных подкубов. На рисунке изображены наиболее и наименее эффективные пути вычисления. Самое эффективный порядок просмотра: 1-64.

Рис. 2.6:

Различные пути построения подкубов в MultiWay

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

Экспериментально показано, что при соответствующем выборе техники обработки разреженных массивов и тщательном упорядочивании подкубов MultiWay намного эффективней традиционных ROLAP-вычислений. В отличие от ROLAP, MultiWay не требует дополнительного места для хранения индексов. Более того, в MultiWay используется прямая адресация в массивах, что намного быстрее чтения по ключу в ROLAP-методах. Для ROLAP-вычислений куба было бы эффективней сначала развернуть куб в памяти в многомерный массив, пересчитать и записать результаты в таблицу. Однако подобный подход эффективен при небольшой размерности кубов, ведь количество подкубов растет экспоненциально при добавлении измерений.

MultiWay неэффективен для вычисления кубов типа айсберг, поскольку невозможно использовать . Вычисления в MultiWay идут "снизу-вверх", поэтому нельзя отбросить ни одну из веток вычислений, т.к. сначала просматриваются детальные ячейки, и даже если они не удовлетворяют заданному условию, возможно, этому условию уже удовлетворяют агрегированные ячейки.

Вперед: Аппроксимирующие алгоритмы

Выше: Синтаксические алгоритмы

Назад: Алгоритм Dwarf

 




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