Введение к работе
Актуальность темы исследования. Сегодня разработка программных средств, предназначенных для хранения и обработки больших объемов разнородных данных, является одним из активно развиваемых направлений ИТ-отрасли, которые дают возможность проводить комплексный многомерный анализ больших объемов различного типа информации (финансовой, статистической, операционной и т.п.) и представлять полученные результаты в виде различных консолидированных отчетов. Основным инструментом, используемым для решения задач обработки многомерных данных, являются OLAP-системы (Online Analytical Processing (OLAP) - оперативная аналитическая обработка, русскоязычный синоним - аналитические информационные системы - АИС). OLAP-технология обработки информации, включающая составление и динамическую публикацию отчётов и документов.
Сегодня в соответствующем сегменте рынка программного обеспечения (ПО) представлено множество OLAP-систем различных производителей: от проприетарных систем (Microsoft Analysis Services, Oracle OLAP Option и т.п.) до свободного программного обеспечения с открытым программным кодом (Mondrian, Palo). Производительность любой СУБД, в том числе и OLAP-системы, напрямую зависит от эффективности применяемого метода доступа к данным - механизма поиска данных, используемых в определённом аналитическом запросе. Например, традиционный для СУБД метод индексирования данных <К,А>, где K={h h h } - набор элементов из D
иерархий {Hi,H2,..HD} реализуется следующими преобразованиями:
(p:K^R\Rl=[0M
Oj-.Hj >R\[OMJ = 1,2,. .D,
(p(h) = d -v^ih^ + d1 -v^h^ + d2 -v^h^)+ ...,d «\,d >0.
Как следствие, количество отрезков из Rl, которые необходимо рассмотреть при расчёте агрегатного запроса Q{h}, экспоненциально быстро увеличивается при увеличении размерности данных D.
Отметим, что открытые OLAP-системы, в отличие от проприетарных OLAP-систем не имеют механизмов доступа к данным. Однако их описания в свободном доступе обнаружить не удается, а потому о методах, используемых в данных системах, можно судить только косвенно, анализируя информацию, приводимую в описаниях данных программных продуктов и в интервью разработчиков. Другим недостатком существующих OLAP-систем является их нацеленность на анализ статических, но не динамических (собираемых и обновляемых в реальном времени) данных.
В данный момент большинство исследований OLAP-систем, главным образом, направлено на изучение различных прикладных аспектов, связанных с проектированием и эксплуатацией OLAP-систем, и, в первую очередь, различных способов их применения. Вместе с тем, устоявшихся принципов построения OLAP-систем, закреплённых соответствующими стандартами,
пока не создано. В то же время необходимо отметить, что за прошедшие 30 лет активно велись работы по разработке теории и методов практического использования пространственного индексирования данных геоинформационных систем (ГИС). (Размерность данных ГИС принимает значение от 2 до 4). Здесь решён целый ряд проблем, связанных с организацией быстрого доступа к многомерным данным, в том числе разработаны эффективные алгоритмы пространственного индексирования. При этом задачи обработки данных, решаемые ГИС, в целом оказываются схожими с задачами обработки данных OLAP-систем.
В связи с этим, разработка на основе идей пространственного индексирования, используемых в ГИС, алгоритмов доступа к многомерным данным в OLAP-системах, зависимость вычислительной сложности которых от размерности данных не выше полиномиальной, является актуальной задачей. (Далее, проводя аналогию с быстрым преобразованием Фурье, для краткости будем называть данные алгоритмы быстрыми алгоритмами доступа к многомерным данным.)
Объект исследования: методы анализа многомерных данных.
Предмет исследования: алгоритмы доступа к многомерным данным в OLAP-системах.
Цель диссертационной работы: разработка быстрых алгоритмов доступа к многомерным данным в OLAP-системах, основанных на использовании пространственных индексов.
Для достижения поставленной цели решаются следующие основные задачи исследования:
Провести анализ методов доступа к данным в ГИС-системах с точки зрения возможности их использования в OLAP-системах.
Разработать быстрые алгоритмы доступа к многомерным данным АИС, основанные на принципах пространственного индексирования данных ГИС.
Получить теоретические оценки эффективности быстрых алгоритмов доступа к многомерным данным АИС.
Разработать программные реализации быстрых алгоритмов доступа к многомерным данным АИС.
Провести анализ результатов внедрения программных реализаций быстрых алгоритмов доступа к многомерным данным АИС.
Методы исследования. В работе были использованы методы теории вероятности, математической статистики, теории кодирования, теории параллельного программирования, теории систем управления базами данных (СУБД).
Научная новизна полученных результатов. К основным новым результатам, полученным в диссертации, можно отнести следующие:
Обоснование возможности и целесообразности использования пространственных индексов, применяемых в ГИС-системах, для индексирования данных в OLAP-системах.
Быстрые алгоритмы доступа к многомерным данным АИС, основанные на принципах пространственного индексирования данных ГИС.
Аналитические модели, позволяющие оценивать эффективность быстрых алгоритмов доступа к многомерным данным в OLAP-системах.
Практическая значимость работы
Разработана программная реализация быстрых алгоритмов доступа к многомерным данным АИС - открытая программная библиотека «Индексирование многомерных классифицированных данных» (ИМКД), которая использована при разработке ПК «САПФИР», программной платформы (ПП) «Сектор», ПК «Карбон». Анализ результатов ее использования подтверждает высокую эффективность предложенного в диссертации подхода.
Проведен сравнительный анализ эффективности разработанных быстрых алгоритмов доступа к многомерным данным АИС и известных алгоритмов, не использующих методы пространственного индексирования данных.
Описаны особенности практического применения пространственного индексирования и структурирования запросов, а также их использования для решения типовых задач OLAP-систем.
Результаты, полученные в ходе выполнения настоящей диссертационной работы, могут быть использованы при разработке АИС, предназначенных для сбора, хранения и анализа больших объёмов данных.
На защиту выносятся:
1. Быстрые алгоритмы доступа к данным OLAP-систем, основанные на
методах пространственного индексирования данных ГИС.
Математические модели оценки эффективности аналитических агрегирующих запросов, использующих быстрые алгоритмы доступа к многомерным данным АИС.
Теоретические и экспериментальные результаты оценки эффективности быстрых алгоритмов доступа к данным АИС.
Достоверность полученных результатов подтверждается обоснованным применением методов теории СУБД, ГИС, теории вероятности и математической статистики, а также согласованностью теоретических результатов с результатами экспериментальных исследований программных реализаций разработанных методов доступа к данным в OLAP-системах. Внедрение результатов диссертационного исследования Результаты диссертационного исследования использованы в ООО «Ок-тоника», ООО «Научно-производственное объединение «Сапфир» при разработке программной библиотеки «ИМКД», ПК «САПФИР», ПК «Карбон» и ПП «Сектор», а также в ФГОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина» в учебном процессе при под-
готовке бакалавров и магистров по направлению «Информатика и вычислительная техника».
Результаты диссертационного исследования были включены в инновационный проект, представленный на конкурсе, проводимом в 2010 г. Фондом содействия развитию малых форм предприятий в научно-технической сфере. По результатам конкурса проект стал победителем программы «Участник Молодежного Научно-Инновационного Конкурса» («УМНИК») 2010 г.
Апробация работы
Материалы работы докладывались на следующих научных конференциях: Международной научно-практической конференции «СВЯЗЬ-ПРОМЭКСПО 2008», Екатеринбург, 6-8 мая 2008 г.; Седьмой Российской конференции с международным участием «Новые информационные технологии в исследовании сложных структур», Томск, 2-5 сентября 2008 г.; Международной научно-практической конференции «СВЯЗЬ-ПРОМЭКСПО 2009», Екатеринбург, 17-19 марта 2009 г.; Межвузовской научной конференции по проблемам информатики «СПИСОК 2009», Екатеринбург, 20-23 апреля 2009 г.; Международной научно-практической конференции «СВЯЗЬ-ПРОМЭКСПО 2010», Екатеринбург, 5-7 мая 2010 г.
Публикации по теме диссертации. По результатам исследований опубликовано 8 печатных работ, из которых в рекомендованных ВАК РФ периодических изданиях - 4, получено свидетельство о регистрации электронного ресурса, а также свидетельство о регистрации программы для ЭВМ.
Структура диссертационной работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка использованных источников, содержащего 105 наименований, и 2-х приложений. Общий объем работы составляет 163 страницы, в том числе 26 рисунков, 8 таблиц.
