Книги, научные публикации
OLAP ТЕХНОЛОГИИ:
ОБЗОР РЕШАЕМЫХ ЗАДАЧ И ИССЛЕДОВАНИЙ Ю. Кудрявцев, аспирант факультета Вычислительной математики и кибернетики Московского государственного университета Рассматриваются технологии OLAP (OnLine Analytical Processing), вклюбчающие в себя дефиницию, исторический обзор исследований, обзор бизнес приложений и существующих проблем при реализации решений подобного класса.
системы должны содержать средства хранении и об ОПРЕДЕЛЕНИЕ ТЕРМИНА OLAP работки разреженных матриц больших объёмов.
Многопользовательская поддержка. OLAP систе ермин OLAP введён в 1993 г. Эдгаром Коддом мы должны поддерживать многопользовательский [Cod93]. Цель OLAP систем - облегчение ре режим работы.
Тшения задач анализа данных. Кодд сформу Неограниченные многомерные операции. Анало лировал 12 признаков OLAP данных, и большин гично требованию о различном числе измерений:
ство современных OLAP средств отвечают этим все измерения считаются равными, и многомерные постулатам. Перечислим их: операции не должны накладывать ограничения на отношения между ячейками.
12 ПРИЗНАКОВ OLAP ДАННЫХ Интуитивно понятные инструменты манипулиро Многомерная концепция данных. OLAP оперирует вания данными. Для формулирования многомерны CUBE данными (см. далее описание работ Грея ми запросами пользователи не должны работать [GBLP95]), которые являются многомерными масси в усложнённых меню.
вами. Число измерений OLAP кубов не ограничено. Гибкая настройка конечных отчётов. Пользовате Прозрачность. OLAP системы должны опирать ли должны иметь возможность видеть только ся на открытые системы, поддерживающие гетеро необходимые им данные, причём все их изменения генные источники данных. должны немедленно отображаться в отчётах.
Доступность. OLAP системы должны предста Отсутствие ограничений. Отсутствие ограниче влять пользователю единую логическую схему ний на количество измерений и уровней агрегации данных. данных.
Постоянная скорость выполнения запросов. Про В дальнейшем Найджел Пендс переформулиро изводительность не должна падать при росте числа вал 12 правил Кодда в более ёмкий тест FASMI (Fast измерений. Shared Multidimensional Information). По его опре Клиент/сервер архитектура. Системы должны делению, OLAP система должна быть:
базироваться на открытых интерфейсах и иметь мо Fast - быстрой, обеспечивать почти мгновен дульную структуру. ный отклик на большинство запросов;
Различное число измерений. Системы не должны Shared - многопользовательской, должен ограничиваться трехмерной моделью представле существовать механизм контроля доступа ния данных. Измерения должны быть эквивалент к данным и возможность одновременной ны по применению любых функций. работы многих пользователей;
Динамическое представление разреженных матриц. Multidimensional - многомерной. Данные Под разреженной матрицей понимается матрица, не должны представляться в виде многомерных каждая ячейка которой содержит данные. OLAP кубов;
66 БИЗНЕС ИНФОРМАТИКА №1Ц2008 г.
Information - данные должны быть полны Примеры продуктов: Microsoft Excel Pivot Tables, с точки зрения аналитика, т.е. содержать всю Microsoft Analysis Services, SAP BW, Oracle Essbase, необходимую информацию. Oracle OLAP, Cognos PowerPlay, MicroStrategy, Busi ness Objects.
Большинство из существующих OLAP средств Финансовое планирование\бюджетирование.
удовлетворяют всем этим признакам. Однако в ре Многомерная модель позволяет одновременно ализации подобных приложений возникает ряд вводить данные и легко анализировать их (напри проблем, прежде всего связанных с увеличением мер, план факт анализ). Поэтому ряд современных объёма данных, которые необходимо хранить. продуктов класса CPM (Corporate Performance В 1995 г. группа исследователей во главе с Джей Management) используют OLAP модели. Важная мсом Греем [GBLP95], проанализировав создава задача - многомерный обратный расчёт (back емые пользовательские приложения баз данных, solve, breakback, writeback), позволяющий рассчи предложили расширение языка SQL - оператор тать требуемые изменения детальных ячеек при CUBE. Данный оператор отвечает за создание изменении агрегированного значения. Это инстру OLAP кубов в SQL. Концепция многомерного мент для анализа что если (what if), т.е. для представления данных намного облегчила жизнь проигрывания различных вариантов событий при разработчикам и пользователям. В той же работе планировании.
исследователи указали ряд эвристических рекомен Примеры продуктов: Microsoft PerformancePint, даций по реализации новой структуры данных. Oracle EPB, Oracle OFA, Oracle Hyperion Planning, CUBE представляет собой обобщение GROUP BY SAP SEM, Cognos Enterprise Planning, Geac.
операторов по всем возможным комбинациям из Финансовая консолидация. Консолидация дан мерений с разными уровнями агрегации данных. ных согласно международным стандартам учёта, Оператор, расширяющий SQL, называется CUBE принимая во внимание доли владения, различные BY (синтаксис такой же, как и у GROUP BY). валюты и внутренние обороты - актуальная задача В стандарт SQLТ99 включён набор операторов для в связи с ужесточающимися требованиями прове работы с OLAP данными. ряющих органов (SOX, Basel II) и выходом компа Расширения стандартов SQL 1999 и SQL 2003, ний на IPO. OLAP технологии позволяют ускорить восполняющие OLAP функциональность языка SQL: расчёт консолидированных отчётов и повысить Grouping Set запросы;
прозрачность всего процесса.
Cube By запросы;
Примеры продуктов: Oracle FCH, Oracle Hype Rollup By запросы;
rion FM, Cognos Controller.
Window By запросы;
Model By запросы в Oracle 10g и выше. МНОГОМЕРНЫЕ КУБЫ, ОПРЕДЕЛЕНИЕ И СВОЙСТВА Исследования в области многомерных массивов Рассмотрим базовую (фактическую) таблицу, на данных велись задолго до работ Грея, но его работа основе которой мы будем строить OLAP куб. Мно стала основополагающей в создании промышлен жество атрибутов условно делят на 2 группы:
ных продуктов и расширении языка SQL. 1. Набор измерений (категорий, локаторов), слу жащие критериями для анализа и определяющие многомерное пространство OlAP куба. За счёт фик БИЗНЕС ПРИЛОЖЕНИЯ НА ОСНОВЕ сации значений измерений получаются срезы (ги OLAP ТЕХНОЛОГИЙ, ПРИМЕРЫ ПРОДУКТОВ перплоскости) куба. Каждый срез представляет со Наиболее часто встречаются следующие приме бой некий запрос к данным, включающий агрегации.
нения OLAP технологий: 2. Набор мер - функции, ставящие данные в со Анализ данных. Задача, для которой изначально ответствие каждой точке пространства.
использовались и до сих пор остаются самыми Из атрибутов создаются измерения, содержащие популярными OLAP средства. Многомерная проекцию по атрибуту, с введённой иерархией модель данных, возможность анализировать значи (например, для таблицы, содержащей фактические тельные объёмы данных и быстрый отклик на за данные по продажам магазина, возможно измере просы делают подобные системы незаменимыми ние Время, содержащее иерархию вида Год для анализа продаж, маркетинговых мероприятий, Месяц Неделя День). Куб представляет собой де дистрибуции и других задач с большим объёмом картово произведение измерений, где для каждого исходных данных. элемента произведения проставлен набор мер.
БИЗНЕС ИНФОРМАТИКА №1Ц2008 г. В кубе существуют отношения обобщения и спе Важное свойство уровневых иерархий - воз циализации (roll up/drill down) по иерархиям изме можное наличие частичного порядка внутри каж рений. Ячейка высокого уровня иерархии может дого уровня иерархии. Например, возможность спускаться (drill down) к ячейке низкого уровня. сравнения месяцев по старшинству или городов по Например, (R1, ALL, весна) может спуститься географическому положению. Большинство совре к ячейке (R1, книги, весна) и наоборот, подни менных средств (алгоритмов) пренебрегают дан маться (roll up) от (R1, книги, весна) к (R1, ALL, ным свойством, удаляя тем самым потенциально весна) по измерению продукты. полезные связи модели.
Измерения. Измерения куба - набор доменов, Агрегирующие функции, меры и формулы. Не по которым создаётся многомерное пространство. отъемлемая часть OLAP модели - задание функ Важная особенность OLAP моделей - разделение ций агрегирования. Поскольку цель OLAP - созда измерений на локаторы (задающие точки) и меры ние многоуровневой модели анализа, данные на (задающие значение). Как отмечено в [Tho02], дан уровнях, отличных от фактического, должны быть ное разделение может носить как условный, так соответствующим образом агрегированы. По каж и жесткий характер. В случае условного разделения дому измерению возможно задавать собственную возможно разворачивать измерения как данные (и не одну) функцию агрегации.
и как аналитики, создавая новое значение куба по В [GC97] приведена следующая классификация продажам - количество продаж. Таким образом, агрегирующих функций с точки зрения сложности чрезвычайно возрастает гибкость моделей и уро распараллеливания:
вень абстракции. Однако данный подход, несмотря дистрибутивные функции позволяют разби на свою привлекательность, чрезвычайно сложен в вать входные данные и вычислять отдельные реализации (в частности, необходимость создания итоги, которые потом возможно объединять;
оптимальных алгоритмов хранения абстрактных алгебраические функции возможно предста типов данных) и, насколько известно, нигде про вить комбинацией из дистрибутивных функ мышленно не реализован. Теоретически, вкупе ций (например, Average() можно представить с моделированием структур логикой предикатов как сумму, разделённую на count);
первого порядка, абстрагирование понятия лизме холистические функции невозможно вычи рение даёт очень интересные результаты. слять на частичных данных или представлять Локаторы куба отличаются иерархической струк каким либо образом.
турой, и для получения значений мер на каждом уров не агрегирования вводятся агрегирующие функции. ХРАНЕНИЕ И ЭФФЕКТИВНЫЙ РАСЧЁТ Иерархии и агрегирование. Иерархичность дан OLAP КУБОВ ных - одно из важнейших свойств многомерных Материализация представлений. Главным свой кубов. Иерархии призваны добавлять новые уровни ством OLAP систем считается возможность в аналитическое пространство пользователя. эффективно отвечать на запросы. Одна из мер по Самый распространённый пример иерархии - вышения этой эффективности - материализация месяцЦнеделяЦгод. Соответственно, для уровней кубов, а не вычисление их на лету (вычисление иерархии работают отношения обобщения и спе агрегаций непосредственно во время обработки циализации (rollup/drilldown). Как правило, в рабо запроса).
тах рассматриваются простые примеры иерархий Считается стандартным представление куба детальное значение - ALL, однако подобного в виде т.н. решетки - графа, в котором узлы опреде уровня детализации может быть недостаточно. ляют представления (view) для ответа на запрос.
Все иерархии можно разбить на 2 типа. Основой Для каждого узла пометка обозначает измерения, разбиения будет служить расстояние от корня до ли по которым есть фактические данные в представле стов. Если расстояние одинаково до всех листов - нии;
по пропущенным измерениям производится иерархии уровневые (leveled), в другом случае - агрегация. Для трехмерного куба (регионы, продук несбалансированные (ragged). ты, время года) структура будет выглядеть следую Примеры типов иерархий: щим образом (рис. 1):
уровневые: деньЦмесяцЦгод;
улица - город - Таким образом, в получившейся структуре куба страна;
материализуется набор представлений, содержа несбалансированные: Организационная диа щий агрегированные данные. Подобные предста грамма, различная группировка продуктов. вления называются подкубами (англ cuboids). Ячей ки базового подкуба называются базовыми ячейками, 68 БИЗНЕС ИНФОРМАТИКА №1Ц2008 г.
Например, нас будут интересовать лишь покупки на сумму свыше 500 рублей. Такой подход позволя ет точнее сфокусировать анализ, сократить время вычисления и отклика. Подобные частично вычи сленные кубы называются кубами айсбергами (англ. iceberg cubes), так большая часть их данных скрыта под водой. Простой подход к вычислению кубов айсбергов заключается в следующем: сначала вычислить весь куб, затем применить условие и отрезать неудовлетворяющие ячейки. Но это слишком расточительно. Нужно вычислять куб айсберг, не вычисляя полный куб. Использование ограничений на значение меры может приводить к ситуациям, требующим бессмысленных повторных. 1. Структура куба в виде набора представлений для аг вычислений. Например, в стомерном кубе суще регации ствуют всего 2 ячейки, отличающиеся по значе ниям одного измерения. Если меры в этих ячейках ячейки других подкубов называются агрегированны больше заданной границы, появится множество ду ми ячейками. блирующих эти суммы ячеек (по всем 99 измере Выбор материализованных элементов этого на ниям), а на деле в кубе разнятся всего три из них.
бора определяет будущую производительность си Множество работ посвящено выбору комплекса стемы. Мы можем получить набор представлений, представлений (подкубов) для материализации.
при использовании которого для выполнения запро Из них необходимо выделить [HRU96], где впервые сов не будет производиться более 1Ц2 агрегаций (по приведена модель оценки стоимости материализа одному измерению), что означает очень быстрый от ции представлений и создания агрегаций. На базе вет на запрос. И наоборот, возможна ситуация, в ко подобных оценок создан алгоритм материализации торой для ответа на запрос необходимо будет созда представлений, оптимизирующий запросы по стои вать все агрегации от фактических данных (базового мости. Но применимость алгоритма [HRU96] и мно куба). Однако количество подкубов экспоненциаль гих последующих сильно ограничена типами запро но зависит от количества измерений, поэтому пол сов, распределением данных, структурой куба и пр.
ная материализация может требовать огромного Ограничения накладываются самими авторами, объёма памяти и места на жестком диске. поэтому часто создаются эффективные алгоритмы.
Изучение алгоритмов полной материализации Доказано, что общая проблема выбора представле помогает в расчётах индивидуальных подкубов. ний для материализации NP полна [KM99], поэтому В дальнейшем их можно хранить на второстепен интересной темой представляется создание алгорит ных носителях, или же создавать полные кубы на мов полной материализации (materialize all) куба, основе подмножества измерений и осуществлять поскольку их применение не имеет подобных огра детализацию (drill down) в исходные данные. ничений и не зависит от выбора начальных параме Подобные алгоритмы должны быть масштабируе тров. Необходимо заметить, что большинство про мыми, принимать во внимание ограниченное коли мышленных OLAP систем строятся на фактических чество оперативной памяти, время вычисления данных, хранимых в реляционных таблицах, поэто и общий размер рассчитанных данных. му обоснованный выбор и последующая настройка Многие ячейки кубов могут не представлять ин набора материализованных представлений даёт тереса для аналитиков, так как данные в них прене результаты выше, чем существующие промышлен брежимо малы. Подобная ситуация возникает ча ные алгоритмы полной материализации.
сто, так как данные разреженно распределены Главная проблема подхода полной материализа в многомерном пространстве куба. Например, ции (materialize all) - это взрыв данных, при кото клиент покупает каждый раз лишь несколько това ром объём данных и время вычисления куба растут ров в одном магазине. Подобное событие будет экспоненциально. Например, десятимерный куб без отражено в виде набора ячеек с малыми показате иерархии внутри измерений, с размерностью 100 для лями мер (объём покупки, количество предметов). каждого измерения, приводит к структуре с ячейка В таких случаях полезно вычислять лишь ячейки со ми. Даже если мы положим разреженность 1 (только значением меры, большим определённой границы. одна из миллиона ячеек содержит данные), куб всё БИЗНЕС ИНФОРМАТИКА №1Ц2008 г. равно будет иметь 1,1^14 непустых ячеек. Таким об HOLAP (Hybrid OLAP) - базовые данные хра разом, сокращение размера куба - насущная задача нятся в реляционной таблице, агрегированные - создателей OLAP приложений. в многомерной структуре.
Еще одно важное ограничение - требование Данный метод пытается совмещать достоинства сохранения семантики отношений обобще предыдущих, не имея их недостатков, но по скоро ния/специализации (roll up/drill down). Отбрасы сти он проигрывает MOLAP. Кроме того, с его по вая это требование, многие алгоритмы достигают мощью невозможно целостное хранение данных хороших результатов, но восстановление этих отно и возрастают затраты на поддержку и определение шений в дальнейшем либо невозможно, либо труд типа хранения для подкубов.
но вычисляется, что ограничивает возможность применения подобных алгоритмов.
ВЫВОДЫ СПОСОБЫ ХРАНЕНИЯ OLAP технологии - актуальная и востребован ROLAP (Relational OLAP) - данные, включа ная тема исследований, её практические результаты ющие в себя все возможные агрегации, хранятся имеют широкое применение.
в реляционных таблицах. Все запросы пользовате Несмотря на достаточно долгую историю иссле ля транслируются в SQL операторы выборки из дований, до сих не существует единых терминоло данной таблицы. гических стандартов, стандартов передачи данных, Плюсы данного подхода: все данные хранятся языка запросов и формирования кубов. Растущие внутри одной СУБД в одном формате. объёмы корпоративных данных повышают значи Минусы данного подхода: чрезмерное увеличе мость средств анализа, большая часть которых по ние объёма таблицы данных для куба и сложности строена на OLAP принципах, в связи с чем актуаль пересчёта агрегированных значений при измене ны проблемы выбора оптимальных схем хранения и ниях начальных данных. обработки OLAP кубов. Интеграция различных ис MOLAP (Multidimensional OLAP) - все данные точников информации для анализа порождает но хранятся в многомерной базе данных. вые применения аналитических технологий, на Все запросы пользователя транслируются в запро пример, для анализа данных геопозиционирования сы многомерной выборки (MDX, Express 4GL и др). (GPS) в привязке к финансовой информации ис Плюсы данного подхода: все данные хранятся пользуются spatioOLAP технологии. Задачи бю в многомерных структурах, что существенно повы джетирования, требующие совмещения скорости шает скорость обработки запросов. ввода транзакционных систем и аналитических Минусы данного подхода: данные куба лоторва возможностей OLAP, представляют собой особый ны от базовой таблицы, необходимы специальные класс систем, алгоритмическая база которых только инструменты для формирования кубов и их перес создается.
чёта в случае изменения базовых значений.
Литература [AS94] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules. In Jorge B. Bocca, Matthias Jarke, and Carlo Zaniolo, editors, Proc. 20th Int. Conf. Very Large Data Bases, VLDB, pages 487Ц499. Morgan Kaufmann, 12Ц15 1994.
[BR99] Kevin Beyer and Raghu Ramakrishnan. Bottom up computation of sparse and iceberg cubes. In SIGMOD, 1999.
[Cod93] E.F. Codd. Providing OLAP for end user analysys: An IT mandate. 1993.
[GBLP95] Jim Gray, Adam Bosworth, Andrew Layman, and Hamid Pirahesh. Data cube: A relational aggregation operator generalizing group by, cross tab, and sub totals. Microsoft Lab, 1995.
[GC97] Sanjay Goil and Alok Choudhary. High performance olap and data mining on parallel computers. Center of Parallel and Distributed Computing Technical Report TR 97 05, 1997.
[HRU96] Venky Harinarayan, Anand Rajaraman, and Jeffrey Ulman. Implementing data cubes efficiently. SIGMOD, 1996.
[KM99] H.J. Karloff and M. Mihail. On the complexity of view selection problem. In PODS, 1999.
[SG99] Gerd Stumme and Bernhard Ganter. Formal Concept Analysis Mathematical Foundations. Springer, 1999.
[SR04] Yannis Sismanis and Nick Roussopoulos. The polynomial complexity of fully materialized coalesced cubes. In VLDB, 2004.
[SS01] Sunita Sarawagi and Gayatri Sathe. Intelligent rollups in multidimensional olap data. In VLDB, 2001.
[Tho02] Erik Thomsen. OLAP Solutions: Building Multidimensional Information Systems Second Edition. Wiley Computer Publishing John Wiley & Sons, Inc., 2002.
70 БИЗНЕС ИНФОРМАТИКА №1Ц2008 г.