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


Виды избыточностей структуры куба


Определение 2.1 Префиксная избыточность. Пусть имеется есть куб с измерениями a, b и с. Каждое значение измерения a участвует в четырех группировках (a, ab, ac, abc) и, возможно, много раз в каждой из сгруппированных таблиц.

DWARF успешно распознает подобный тип изыбыточности и устраняет его за счет хранения каждого префикса лишь один раз.

Определение 2.2   Суффиксная избыточность

возникает, если 2 или более сгруппированные таблицы разделяют однаковый суффикс (например, abc и bc).

Рассмотрим значение

$ b_j$

измерения

$ b$

, которое появляется в базовой таблице с единственным значением

$ a_i$

измерения

$ a$

. Тогда сгруппированные таблицы

$ <a_i,b_j,x>$

и

$ <b_j,x>$

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

$ a_i$

) с

$ b_j$

и

$ x$

. Эта идея расширяет понятие базового единичного кортежа (BST, Base Single Tuple) (см. ) из алгоритма ''сжатого'' куба [25]. Поскольку

$ x$

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




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



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