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

Одним из самых интересных алгоритмов сжатия OLAP-кубов представляется алгоритм Quotient Cube ([6]) и также основанный на понятии замыкания ячеек куба алгоритм CCubing([7]). Представление многомерных кубов в виде решеток дает возможность использования операторов замыкания для формирования классов эквивалентности ячеек куба и соответствующей оптимизации объема хранимых ячеек.

В связи с вычислительной сложностью задачи расчета OLAP-кубов представляется целесообразным распараллеливать вычисления на многопроцессорных серверах и кластерах серверов. Популярная парадигма параллельного программирования Map/Reduce ([3]), созданная в Google, поддерживает кластера, включающие десятки тысяч серверов, обеспечивая отказоустойчивость и масштабируемость вычислений.

В докладе будут рассмотрены следующие вопросы:

1. Математическая модель описания OLAP-кубов, основанная на теории решеток. В рамках указанной модели доказана эффективность представления кубов замкнутыми решетками.
2. Алгоритм параллельного создания и обработки замкнутых кубов.
3. Представление алгоритма в виде Map/Reduce задач, выполняющихся на Apache/Hadoop кластере.

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

Литература:

1. Providing OLAP for end-user analysys: An IT mandate. E.F. Codd.
2. OLAP Solutions: Building Multidimensional Information Systems Second Edition. Erik Thomsen. ISBN: 978-0471400301.
3. J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. Operating Systems Design and Implementation, 2004.
4. R.Baeza-Yates, R.Ramakrishnan. Data challenges at Yahoo! EDBT-08.
5. D. Xin, Z. Shao, J. Han, and H. Liu. C-cubing: Efficient computation of closed cubes by aggregation-based checking. ICDE-2006.
6. Y. Zhao. Quotient Cube and QC-Tree: Efficient Summarizations for Semantic OLAP, SIGMOD 2003.
7. Кудрявцев Ю. Обзор алгоритмов MOLAP. http://citforum.ru/consulting/BI/molap_overview/
8. Кузнецов С.Д., Кудрявцев Ю. «Математическая модель OLAP-кубов». http://ykud.ru/articles/olap_lattices/index.html