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

2008 г.

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

Вперед: Многопозиционное агрегирование массивов для вычисления кубов Выше: Синтаксические алгоритмы Назад: Синтаксические алгоритмы Содержание

Подразделы

Алгоритм DWARF

Алгоритм DWARF (карлик) (см. [21]) назван так с намеком на звезды карликового типа, которые имеют небольшой объем, но огромную массу. Это синтаксический алгоритм, распознающий два типа избыточности хранения данных и устраняющий их во время создания и поддержки куба.

Ключевыми понятиями алгоритма являются префиксная избыточность и суффиксная избыточность (см. определения).

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

Не менее важным является сокращение времени создания и расчетов. Каждый избыточный суффикс идентифицируется до его вычисления, что ведет к существенным уменьшениям времени создания. Более того, вследствие уменьшения общего размера куба пропорционально падает и время обработки запросов.

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

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

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

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

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

измерения

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

измерения

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

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

) с

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

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

Структура куба

Пример куба

**Таблица 5.1:** Копия таблицы 1.1
$\displaystyle \begin{tabular}{\vert c\vert c\vert c\vert c\vert} \hline Регион ... ...e R1 & Еда & Осень & 3\\ \hline R2 & книги & Осень & 6\\ \hline \end{tabular}$

Для начала приведем пример структуры куба, а в дальнейшем дадим формальное определение. Рисунок 2.1 показывает структуру куба для таблицы 1.1, в качестве агрегирующей функции используется SUM.

Рис. 2.1: DWARF-куб

Вершины пронумерованы в порядке их создания. Высота куба равна числу измерений, каждое из которых относится к одному из уровней, как показано на рисунке.

Корневая вершина содержит ячейки вида {ключ, указатель} для каждого значения первого измерения. Указатель каждой ячейки направлен к лежащей ниже вершине, которая содержит все различные значения следующего измерения, ассоциированные с ключом ячейки.

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

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

Свойства DWARF-куба

Это ациклический ориентированный граф с одной корневой вершиной, имеющий ровно D уровней, где D-число измерений.
Вершины уровня D (листья) содержат ячейки вида {ключ, агрегирующее значение}.
Вершины на уровнях, отличных от уровня D, (нелистовых) содержат ячейки вида {ключ, указатель}. Ячейка С в нелистовой вершине уровня i указывает на вершину уровня i+1, которую она обобщает. С — родительская вершина для обобщаемой вершины.
В каждой вершине имеется специальная ячейка, которая содержит псевдо-значение ALL как ключ. Эта ячейка содержит указатель или на нелистовую вершину, или на агрегирующее значение листовой вершины.
Ячейки на i-ом уровне содержат ключи, являющиеся значениями i-того измерения куба. Внутри одной вершины не может встречаться повторения ключа.
Каждая ячейка на i-ом уровне структуры отвечает последовательности из i ключей, входящих в путь от корня до ячейки. Такой путь соответствует оператору group by с (D-i) не указанными измерениями. Все группировки, содержащие в качестве префикса, будут относиться к ячейкам, являющимся потомками в структуре куба. Для всех подобных группировок их общий префикс будет хранится единожды.
Когда две или более группировки создают одинаковые вершины и ячейки, их хранение обобщается (поглощается), чтобы можно было хранить только одну копию. В таком случае результирующая вершина будет достижима более чем одним путем из корня, причем все пути будут иметь одинаковый суффикс. Если вершина N — обобщающая, то все ее потомки будут обобщающими вершинами.

Выполнение различных типов запросов

Точечные запросы: выполняются последовательным разыменованием пути в структуре куба. Таким образом, этот вид запросов выполняется намного быстрее, чем в аналогичных алгоритмах или базовых таблицах, за счет того, что для каждого запроса требуется ровно D обращений к вершинам куба, где D — число измерений (уровней) куба.
Интервальные запросы: включают хотя бы одно измерение с интервалом значений. Для каждого из ключей i-ого уровня, попадающего в интервал, строятся рекурсивные подзапросы к нижележащим подкубам, что тоже достаточно просто по структуре.
Обратные запросы: оптимизаций по выполнению обратных запросов этот алгоритм не дает, но возможно его сочетание с какими-либо другими алгоритмами, ориентированными на обратные запросы. Правда, в настоящее время все оптимизации обратных запросов основаны на специально создаваемых кубах, поэтому такое объединение алгоритмов — нетривиальная задача. См. также Алгоритм Bottom-Up Computation.

Сложность

Несмотря на то, что показана NP-полнота общей задачи выбора представлений для материализации [10], в работе [22] были даны новые оценки сложности алгоритма DWARF. Большая часть этих результатов вошла в данный раздел. При этом хотелось бы в очередной раз подчеркнуть, что DWARF — алгоритм полной материализации (materialize-all). Также хотелось бы отметить, что оценки в работе [22] были получены при наложении определенных условий на начальные данные.

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

$\displaystyle O(T\frac {d^{\log_c T + 1}} {\log_c T!}) = O(d\bullet T^{1+ \frac 1 {\log_d C}})$

— число измерений

— мощность измерения

— число фактических кортежей

Приведем некие трактовки данного результата.

Положим, размерность куба растет , т.е. все кортежи фактической таблицы ''расширяются'' путем добавления новых столбцов. Тогда:

$\displaystyle T = const, d\uparrow \Rightarrow O(T\frac {d^{\log_c T + 1}} {\log_c T!})\sim O(d^{\log_c T})$

Причем ${\log_c T}$ для реальных баз данных довольно мало.
Правая часть равенства показывает, что размер и время вычисления куба при постоянном числе измерений и добавлении новых фактических кортежей растет почти полиномиально от T, которое возводится в $1 + \frac1 {\log_d C}$ (что очень близко к единице для больших фактических таблиц).

Модель опирается на понятия префиксной, суффиксной избыточности, приведенные выше в описании алгоритма (см. определения ). Разобьем категории сжатия на две группы:

сжатие разреженности (sparsity coalescing)
сжатие связанности (implication coalescing)

Виды сжатия

Сжатие разреженности

Введем категории сжатия разреженности. Хвостовое сжатие (Tail Coalescing) происходит на всех группировках, имеющих префикс

, где

путь ведет к подкубу, агрегирующему только один фактический кортеж (см. также случай базового единичного кортежа (BST);
путь не проходит ни через один указатель .

Левое сжатие (Left Coalescing) происходит на всех группировках, имеющих общий префикс , где

путь ведет к подкубу, агрегирующему только один фактический кортеж;
путь проходит хотя бы через один указатель ALL. Области куба, агрегирующие только один фактический кортеж, создают большую избыточность структуры. Ниже будет показано, что избавление от избыточности разреженности приводит к почти полиномиальному времени создания куба.

Примеры категорий сжатия разреженности:

**Рис. 2.2:** Категории сжатия разреженности

Сжатие связанности

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

Рис. 2.3: Сжатие связанности

Сжатие связанности, таким образом, представляет собой расширение понятия левого сжатия на случай наличия связей (implications) между значениями измерений. Подобные связи часто наблюдаются в реальных базах данных.

Доказательство

Авторы опускают необходимую при создании DWARF-куба лексикографическую сортировку начальной таблицы (во время создания куба появление нового префикса означает необходимость создания новой вершины на уровне, где различаются префиксы). Сортировка всей фактической таблицы — $O(n\log n)$ или в лучшем случае (сортировка слиянием, кучами или подсчетом, вычерпыванием). Но с учетом NP-полноты начальной задачи, этим затратами можно пренебречь.

Пусть существует таблица фактических данных с измерениями ( $\forall Dim \in D \vert Dim\vert=C$ ), и количество фактических кортежей . Не нарушая общности, положим $\exists L: C=L!$ . У получившегося сжатого куба (или DWARF-куба) корневая ячейка будет иметь вид, показанный на рисунке 2.4. Группа содержит ячейки, не имеющие связи с фактическими кортежами, группа — ячейки, связанные с одним кортежем фактической таблицы, — два фактических кортежа.

Рис. 2.4: Вершина G, разбитая на группы, где группа

связана с

фактическими кортежами

Лемма 1

Если из набора равномерно распределенных элементов выбрать некоторый элемент и повторить выбор раз, то вероятность выбора этого элемента ровно раз приблизительно равна:

$\displaystyle P_z(C,T) =\frac{{T\choose z}}{{(C-1)}^z}e^{(-\frac T C)}$

Равномерность — еще одно ограничение на входные фактические данные. В общем случае:

$\displaystyle P_z(C,T) ={T\choose z}p^z{(1-p)}^{T-z} = {T\choose z} {\left({\frac {p} {1-p}}\right)} ^z(1-p)^T$

Коротко укажем дальнейшие пункты доказательства.

Применяя лемму 1 к группам и подставляя , получим

Лемма 2

$G_z, z\in \{0\ldots(L-1)\}$ содержит $\approx {\frac C {z!}} e^{-1}$ ячеек, которые адресуют ровно кортежей.

В общем случае в попадает

$\displaystyle \begin{array}{clr} \char93 G_z&=&\sum\limits_{x=1}^C P_z(x,C,C)\c... ...=1}^C {\left({\frac {p(x)} {1-p(x)}}\right)}^z(1-p(x))^T \cdot x\\ \end{array}$

В случае неравномерного распределения кортежей, данная сумма будет отличаться от результатов [22], и это повлечет изменение всех дальнейших оценок в леммах.

Лемма 3

Число дубликатных ключей в вершине, на которую указывает ячейка группы , равно 0. ( $\frac{(L-1)} {{L!}^2} \approx 0$ )

Основываясь на введенных выше понятиях левого и хвостового сжатий, можно показать, что

$\displaystyle \begin{array}{rcl} NLeft (T=C^k,d,C)&=&C\cdot\sum^{d-1}_{i=1}NLef... ...^{k-1}{d\choose {k-i}} + 1\\ [5 pt] \mbox{где}~a_0=\frac {e-2} e&& \end{array}$

$\displaystyle \begin{array}{rcl} NTail(T=C^k,d,C) & = & C\cdot NTail(C^{k-1},d-... ...hoose {k-i}}-1]+b_0C^k\\ [5pt] \mbox{где}~b_0=\frac {2e-2} e & &\\ \end{array}$

Здесь — число ячеек, подвергающихся левому сжатию, и — число ячеек, подвергающихся хвостовому сжатию.

Из последней формулы получим следующее соотношение для числа ячеек куба:

$\displaystyle Number\_of\_Cells = O(T\frac {d^{\log_c T + 1}} {\log_c T!}) = O(d T^{1+ \frac 1 {\log_d C}})$

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

Вывод

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