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


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


Например, на первом шаге алгоритма создается корневой узел дерева-потомка BCD, на втором — корневой узел дерева ACD/A, на третьем — корневой узел ABD/AB и узел b*.

Рис. 4.5:

Первый этап агрегирования: обработка левой ветви базового дерева

Рис. 4.6:

Второй этап агрегирования: обработка второй ветви базового дерева

В правой части рисунка показаны деревья в памяти на 5-ом шаге алгоритма. Поскольку к этому моменту поиск в глубину достигает листа дерева, происходит возврат. До возврата алгоритм отмечает, что все возможные узлы базового измерения ABC уже были просмотрены. Это значит, что дерево ABC/ABC уже просмотрено, и результат равен count, а дерево можно удалить. Аналогично, двигаясь назад от d* к c* и принимая во внимание, что у c* нет потомков, алгоритм устанавливает, что count в ABD/AB является финальным результатом, и дерево удаляется.

При возврате в вершине b*, поскольку существует одноуровневый узел

$ b_1$

, дерево ACD/A будет сохранено в памяти, и поиск в глубину пойдет от вершины

$ b_1$

, так же, как до этого от b*. Результирующие деревья изображены на рисунке . Деревья потомки ACD/A и ABD/A создаются заново, со значениями из поддерева

$ b_1$

. К примеру, агрегированное значение с* в ACD/D возрастает от 1 до 3. Деревья остаются неизменными, к ним лишь добавляются новые ветви либо увеличиваются агрегированные значения. Например, дополнительная ветвь добавляется в дерево BCD.

По достижению листа d* алгоритм вновь возвращается, в этот раз до

$ a_1$

, где будет замечен одноуровневый узел

$ a_2$

. В этом случае будут удалены все деревья, кроме BCD на рисунке . После этого аналогичный обход будет совершен для

$ a_2$

. Дерево BCD продолжает расти, а остальные деревья начинаются с корня в

$ a_2$

.

Для того, чтобы у узла были потомки, необходимо выполнение двух условий:

  1. узел должен удовлетворять условию MinSup ;
  2. дерево, исходящее из этого узла, должно быть невырожденным, т.е. содержать хотя бы один нетривиальный узел (не узел-звезду).

Это необходимо, поскольку, если все узлы будут тривиальными, ни один из них не будет удовлетворять условию MinSup, и вычислять их будет нецелесообразно.


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