Алгоритмы эффективной обработки MOLAP-кубов

• Автор: Кудрявцев, Юрий Александрович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 142 с. : ил.

Оглавление

1 Введение б

1 Объект исследования и актуальность темы

2 Цели и задачи исследования

3 Научная новизна

4 Положения, выносимые на защиту.

5 Апробация результатов работы.

6 Содержание работы.

2

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

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

2 I тест
2.2 Многомерные кубы, определение и свойства
1 Пример
2 Измерения.
3 Иерархии и агрегирование
2.3 Виды запросов к кубам
1 Точечные запросы i i
2 Интервальные запросы. i
3 Обратные запросы. I i.
4 Ii запросы.
2.4 Хранение и эффективный расчет кубов
1 Представление нулевых данных
2 Взрыв данных .
3 Материализация представлений .
2.5 Общие стратегии вычисления кубов
1 Способы хранения
2 Классификация алгоритмов хранения АРданных
2.6 и статистические базы данных.
3.1 Требования к многомерным моделям данных.
3 Анализ существующих алгоритмов
3.2 Алгоритм
1 Виды избыточностей структуры куба.
2 Структура куба
3 Выполнение различных типов запросов.
4 Сложность
5 Виды сжатия.
6 Вывод.
3.3 Многопозиционное агрегирование массивов для вычисления
кубов.
1 Пример Вычислений.
3.4 Аппроксимирующие алгоритмы
1 Вейвлеты
3.5 Алгоритм i
3.6 Алгоритм i
3.7
3.8 i .
1 Разбиение на классы ячеек
2 .
3 Выполнение различных типов запросов
4.1 Некоторые определения из теории решеток.
1 Частичноупорядоченное множество, решетка
2 Описание решеток. Изомофизм решеток. Оператор замыкания.
4 Математическая модель данных
4.2 Математическая модель кубов
1 Общие определения. Меры, измерения, операторы в
многомерном пространстве
2 Операторы в г
3 Классы эквивалентности решетки куба
4 Замыкания и замкнутые решетки кубов
5.1 парадигма параллельных вычислений
1 на многопроцессорных машинах
2 и .
5 Алгоритм вычисление замкнутых кубов с использованием

5.2 Предложенный алгоритм
1 Общий подход к вычислениям .
2 Алгоритм создания замкнутого куба на многопроцессорном сервере.
3 Результаты экспериментов.
6 Заключение
Литература


Multidimensional - многомерной, данные должны представляться в виде многомерных кубов. Information - данные должны быть полны с точки зрения аналитика, т. Джимом Греем [GBLP], проанализировав создававшиеся тогда пользовательские приложения баз данных, и предложив расширение языка SQL - оператор CUBE. Этот оператор отвечает в SQL за создание многомерных кубов. Концепция многомерного представления данных является, наряду с моделью транзакций, одной из самых известных идей Кодда. В этой работе исследователи указали ряд эвристических рекомендаций но реализации новой структуры данных. CUBE представляет собой обобщение операторов GROUP BY по всем возможным комбинациям измерений с разными уровнями агрегации данных. Каждая сгруппированная таблица относится к группе ячеек, описываемых кортежами из измерений, по которым формируется куб. Оператор, расширяющий SQL, называется CUBE BY (синтаксис такой же, как и у GROUP BY). Дальнейшее развитие OLAP-операций в SQL привело к тому, что в стандарт SQL’ был включен набор операторов для работы с OLAP-данными (запросы grouping set, rollup by, cube by, window by, rank, rownura и пр. В реализации подобных OLAP-приложений возникает ряд проблем, прежде всего связанных с экспоненциальным увеличением объема данных, которые необходимо хранить или рассчитывать. Следующие особенности работы определяю! OLAP-кубов предложен алгоритм, использующий парадигму Map/Reduce. См 5. Apache Hadoop (многомашинный кластер, см [KMSB]) и Standord Phoenix (использование map/reduce для многопроцессорных серверов, см [RRP+]), проведены эксперименты, показывающие преимущества данного алгоритма по отношению к уже существующим, см § 3. Алгоритм параллельного создания замкнутых OLAP-кубов, созданный на основе map/reduce парадигмы (см [DG]), 5. На семинаре ’Проблемы современных информационновычислительных систем’ под управлением Васенина В. Неоднократно на семинаре ’Технологии баз данных’ иод управлением Кузнецова С. Д. и Маркова А. Математическая модель OLAP-кубов5, Кузнецов С. Д., Кудрявцев Ю. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Во введении раскрывается актуальность темы диссертации, формулируются проблемы исследования, определяется цель работы, описываются методы исследования, излагаются основные научные результаты, обосновывается теоретическая и практическая значимость работы, даётся её общая характеристика. В Главе 2 — “OLAP” описана одноименная задача, указано на ее ключевую роль в анализе данных. Приводятся основные определения, история задачи, основные проблемы. Дается основания для классификации методов. В Главе 3 — “Анализ существующих алгоритмов” приводится обзор различных подходов создания OLAP-кубов на базе классификации из главы 1. Указываются недостатки и достоинства алгоритмов, лучшие ситуации для применения тех или иных алгоритмов. Глава 4 — “Математическая модель OLАР-данных” содержит математическую модель OLAP данных. Указывается связь между OLAP-моделью и рядом определений теории решеток. Доказывается оптимальность представления кубов замкнутыми решетками. Глава 5 — “Предложенный алгоритм. Результаты экспериментов” содержит краткий обзор парадигмы параллачьных вычислений Map/Reduce, описание предложенного алгоритма создания OLAP-кубов с использованием Map/Reduce кластеров и результаты проведенных экспериментов. Термин OLAP был введен в Эдгаром Кодцом [Cod|. OLAP систем - облегчение решения задач анализа данных. Многомерная концепция данных. OLAP оперирует CUBE (см далее описание работ’ Грея [GBLP]) данными, которые являются многомерными массивами. Число измерений OLAP кубов не ограничено. Прозрачность. OLAP системы должны опираться на открытые системы, поддерживающие гетерогенные источники данных. Доступность. OLAP системы должны представлять пользователю единую логическую схему данных. Постоянная скорость выполнения запросов. Производительность не должна падать при росте числа измерений. Клиент/сервер архитектура. Системы должны базироваться на открытых интерфейсах и иметь модульную структуру.