В 1993 году Э. Коддом была предложена концепция OLAP-систем (Online Analytical Processing), включающая в себя 12 правил представления данных пользователю. Подобные системы, как следует из названия, предназначены для анализа данных в интерактивном режиме. В связи с этим основной задачей OLAP-средств является представление больших объемов данных в виде, удобном для анализа конечными пользователями.

В 1995 году группа исследователей из Microsoft Lab во главе с Д. Греем предложила расширение языка SQL для поддержки и создания многомерных кубов для визуализации данных(оператор Cube By) [1]. Представление данных в виде многомерных кубов в настоящее время является de facto стандартом пользовательской работы с большими массивами данных. Доклад посвящен исследованиям в области создания схем хранения MOLAP-данных. MOLAP-системы (Multidimensional OLAP) хранят как фактическую информацию для генерации кубов, так и агрегаты в виде многомерных структур. Дается обзор существующих методов хранения и алгоритмов преобразования MOLAP-данных, перспективным направлениям исследований и созданию математической модели представления OLAP данных.

Рассматриваются следующие группы алгоритмов:

• синтаксические – алгоритмы, преобразующие только схему хранения данных (например, DWARF [2])
• семантические – алгоритмы, преобразующие структуру куба, например, меняющие roll-up, drill-down последовательности и систему агрегатов (например, Quotient Cube[3], Condensed[4])
• аппроксимирующие – алгоритмы, осуществляющие сжатие первоначальных данных для уменьшения объема результирующего куба(например, аппроксимация на базе вейвлетов [5]).

Описывается ряд последних разработок в области визуализации OLAP-данных, основанных на исследованиях особенностей восприятия информации [6].

В заключение предлагается алгебраическая модель многомерного куба, вводятся алгебраические определения ключевых для OLAP операций Roll-Up и Drill-Down, определение отношений эквивалентности между структурами кубов и структур с учетом сложных запросов к данным [7]. С помощью приведенной модели проводится доказательство оптимальности ряда алгоритмов создания и хранения OLAP-кубов.

Слайды к докладу в формате PDF: Kudriavzev.pdf

Литература:

1. Jim Gray, Adam Bosworth, Andrew Layman, Hamid Pirahesh. Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals.
   http://research.microsoft.com/research/pubs/view.aspx?type=Technical%20Report&id=144
2. Yannis Sismanis Antonios Deligiannakis Nick Roussopoulos Yannis Kotidis. Dwarf: Shrinking the PetaCube .
   http://www.cs.umd.edu/~nick/projects/Dwarf.pdf
3. Yan Zhao. Quotient Cube and QC-Tree: Efficient Summarizations for Semantic OLAP.
   http://www.cs.ubc.ca/nest/dbsl/thesis/yzhao_thesis.pdf
4. Wei Wang, Jianlin Feng, Hongjun Luy, Jeffrey Xu Yu. Condensed Cube: An Effective Approach to Reducing Data Cube Size.
   http://www-courses.cs.uiuc.edu/~cs591han/papers/luhjcubeicde02.pdf
5. Jeffrey Scott Vitter, Min Wangy, Bala Iyer. Data Cube Approximation and Histograms via Wavelets (Extended Abstract).
   http://www.cs.duke.edu/~jsv/Papers/VWI98.data_cube.pdf
6. Andreas S. Maniatis,Panos Vassiliadis,Spiros Skiadopoulos,Yannis Vassiliou. Advanced Visualization for OLAP.
   http://www.cs.brown.edu/courses/cs227/Papers/Visualization/DOLAPmaniatis.pdf
7. Alain Casali, Rosine Cicchetti, Lotfi Lakhal. Cube Lattices: a Framework for Multidimensional Data Mining.
   http://www.siam.org/meetings/sdm03/proceedings/sdm03_35.pdf