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


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


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

$ (P,x)$

, где

  1. путь
    $ (P,x)$

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

  2. путь
    $ (P,x)$

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

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

$ (P,ALL,y)$

, где

  1. путь
    $ (P,ALL,y)$

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

  2. путь
    $ (P,ALL,y)$

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

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

Рис. 2.2:

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

Image dwarf_sparsity




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



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