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



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


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

$ (P,x)$

, где

  • путь
    $ (P,x)$

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

  • путь
    $ (P,x)$

    не проходит ни через один указатель .

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

    $ (P,ALL,y)$

    , где

  • путь
    $ (P,ALL,y)$

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

  • путь
    $ (P,ALL,y)$

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

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

    Рис. 2.2:

    Категории сжатия разреженности

    Image dwarf_sparsity




    Содержание  Назад  Вперед