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


Алгоритм Star-Cubing - часть 2


К примеру, если в разделяемом измерении А значение

$ a_1$

не удовлетворяет условию MinSup, то отсекается вся ветвь от

$ a_1CD/a_1$

(включая

$ a_1C/a_1C,a_1D/a_1,a_1/a_1$

), поскольку эти ячейки заведомо не удовлетворяют условию MinSup.

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

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

изображена часть дерева куба для подкуба ABCD. Каждый уровень дерева представляет собой измерение, и каждый узел представляет собой значение атрибута. Каждый узел имеет 4 поля: значение аттрибута, агрегированное значение, указатель/указатели на потомков и указатель/указатели на элементы того же уровня. Кортежи подкуба вставляются в дерево один за другим. Путь от корня к листу представляет собой кортеж. К примеру, агрегированное значение (по мере count) узла

$ c_2$

в дереве равно 5, что означает 5 ячеек значения

$ (a_1,b_1,c_2,*)$

. Подобное представление позволяет сократить пространство, требуемое для хранения общих префиксов (см. также ), и хранить агрегированные значения в внутренних узлах, что позволяет на этапе вычисления отсекать ветви, основанные на разделяемых измерения. К примеру, дерево подкуба AB может быть использовано для отсечения возможных ячеек в ABD.

Рис. 4.3:

Фрагмент дерева одного из базовых подкубов

Если агрегированое значение, допустим p, не удовлетворяет условию, то бесполезно различать подобные узлы в процессе вычисления куба. Поэтому узел p можно заменить *, еще больше сжимая таким образом дерево. Будем называть узел р узлом-звездой (star-node), если агрегированное значение по измерению в точке p не удовлетворяет условию MinSup. Дерево подкуба, сжатое с помощью узлов-звезд, будем называть деревом звезд (star-tree).

Рассмотрим пример построения дерева-звезд.

Таблица 4.1:

Фактическая таблица для куба из четырех измерений до начала работы алгоритма Star-Cubing.

$\displaystyle \begin{tabular}{\vert c\vert c\vert c\vert c\vert c\vert} \hline ... ... $d_4$ & 1\\ \hline $a_2$ & $b_4$ &$c_3$ & $d_4$ & 1\\ \hline \end{tabular} $

Как показывает таблица всего существует 5 кортежей и 4 измерения. Размерности измерений A,B,C,D равны 2,4,4,4 соответственно. Одномерные агрегаты приведены в таблице .


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