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


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


Предположим MinSup = 2, тогда только значения
$ a_1, a_2, b_1, c_3, d_4$

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

Таблица 4.2:

Агрегаты по каждому из измерений.

$\displaystyle \begin{tabular}{\vert c\vert c\vert c\vert} \hline Dimension & co... ..._4$ &$c_3(2)$\\ \hline $D$ & $d_1,d_2,d_3$ &$d_4(2)$\\ \hline \end{tabular} $

Таблица 4.3:

Фактическая таблица после удаления узлов-звезд.

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

Рис. 4.4:

Дерево звезд

Image star_cubing_star_tree

Таблица 4.4:

Таблица узлов-звезд для рисунка

$\displaystyle \begin{tabular}{\vert c\vert} \hline $b_2 \rightarrow *$ \\ \hli... ... *$ \\ \hline $d_1 \rightarrow *$ \\ \hline \ldots \\ \hline \end{tabular} $

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

$ *,p_1,p_2,...,p_n$

на каждом уровне.

Рассмотрим на этом же примере примере, как в работе Star-Cubing алгоритма используются деревья-звезды.

При агрегировании используется дерево-звезд типа того, которое изображено на рисунке . Агрегирование начинается снизу-вверх, при этом используется алгоритм поиска в глубину. Первый этап вычислений (т.е. обработка первой ветви дерева) изображен на рис . В левой части рисунка показано основное дерево звезд. Для каждого значения атрибута изображено агрегированное значение этого узла. Подстрочный номер указывает порядок обхода узлов. Остаются деревья BCD, ACD/A, ABD/AB, ABC/ABC, потомки основного дерева звезд, отвечающие за уровень выше базового на рисунке . Подстрочные номера вновь указывают на порядок обхода.


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



Книжный магазин