| ||||||||||||
| ||||||||||||
|
2008 г.
Обзор алгоритмов MOLAPЮрий Кудрявцев, факультет ВМиК МГУ ПодразделыМногомерные кубы, определение и свойства
Рассмотрим базовую (фактическую) таблицу
Из атрибутов ПримерРассмотрим пример, который будет и в дальнейшем использоваться в рамках данной работы.
Размер куба данных определяется по формуле
Таким образом, при базовой таблице в 3 кортежа результирующий куб в простой реляционной таблице (называемой Binary Storage Footprint), в которой напрямую хранятся все агрегаты, занимает 27 кортежей. ИзмеренияИзмерения куба — набор доменов, по которым создается многомерное пространство. Важной особенностью OLAP-моделей является разделение измерений на локаторы (задающие точки) и меры (задающие значение). Как отмечается в [23], данное разделение может носить как условный, так и жесткий характер. В случае условного разделения измерения можно ''разворачивать'' как данные и как аналитику, создавая новую аналитику куба по продажам — ''количество продаж''. Таким образом, возрастает гибкость моделей и уровень абстракции. Однако данный подход, несмотря на свою привлекательность, сложен в реализации (для примера отметим необходимость создания оптимальных алгоритмов хранения абстрактных типов данных) и, насколько нам известно, нигде промышленно не реализован. Теоретически, вкупе с моделированием решеток кубов логикой предикатов первого порядка, абстрагирование понятия ''измерение'' дает очень интересные результаты. Локаторы куба отличаются иерархической структурой, и для получения значений мер на каждом уровне агрегирования вводятся агрегирующие функции. Иерархии и агрегированиеИерархичность данных — одно из важнейших свойств многомерных кубов. Иерархии призваны добавлять новые уровни в аналитическое пространство пользователя. Самым распространенным примером иерархии является ''день-неделя-месяц-год''. Соответственно, для уровней иерархии работают отношения обобщения и специализации (rollup/drilldown). Как правило, в научных работах рассматриваются простые примеры иерархий ''детальное значение — ALL'', однако, как мы увидим далее, подобного уровня детализации может быть недостаточно.
Все иерархии можно разбить на 2 типа, о которых пойдет речь ниже. Основой разбиения будет служить расстояние Примеры типов иерархий:
Важным свойством уровневых иерархий является возможное наличие частичного порядка внутри каждого уровня иерархии, например, возможность сравнения месяцев по старшинству или городов по географическому положению. В большинстве современных средств (алгоритмов) данным свойством пренебрегают , удаляя, тем самым, потенциально полезные связи модели. Агрегирующие функции, меры и формулы
Неотъемлемой частью OLAP-модели является задание функций агрегирования. Поскольку целью OLAP является создание многоуровневой модели анализа, данные на уровнях, отличных от фактического, должны быть соответствующим образом агрегированы. Важно отметить, что по каждому измерению можно задавать собственную (и не одну) функцию агрегации. Таким образом, в случае куба с
![$\displaystyle f(x) = [\{f_{1,1},\ldots,f_{1,k_1}\},\ldots,\{f_{n,1},\ldots,f_{n,k_n}\}]
$](img15.gif){kind=small}
где 
— точка куба, а 
- 
-ая функция
агрегирования по 
-ому измерению.
В [7] приведена следующая классификация агрегирующих функций с точки зрения сложности распараллеливания.
Эта классификация окажется полезной, когда мы будем рассматривать классы разбиения в алгоритме Quotient Cube (см. раздел Quotient Cube, работы [12],[11],[26]), в котором разбиение по покрытию применимо для дистрибутивных и алгебраических функций.
|
, на основе которой мы будем строить OLAP-куб. Множество атрибутов r условно делятся на 2 группы:
, где 
-измерения (''столбцы''),
размерность измерения 
— количество различных значений кортежей по этому измерению (Select Count(distinct dimension) from table), 
отвечает за значение 
, агрегирующее все возможные значения измерения.
) до листьев. В случае, если 
, иерархии называются уровневыми (leveled), иначе — несбалансированными (ragged).
измерениями функция агрегирования:
 | |||||||||
| |||||||||
|
CITForum © 1997–2025