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

       

Сложность


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

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

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

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

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

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

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

    Причем

    для реальных баз данных довольно мало.

  • Правая часть равенства показывает, что размер и время вычисления куба при постоянном числе измерений и добавлении новых фактических кортежей растет почти полиномиально от T, которое возводится в

    (что очень близко к единице для больших фактических таблиц).

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

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



    Содержание раздела