Обзор алгоритмов MOLAP. История Задачи

2008 г.

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

Вперед: Многомерные кубы, определение и свойства Выше: Введение. Анализ задачи Назад: Введение. Анализ задачи Содержание

Подразделы

История Задачи

Термин OLAP был введен в 1993 Эдгаром Коддом [5]. Цель систем OLAP — облегчение решения задач анализа данных. Кодд сформулировал 12 признаков OLAP-данных, и большинство современных средств OLAP отвечает этим постулатам. Перечислим их:

12 Признаков OLAP Данных

Многомерная концепция данных.: OLAP оперирует данными CUBE (см. далее описание работ Грея [8]), которые являются многомерными массивами. Число измерений OLAP-кубов не ограничено.
Прозрачность.: OLAP системы должны опираться на открытые системы, поддерживающие гетерогенные источники данных.
Доступность.: OLAP системы должны представлять пользователю единую логическую схему данных.
Постоянная скорость выполнения запросов.: Производительность не должна падать при росте числа измерений.
Клиент/сервер архитектура.: Системы должны базироваться на открытых интерфейсах и иметь модульную структуру.
Различное число измерений.: Системы не должны ограничиваться трехмерной моделью представления данных. Измерения должны быть эквивалентны по применению любых функций.
Динамическое представление разреженных матриц.: Под разреженной матрицей понимается такая матрица, не каждая ячейка которой содержит данные. OLAP-системы должны содержать средства хранении и обработки разреженных матриц больших объемов.
Многопользовательская поддержка.: OLAP-системы должны поддерживать многопользовательский режим работы.
Неограниченные многомерные операции.: Аналогично требованию о различном числе измерений: все измерения считаются равными, и многомерные операции не должны накладывать ограничения на отношения между ячейками.
Интуитивно понятные инструменты манипулирования данными.: Для формулировки многомерных запросов пользователи не должны работать со усложненными меню.
Гибкая настройка конечных отчетов.: Пользователи должны иметь возможность видеть только то, что им необходимо, причем все изменения данных должны немедленно отображаться в отчетах.
Отсутствие ограничений.: Не должны иметься какие-либо ограничения на количество измерений и уровней агрегации данных.

FASMI тест

В дальнейшем Найджел Пендс переформулировал 12 правил Кодда (см. [18]) в более емкий тест FASMI (Fast Shared Multidimensional Information). По определению Пендса, OLAP-система должна быть:

Fast — быстрой, обеспечивать почти мгновенный отклик на большинство запросов;
Shared — многопользовательской; должен существовать механизм контроля доступа к данным, а также возможность одновременной работы многих пользователей;
Multidimensional — многомерной; данные должны представляться в виде многомерных кубов;
Information — данные должны быть полны с точки зрения аналитика, т.е. содержать всю необходимую информацию.

Большинство существующих OLAP-средств удовлетворяет всем этим признакам. Однако в реализации подобных приложений возникает ряд проблем, прежде всего связанных с увеличением объема данных, которые необходимо хранить.

В 1995 группа исследователей во главе с Джимом Греем [8], проанализировав создаваемые тогда пользовательские приложения баз данных, предложила расширение языка SQL — оператор CUBE. Данный оператор отвечает за создание многомерных кубов в SQL. Концепция многомерного представления данных является, наряду с моделью транзакций, одной из самых известных идей Грея. В этой работе исследователи указали ряд эвристических рекомендаций по реализации новой структуры данных.

CUBE представляет собой обобщение операторов выборки с разделом GROUP BY по всем возможным комбинациям измерений с разными уровнями агрегации данных. Каждая сгруппированная таблица относится к группе ячеек, описываемых кортежами из измерений, по которым формируется сгруппированная таблица. Оператор, расширяющий SQL, называется CUBE BY (синтаксис такой же, как и у GROUP BY).

В стандарт SQL'99 включен набор операторов для работы с OLAP-данными (запросы grouping set, rollup by, cube by, window by, rank, rownum и пр).