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


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


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

$ O(n\log n)$

или

$ O(n)$

в лучшем случае (сортировка слиянием, кучами или подсчетом, вычерпыванием). Но с учетом NP-полноты начальной задачи, этим затратами можно пренебречь.

Пусть существует таблица фактических данных с

$ D$

измерениями (

$ \forall Dim \in D \vert Dim\vert=C$

), и количество фактических кортежей

$ T = C$

. Не нарушая общности, положим

$ \exists L: C=L!$

. У получившегося сжатого куба (или DWARF-куба) корневая ячейка будет иметь вид, показанный на рисунке . Группа

$ G_0$

содержит ячейки, не имеющие связи с фактическими кортежами, группа

$ G_1$

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

$ G_2$

— два фактических кортежа.

Рис. 2.4:

Вершина G, разбитая на группы, где группа

$ G_z$

связана с

$ z$

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

Лемма 1

Если из набора равномерно распределенных

$ C$

элементов выбрать некоторый элемент и повторить выбор

$ T$

раз, то вероятность выбора этого элемента ровно

$ z$

раз приблизительно равна:

$\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 к группам

$ G_z$

и подставляя

$ C=T$
, получим

Лемма 2

$ G_z, z\in \{0\ldots(L-1)\}$

содержит

$ \approx {\frac C {z!}} e^{-1}$

ячеек, которые адресуют ровно

$ z$

кортежей.

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

$ G_z$

попадает

$\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

Число дубликатных ключей в вершине, на которую указывает ячейка группы

$ G_z$
,

равно 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}$

Здесь

$ NLeft$

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

$ NTail$

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

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

$\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, в отличие от других алгоритмов, проверяет каждую ячейку только один раз (автору неизвестны алгоритмы, которые для устранения суффиксной избыточности не проверяли бы каждую ячейку экспоненциальное число раз), получаем ту же оценку и для сложности работы алгоритма.




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



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