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

На правах рукописи

Елисеев Дмитрий Владимирович

МЕТОДИКА ОБРАБОТКИ ТЕМПОРАЛЬНОЙ РЕЛЯЦИОННОЙ БАЗЫ ДАННЫХ В МИВАРНОМ ПРОСТРАНСТВЕ

Специальность 05.13.17 - Теоретические основы информатики (технические науки)

1 О НОЯ 2011

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва, 2011

4859168

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Московский государственный технический университет имени Н.Э. Баумана»

Научный руководитель: доктор технических наук, профессор

Балдин Александр Викторович

Официальные оппоненты: доктор технических наук,

старший научный сотрудник Варламов Олег Олегович

кандидат технических наук, доцент Рудаков Игорь Владимирович

Ведущая организация: ОАО «Научно-исследовательский институт

систем автоматизации»

Защита диссертации состоится «8» декабря 2011 года в 16:30 на заседании диссертационного совета Д212.141.10 в Московском государственном техническом университете им. Н.Э. Баумана по адресу: 105005, г. Москва, 2-я Бауманская ул., д. 5, стр. 1

С диссертацией можно ознакомиться в библиотеке Московского государственного технического университета им. Н.Э. Баумана.

Автореферат разослан «_»_2011 года

Ученый секретарь

Диссертационного совета Д 212.141.10 к.т.н., доцент

С.Р. Иванов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В разработку методов хранения и обработки темпоральных данных внесли вклад учёные, такие как Р. Снодграс, К. Дженсен, Дж. Бен-Зви, С. Гадия, Е. МакКензи, А. Стейнер.

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

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

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

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

В работе решаются следующие задачи:

1. Исследование и анализ основных методов хранения и обработки темпоральных данных, с целью формирования новых принципов построения темпоральных реляционных моделей с изменяемой структурой данных.

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

3. Разработка методики обработки темпоральной базы данных с изменяемой структурой.

4. Разработка алгебры многомерных пространств для работы с миварным пространством.

5. Разработка операторов преобразования из реляционной модели в многомерное пространство и обратно.

6. Разработка грамматики и интерпретатора языка запросов к многомерному пространству.

7. Разработка операторов изменения реляционной базы данных через миварное пространство.

8. Оценка границ применимости новой методики обработки темпоральной реляционной базы данных с изменяемой структурой.

Объект исследования. Объектом исследования настоящей работы являются темпоральные реляционные базы данных.

Предмет исследования. Предметом исследования являются процессы хранения и обработки темпоральных данных посредством использования реляционной СУБД и миварного пространства.

Научная новизна. В работе получены следующие новые научные результаты:

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

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

3. Разработаны алгоритмы операторов преобразования реляционной модели в многомерное пространство и обратно для использования стандартных SQL запросов к реляционной базе данных.

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

5. Разработана грамматика языка запросов к миварному пространству на базе языка SQL.

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

Практическая ценность полученных результатов. В данной работе для практического использования предложенной методики обработки темпоральной реляционной базы данных с изменяемой структурой разработано программное средство на базе технологической платформы «1С: Предприятие 8.2». Оно позволяет сформировать многомерное представление темпоральной реляционной модели, вносить изменения как в саму многомерную модель, так и в структуру многомерного пространства и динамически формировать отношения из многомерных структур данных при выполнении запросов. Таким образом, данную методику можно использовать с базами данных уже функционирующих информационных систем, чтобы не перекачивать накопленный архив изменений состояний темпоральных объектов, и разрабатывать новые информационные системы на базе многомерного представления реляционной модели данных.

Внедрение результатов исследований. Методика обработки реляционной базы данных с изменяемой структурой и разработанное программное средство внедрены для базы данных информационной системы кадрового учёта Московского государственного технического университета имени Н.Э. Баумана.

Публикации по теме. По материалам настоящей работы опубликовано 4 научные работы в журналах, рекомендуемых ВАК.

Апробация работы. Основные результаты работы докладывались на IV Всероссийской конференции молодых учёных и специалистов «Будущее машиностроения России» (Москва, 2011 г), на XIII Международной научно-практической конференции «Актуальные вопросы современной науки» (Москва, 2011 г).

Материалы работы были изложены автором на семинарах кафедры «Системы обработки информации и управления» МГТУ им. Н.Э. Баумана в 2009 - 2011 годах.

Объем работы. Диссертационная работа содержит 149 страниц, 47 рисунков и список литературы из 89 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

методике обработки темпоральных реляционных баз данных с изменяемой структурой.

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

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

2. Темпоральные модели данных хранят информацию об эволюции объектов предметной области: в базе данных сохраняются все состояния объекта предметной области в течение его времени жизни.

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

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

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

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

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

Миварное пространство состоит из множества осей, множеств элементов осей, множества точек пространства и множества значений точек. Формальное описание миварного пространства приведено ниже:

ПустьА = {ап}, п= 1, ТУ, где А - множество названий осей миварного пространства, И - количество осей миварного пространства.

Тогда V ап 3Вп = {¿„,-}, п = \,И, г'„ = 1 ,/„, где - множество элементов оси а„, 4 - идентификатор элемента множества 5„, /„ = |5„(.

Множества Вп образуют многомерное пространство: М = В[хВ2 х...х Вм.

и = (уг,...1,),и!еМ, т - точка многомерного пространства, (¡,,12,...!„) -координаты точки т.

Существует множество значений точек многомерного пространства М:

К =1,1„12=1,12,...,1„=\,1„}, где . значение точки

многомерного пространства Мс координатами (г^,...^).

Для каждой точки пространства М не существует или существует единственное значение из множества См- Таким образом, См - множество изменений состояний модели данных, представляемой в многомерном пространстве. Для перехода между многомерным пространством и множеством значений точек было введено отношение /¿: Сх~ц(Мх), где

Для описания реляционной модели данных в миварном пространстве необходимо выделить три оси: ось отношений V, ось атрибутов отношения 5 и ось идентификаторов записей отношения Ю как показано на рис. 16. Данные множества являются независимыми в отличие от реляционной модели данных.

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

Свойства реляционной модели данных при миварном подходе зависят от структуры пространства. Для того чтобы описывать темпоральные данные необходимо к рассмотренным трём осям добавить ось времени Т.

Атрибут 1(51) Атрибут 2(52) Атрибут П(вп)

Значение 1.1 Значение 1.2 Значение 1.п

Значение 2.1 Значение 2.2 Значение 2.п

Значение к.1 Значение к.2 Значение к.п

6 в

Рис. 1. Реляционное и многомерное представление данных Определение 1. Пространство <отношение, атрибут, идентификатор> называется определяющим, а образующие это пространство оси -определяющими осями.

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

Определение 2. Последнее (первое) состояние модели данных в момент времени г - совокупность точек многомерного пространства С„ значения которых в определяющем пространстве по параметру оси времени являются последними (первыми) до заданного момента времени

Для реляционной модели состоянием модели данных является совокупность отношений в определённый момент времени. Таким образом, состояние реляционной модели изменяется, когда изменяется хотя бы одно значение атрибута в каком-либо отношении или изменяется схема какого-либо отношения.

На рис. 1в показано изменение значения атрибута в многомерном пространстве. Для описания этого процесса была введена функция 3, которая по заданной точке определяет другую точку многомерного пространства, имеющую такие же координаты в определяющем пространстве, и координату по оси времени, равную следующему изменению значения этой точки в определяющем пространстве! На рис. 1в (,=^,,„¡>(1), где - времена изменения значения атрибута кортежа 2 отношения V,.

Тогда многомерное пространство для описания темпоральной реляционной базы данных будет иметь следующий вид: М = Ух8хЮхТ.

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

Носителем алгебры является следующее множество: Е= №х М =М}, где М - общее многомерное пространство

темпоральной реляционной базы данных, им - операция многомерного объединения пространств, рассмотренная ниже.

Сигнатура алгебры состоит из 4 операций: операции многомерного объединения (ии), пересечения (Г\м), разности (V) пространств и операция

многомерного среза (Ум '''')• Данные операции выполняются на множествах, образующими оси пространства, не анализируя множество значений точек Си. Пусть даны два многомерных пространства:

МА=УАх8Ах Юл х ТА, УА сК.^с ЮА с Ю, ТА с Т,

Мв = Ув хБв х /Дв хГ3, ^ с К, с 5, Я>, с /Д Г, с Т.

Операции многомерного объединения пространств

=МА им М„ = Ув хЮ0хТв, У0 =УА иУе, = /£,

т0=тл^тв.

Операции многомерного пересечения и разности пространств определяются аналогично.

Операция многомерного среза пространства

м„ = чС'*М''\Мл) = УохБ0 хЮвхТв, где

Ду.зМЛ) - общее логическое условие для операции многомерного среза. Это условие состоит из конъюнкции логических условий для каждого множества, образующего ось многомерного пространства^.

= Ь>л /к К) = истина} ,$0={зА: /5 (яА ) = истина},

Юв = {1с1 л : /ю (¿¿А) = истина}, Тв = {¿А : /т (1А) = истина}.

Для введённых операций алгебры многомерных пространств были выявлены и доказаны шесть основных свойств.

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

Для темпоральной реляционной базы данных необходима возможность получения состояний реляционной модели в определённые моменты времени.

Чтобы выполнять указанную операцию были разработаны операторы преобразования «Срез первых» и «Срез последних».

Преобразование «Срез первых» («Срез последних»)

Преобразование «Срез первых» формирует первое состояние реляционной модели данных с заданного момента времени / («Срез последних» - последнее состояние реляционной модели данных до заданного момента времени <):

Ст, =1>(С,0 = {ттгК(]Ря}, где сщ еС,^, С,^ = {с,„ и>1„ ст еС}.

(СГ: = т,(С,г0) = {шахг[с,л_]р^}, где с„г е С,5,о, СШа = {с„,: 1 < г0, с„ е С}.)

уОда - отношение эквивалентности на множестве значений точек многомерного пространства См-

т[ = {V,, £,, М,, Ц}, т2 = (у2, , г'с/2, ¿2),

С„,3 = РкмА,,,) о V, = У2 ы 5, = и И, = й2.

Множество ={с„, :с,„=>огам(с„1о)})гдес„,о,стеСд. - класс

эквивалентности по отношению р^и- Множество классов эквивалентности по отношению ру$и на множестве значений точек многомерного пространства См образует разбиение этого множества и обозначается См / ргш.

Так как множество Г является упорядоченным, элементы множества [с„,о ] можно упорядочить по оси Г и найти максимальный (тахг|с,„о]^) или

минимальный (ттг[с„,в | ) элемент.

При выполнении операции «Срез первых» («Срез последних») сначала отбираются все значения точек, которые имеют координату по оси времени больше С,^{ст:1>1й,стеС) (меньше С,щ = {с„,: I </0, с„, е С}) заданного значения Затем выбранные значения точек разбиваются на классы эквивалентности по отношению ¿уда и в каждом классе эквивалентности ищется наименьшая (наибольшая) точка по отношению порядка, заданного на оси времени.

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

(р-.Я0-^См. При этом выполняются следующие действия:

I _ у = [угх, уг2 ,..., угк }, где уг( - название отношения п, г = 1, К.

к

2. 5 = Щ , где Д, - схема отношения г,-.

/=1

3. Вп - конечное множество кортежей отношения г„ значит существует взаимно однозначное соответствие Л^,.., где

Л'а, = {1, 2,..., |.£>/-|}, | - мощность множества £>п. Тогда

4. __ _ _

5- ^^„^Бг^Я^, 1 = 1,К, п = \,Щ, у = 1,А', где Л^ДЛ, -

значение атрибута ЛИ, в кортеже п отношения г„ Р1 - количество атрибутов в схеме отношения Л,-.

Многомерное пространство, описывающее темпоральную реляционную модель данных, накапливает изменения исходной реляционной модели. Чтобы динамически формировать изменённую реляционную модель данных, были разработаны операторы преобразования значений точек многомерного пространства а и /?.

Оператор преобразования а получает из определённого множества значений точек многомерного пространства соответствующую ему реляционную модель данных: а\Си -> Яв. При этом выполняются следующие действия:

2. Я, = и {Идентификатор}, г = 1, |Р"Си |.

3. = {с„ : ¡с! = 1У„, с„, б Сг, ст Ф пиЩ, * 0) =>£)?;.„= и }, = {Иг,,}, / = = К), п = 1, ^ |.

4. г^(ЯьОгд,Яо=Ш, г' = 1'К„|-

Оператор преобразования /? получает из определённого множества значений точек многомерного пространства соответствующую ему реляционную модель данных, состоящую из отношений с темпоральными кортежами: /?: С^ Нв. При этом выполняются следующие действия:

1. СЛ. = {с,„: V = V/}, ст е С^}, г = 1,\УСи |. _

2. Я, = и {Период, Идентификатор нетемпорального кортежа}, г = 1,|УСи |.

3. шк, ({с,„ -.ы = ык Л* = *,, ст вСЛ1}*0)=>

=> = {с,„: 1с1 = 1йк Л г = (р, ст е С^} и {У,, 1р}, Я/г,. = {ДА,,}, / = = {¿¿Л, к = 1, |, ={/,}, р = 1, |ГС> |.

4. Иг(Нь ОЩ, НВ={Ь}, i = \\VcX

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

данных с изменяемом представлена на рис. 2.

Исходная реляционная модель данных

структурой в миварном пространстве, которая

Многомерное пространство

Ч>-

преобразование

C,ai =/1{АЩУ)

Подпространство,

содержащее результат запроса

■г

Операции над координатами

точек пространства

а.Р-

преобраз ование

Анализ и формализация изменеий объектов предметной области

Ввод новых данных и изменение данных

К, L____

Операции реляционной алгебры! ,

Результат = Р(R'u ) г

Результат запроса

Рис. 2. Методика обработки темпоральной реляционной базы данных с изменяемой структурой в миварном пространстве

Методика состоит из трёх этапов:

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

Исходными данными для построения темпоральной реляционной базы данных в многомерном пространстве является реляционная модель данных Roo=(roi, г02, ■■■, r0k). Rdo посредством оператора ср преобразуется в многомерную модель данных: С0 = tp(RD0).

2 этап. Изменение модели предметной области в многомерном пространстве

Изменение реляционной модели проводится в многомерном пространстве. Процесс изменения реляционной модели происходит посредством добавления новых точек в многомерное пространство. Координаты точек определяют структуру данных.

На рис. 2 изменение многомерного пространства изображено двумя блоками:

1. «Анализ и формализация изменений объектов предметной области». Результатом выполнения данной функции является изменение многомерного пространства: либо изменяется структура пространства (добавляются новые оси), либо происходит изменение множеств, определяющих оси пространства (добавляются новые элементы в эти множества).

2. «Ввод новых данных и изменение данных». Результатом выполнения данной функции является сохранение значений новых точек в многомерном пространстве.

Процесс изменения реляционной базы данных является итерационным (рис. 3), т.е. каждое следующее состояние базы данных зависит от предыдущего: Cí=5(C¡_i), где д - функция, задающая изменения текущего состояния от предыдущего.

¿•(Q) s(c,.;). ■ m) ,) •

■ со j to " i ci J ti l— ' ... i Jt ( ci i ti ... r:: : > Cn tn I

Рис. 3. Процесс изменения модели предметной области Кроме того, рассматриваемый процесс протекает во времени, т.е. каждое состояние базы данных действительно в определённом интервале времени: tM). Преобразование реляционной базы данных в многомерное пространство позволяет описать процесс её изменения во времени. При этом состояние базы данных получается из многомерного пространства посредством использования оператора преобразования «Срез последних»: С,- = т,(См, t,). 3 этап. Выполнение запросов к многомерному пространству Данный этап состоит из трёх подпунктов.

3.1. Выделение подпространства, содержащего результат запроса. На данном этапе выполняются операции над координатами точек в многомерном пространстве (операции алгебры многомерных пространств), не анализируя значения самих точек. В результате из всего многомерного пространства выделяется подпространство, содержащее результат запроса: CRь =р(А(М)),

где А(М) - выражение алгебры многомерных матриц.

3.2. Преобразование выделенного подпространства CR,o в реляционную

модель данных. С помощью операторов а и ß выделенное подпространство преобразуется в реляционную модель данных R'di=oc(Cr. )=(r',h r'i2, ..., r'ik), либо в реляционную модель данных с темпоральными кортежами H'Di=

ß(C*J=(h'u.h'a. -.AW-

3.3. Получение окончательного результата запроса. Окончательный результат запроса вычисляется из полученной реляционной модели данных посредством операций реляционной алгебры: Результат = P(R'D) или

Результат = P(H'D.), где P(R'DJ и P(H'D,)- выражение реляционной алгебры.

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

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

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

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

В диссертационной работе было предложено использовать ROLAP технологии для реализации многомерного пространства темпоральной реляционной базы данных. При таком подходе применяется схема «звезда», которая состоит из центральной таблицы, описывающей факты (точки многомерного пространства) и нескольких связанных с ней таблиц, описывающие измерения (элементы осей многомерного пространства).

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

В диссертационной работе для модификации отношений темпоральной реляционной базы данных по аналогии с языком SQL были разработаны и реализованы пять операторов изменения темпоральной реляционной базы данных через миварное пространство: добавление новых записей в отношение (MINSERT), обновление существующих записей в отношении (MUPDATE), удаление существующих записей из отношения (MDELETE), удаление атрибутов из отношения (MDROP COLUMN), изменение многомерного пространства (MDIMENTION).

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

В четвертой главе выполнена реализация многомерного пространства и интерпретатора грамматики языка запросов средствами технологической платформы «1С: Предприятие 8.2». Проведена практическая апробация предложенной методики и операторов языка запросов на примере кадровой системы Московского государственного технического университета имени Н.Э.Баумана и выполнена оценка эффективности методики по обработке

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

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

1. Изменения структуры объектов предметной области и форм представления отчётности.

2. Наличие объектов темпорального характера (данные о работниках, зарплата, вакансии и так далее).

3. Запросы, связанные с обработкой истории изменения темпоральных объектов (динамика изменения численности работников, текучести кадров и так далее).

4. Запросы к прошлым состояниям темпоральных объектов (отчёты, связанные с выходом работника на пенсию, расчёт средней зарплаты).

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

В работе была выполнена практическая реализация предложенной структуры многомерного пространства для темпоральной реляционной базы данных и разработана программная реализация интерпретатора и операторов работы с темпоральными данными на миварном пространстве в рамках технологической платформы «1С:Предприятие 8.2». Для практической проверки предложенной методики была использована база данных системы кадрового учёта МГТУ им. Н.Э. Баумана, которая посредством разработанного оператора ср была преобразована в многомерное представление. Фрагмент <р-преобразования базы данных системы кадрового учёта представлен на рис. 4.

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

Часть мифологической модели

Описание многомерного пространства

Отношение (у^

I I название I

Атрибут (в)

Часть базы данных ФизЛицо . _ ... _________

КодФЛ \ Фяиилий ; Имя | Отчество ; д«»?««.»» .""' 01 "1 Иванов"! Иван [ Иваныч |ОЗГТО. 1980

—4-------1----И^втплвы -1--:---

МАтрибутэ Нвэмнме 1» «4>и<гт«

код Число

2 Фамилия Строка

3 Имя Строка

4 Отчество Строка

5 Дата

6 ФизЛицо Число

7 Ставка Число

Дата с Дата 1

9 Дата по Дата

Многомерное представление базы ............ данных .......

' гплг' Время Значение

"'1 ' 1 ' Чо ;=01

" 2 1 и" 1=Иазнов

3 '

И

=Иааныч

Ю

2__ю_____

"2 1=Пётр__1

2 I Ю :=Петроаич 1

"2 Ю_ '=12 03 1931!

=Иван

=03.10.1980

02

Работник

Иванов I Иван Иваныч 14

.1981

КодФЛ Дата с Дата по

СИ 01 01.01.2010

02 02 1 01.01.2010 31.12.2010

03 01 0,6 01.03.2010 31.12.2011

ис. 4. Пример <р -преобразования части реляционной модели системы кадрового учёта в многомерное пространство

Для определения границ применимости предложенной методики были разработаны модель оценки размера отношения с темпоральными кортежами и модель оценки размера этого отношения в многомерном пространстве (рис. 5а), которые зависят от пяти параметров:

1.0- количество объектов предметной области, хранимое в отношении. Диапазон изменения этого параметра [1,л].

2.р - частота изменения значения атрибута в двух кортежах, определяющих последовательные состояния объекта предметной области. Диапазон изменения этого параметра (0,1].

3. с - частота изменения схемы отношения при допущении, что схема отношения изменяется равномерно, каждые с кортежей. Диапазон изменения этого параметра (1,оо).

4. а - начальное количество атрибутов в схеме отношения. Диапазон изменения этого параметра (1,°о).

5. п - количество кортежей в отношении.

Размер отношения вычисляется как количество хранимых значений атрибутов.

Результаты анализа эффективного применения методики приведены в виде графиков: зависимость минимального количества кортежей в отношении (Ы„,1п) от частоты изменения значения атрибута при различных значениях параметра с (рис. 56) и при различных значениях параметра о (рис. 5г). Размер реляционного отношения, описывающего работника, уменьшился при «=50000 на 26%, а при «=100000 на 48%. На рис. 5в представлены графики времени

адаптации информационной системы при пяти изменениях схемы БД для реляционной базы данных и многомерного пространства. Время адаптации информационной системы при использовании разработанной методики в среднем уменьшилось на 53%.

■ К" 35 ® о)

I * 50

I ? 25 г 5 го

О о 15

I Многомерно* про стран ет* о

и 25 50 75

Количество кортежей в отношении (п), #1 ООО

0.1 0.15 0.2 0.25 0.3 0.35 Частота изменения значения атрибута, р б

2 3.4 5

Количество изменений схемы БД

0.1 0.15 0.2 0.25 0.3 0.35 Частота изменения значения атрибута, р

Рис. 5. Анализ результатов моделирования Таким образом, результаты проведённых экспериментов показывают, что применение разработанной методики позволяет уменьшить размер отношений реляционной модели в среднем на 32% и сократить время адаптации информационной системы в среднем на 53%.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

6. На основе разработанной алгебры многомерных пространств и операторов преобразования значений точек в реляционную модель данных разработан язык запросов и интерпретатор для него, как расширение языка SQL. Проведена практическая реализация интерпретатора и операторов языка запросов в рамках технологической платформы «1 С:Предприятие 8.2».

7. Проведена практическая апробация предложенной методики и операторов языка запросов на примере кадровой системы Московского государственного технического университета имени Н.Э.Баумана. Была показана возможность получения истории работы сотрудника в условиях изменения места работы и структуры организации, а также возможность оперативной адаптации такой системы к новым требованиям.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Елисеев Д.В. Модель представления знаний при создании адаптивной информационной системы [Электронный ресурс], - Электрон, журн. - М.: «Наука и образование: электронное научно-техническое издание», 2010 -Режим доступа: http://technomag.edu.ru/doc/139659.html, свободный (Дата обращения: 06.10.2011).

2. Елисеев Д.В., Балдин A.B. Адаптируемая модель данных на основе многомерного пространства [Электронный ресурс], - Электрон, журн. - М.: «Наука и образование: электронное научно-техническое издание», 2010 -Режим доступа: http://technomag.edu.ru/doc/161410.html, свободный (Дата обращения: 06.10.2011).

3. Елисеев Д.В., Балдин A.B. Алгебра многомерных матриц для обработки адаптируемой модели данных [Электронный ресурс], - Электрон, журн. -М.: «Наука и образование: электронное научно-техническое издание», 2011 - Режим доступа: http://technomag.edu.ru/doc/199561.html, свободный (Дата обращения: 06.10.2011).

4. Елисеев Д.В., Балдин A.B. Адаптация темпоральной реляционной модели данных в многомерном пространстве [Электронный ресурс], - Электрон, журн. - М.: «Наука и образование: электронное научно-техническое издание», 2011 - Режим доступа: http://technomag.edu.ru/doc/225699.html, свободный (Дата обращения: 06.10.2011).

Подписано к печати 28.10.11. Заказ №737 Объем 1,0 печ.л. Тираж 100 экз. Типография МГТУ им. Н.Э. Баумана 105005, Москва, 2-я Бауманская ул., д.5 (499) 263-62-01

ВВЕДЕНИЕ.

Глава 1. Анализ методов хранения и обработки темпоральных данных.

1.1. Темпоральные данные и темпоральные базы данных.

1.2. Реляционная модель данных.

1.3. Анализ темпоральных моделей данных на базе реляционной.

1.4. Представление времени в темпоральных моделях.

1.5 Тип временной отметки.

1.6. Линия времени.

1.6.1. Нетемпоральная база данных.

1.6.2. Историческая база данных.

1.6.3. База данных с откатом.

1.6.4. Битемпоральная база данных.

1.7. Уровень темпоральности данных.

1.7.1. Темпоральность на уровне базы данных.

1.7.2. Темпоральность на уровне отношения.

1.7.3. Темпоральность на уровне кортежа.

1.7.4. Темпоральность на уровне атрибута.

1.8. Расширение реляционной модели данных до темпоральной модели.

1.9. Темпоральные реляционные модели с изменяемой структурой данных.

1.10. Миварный подход к описанию предметной области.

1.11. Темпоральная реляционная модель с изменяемой структурой данных на базе многомерного пространства.

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

Глава 2. Описание темпоральной реляционной базы данных в миварном информационном пространстве и разработка методов его обработки.

2.1. Миварная концепция представления данных.

2.1.1. Формализованное описание миварного информационного пространства.

2.1.2. Реляционная и миварная концепции представления данных с изменяемой структурой.

2.1.3. Миварное представление реляционной модели данных.

2.2. Разработка представления темпоральных данных в миварном пространстве.

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

2.4. Разработка алгебры многомерных пространств.

2.4.1. Разработка преобразования между многомерным пространством и множеством значений точек пространства.

2.4.2. Алгебра многомерных пространств.

2.4.3. Свойства операций алгебры многомерных пространств.

2.5. Разработка операторов преобразования значений точек многомерного пространства.

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

2.6.1 Разработка оператора преобразования реляционной модели данных в многомерное пространство.

2.6.2. Формализованное описание обобщённой темпоральной модели данных на базе реляционной.

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

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

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

Глава 3. Реализация миварного представления темпоральной реляционной базы данных с изменяемой структурой на реляционных СУБД.

3.1. Реализация многомерного пространства в реляционных СУБД.

3.2. Разработка грамматики расширенного языка SQL.

3.3. Реализация грамматики расширенного языка SQL.

3.3.1. Разработка алгоритма разбора запроса на базе грамматики расширенного языка SQL.

3.3.2. Разработка реализации операций алгебры многомерных пространств на языке SQL.

3.3.3. Разработка реализации преобразований значений точек многомерного пространства на языке SQL.

3.3.4. Разработка алгоритма реализации а и /? преобразований значений точек многомерного пространства.

3.4. Разработка операторов изменения реляционной модели в многомерном пространстве.

3.4.1. Разработка оператора добавления новой записи в отношение намиварном пространстве.

3.4.2. Разработка оператора обновления существующих записей в отношении на миварном пространстве.

3.4.3. Разработка оператора удаления существующих записей из отношения на миварном пространстве.

3.4.4. Разработка оператора удаление атрибутов из отношения на миварном пространстве.

3.4.5. Разработка оператора изменения многомерного пространства.

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

Глава 4. Оценка эффективности разработанной методики на базе данных системы кадрового учёта.

4.1. Специфика обработки и хранения данных в системе кадрового учёта.

4.2. Преобразование базы данных системы кадрового учёта в многомерное пространство.

4.3. Реализация многомерного пространства базы данных системы кадрового учёта на платформе «1С:Предприятие 8.2».

4.4. Выполнение запросов к многомерному пространству системы кадрового учёта.

4.5. Реализация системы кадрового учёта на базе многомерного пространства.

4.6. Оценка эффективности разработанной методики.

4.6.1. Разработка модели отношения с темпоральными кортежами.

4.6.2. Разработка модели многомерного представления отношения с темпоральными кортежами.

4.6.3 Условие эффективности применения разработанной методики. 131 4.6.4. Сравнительный анализ результатов моделирования.

4.7. Оценка времени адаптации информационной системы.

4.8. Выводы по четвёртой главе.

ВЫВОДЫ.

Актуальность темы. В настоящее время сложной задачей является адаптация класса информационных систем, обрабатывающих темпоральные данные посредством реляционной модели и функционирующих в динамично меняющихся предметных областях. Особенностью таких информационных систем является то, что они работают с темпоральными данными, структура которых также изменяется со временем. Описание темпоральных данных с изменяющейся структурой существующими методами является не всегда эффективным, а иногда невозможным, так как это приводит к перепроектированию базы данных. Процесс адаптации такой базы данных к новым условиям является сложным, приводит к необходимости перекачки данных и требует добавления новых объектов поверх старых с сохранением истории изменения темпоральных данных. Примерами рассматриваемого класса информационных систем являются: система управления предприятием [24, 25], система управления персоналом [30, 36], финансовые приложения, страховые приложения и ряд других, которые обладают следующими свойствами:

1. Информационная система использует реляционную базу данных.

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

3. Информационная система обрабатывает темпоральные данные.

4. Информационная система накапливает историю изменения темпоральных данных.

В разработку методов хранения и обработки темпоралльных данных внесли вклад учёные, такие как Р. Снодграс [3, 73], К. Дженсен Дженсеном [3, 48, 57, 59], Дж. Бен-Зви [3], С. Гадия [3], Е. МакКензи [3, 66], А. Стейнер [79].

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

В настоящее время существует разработанный Варламовым О.О. новый миварный подход [9, 10, 11, 12, 13] к описанию изменяемых, динамических предметных областей, который позволяет устранить избыточность хранения данных. Миварный подход используется для класса обучаемых систем, задачей которых является изучение и моделирование сложных динамичных предметных областей. Основой миварного подхода к представлению данных является целостное, единое описание изучаемой предметной области с различных точек зрения посредством многомерного пространства. Однако, использование этого подхода для работы с темпоральной реляционной базой данных невозможно, так как отсутствует механизм обработки многомерного представления изменяющихся отношений.

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

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

Задачи исследования

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

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

3. Разработка методики обработки темпоральной базы данных с изменяемой структурой.

4. Разработка алгебры многомерных пространств для работы с миварным пространством.

5. Разработка операторов преобразования из реляционной модели в многомерное пространство и обратно.

6. Разработка грамматики и интерпретатора языка запросов к многомерному пространству.

7. Разработка операторов изменения реляционной базы данных через миварное пространство.

8. Оценка границ применимости новой методики обработки темпоральной реляционной базы данных с изменяемой структурой.

Объектом исследования настоящей работы являются темпоральные реляционные базы данных.

Предметом исследования являются процессы хранения и обработки темпоральных данных посредством использования реляционной СУБД и миварного пространства.

Научная новизна. В работе получены следующие новые научные результаты:

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

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

3. Разработаны алгоритмы операторов преобразования реляционной модели в многомерное пространство и обратно для использования стандартных SQL запросов к реляционной базе данных.

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

5. Разработана грамматика языка запросов к миварному пространству на базе языка SQL.

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

Практическая значимость работы. В данной работе для i практического использования предложенной методики обработки темпоральной реляционной базы данных с изменяемой структурой разработано программное средство на базе технологической платформы «1С: Предприятие 8.2». Оно позволяет сформировать многомерное представление темпоральной реляционной модели, вносить изменения как в саму многомерную модель, так и в структуру многомерного пространства и динамически формировать отношения из многомерных структур данных при выполнении запросов. Таким образом, данную методику можно использовать с базами данных уже функционирующих информационных систем, чтобы не перекачивать накопленный архив изменений состояний темпоральных объектов, и разрабатывать новые информационные системы на базе многомерного представления реляционной модели данных.

Методика адаптации реляционной базы данных с изменяемой структурой внедрена для базы данных информационной системы кадрового учёта МГТУ им. Н.Э. Баумана и реализована посредством использования технологической платформы «1С: Предприятие 8.2».

Структура диссертационной работы. В первой главе приведено описание темпоральных моделей данных и выделены следующие их особенности:

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

2. Темпоральные модели данных хранят информацию об эволюции объектов предметной области: в базе данных сохраняются все состояния объекта предметной области в течение его времени жизни.

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

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

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

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

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

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

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

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

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

В главе были разработаны операторы преобразования из реляционной модели данных в многомерное пространство (^-преобразование) и обратные преобразования (а, /^-преобразования), которые позволяют адаптировать, к изменяющейся структуре существующие базы данных посредством их перевода в многомерное пространство и использовать существующие запросы в системе, выполняя обратное преобразование определённой части множества значений точек пространства. Оператор «^-преобразования выполняет начальное построение и заполнение многомерного пространства на основе исходной реляционной модели базы данных. Оператор а-преобразования получает из определённого множества значений точек многомерного пространства соответствующее ему состояние реляционной модели данных, тогда как оператор /^-преобразования получает из определённого множества значений точек многомерного пространства соответствующую ему реляционную модель данных, использующую отношения с темпоральными кортежами.

В результате на основе предложенной алгебры многомерных пространств и разработанных операторов преобразования была сформулирована методика обработки темпоральной реляционной модели данных, которая состоит из трёх этапов:

1. Однократное преобразование начальной реляционной модели данных в многомерное пространство посредством оператора (р.

2. Итерационное изменение темпоральной реляционной базы данных в многомерном пространстве.

3. Выполнение запросов к многомерной темпоральной реляционной модели с изменяемой структурой данных.

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

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

3.3.Получение окончательного результата запроса с помощью операций реляционной алгебры.

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

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

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

Для предложенной грамматики языка запросов к миварному пространству были разработаны алгоритмы преобразования операций алгебры многомерных пространств, а также операторов преобразования «Срез первых» и «Срез последних» к стандартным конструкциям языка SQL, которые выполняются над реляционной базой данных, реализующей многомерное пространство. Для операторов а и ^-преобразования были разработаны соответствующие алгоритмы, которые позволяют сформировать отношения реляционной модели из отношения, описывающее множество значений точек многомерного пространства. Эти динамически полученные отношения затем обрабатываются посредством стандартных операторов языка SQL.

В главе по аналогии с языком запросов SQL были разработаны пять операторов изменения темпоральной реляционной модели данных в миварном пространстве, которые представлены ниже:

1. Оператор вставки новой записи в отношение на миварном пространстве (MINSERT) добавляет новые значения в точки многомерного пространства, которые определяют начальные состояния новых объектов предметной области, не содержащихся в отношении темпоральной реляционной модели.

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

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

4. Оператор удаления атрибутов из отношения на миварном пространстве (MDROP COLUMN) добавляет пустые значения в точки многомерного пространства, которые соответствуют удаляемому атрибуту во всех текущих записях отношения темпоральной реляционной модели.

5. Оператор изменения многомерного пространства (MDIMENTION) добавляет новые элементы во множества, описывающие оси многомерного пространства.

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

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

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

1. Изменение структуры объектов предметной области и форм представления отчётности.

2. Наличие объектов темпорального характера (данные о работниках, зарплата, вакансии и так далее).

3. Запросы, связанные с обработкой истории изменения темпоральных объектов (динамика изменения численности работников, текучести кадров и так далее).

4. Запросы к прошлым состояниям темпоральных объектов (отчёты, связанные с выходом работника на пенсию, вычисление средней зарплаты работника).

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

В работе была выполнена практическая реализация предложенной структуры многомерного пространства и разработана программная реализация интерпретатора и операторов работы с темпоральными данными на миварном пространстве в рамках технологической платформы «1С:Предприятие 8.2». Для практической проверки предложенной методики была использована база данных системы кадрового учёта МГТУ им. Н.Э. Баумана, которая посредством разработанного оператора ср была преобразована в многомерное представление.

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

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

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

138 ВЫВОДЫ

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

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

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

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

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

6. На основе разработанной алгебры многомерных пространств и операторов преобразования значений точек в реляционную модель данных разработан язык запросов и интерпретатор для него, как расширение языка SQL. Проведена практическая реализация транслятора и операторов языка запросов в рамках технологической платформы «1С:Предприятие 8.2».

7. Проведена практическая апробация предложенной методики и операторов языка запросов на примере кадровой системы Московского государственного технического университета имени Н.Э.Баумана. Была показана возможность получения истории работы сотрудника в условиях изменения места работы и структуры организации, а также возможность оперативной адаптации такой системы к новым требованиям

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

1. Архипенков СЛ., Голубев Д.В., Максименко О.Б. Хранилища данных. От концепции до внедрения. М.: ДИАЛОГ-МИФИ, 2002. -528 с.

2. Ахо A.B., Хопкрофт Дж.Э., Ульман Дж.Д. Структуры данных и алгоритмы: Учеб. пособие / пер. с англ. A.A. Минько. М.: Вильяме, 2000. - 384 с.

3. Базаркин А. И. Исследование и разработка темпоральной модели данных в рамках МИС Интерин PROMIS Электронный ресурс., 2009 Режим доступа: https://edu.botik.ni/proceedings/psta2009/v2/037-Bazarkin.Researchand.pdf (Дата обращения: 14.08.2011).

4. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для втузов / под ред. B.C. Зарубина, А.П. Крищенко М.: Изд-во МГТУ им. Н.Э. Баумана, 2001,- 743 с.

5. Вениаминов Е.М., Ефимова Е.А. Элементы универсальной алгебры и ее приложений в информатике: Учеб. пособие для вузов. М.: Научный мир, 2004,- 167 с.

6. Биркгоф Г., Барти Т. Современная прикладная алгебра / пер. с англ. Ю.И. Манина М.: Мир, 1976. - 400 с.

7. Варламов О.О., Адамова JOLE. Создание эволюционных баз данных и знаний // Научная сессия МИФИ. 2002. Сб. науч. трудов. Т.2. - М.: МИФИ, 2002. - С. 101-103.

8. Ю.Варламов О.О., Амарян М.Р. Многомерное изменяющееся представление данных для компаний электросвязи // Вестник связи International. 2003. - № 1. - С. 23-25.

9. П.Варламов О.О. Основы многомерного информационного развивающегося (миварного) пространства представления данных и правил // Информационные технологии. 2003. - № 5. - С. 42-47.

10. Варламов О.О. Системный анализ и синтез моделей данных и методы обработки информации в самоорганизующихся комплексах оперативной диагностики: 05.13.01: дис. . дтн.; МАРТИТ. М., 2003.-307 с.

11. Варламов О.О. Эволюционные базы данных и знаний для адаптивного синтеза интеллектуальных систем. Миварное информационное пространство. М: Радио и связь, 2002. - 286 с.

12. Н.Виноградова М.В. Методика создания мультиаспектной информационной системы с алгоритмоориентированной структурой данных : дис. . ктн.; МГТУ им. Н. Э. Баумана. М., 2005. - 155 с.

13. Профессиональная разработка в системе 1С:Предприятие 8 / А.П. Габец, Д.И. Гончаров, Д.В. Козырев и др. М.: ООО «1С-Паблишинг», СПб: Питер, 2006,- 808 с.

14. Гарсиа-Молина Г., Ульман Д., Уидом Д. Системы баз данных. Полный курс / пер. с англ. A.C. Варакина. М.: Вильяме, 2003. — 1088 с.

15. П.Григорьев А.Ю., Ухаров А.О., Плутенко А.Д. Использование вейвлет-преобразования для приближённой аналитической обработки многомерных данных // Информатика и системы управления. 2008. - №4. - С. 3-10.

16. Дейт К. Введение в системы баз данных. 8-е изд. - М.: Вильяме, 2006. -1328 с.

17. Дулин С.К. Структурная согласованность данных и знаний. M.: МЗ Пресс, 2005. - 143 с.

18. Емельянов В.В., Курейчик В.М., Курейчик В.В. Теория и практика эволюционного моделирования. М.: Физматлит, 2003. - 431 с.

19. Емельянов В.В., Ясиновский С.И. Имитационное моделирование систем : Учеб. пособие для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2009. - 583 с.23.3амулин A.B. Системы программирования баз данных и знаний. -Новосибирск: Наука, 1990. 350 с.

20. Информационные технологии в инженерном образовании / под ред. C.B. Коршунова, В.Н. Гузненкова. М.: Изд-во МГТУ им. Н.Э. Баумана, 2007. - 432 с.

21. Информационная управляющая система МГТУ им. Н.Э. Баумана «Электронный университет»: концепция и реализация / Т.И. Агеева, A.B. Балдин, В.А. Барышников и др.; под ред. И.Б. Фёдорова, В.М. Черненького. М.: Изд-во МГТУ им. Н.Э. Баумана, 2009. - 376 с.

22. Классификация OLAP-систем вида xOLAP Электронный ресурс. / А.Н. Андреев, 2010 Режим доступа:http ://citforum.ru/consulting/BI/xolapclassification/ (Дата обращения : 09.10.2011).

23. Ковтун И.И. Матрично-реляционная модель данных для представления и обработки информации в автоматизированных системах мониторинга и управления // Программирование. 1997. -№ 6. - С. 58 - 72.

24. Коршунов Ю.М. Математические основы кибернетики. М.: Энергоатомиздат, 1987. - 496 с.

25. Костенко Б.Б., Кузнецов С.Д. История и актуальные проблемы темпоральных баз данных Электронный ресурс., 2007 Режим доступа: http://citforum.rU/database/articles/temporal/4.shtml (Дата обращения: 14.08.2011).

26. Марков A.A. Моделирование информационно-вычислительных процессов : Учеб. пособие для студентов вузов. М.: Изд-во МГТУ им. Н. Э. Баумана, 1999. - 358 с.

27. Мартин Дж. Организация баз данных в вычислительных системах. -М.: Мир, 1980. 524 с.

28. Плоткин Б.И. Универсальная алгебра, алгебраическая логика и базы данных. М.: Наука, 1991. - 448 с.

29. Фалевич Б .Я. Теория алгоритмов: Учеб. пособие для вузов. М.: Машиностроение, 2004. - 160 с.

30. Федоров А.А., Елманова Н.В. Введение в OLAP-технологии Microsoft. M.: ДИАЛОГ-МИФИ, 2002. - 268 с.

31. Четвериков В.Н., Ревунков Г.И., Самохвалов Э.Н. Базы и банки данных: Учебник для вузов / под ред. В.Н. Четверикова. М.: Высш. шк., 1987. - 245 с.

32. Abello A., Samos J., Saltor F. Understanding facts in a multidimensional object-oriented model // Proceedings of the 6th ACM international workshop on Data warehousing and OLAP. 2003. - P. 56-62.

33. Ahn I., Snodgrass R.T. Partitioned Storage Structures for Temporal Databases // Information Systems. 1988. - 13(4). - P. 369-391.

34. Allen J.F. Maintaining knowledge about temporal intervals // Communications of the ACM. 1983. - 16(11). - P. 832-843.

35. Ariav G. A temporally oriented data model // ACM transactions on database systems. 1986. - 11(4). - P. 499-527.

36. Binh N.T., Tjoa A.M. Conceptual multidimensional data model based on object-oriented metacube // Proceedings of the 16th ACM symposium on Applied computing. 2001. - P. 295-300.

37. Bohlen M.H. Temporal database system implementations // SIGMOD Rec. 1995. - 24(4). - P. 53-60.

38. Bohlen, M.H., Jensen C.S. Temporal data model and query language concepts // Encyclopedia of information systems. 2003. - Vol. 4, P. 437453

39. Bohlen M., Jensen C.S., Snodgrass R.T. Temporal statement modifiers // ACM transactions on database systems. 2000. - 25(4). - P. 407-456.

40. Dyreson C.E., Evans W., Snodgrass R.T. Efficiently supporting temporal granularities // IEEE transactions on knowledge and data engineering. -2000.- 12(4).-P. 568-587.

41. Dyreson C.E., Snodgrass R.T. Timestamp semantics and representation // Information systems. 1993. - 18(3). - P. 143-166.

42. Gadia, S.K. A homogeneous relational model and query languages for temporal databases // ACM transactions on database systems. 1988. -13(4).-P. 418-448.

43. Gadia S.K., Nair S.S. Temporal databases: A prelude to parametric data // Temporal databases: theory, design, and implementation / A. Tansel, J. Clifford, S. Gadia, et al. Benjamin/Cummings Publishing Company, 1993.-Chapter2.-P. 28-66.

44. Gao D., Jensen C.S., Snodgrass R.T. Join operations in temporal databases // The VLDB journal. 2005. - 14(1). - P. 2-29.

45. Gregersen H., Jensen C.S. Temporal entity-relationship models a survey // Knowledge and Data Engineering. - 1999. - 11(3). - P. 464-497.

46. Hsu S., Snodgrass R.T. Optimal block size for set-valued attributes // Information processing letters. 1993. - 45(3). - P. 153-158.

47. Jensen C.S., Dyreson C.E. A Consensus glossary of temporal database concepts // Temporal databases: research and practice / O. Etzion, S. Jajodia, and S. Sripada. Springer-Verlag, 1998. - P. 367-405.

48. Jensen C.S., Mark L., Roussopoulos N. Incremental implementation model for relational databases with transaction time // IEEE transactions on knowledge and data engineering. 1991. - 3(4). - P. 461-473.

49. Jensen C.S., Snodgrass R.T. Semantics of time-varying information Электронный ресурс. // Information systems. 1996. - 21(4). - P. 311— 352, Режим доступа: http://www.cs.arizona.edu/~rts/pubs/ISJune96.pdf, свободный (Дата обращения: 14.08.2011).

50. Jensen C.S., Snodgrass R.T. Temporal data management // IEEE transactions on knowledge and data engineering 1999. - 11(1). - P. 3644.

51. Jensen C.S., Snodgrass R.T., Soo M.D. Extending existing dependency theory to temporal databases // IEEE transactions on knowledge and data engineering. 1996. - 8(4). - P. 563-582.

52. Jensen, C.S., Snodgrass R.T., Soo M.D. Unifying temporal data models via a conceptual model // Information systems. 1994. - 19(7). - P. 513547.

53. Katz R., Lehman Т. Database support for versions and alternatives of large design files // IEEE transactions on software engineering. 1984. -10(2).-P. 191-200.

54. McKenzie Е., Snodgrass R.T. Schema evolution and the relational algebra // Information systems. 1990. - 15(2). - P. 207-232.

55. Sarda N.L. Algebra and query language for a historical data model // The computer journal. 1990. - 33(1). - P. 11-18.

56. Sarda, N.L. Extensions to SQL for historical databases // IEEE transactions on knowledge and data engineering. 1990. - 2(2). - P. 220230.

57. Slivinskas G., Jensen C.S., Snodgrass R.T. A foundation for conventional and temporal query optimization addressing duplicates and ordering // Knowledge and data engineering. 2001. - 13(1). - P. 21-49.

58. Snodgrass R.T. Developing time-oriented database applications in SQL. -San Francisco: Morgan Kaufmann Publishers, 1999. 504 p.

59. Snodgrass R.T. The temporal query language TQuel // ACM transactions on database systems. 1987. - 12(2). - P. 247-298.

60. Snodgrass R.T. The TSQL2 temporal query language. Kluwer Academic Publishers, 1995. - 674 p.

61. Snodgrass R.T., Ahn I. A taxonomy of time in databases // Proceedings of ACM SIGMOD International conference on management of data. -Austin, TX.-P. 236-246.

62. Snodgrass R.T., Ahn I. Temporal databases // IEEE computer. 1986. -19(9).-P. 35-42.

63. Snodgrass R.T., Gomez S., McKenzie E. Aggregates in the temporal query language TQuel // IEEE transactions on knowledge and data engineering, 1993. 5(5). - P. 826-842.

64. Steiner A. A generalisation approach to temporal data models and their implementations Электронный ресурс., 1998 Режим доступа: http://www.timeconsult.com/Publications/diss.pdf (Дата обращения: 14.08.2011).

65. Tansel A. Adding time dimension to relational model and extending relational algebra//Information systems. 1986. - 11(4). - P. 343-355.

66. Tansel A. A Generalized relational framework for modeling temporal data // Temporal databases: theory, design, and implementation / A. Tansel, J. Clifford, S. Gadia et al. Benjamin/Cummings Publishing Company, 1993.-P. 183-201.

67. Torp K., Jensen C.S., Bohlen M.H. Layered temporal DBMS: Concepts and techniques // Database systems for advanced applications. 1997. - P. 371-380.

68. Torp K., Snodgrass R.T., Jensen C.S. Effective timestamping in databases // The VLDB journal. 2000. - 8(4). - P. 267-288.

69. Torp K., Snodgrass R.T., Jensen C.S. Modification semantics in now-relative databases // Information systems. 2004. - 29(8). - P. 653-683.

70. Tsuji Т., Нага A., Higuchi K. An extendible multidimensional array system for MOLAP // Proceedings of the 2006 ACM symposium on applied computing, 2006. P. 503-510.

71. Описание темпоральной базы данных TimeDB сайт. Режим доступа: http://www.timeconsult.com (Дата обращения: 09.10.2011).1. С149 ^

72. Описание технологической платформы «1С: Предприятие 8» сайт.