автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Многомерная битовая логическая модель представления информации в базах данных

Введение.

Актуальность темы.

Цель работы и задачи исследования.

На защиту выносится.

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

Глава 1. Битовая многомерная модель представления данных.

1.1 Особенности битовой гиперкубической модели представления данных.

1.2 Недостатки гиперкубической модели и методы их преодоления.

1.3 Определение символики описания компонентов битовой многомерной модели.

1.4 Конвертирование классической многомерной модели данных в битовую.

1.5 Выводы по первой главе.

Глава 2. Алгебра операций над информационными объектами многомерного гиперкуба и его окружением.

2.1 Элементарные операции над атомарными информационными объектами многомерного гиперкуба.

2.1.1 Удаление.

2.1.2 Изменение.

2.1.3 Добавление.

2.1.4 Реляционная аналогия.

2.2 Основные операции над информационными объектами гиперкуба

2.2.1 Операции над многомерными множествами.

Объединение.

Пересечение.

2.2.2 Дискретные операции многомерной алгебры.

2.2.3 Специальные операции многомерной алгебры.

Надстройка.

Порождение.70

Проецирование.71

2.3 Операции над множествами размерностей.73

Пересечение.75

Вычитание.76

Объединение.77

2.4 Операции над разнотипными информационными объектами.78

Операции сравнения информационных объектов гиперкуба.78

Произведение.79

Деление.80

2.5 Выводы по второй главе.82

Глава 3. Разработка программного обеспечения, реализующего предложенную модель хранения данных и оценка практического эффекта.84

3.1 Уровни абстракции информационной системы контроля и учета сетевого трафика.85

3.2 Схема данных информационной системы контроля и учета сетевого трафика.89

3.3 Оценка эффективности предложенных методов в сфере контроля и учета сетевого трафика.95

3.4 Выводы по третьей главе.103

Заключение.106

Список литературы.108

Приложение 1. Иллюстрация первой подзадачи транзакций синтеза гиперкуба.121

Приложение 2. Примеры MDX-запросов, использованных при оценке эффективности предложенных методов.122

Введение

Актуальность темы

Системы хранения и обработки информации, или, по-другому, системы управления базами данных (СУБД) в настоящее время являются одним из самых важных компонентов информационных систем. Во многих сферах жизнедеятельности человека специфика предметной области предъявляет к хранению и обработке данных очень жесткие требования. Это обусловлено необходимостью производить сложный анализ большого количества информации. К таким предметным областям можно отнести, например сбор статистических данных с многочисленных объектов нефтедобычи, экологический мониторинг какого-либо региона, дистанционное образование и т.д.

Предметной областью данной работы является контроль и учет сетевого трафика на уровне крупных интернет-провайдеров. Выбор данной сферы обусловлен тем, системы связи сегодня используются повсеместно. С совершенствованием интернет-технологий к системам контроля сетевого трафика предъявляются все более высокие требования, касающиеся в первую очередь их производительности. Это обусловлено тем, что таким системам приходится оперировать большими потоками самой разнообразной информации. Это могут быть данные о клиентах, о состоянии их счета, о запрашиваемых ими ресурсах, о времени и скорости соединения и т.д. [70, 80].

Одним из ключевых понятий любой СУБД является структура хранимых данных. Под структурой данных обычно понимают совокупность связей и ограничений между различными частями данных, которая образовалась при конкретном способе декомпозиции [2, 4, 13, 18, 54]. С этим понятием тесно связано понятие модели данных. Модель данных — это структура данных вместе с множеством операций над элементами этой структуры [61, 64, 94]. Модель данных предоставляет пользователям СУБД средства описания данных и средства манипулирования ими [15, 26].

В современных СУБД можно выделить два основных класса моделей данных - это логическая и физическая модели [4, 58, 116]. Логическая модель представления данных отвечает за диалог СУБД с конечным пользователем, позволяет ему описывать данные, строить запросы и оценивать их результаты. Эта модель является безотносительной к конкретной реализации на ЭВМ. Физическая модель описывает структуру хранения данных на устройствах памяти ЭВМ и отвечает за быстрое реагирование на команды логической модели и оптимальное размещение данных на физических носителях [58, 83, 84, 116, 132].

В настоящей работе будут рассматриваться логические модели представления данных, поскольку именно они являются инструментами конечных пользователей, предназначенными для реализации сложной аналитической обработки данных.

Для сравнения характеристик логических моделей представления данных обычно используют следующие критерии [22, 50,100]:

• используемый подход к хранению и обработке информации;

• максимально возможный объем хранимых данных;

• средняя и максимальная скорость выполнения запросов;

• наличие средств хранения и работы с «хронологическими» данными

• степень развития аппарата математической формализации данных и операций для этой модели.

Среди известных подходов к хранению и обработке информации можно выделить два основных типа: OLTP и OLAP. Термин OLTP (OnLine Transaction Processing) в разных источниках [5, 8, 13, 24] переводится как транзакционная обработка данных или интерактивная диалоговая обработка запросов. Системы, построенные на концепции OLTP (оперативные системы) обеспечивают регистрацию некоторых фактов, их непродолжительное хранение и сохранение в архивах. OLTP-приложения обычно автоматизируют офисные задачи по обработке данных типа входных ордеров, банковских транзакций и т.п. Эти задачи - структурируемы, повторяемы и состоят из коротких, изолированных транзакций. Операционные базы данных являются, как правило, реляционными и имеют размеры от сотен мегабайт до гигабайтов. Термином OLAP (OnLine Analytical Processing) обозначают принцип многомерного представления данных [9, 23, 25, 52, 82, 91]. Известно, что реляционные системы управления базами данных и OLTP-подход не способны объединять, просматривать и анализировать данные с точки зрения множественности измерений (то есть самым понятным для аналитиков способом) [46, 58, 62]. Таким образом, в системах, где требуются продвинутые средства анализа данных, применяется именно OLAP-подход. Базы данных, построенные на основе этого подхода называются аналитическими и имеют значительно большие по сравнению с оперативными БД размеры.

Актуальность проблемы манипуляции большими объемами данных объясняется тем, что рост этих объемов напрямую связан со снижением быстродействия системы, что может пагубно отразиться на быстроте принятия того или иного важного решения. В системах контроля сетевого трафика это может привести к запоздалой реакции на вирусные атаки, появлению слабых мест в защите серверов, выполняющих важные функции, и к общему снижению информационной безопасности. Данную проблему можно решать на физическом уровне (распределение системы и совершенствование ее аппаратных характеристик) и на логическом уровне (совершенствование структуры представления данных). Решение проблемы на физическом уровне приносит весьма хорошие результаты, но они сопровождаются ростом стоимости аппаратных компонентов системы, что является неприемлемым в условиях дефицита денежных средств. Существующие же на сегодняшний момент решения на логическом уровне представлены такими подходами как «Хранилища данных» (DataWarehouses), «Витрины данных» (DataMarts) и, соответственно, присущими им логическими моделями представления данных.

Термин DataWarehousing в переводе означает «создание, поддержку, управление и использование хранилища данных» [101, 105, Í17, 120]. Общая архитектура этих концепций выглядит следующим, показанным на рисунке I образом.

Оперативные данные (то есть текущая информация) собираются из различных источников, очищаются, интегрируются и складываются в реляционное хранилище. При этом они уже доступны для анализа на уровне построения отчетов. Полноценные же возможности для анализа данных появляются лишь после загрузки (полной или частичной) их в специальное, многомерное ОЬ АР-хранилище.

Как видно из приведенной на рисунке 1 схемы большая часть одних и тех же данных хранится в двух, или даже в трех, различных местах.

Однако этот подход к хранению данных вызывает такие негативные последствия, как: а) необходимость

Оперативные базы данных

Построение отчетов

OLAP-клиент

Рис. I Архитектура Data Warehouse применения средств переноса и трансформации данных, на функционирование которых приходится отводить большое количество времени; б) сильная избыточность данных и, как следствие, резкое увеличение размеров БД [45].

Кроме того, ОЬАР-хранилище подразумевает необходимость хранения предвычисленных агрегатных значений (то есть суммарных, усредненных, статистических показателей, вычисленных на основе имеющихся данных), что еще больше усугубляет проблему избыточности данных.

Проблема обеспечения приемлемой скорости выполнения любых запросов, как простых, так и сложных, комплексных является особенно актуальной в тех сферах, где требуются средства анализа для принятия решений. В рассматриваемой предметной области, например, заранее предугадать, какие виды анализа и формы отчетности могут потребоваться пользователям системы при работе с ней, как правило, невозможно. Это исключает возможность подстройки системы «под конкретные нужды», которая смогла бы повысить скорость выполнения некоторых запросов ценой снижения скорости выполнения остальных. При решении данной проблемы, разработчики останавливают свой выбор либо на OLTP, либо на OLAP технологиях.

В OLTP-системах используются широко известные реляционные базы данных. Реализация систем принятия решений на OLTP системах, как правило, приводит к неудаче [14, 49, 59, 108, 132], так как, во-первых, аналитические запросы конкурируют с оперативными транзакциями, блокируя данные и вызывая нехватку ресурсов сервера БД, во-вторых, структура оперативных данных (обычно это 3-я нормальная форма) состоит из множества сложным образом связанных таблиц и поэтому конечному пользователю понять ее слишком сложно. И, в-третьих, такая структура не обеспечивает должной л скорости выполнения сложных аналитических запросов, так как в одном запросе связывается большое количество таблиц.

Построение же таких систем на основе технологии OLAP также имеет отрицательные стороны. Слабое место многомерной OLAP - плохая масштабируемость (с увеличением объема данных производительность может непропорционально падать) [62, 97], реляционная же OLAP со схемой звезды или снежинки проигрывает в том, что из-за ограничений реляционной схемы продолжительность выполнения запроса зависит от того, по какому измерению производится срез куба или построение агрегата. В этом случае максимальная скорость выполнения запросов может очень сильно отличаться от средней.

Наличие средств хранения и работы с «хронологическими» данными актуально тем, что именно они зачастую и составляют основу для принятия того или иного решения, для формирования подавляющего большинства отчетов и для функционирования алгоритмов, направленных на самообучение и развитие системы [56, 84]. Существующие подходы к проблеме хронологических данных сегодня, как правило, основываются на технологиях DataWarehousing и Write-back. Основным положением первой является наличие большого хранилища неизменяемых исторических данных (то есть OLAP-хранилища). Недостатки такого подхода очевидны - ограниченность набора запросов к такой базе только запросами на выборку данных и невозможность моделирования различных ситуаций типа «что если?», так как это предполагает изменение (пусть и кратковременное) исторических данных [83, 84, 95]. Вторая же позволяет обойти принцип неизменяемости, но делает это за счет образования дополнительных структур хранения измененных данных, что обуславливает рост размеров такой базы [82, 90, 133].

Из вышеприведенного анализа можно сделать вывод о том, что для вышеупомянутых предметных областей, и, в частности, для контроля и учета сетевого трафика, информационную систему реального времени с поддержкой средств анализа данных для принятия решений следует основывать на СУБД, использующей многомерные технологии представления информации. Однако следует заметить, что существующие на сегодняшний день многомерные модели данных имеют ряд недостатков, из которых, кроме описанных выше, можно выделить отсутствие математически формализованного описания данных в составе модели данных и операций по манипулированию этими данными.

Таким образом, актуальным представляется дальнейшее совершенствование характеристик СУБД, с целью повышения их производительности, для чего целесообразно использовать качественно новую многомерную логическую модель представления данных и аппарата математической формализации данных и операций для этой модели.

Цель работы и задачи исследования

Разработка многомерной логической модели представления данных, способной к выполнению сложных аналитических запросов и обладающей простотой масштабирования.

Для достижения поставленной цели в работе решаются следующие задачи:

1. Разработка битовой модели многомерного представления данных, базирующейся на гиперкубической многомерной технологии с выделением временного параметра в отдельную размерность.

2. Определение архитектуры баз данных, основанных на предлагаемой модели их логического представления, а также, алгоритмов и методов конвертирования данных из наиболее известных моделей в предлагаемую.

3. Разработка для предлагаемой модели собственного математического аппарата, формализующего ее данные и операции над ними.

На защиту выносится

1. Битовая многомерная модель хранения данных, основанная на гиперкубической технологии.

2. Аппарат математической формализации данных предлагаемой модели, ее компонентов и операций над ними. *

3. Алгоритмы конвертирования реляционных и классических многомерных баз данных (МБД) в битовую МБД.

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

1. Предложена логическая модель битовой МБД, устойчивая к запросам по любым атрибутам, легко масштабируемая, позволяющая перейти от сложного базиса запросов к поликубам, к простому базису многоиндексных переменных (бинарных многомерных матриц), повышая этим скорость обработки сложных запросов и целостность (а, следовательно, и надежность) хранения и представления данных.

2. Выработан ряд алгоритмов, направленных на конвертирование данных, что существенно упрощает перенос информации между различными программными и аппаратными платформами. Тем самым достигается одно из основных требований открытых систем - переносимость.

3. В качестве математически формализованного описания данных в составе предложенной модели и ее компонентов, а также, операций над ними определена алгебра операций над многомерными объектами, содержащая в себе базис операций, необходимый для формирования на его основе системы управления базами данных и языка запросов любой степени сложности.

Гпава 1. Битовая многомерная модель представления данных

3.4 Выводы по третьей главе

В процессе разработки биллинговой информационной системы контроля и учета сетевого трафика и проведения экспериментов были сделаны следующие выводы:

1. Необходимость разделения системы на уровни абстрагирования продиктовано существующим стандартом на разработку любых систем управления данными. Совместимость с этим стандартом позволяет легко организовывать такие процессы как интеграция с СУБД сторонних производителей, перенос информации из любых совместимых источников, построение сети распределенных вычислений с применением различных систем управления базами данных. Кроме того, это позволяет более четко отделить ее логическую часть от физической, что упрощает процесс совершенствования системы, поскольку становится возможным вести его независимо как на логическом, так и физическом уровнях.

2. Целесообразность построения системы на основе многомерных баз данных обусловлена необходимостью работы с большими объемами информации (в том числе и «хронологической») и обеспечения приемлемого времени отклика на запросы любой степени сложности.

3. Произведенное сравнение производительности классической многомерной модели с предлагаемой - битовой наглядно демонстрирует преимущество последней. Это позволяет сделать выбор в ее пользу при реализации информационных биллинговых систем контроля и учета сетевого трафика.

4. Построение всех возможных агрегатов для битовой многомерной модели, во-первых, резко увеличивает ее производительность, а во-вторых, занимает гораздо меньше времени, чем аналогичная процедура в классической МБД из чего следует необходимость применения в системе полностью агрегированной базы данных.

5. Результаты сравнения битовой и классической многомерных моделей логического представления данных в информационных системах контроля и учета сетевого трафика показали превосходство в производительности систем, основанных на битовой модели приблизительно в полтора раза.

Результатами, описанными в данной главе и реализованными в сфере контроля и учета сетевого трафика, являются:

1. Правила декомпозиции информационной системы на три общепринятых уровня абстрагирования.

2. Схема данных определенная для процесса деятельности крупного интернет-провайдера.

3. Статистическая система анализа и контроля сетевого трафика, реализованная на основе полностью агрегированной битовой многомерной СУБД.

106

Заключение

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

В частности, были достигнуты следующие результаты:

1. Сформулирована общая концепция построения баз данных на основе предлагаемой автором битовой многомерной модели представления данных.

2. Рассмотрены процедуры и методы переноса данных в битовую многомерную БД из баз данных, реализованных на других широко известных платформах. Тем самым обеспечена возможность совместимости данных между системой, построенной на основе предлагаемой модели и другими популярными СУБД.

3. Должное внимание уделено освещению одного из самых острых вопросов, возникающих при построении баз данных - вопросу целостности информации, а именно - построению многомерной базы данных по гиперкубическому принципу и разработке методов (таких как синтез гиперкуба и маркировка размерностей) повышающих централизованность а, следовательно, и целостность информации.

4. Все манипуляции с объектами и составными частями БД, построенной по предлагаемой методике, формализованы в виде алгебры операций над объектами битовой МБД, которая является посредником для связи уровней абстрагирования информационных систем, реализованных на базе такой МБД.

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

1. Айвазян С.А., Бухштабер В.М., Мешалкин Л.Д. Прикладная статистика: Классификация и снижение размерности. М.: Финансы и статистика, 1989.-86 С.

2. Аналитические системы и хранилища данных http://www.interface.ru/oracle/acdc.htm

3. Артемьев В. Что такое Business Intelligence? // Открытые системы. -2003. №4. - С.23-29.

4. Архипенков С., Голубев Д., Максименко О. Хранилища данных. От концепции до внедрения / Под общей редакцией С.Я. Архипенкова // М: Диалог-МИФИ, 2002. 156 С.

5. Аткинсон М.И. и др. Манифест систем объектно-ориентировнных баз данных// СУБД. 1995. -№4. - С. 142-155.

6. Банасевич А., Кудинов А. От Informix к SQL Server. // Открытые системы. 2002. - №1. - С. 13-27.

7. Баутов А. ИТ и прогнозирование экономических процессов // Директор ИС. 2002. - №9. - С.57-80.

8. Бич Д. К объектным моделям данных // Открытые системы. 1994. -№4. - С.45-55.

9. Бобровски С. Oracle 7 вычисления клиент-сервер. М.: Лори, 1996. -420 С.

10. Буч Г. Объектно-ориентированный анализ и проектирование с примерами на С++, 2-е изд. / Пер. с англ. М.: Бином, СПб: Невский Диалект, 1998.-680 С.

11. Вирин В. Храните данные в микрокубе // Computer World. 2002. -№46. - С.31-35.

12. Волков Д. От частного к общему // Открытые системы. 2002. - №2. -С. 11-20.

13. Волков И., Галахов И. Архитектура современной информационно14