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


Сложность


Несмотря на то, что показана 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}}) $

$ d$

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

$ C$

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

$ T$

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

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

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

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




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