Сжатие разреженности
Введем категории сжатия разреженности. Хвостовое сжатие (Tail Coalescing) происходит на всех группировках, имеющих префикс
, где
ведет к подкубу, агрегирующему только один фактический кортеж (см. также ;
не проходит ни через один указатель .
Левое сжатие (Left Coalescing) происходит на всех группировках, имеющих общий префикс
, где
ведет к подкубу, агрегирующему только один фактический кортеж;
проходит хотя бы через один указатель ALL. Области куба, агрегирующие только один фактический кортеж, создают большую избыточность структуры. Ниже будет показано, что избавление от избыточности разреженности приводит к почти полиномиальному времени создания куба.
Примеры категорий сжатия разреженности:
Рис. 2.2:
Категории сжатия разреженности
 |
